Separation of large numbers in Python

Question

I'm trying to split some big numbers in Python, but getting some weird results

NStr = "7D5E9B01D4DCF9A4B31D61E62F0B679C79695ACA70BACF184518" \ "8BDF94B0B58FAF4A3E1C744C5F9BAB699ABD47BA842464EE93F4" \ "9B151CC354B21D53DC0C7FADAC44E8F4BDF078F935D9D07A2C07" \ "631D0DFB0B869713A9A83393CEC42D898516A28DDCDBEA13E87B" \ "1F874BC8DC06AF03F219CE2EA4050FA996D30CE351257287" N = long(NStr, 16) f2 = 476 fmin = N / float(f2) print N - (fmin * float(f2)) 

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

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

I still get output 0.0

I also tried using decimal package

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

But it gives me the result -1.481136900397802034028076389E+280

I assume that I am not telling python how to handle large numbers correctly, but I am at a dead end on where to go from here.

I should also add that the ultimate goal is to compute

 fmin = ceil(N / float(f2)) 

as long and precise as possible

Answer 1

Expanding my comment, if N and f2 long strictly greater than 0, then

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

exactly ceil(N / float(f2)) (but even more accurate than using float).

(Using // instead of / for integer division for compatibility with Python 3.x requires no extra effort.)

This is because N // f2 gives you (mostly) floor(N / float(f2)) , and so N // f2 + 1 almost always matches ceil . However, when N is a multiple of f2 , N // f2 + 1 too large ( +1 should not be there), but using N - 1 corrects this and does not violate another case.

(This does not work for N , f2 less than or equal to 0, but can be processed separately)

Answer 2

fmin is a float after you divide a long integer by a float. Its value is 1.84952718165824e+305 . Appendix 1 to this does not change it at all, the accuracy is simply not so high.

If you do integer division, fmin remains long :

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

Of course, you are not getting 0 due to integer division, in which the decimal part of the result is discarded. But now the addition of 1 will matter:

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

Using the Decimal module Decimal not change the problem:

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

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

Answer 3

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

 fmin = (N + f2 - 1) / f2 

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

Answer 4

Floats simply do not have sufficient accuracy for this type of operation.

You can improve the accuracy of the decimal module with getcontext() . For example, to use 65536 decimal places:

 from decimal import Decimal, getcontext getcontext().prec = 2**16 

Then:

 >>> print Decimal(N) - (fmin * Decimal(f2)) -2E-65228 

Not yet 0, but closer :)

See this answer to make ceil() in a decimal object.

Answer 5

I also found the behavior in python 2.7.2:

 In [17]: N Out[17]: 8803749384693223444020846698661754642258095369858506383021634271204825603217187705919415475641764531639181067832169438773077773745613648054092905441668 8183122792368821460273824930892091174018634908205253603559871152770444609114256540750019592650731223893254070047675403322419289706083795604293822590057017991L In [18]: In [18]: (fmin * float(f2)) Out[18]: 8.803749384693223e+307 In [19]: N - (fmin * float(f2)) Out[19]: 0.0 In [20]: (fmin * float(f2)) Out[20]: 8.803749384693223e+307 In [21]: N == (fmin * float(f2)) Out[21]: False In [22]: N < (fmin * float(f2)) Out[22]: False In [23]: N > (fmin * float(f2)) Out[23]: True 

For reasons I don't understand, it seems that subtracting the float from long gives 0.

The solution will be to convert both to decimal.Decimal :

 In [32]: decimal.Decimal(N) - decimal.Decimal(fmin * float(f2)) Out[32]: Decimal('4.099850360284731589507226352E+291') 

Answer 6

Fraction from fractions module can 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