Geek asks and answers

The factorial of a large number in python

Here is my approach to factorials:

def factorial(n):
    '''Returns factorial of n'''
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

I think this is quite simple, although I think you could do something more efficient because it takes ages for large numbers like 100000. My question is, is there? math.factorial () is also not suitable, it takes about the same amount of time.

+5
source share
9 answers

Multiplication of numbers in a sequence,

for i in range(1, n + 1):
    r *= i
return r

creates a large number (as in tens of thousands of bits) very quickly, and then you have many multiplications by one huge number and one small number. Multiplications, when at least one of the factors is huge, is slow.

You can speed it up significantly by reducing the number of multiplications including huge numbers, like

def range_prod(lo,hi):
    if lo+1 < hi:
        mid = (hi+lo)//2
        return range_prod(lo,mid) * range_prod(mid+1,hi)
    if lo == hi:
        return lo
    return lo*hi

def treefactorial(n):
    if n < 2:
        return 1
    return range_prod(1,n)

, 100000! % 100019 ( len(str(fun(100000)), , , ):

$ python factorial.py 
81430
math.factorial took 4.06193709373 seconds
81430
factorial took 3.84716391563 seconds
81430
treefactorial took 0.344486951828 seconds

10 × 100000!.

+15

, , .

+6

, .

lgamma, n-1.

, (n) lgamma (n + 1).

log10, 10.

, , Python :

from math import *
print ceil(lgamma(100000+1)/log(10))
+4

, , .

( ) - , GMP, Multiple Precision GNU. Python.

+2

, (100000) 2.8242294080 × 10 ^ 456 573
, .

0

- (math.gamma(x)), , , for

0

, : n , .

. ( FFT). , , . .

.

0

, :

>>> from functools import reduce
>>> mul = int.__mul__
>>> len(str(reduce(mul, range(2,100001), 1)))
456574
>>>

Python 2 longs: long.__mul__ len(str(reduce(mul, range(2L,100001L), 1L)))

0

def for_factorial (num): if num <2: return 1 res = num and num> 1: num - = 1 res * = num return res

-2
source

More articles:


All Articles