CODEWITHSUNDEEP
pythonfactorial
MrPrg
MrPrg

Reputation: 13

calculating factorial of large numbers in 0.5 second with python

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

Upvotes: 0

Views: 2209

Answers (5)

Selahattin Mert Akel
Selahattin Mert Akel

Reputation: 58

Maybe you can try to make use of threads.

Upvotes: 0

Guillaume S
Guillaume S

Reputation: 190

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.

Upvotes: 0

Moinuddin Quadri
Moinuddin Quadri

Reputation: 48067

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

Upvotes: 0

Philippe Banwarth
Philippe Banwarth

Reputation: 17725

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

Upvotes: 1

abukaj
abukaj

Reputation: 2712

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.

Upvotes: 0

Related Questions