Calculating large fractions in Python?

Question

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, outputting denominators less than 1,000,000

Fraction = 1217471/860882

When I don't use limit_denominator, I get repeat outputs like this:

Fraction = 141421356237/100000000000

Eventually I want to iterate i to 1000, so my fractions will be very large. Any help?

from fractions import *
i = 0
x = 1/2.0
x1 = 0
count = 0
while i < 20:
    (y) = (1.0 + (x))
    (x) = (1 / (2.0 + (x)))
    y1 = Fraction(str(y)).limit_denominator()
    print("\nFraction = " + str(y1))
    i += 1

Answer 1

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 in range(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.

Answer 2

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

Answer 3

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 in range(40):
    y = Fraction(1) + x
    x = Fraction(1) / (Fraction(2) + x)
    print("Fraction = " + str(y))

Output:

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