Caution

** This article contains spoilers for "Atcoder Beginner Contest 148 E --Double Factorial". Please refrain from browsing if you plan to solve this problem on your own. ** **

Overview

I got into a title issue while solving Atcoder, so I'll post this article as a reminder and to hear the opinions of Python experts.

problem

Atcoder Beginner Contest 148 E - Double Factorial

For an integer n greater than or equal to 0, define f (n) as follows:

・ F(n) = 1 [n <When]\\
・ F(n) = nf(n-2) [n \When geq 2]

Given the integer N. Find how many 0s follow when f (N) is written in decimal.

environment

MacBook Pro（64bit）
Python 3.8

The Python 3 version of Atcoder is "3.4.3", but it has been confirmed in advance that the same result can be obtained in the above environment.

phenomenon

In the following two codes, ** the upper part is AC (correct answer) **, but the lower part is WA (incorrect answer) **.

`AC.py`


import math
N = int(input())
ans = 0
if N % 2 != 0:
    pass
else:
    for i in range(0, 25):
        ans += N // (10 * 5 ** i)
print(ans)

`WA.py`


import math
N = int(input())
ans = 0
if N % 2 != 0:
    pass
else:
    for i in range(0, 25):
        ans += math.floor(N / (10 * 5 ** i))
print(ans)

There are 15 test cases for this problem, but the following 2 test cases have become WA.

[15.txt]
IN:  237590337949089028
OUT: 29698792243636116

[16.txt]
IN:  999003990299500294
OUT: 124875498787437525

Expected cause

** The probable cause is a spelling of what I tried variously until I identified the cause. ** ** ** I just want to know the result! I hope you can skip to the next chapter. ** **

The following parts are related to AC and WA.

ans += N // (10 * 5 ** i) #AC
ans += math.floor(N / (10 * 5 ** i)) #WA

Both are doing similar things and are likely to give the same result, but not.

For the time being, let's output where the error is occurring. Do as follows.

Use the test case "237590337949089028" whose N value is WA.

`debug.py`


import math
N = int(input())
ans_ac = 0
ans_wa = 0
if N % 2 != 0:
    pass
else:
    for i in range(0, 25):
        ans_ac = N // (10 * 5 ** i)
        ans_wa = math.floor(N / (10 * 5 ** i))
        print('i =', i)
        print('d =', N / (10 * 5 ** i))
        print('AC:', ans_ac)
        print('WA:', ans_wa)

The result is as follows.

i = 0 #error: 2
d = 2.3759033794908904e+16
AC:  23759033794908902
WA:  23759033794908904

i = 1 #error: 1
d = 4751806758981781.0
AC: 4751806758981780
WA: 4751806758981781

i = 2 #error: 0
d = 950361351796356.1
AC: 950361351796356
WA: 950361351796356

i = 3 #error: 0
d = 190072270359271.22
AC: 190072270359271
WA: 190072270359271

(Omitted below)

Subsequent repetitions (i is 3 or more and less than 25) had all 0 AC and WA errors (AC and WA are equal). It seems that the error occurred only at the beginning of the repetition (i = 0, 1). For the time being, I don't seem to know anything as it is, so I decided to think about something different.

One thing that came to my mind here. What are the types of these calculations? There are two types of real numbers in Python.

int
float

The former has no accuracy limits, but the latter does. What type of deviation do the two calculation methods in question have?

abc.001.jpeg

Regarding //, according to the official documentation

x // y The quotient of x and y is rounded down Also known as integer division. The result type is not necessarily an integer type, but the result value is an integer. The result is always rounded towards negative infinity.

There is. In AC calculation, it seems that it is assigned to a variable without becoming a float type even once.

But what about WA calculations? This goes through the float type once depending on the calculation result of x / y. I checked it in the environment at hand.

`test.py`


A = 4
B = 2
print(type(A), type(B))
print(type(A / B))
print(A / B)

'''
<class 'int'> <class 'int'>
<class 'float'>
2.0
'''

In other words, it is already a float type before using math.floor (). Isn't // and math.floor () similar and different? I thought, but it doesn't seem to be the cause.

The definition of math.floor () in the Official Document is as follows.

Returns the "floor" of x (the largest integer less than or equal to x). If x is not a floating point number, x.__ floor __ () is executed internally and the Integral value is returned.

Rather, I expected that the WA calculation was via ** float type **, passing an inappropriate value to math.floor () in the first place.

As mentioned at the time of type introduction, float type has a limitation of accuracy unlike int type. There were the following ways to check this.

`dig.py`


import sys
print(sys.float_info.dig)
# 15

The Official Document is as follows.

sys.float_info Named tuples holding information about float types dig: The largest decimal digit that can be displayed accurately in floating point numbers

Apparently, the float type can be accurate up to 15 digits, but the digits beyond that are suspicious ... Now, let's reconfirm the test case that issued the WA earlier. This time we will focus on the number of digits.

i = 0 #error: 2
d = 2.3759033794908904e+16 #17 digits of integer,Decimal 0 digits
AC:  23759033794908902     # 23759033794908904
WA:  23759033794908904     #17 digits>15 digits

i = 1 #error: 1
d = 4751806758981781.0     #16 digits of integer,Decimal 1 digit
AC: 4751806758981780       #16 digits>15 digits
WA: 4751806758981781

i = 2 #error: 0
d = 950361351796356.1      #15 digits of integer,Decimal 1 digit
AC: 950361351796356        #15 digits=15 digits
WA: 950361351796356

i = 3 #error: 0
d = 190072270359271.22     #15 digits of integer,Decimal 2 digits
AC: 190072270359271        #15 digits=15 digits
WA: 190072270359271

(Omitted below)

The integer digit part is important for the answer to the Atcoder problem this time. It turns out that an error occurs when the integer digits are more than the float type precision of 15 digits! When 4 <= i <25, the integer digit never becomes larger than 15 digits, so it seems that there was no error.

It seems that AC was not this time by biting the floor type d with the error inmath.floor ().

Summary

--ʻA // Bandmath.floor (A / B) are doing the same thing --When both ʻA and B are integer (int) type ʻA // B is output as ** integer type ** --Even if both ʻA and B are integer (int) type, math.floor (A / B) is ʻA / B via ** floating point type **. --If the result of ʻA / B exceeds the precision of float type, an error will occur. -** Depending on the value of ʻA, B, the result of ʻA // B andmath.floor (A / B)may be different ** -** Be careful in competition pros! !! ** **

That's it. Thank you for reading!

[Python3] "A // B" and "math.floor (A / B)" are not always the same! ??