Dividing large numbers in Python

Question

I'm trying to divide some large numbers in Python but i'm getting some strange results

NStr = "7D5E9B01D4DCF9A4B31D61E62F0B679C79695ACA70BACF184518" \
       "8BDF94B0B58FAF4A3E1C744C5F9BAB699ABD47BA842464EE93F4" \
       "9B151CC354B21D53DC0C7FADAC44E8F4BDF078F935D9D07A2C07" \
       "631D0DFB0B869713A9A83393CEC42D898516A28DDCDBEA13E87B" \
       "1F874BC8DC06AF03F219CE2EA4050FA996D30CE351257287" 

N = long(NStr, 16)
f2 = 476

fmin = N / float(f2)

print N - (fmin * float(f2))

This outputs as 0.0 as expected. However if I, for example, change the code to

fmin = N / float(f2)
fmin += 1

I still get an output of 0.0

I also tried using the decimal package

fmin = Decimal(N) / Decimal(f2)
print Decimal(N) - (fmin * Decimal(f2))

But that gives me an output of -1.481136900397802034028076389E+280

I assume i'm not telling python how to handle the large numbers properly, but i'm stumped on where to go from here.

I should also add that the end goal is to calculate

fmin = ceil(N / float(f2))

as a long and as accurate as possible

Answer 1

Expanding on my comment, if N and f2 are longs strictly greater than 0, then

 fmin = (N - 1) // f2 + 1

is exactly ceil(N / float(f2)) (but even more accurately than using floats).

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

It is because N // f2 gives you (basically) floor(N / float(f2)) and so N // f2 + 1 is almost always the same as ceil. However, when N is a multiple of f2, N // f2 + 1 is too large (the +1 shouldn't be there) but using N - 1 fixes this, and doesn't break the other case.

(This doesn't work for either N, f2 less than or equal to 0, but that can handled separately)

Answer 2

fmin is a float after you divide the long integer by a float. Its value is 1.84952718165824e+305. Adding 1 to that doesn't change it at all, the precision is simply not that high.

If you do integer division instead, fmin remains a long:

>>> fmin = N / f2
>>> fmin
18495271816582402193321106509793602189617847415669131056768139225220221855498293
49983070478076000952025038039460539798061570960870927236986153971731443029057201
52035339202255934728764897424408896865977423536890485615063959262845076766281553
766072964756078264853041334880929452289298495368916583660903481130L
>>> N - (fmin * f2)
111L

Of course, you're not getting 0 because of the integer division where the decimal part of the result is discarded. But now, adding 1 will make a difference:

>>> N - ((fmin+1) * f2)
-365L

Using the Decimal module doesn't change the problem:

>>> from decimal import Decimal, getcontext
>>> fmin = Decimal(N) / Decimal(f2)
>>> fmin
Decimal('1.849527181658240219332110651E+305')

There still is no unlimited precision, and even if you set Decimal.getcontext().prec = 2000, you still wouldn't get exactly 0.

Answer 3

If you need precision, avoid floating point arithmetic altogether. Since python has arbitrary-precision integers, you can calculate the ceiling of the division using basic integer arithmetic. Assuming the dividend and divisor are both positive, the way to do that is to add divisor - 1 to the dividend before dividing. In your case:

fmin = (N + f2 - 1) / f2

On Python 3.x use the // operator instead of / to get integer division.

Answer 4

Fraction from the fractions module might be useful:

>  : N = Fraction(N)   
>  : f2 = Fraction(f2)
>  : fmin = N / f2
>  : print N-f2*fmin
0
>  : fmin += 1
>  : print N-f2*fmin
-476

But if your only goal is to calculate ceil(N / float(f2)) you can use:

>  : fmin = N/f2 + int(ceil((N % f2) / float(f2)))
>  : print fmin
184952718165824021933211065097936021896178474156691310567681392252202218554982934998307047807600095202503803946053979806157096087092723698615397173144302905720152035339202255934728764897424408896865977423536890485615063959262845076766281553766072964756078264853041334880929452289298495368916583660903481131