Python not correctly dividing large floats

Question

I am writing a program to compute the factorial digit sum of 100. We are not allowed to use looping structures or have a program state; we are only supposed to use recursion. This means that I will first calculate 100! and then add each digit in the answer together. Ex: 10! = 3628800. 3+6+2+8+8+0+0 = 27.

The program is set up using 2 recursive loops. The first loop is a simple recursion structure calculating the factorial of n. This operates properly using n = 100.

Next, in order to add the digits using recursion, a function of 3 components was written.

1. n % 10: this will isolate the last digit of n
2. math.floor( n / 10 ) : once the digit is isolated, we need to remove it from the number. We do this by dividing n by 10 and rounding down to the nearest integer.
3. return ( n % 10 ) + Summation( math.floor( n / 10 )): this will add each isolated digit in a recursive call

This program works perfectly up to an input of 22. However, when trying to calculate the digit sum of 23!, math.floor( n % 10 ) does not divide properly.

Here is the output when I run using 100 as an input. The first line is the calculated factorial, Mod is the last digit, Divide is the factorial divided by 10 (not rounded), and New Num is the rounded down value. As you can see, New Num was not accurately divided

The big question here, what is making this computation incorrect at such high values? Does this have to do with Python's level of precision? Thanks!

Code:

'''
--------------------------------------------------------
Problem 20:
n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!
----------------------------------------------------------
'''
import math


def Divide(n):
  return float(n/10)

'''
How to sum the digits:
First, we access the last digit by using Mod 10, which gives us the remainder
Second, in order to dispose of that digit (as we have already retrieved it), 
we divide the number by 10 and round down to the nearest integer. This is done by 
using math.floor(x)
Lastly, we add the retrieved digit to the recursive call of Summation that passes 
through the rounded-down, divided number
'''
def Summation(n):
  if n <= 0:
    return n
  else:
    print("---------------------")
    print("Number: ", n)
    print("Mod: ", n%10)
    print("Divide: ", str(n/10))
    print("New Num: ", math.floor(Divide(n)))
    return (n % 10) + Summation(math.floor(Divide(n)))

def Factorial(n):
  if n == 1:
    return n
  else:
    return n * Factorial(n-1)

def Main(n):
  return Summation(Factorial(n))

'''
To run the program: call Main(100). Then, on the first printed segment, compare 
Number to New Num. The only difference between these numbers is that New Num should 
have the last digit removed since we divided by 10 and got rid of the decimal. However, 
as you can see, the number changes drastically after this simple computation. If you 
scroll more towards the bottom, you can see this method work correctly.
'''

Answer 1

The calculation math.floor( n / 10 ) converts to a 64-bit float and then back to an integer. You should instead keep the number as an integer. Integers in Python have unlimited precision, so they can represent numbers like 100! exactly. It is not possible to represent 100! exactly in floating-point, without using a higher-precision floating-point number.

Just use n // 10 instead of math.floor(n / 10), avoiding the conversion.

You can see how / and // work in Python for yourself:

>>> type(10)
<class 'int'>
>>> type(10/10)
<class 'float'>
>>> type(10//10)
<class 'int'>
>>> 10/10
1.0
>>> 10//10
1

Answer 2

Using floor(x/10) will first compute x/10 as a float. Floats only have 53 significant bits of precision, so they won't handle huge numbers correctly. When working with huge numbers, it's best to stick to using integer arithmetic. Replace:

floor(x / 10)  --->  x // 10