python: computing extremely large number

Question

I need to compute extremely large numbers using Python.

It could be as large as

factorial(n x 10,000,0000)*factorial(n x 10,000,0000)

so I think on a usual 32-bit computer it overflows...

Is there a workaround?

possible duplicate of [Handling very large numbers in Python](http://stackoverflow.com/questions/538551/handling-very-large-numbers-in-python) — Jan Vorcak, Jul 28 '13 at 10:15
Can you provide an example of how the results using Python differ from your expected results? — casevh, Jul 28 '13 at 17:24

score 3 · Accepted Answer · answered Jul 28 '13 at 10:14

3

This is not an issue under Python.

>>> 2**100
1267650600228229401496703205376L

Python automatically converts plain integers into long integers and does not overflow.

http://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex

answered Jul 28 '13 at 10:14

cha0site

10,517
3
33
51

thanx. but somehow the factorial returned by python is different and much smaller than my calculation on excel. I was wondering why that might be. – ytrewq Jul 28 '13 at 10:34

score 1 · Answer 2 · answered Jul 28 '13 at 10:14

1

You want to use bignums. Python has them natively.

answered Jul 28 '13 at 10:14

Basile Starynkevitch

223,805
18
296
547

score 1 · Answer 3 · answered Jul 28 '13 at 10:41

Stirling's approximation to n! is (n/e)^n * sqrt(2 * pi * n). This has roughly n * log(n/e) digits.

You're computing (n * 1e8)!^2. This will have roughly 2 * n * 1e8 * log(n * 1e8 / e) digits, which is 2e8 * n * (17 + log(n)). Assuming n is relatively small and log(n) is negligible, this is 3.4e9 * n digits.

You can store around 2.4 digits in a byte, so your result is going to use (1.4 * n) gigabytes of RAM, assuming Python can store the number perfectly efficiently.

A 32 machine can address at most 4GB of RAM, so n = 1 or 2 is theoretically possible to compute, but for n = 3, the machine can't even hold the result in RAM. As you compute your result, Python's going to have to hold in RAM multiple bignums (for example, temporary variables), so the actual memory usage is going to be higher than the calculations above suggest.

In practice, I'd expect on a 64 bit machine with plenty of RAM you can never get to a result for this calculation in Python -- the machine will spend all its time garbage collecting.

score 0 · Answer 4 · answered Jul 28 '13 at 10:14

0

As far as I know, integers in Python (3) can be arbitrarily large.

answered Jul 28 '13 at 10:14

ConfusedProgrammer

606
1
5
14

python: computing extremely large number

4 Answers4