Calculating Large Fractions In Python?

I am trying to calculate fractions in Python 2.7. The limit_denominator method works great for the first 15 iterations of this code. However, then the code gets stuck in a loop,

Solution 1:

The values converge to sqrt(2.0), which gives you a narrow range of fractions that will accurately represent the 64-bit float value. Your rational fraction cannot be more accurate than the float you give it.

If you want larger denominators, then you have to specify a larger denominator limit. You're still limited by the float accuracy: once you converge within the accuracy of your computational type (likely float64), you will not get more accuracy in your rational representation thereof. If you want greater accuracy, convert the entirety to fraction computations:

from fractions import *

x = Fraction(1,2)

for i inrange(40):
    y = Fraction(1) + x
    x = Fraction(1) / (Fraction(2) + x)
    print("Fraction = " + str(y))

Output:

Fraction = 3/2Fraction = 7/5Fraction = 17/12Fraction = 41/29Fraction = 99/70Fraction = 239/169Fraction = 577/408Fraction = 1393/985Fraction = 3363/2378Fraction = 8119/5741Fraction = 19601/13860Fraction = 47321/33461Fraction = 114243/80782Fraction = 275807/195025Fraction = 665857/470832Fraction = 1607521/1136689Fraction = 3880899/2744210Fraction = 9369319/6625109Fraction = 22619537/15994428Fraction = 54608393/38613965Fraction = 131836323/93222358Fraction = 318281039/225058681Fraction = 768398401/543339720Fraction = 1855077841/1311738121Fraction = 4478554083/3166815962Fraction = 10812186007/7645370045Fraction = 26102926097/18457556052Fraction = 63018038201/44560482149Fraction = 152139002499/107578520350Fraction = 367296043199/259717522849Fraction = 886731088897/627013566048Fraction = 2140758220993/1513744654945Fraction = 5168247530883/3654502875938Fraction = 12477253282759/8822750406821Fraction = 30122754096401/21300003689580Fraction = 72722761475561/51422757785981Fraction = 175568277047523/124145519261542Fraction = 423859315570607/299713796309065Fraction = 1023286908188737/723573111879672Fraction = 2470433131948081/1746860020068409

Solution 2:

I rewrote your code trying to solve your problem because i did not understand the need for limit_denominator. This is the result:

from fractions import *
x = Fraction(1, 2)
for i inrange(1000):
    y = 1 + Fraction(x)
    print'Y', y
    x = 1 / (2 + x)
    print'X', x

The problem is that computers don't really understand numbers, instead they work with an abstract representation of numbers in memory called floating point (the origin of float i assume). This representation has a given precision (limit) which depends on the amount of memory reserved for the data type. That is why int32 has fewer accepted values than int64 for example. However, python has a smart and efficient way of calculating large numbers. Besides, the fractions library provides you with a way of representing numbers (fractions) that escape (not really, after all it is a computer) the floating point numbers constraint. If you want to dive more into floating point arithmetic I recommend the all-mighty Numerical Analysis by Burden & Faires and Numerical Methods by Dr David Ham.

Solution 3:

As Prune says, it's best to avoid floats when working with Fraction. And if you want to convert your fraction to a decimal without losing any accuracy you need to use a numeric type like Decimal which has enough precision. Another option is to just work with Python integers, and scale up your numerator with a sufficiently large multiplier.

Your series finds the convergents to the continued fraction of the square root of two. If you want to loop over all the convergents you can use the algorithm shown in Prune's answer. But if you want to calculate sqrt(2) quickly to a large number of digits, there's a better way, known as Hero's method (or Heron's method). This is a special case of Newton's method for calculating roots of algebraic equations. Instead of calculating the terms for each i in Prune's algorithm 1 by 1 we're essentially doubling i on each iteration, so the numerator & denominator grow large very quickly, doubling the accuracy of the answer on each loop iteration.

Here's a short demo that calculates sqrt(2) accurate to 100 digits. I'd normally do this using plain Python integers (or long integers in Python 2), but it's also easy to do it with a Fraction.

from __future__ import print_function
from fractions import Fraction as F

digits = 100
m = 10 ** digits

x = F(1, 1)
while x.denominator < m:
    print(x)
    x = x / 2 + 1 / x

print()
print(m * x.numerator // x.denominator)

output

1
3/2
17/12
577/408
665857/470832
886731088897/627013566048
1572584048032918633353217/1111984844349868137938112
4946041176255201878775086487573351061418968498177/3497379255757941172020851852070562919437964212608
48926646634423881954586808839856694558492182258668537145547700898547222910968507268117381704646657/34596363615919099765318545389014861517389860071988342648187104766246565694525469768325292176831232

14142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727

Tested on Python 2.6 and 3.6