calculating factorial of large numbers in 0.5 second with python

Question

I've been trying to find a super fast code that can calculate the factorial of a big number like 70000 in 0.5 second,My own code could do it in 10 seconds.I've searched everywhere, every code I find has memory error problem or is not as fast as I want. Can anyone help me with this?

enter code here
import math
num =int(raw_input())
usefrm=0
if len(str(num)) > 2:
  if int(str(num)[-2]) % 2 == 0:
        usefrm = 'even'
  else:
        usefrm = 'odd'
else:
  if num % 2 == 0:
        usefrm = 'even1'
  else:
        usefrm = 'odd1'

def picknumber(num):
  s = str(math.factorial(num))
  l = []
  for n in s:
        if int(n) != 0:
              l.append(int(n))
  return l[-1]

  def picknumber1(num):
  s = str(num)
  l = []
  for n in s:
        if int(n) != 0:
              l.append(int(n))
  return l[-1]
  if usefrm == 'even':
     e=picknumber1(6*picknumber(int(num/5))*picknumber(int(str(num)[-1])))
  if usefrm == 'odd':
     e=picknumber1(4*picknumber(int(num/5))*picknumber(int(str(num)[-1]))) 
  else:
  e=picknumber1(math.factorial(num))
  print e

70000! is absolutely gigantic. What kind of big number library are you using? — Bathsheba, Sep 30 '16 at 11:15
Possible duplicate of http://stackoverflow.com/questions/1751334/fast-algorithms-for-computing-the-factorial (just with the python flag) — Mijago, Sep 30 '16 at 11:24
Using the gmpy library I can calculate 70000! in around 0.5 seconds on this old 2GHz machine. — PM 2Ring, Sep 30 '16 at 11:27
oh sorry I forgot to put my code.I just fixed it. @Bathsheba — MrPrg, Sep 30 '16 at 11:27
What's the goal here, algorithmic or practical? It takes me < 0.2 s to compute 70000! using the built-in `math.factorial`. — DSM, Sep 30 '16 at 11:27
@DSM Wow! `math.factorial(70000)` takes over 43 seconds on this old beast; that includes printing it (to /dev/null). — PM 2Ring, Sep 30 '16 at 11:32
That time measurement (using the bash time command) was on Python 3.6; on Python 2.6 it takes over 2m23s. — PM 2Ring, Sep 30 '16 at 11:38
@PM2Ring `math.factorial(70000)` took 0.18 seconds on my system, timed using `timeit.timeit` (not including import times) — Chris_Rands, Sep 30 '16 at 11:53
@Chris_Rands: A significant proportion of my times are for the conversion / printing. If I just do the calculation, then the times (for `math.factorial(70000)`) are 1.312s on Py3.6 and 25.007s on Py2.6. — PM 2Ring, Sep 30 '16 at 12:05
@Boris Not really; `reduce` is still doing the factorial arithmetic with Python integers, at Python speed. — PM 2Ring, Sep 30 '16 at 12:10

score 1 · Answer 1 · answered Sep 30 '16 at 11:51

For most practical use, the Stirling's approximation is very fast and quite accurate

import math
from decimal import Decimal

def fact(n):
    d = Decimal(n)
    return (Decimal(2 * math.pi) * d).sqrt() * (d / Decimal(math.e)) ** d

print(fact(70000))

1.176811014417743803074731978E+308759

score 0 · Answer 2 · answered Sep 30 '16 at 11:22

Try to use the commutativity property of integer multiplication.

When multiplied numbers are long (they do not fit in a single word), the time necessary to perform the operation grows superlinearly with their length.

If you multiply the smallest (shortest in terms of memory representation) factors (and partial products) first, you may save a lot of time.

Guillaume S · Answer 3 · 2016-09-30T13:27:33.790

0

If you don't want a perfect precision, you can use the Stirling's approximation https://en.wikipedia.org/wiki/Stirling's_approximation

import np
n! ~ np.sqrt(2*np.pi*n)*(n/np.e)**n

for large n values. This calculation is literally instantaneous.

edited Sep 30 '16 at 13:27

answered Sep 30 '16 at 12:24

Guillaume S

190
2
4

score 0 · Answer 4 · answered Sep 30 '16 at 12:25

You may use math.factorial(). For example:

from math import factorial 
factorial(7000)

with execution time of 20.5 msec for calculating the factorial of 7000:

python -m timeit -c "from math import factorial; factorial(7000)"
10 loops, best of 3: 20.5 msec per loop

score 0 · Answer 5 · answered Mar 09 '20 at 15:42

0

Maybe you can try to make use of threads.

answered Mar 09 '20 at 15:42

Selahattin Mert Akel

58
1
6

Please make a more elaborate answer OP could actually use. Thank you. – THess Mar 09 '20 at 16:01

calculating factorial of large numbers in 0.5 second with python

5 Answers5