How to run faster a code that calculates the number of factorial digits of a number?

Question

The code must print how many digits have the factorial of N.

I am trying to perform a simple factor challenge on the URI site and when I submit the code the answer is always "Time limit exceeded", the limit is 1.00s and is giving 2.00s. I already researched about the problem and tried to modify the code to get faster, but the error repeats. Follow the codes I submitted:

N = int(input())
for i in range(1, N):
  N = (i * N)
print(len(str(N)))

This one too:

import math
N = input()
print(len(str(math.factorial(int(N)))))

I tried to use the stdout.write but gave "Presentation Error" although it ran also in 2.00s

import math
from sys import stdin, stdout
N = int(input())
for i in range(1, N):
  N = N * i
  stdout.flush()
N = len(str(N))
stdout.write(str(N))

import math
from sys import stdin, stdout
N = int(input())
for i in range(1, N):
  N = N * i
  stdout.flush()
N = len(str(math.factorial(N)))
stdout.write(str(N))

I would like tips on which way to go for better execution time and why these did not work.

Answer 1

The problem is that the factorial grows very fast, and in a short time you will be multiplying huge numbers, which is quite time consuming. Just to give you an idea, the factor of 10⁸ (which is the maximum limit you indicated) is a number with more than 750 million digits. Manipulating numbers of this magnitude cannot be fast...

So an alternative is to calculate the number of factorial digits, but without having to calculate the factor value.

One way to get the number of digits of a number is to calculate the logarithm at base 10, round down and add 1.

Another detail is that the log₁₀(a * b) is equal to log₁₀(a) + log₁₀(b).

And since the factorial of N is the multiplication of all integers between 1 and N, we can calculate the log₁₀(N! ) summing up the logs of all numbers between 1 and N. That is:

• log₁₀(N! ) is the same as log₁₀(1 * 2 * 3 * ... * N)
• which in turn is the same as log₁₀(1) + log₁₀(2) + log₁₀(3) + ... + log₁₀(N)

Then just add the logs of all numbers from 1 to N, round down and add 1, to get the number of digits of N! (no need to calculate the factor value).

Would look like this:

from math import floor, log10

n = int(input())

res = 0
for i in range(1, n + 1):
  res += log10(i)

print(floor(res) + 1)

Or else:

print(floor(sum(map(log10, range(1, n + 1)))) + 1)

I didn’t test it in the online URI, but I did little test in which the two options above proved to be much faster than calculating the factorial:

from math import floor, log10, factorial
from timeit import repeat

def log(n):
  res = 0
  for i in range(1, n + 1):
    res += log10(i)

  return floor(res) + 1

def log2(n):
  return floor(sum(map(log10, range(1, n + 1)))) + 1

def fact(n):
  return floor(log10(factorial(n))) + 1 

n = 200000
x = 1
r = 3
print (repeat ('log(n)', repeat=r, number=x, globals=globals()))
print (repeat ('log2(n)', repeat=r, number=x, globals=globals()))
print (repeat ('fact(n)', repeat=r, number=x, globals=globals()))

And the higher the N, the greater the difference between approaches.

And it makes sense. When calculating the factorial, you are multiplying bigger and bigger numbers, while in the logarithmic method we are adding small numbers (all right we have to calculate the logarithm of all numbers, but it still compensates and is faster).

Answer 2

You can use the kamenetsky’s formula to calculate the number of digits contained in the factorial of N, look at you:

def kamenetsky(n):
    if n < 0:
        return 0
    if n <= 1:
        return 1
    x = (n * log10(n / e)) + (log10(2 * pi * n) / 2.0)
    return floor(x) + 1

For the purpose of comparing the algorithms tested, I suggest implementing a function capable of measuring the processing time spent by each of them:

from timeit import default_timer

def teste( func, n, cont=1000 ):
    inicio = default_timer()
    for i in range(cont):
        func(n)
    fim = default_timer()
    total = fim - inicio
    return (total / cont) * (10**6) # Tempo em microsegundos 

Testing:

from math import log10, floor, factorial, pi, e
from timeit import default_timer

def teste( func, n, cont=1000 ):
    inicio = default_timer()
    for i in range(cont):
        func(n)
    fim = default_timer()
    total = fim - inicio
    return (total / cont) * (10**6)

def f1(n):
    for i in range(1, n):
        n = i * n
    return len(str(n))

def f2(n):
    n = factorial(n)
    return len(str(n))

def f3(n):
    if n < 0:
        return 0
    if n <= 1:
        return 1
    x = (n * log10(n / e) + log10(2 * pi * n) / 2.0)
    return floor(x) + 1

N = 100
print('f1(): {:.3f} uS'.format(teste(f1, N)))
print('f2(): {:.3f} uS'.format(teste(f2, N)))
print('f3(): {:.3f} uS'.format(teste(f3, N)))

Exit:

f1(): 7.629 uS
f2(): 1.796 uS
f3(): 0.678 uS

Answer 3

This question refers to the number problem "3096", whose title is "overflow", made available by URI Online Judge (online programming marathon).

See here the entirety of the statement.

The question emphasizes that in many cases where it is necessary to calculate the factorial of a number, whose result has a number muito grande of digits, possibly can result in a overflow.

Note that the question says that the program must support values N, such that, 1<= N <= 10^8, that is, it must bear values between 1 and 100000000. Now, imagine how much computational resources a program would use if it had to calculate the factor of 100000000?

To begin with, the número total de dígitos of 100000000! is 756570557. To improve readability we can divide into thousands and leave it as follows 756.570.557,that is, the total number of digits resulting from the 100.000.000 is setecentos e cinquenta e seis milhões, quinhentos e setenta mil, quinhentos e cinquenta e sete.

How much demorado the correct value for factors of grandes values, the problem asks us to calculate apenas the number of digits of the possible factorial.

In mathematics, we can calculate the number of digits of the factorial result without even having calculated the factorial of that number. To do this, simply use the formula Kamenetsky.

In order to implement this formula correctly in the Uri issue, with all the constraints that are emphasized, we must write the following code...

from math import log10, e, pi, floor

n = int(input())

num_digitos = floor((n * log10(n / e)) + (log10(2 * pi * n) / 2.0)) + 1
print('{}'.format(num_digitos))

See here the functioning of the algorithm.

Note that when we run this program, the console screen is limpa, awaiting the typing of the value of N. After we enter the value of N and then press Enter, the program completes the task.

This code has already been testado, submetido and properly aprovado, in the marathon that I refer to at the beginning of the post, under programming language Python 3.

For the record, this program only took 0.028 s to run on the website URI.

Answer 4

You can compute the factorial of a number using the Ramanujan Gamma function which is similar to Gamma de Stirling, but it is more precise:

Gamma function or Γ is the extension of the factorial function to the set of real and complex numbers. Gamma function is defined for all complexes except negative integers.

As the domain established by AP [0, 10 ] is of extension greater than sys.float_info.max I used the library Mpmath which is a Python library for arbitrary precision floating-point arithmetic.

The implementation to compute the number of digits of a factorial looks like this:

#No comentário foi definido o domínio [0, 10 ^ 80] então usei mpmath 
from mpmath import log10, pi, e, sqrt

def gamma(x):
  return int(log10(sqrt(pi)*(x/e)**x * (((8*x + 4)*x + 1)*x + 1/30.)**(1./6.))) + 1

Test in Repl.it: https://repl.it/repls/RelievedJaggedLogins

Answer 5

Send the question if that code doesn’t help you.

num = int(input('Numero: '))
for i in range(1, num):
  num = i * num
#Mostrando o fatorial do numero digitado
print(num)
#Essa varivel converte o valor int para string
converte = str(num)
#Aqui ele mostra o tamanho da string
print(len(converte))