How to Manage Division of Huge Numbers in Python

How to manage division of huge numbers in Python?

In Python 3, number / 10 will try to return a float. However, floating point values can't be of arbitrarily large size in Python and if number is large an OverflowError will be raised.

You can find the maximum that Python floating point values can take on your system using the sys module:

>>> import sys
>>> sys.float_info.max
1.7976931348623157e+308

To get around this limitation, instead use // to get an integer back from the division of the two integers:

number // 10

This will return the int floor value of number / 10 (it does not produce a float). Unlike floats, int values can be as large as you need them to be in Python 3 (within memory limits).

You can now divide the large numbers. For instance, in Python 3:

>>> 2**3000 / 10
OverflowError: integer division result too large for a float

>>> 2**3000 // 10
123023192216111717693155881327...

How to do correct division for large numbers in Python?

Here is a very nice explantion

What you need is

print(int(231871064940156750//5),231871064940156750/5%100)

The use of // rather than / for integer division is for compatibility with Python 3.x for no extra effort.

Also make sure to take a quick look

for the / and // operators

Handling very large numbers in Python

Python supports a "bignum" integer type which can work with arbitrarily large numbers. In Python 2.5+, this type is called long and is separate from the int type, but the interpreter will automatically use whichever is more appropriate. In Python 3.0+, the int type has been dropped completely.

That's just an implementation detail, though — as long as you have version 2.5 or better, just perform standard math operations and any number which exceeds the boundaries of 32-bit math will be automatically (and transparently) converted to a bignum.

You can find all the gory details in PEP 0237.

Does Python have trouble with large numbers/lists, or is there something wrong with my code?

Somewhere along the way you are getting a floating point error. "But I am using integers!" I hear you say, well Python is doing a float division on this line:

i = n / 2

Seems innocuous enough, but changing to integer division solves the problem:

i = n // 2

After several hundred values, one of those divisions is giving you an error with the value being some epsilon less than the actual integer value, which then rounds down when you call int(n).

EDIT: After double checking my last point to find the value that fails, I wasn't quite correct. What is actually happening is that while integer division is always accurate thanks to Pythons BigInt implementation, float division isn't since it still uses regular floating point numbers for speed. If your number is large enough then there simply aren't enough bytes to accurately store the number which will result in rounding errors.

The number in question is 19981441939834942. With integer division you get 9990720969917471, while float division yields 9990720969917472.0.

This will be a problem in any language you use (except that most other languages won't allow you to accidentally use float division on integers), so make sure to use integer divisions!

Why does division become faster with very large numbers

Why does the division generally get faster later on as opposed to the time of the first two terms which are the smallest?

It doesn't, actually. If I replace di with:

def di(n):
    for i in range(10000000): n / 101

Then I get (Python 3.5, which I presume you are using):

On 10 0.546889
On 100000 0.545004
On 1000000000 0.5454929999999998
On 10000000000000 0.5519709999999998
On 100000000000000000 1.330797
On 1000000000000000000000 1.31053
On 10000000000000000000000000 1.3393129999999998
On 100000000000000000000000000000 1.3524339999999997
On 1000000000000000000000000000000000 1.3817269999999997
On 10000000000000000000000000000000000000 1.3412670000000002
On 100000000000000000000000000000000000000000 1.3358929999999987
On 1000000000000000000000000000000000000000000000 1.3773859999999996
On 10000000000000000000000000000000000000000000000000 1.3326890000000002
On 100000000000000000000000000000000000000000000000000000 1.3704769999999993
On 1000000000000000000000000000000000000000000000000000000000 1.3235019999999995
On 10000000000000000000000000000000000000000000000000000000000000 1.357647
On 100000000000000000000000000000000000000000000000000000000000000000 1.3341190000000012
On 1000000000000000000000000000000000000000000000000000000000000000000000 1.326544000000002
On 10000000000000000000000000000000000000000000000000000000000000000000000000 1.3671139999999973
On 100000000000000000000000000000000000000000000000000000000000000000000000000000 1.3630120000000012
On 1000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.3600200000000022
On 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.3189189999999975
On 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1.3503469999999993

As you can see, there are roughly two times: one for smaller numbers, and one for larger numbers. In Python 3.5, / does floating point division, so it should actually take about the same amount of time regardless of the size of the numbers.

However, there is that gap from small to large. The same result happens with Python 2.7 using the following function to preserve semantics:

def di(n):
    for i in xrange(10000000): n / 101.0

On the same machine, I get:

On 10 0.617427
On 100000 0.61805
On 1000000000 0.6366
On 10000000000000 0.620919
On 100000000000000000 0.616695
On 1000000000000000000000 0.927353
On 10000000000000000000000000 1.007156
On 100000000000000000000000000000 0.98597
On 1000000000000000000000000000000000 0.99258
On 10000000000000000000000000000000000000 0.966753
On 100000000000000000000000000000000000000000 0.992684
On 1000000000000000000000000000000000000000000000 0.991711
On 10000000000000000000000000000000000000000000000000 0.994703
On 100000000000000000000000000000000000000000000000000000 0.978877
On 1000000000000000000000000000000000000000000000000000000000 0.982035
On 10000000000000000000000000000000000000000000000000000000000000 0.973266
On 100000000000000000000000000000000000000000000000000000000000000000 0.977911
On 1000000000000000000000000000000000000000000000000000000000000000000000 0.996857
On 10000000000000000000000000000000000000000000000000000000000000000000000000 0.972555
On 100000000000000000000000000000000000000000000000000000000000000000000000000000 0.985676
On 1000000000000000000000000000000000000000000000000000000000000000000000000000000000 0.987412
On 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0.997207
On 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0.970129

This has something to do (exact specifics to be determined) with converting the integer to a floating point number. This is slower with integers beyond a certain point, and when that point is crossed, the division starts taking longer.

Python integer division when integers are very long

In python 3:

// is used for integer division, this will give you the correct result.

print(N//5)

output:

37976099630974882181694214460891074195560794810598715548942859588791116710647901151257847105814835418037954576749411059998307979336216414740

where
/ is used for floating point division, so it might give errors while rounding up the digits.

---

Related Topics