Python Code For Continued Fractions

Python Code For Continued Fractions

Dan
Dozens Disciple
Dan
Dozens Disciple
Joined: Aug 8 2005, 02:45 PM

Apr 4 2017, 04:26 AM #1

Here are functions for converting rational numbers from the continued fraction representation [a, b, c, d, ...] to the Fraction object a+1/(b + 1/(c + 1/(d + ...))) that it represents.

Code: Select all

from fractions import Fraction

def contfrac_to_frac(cfr):
    if len(cfr) == 0:
        return Fraction(0)
    elif len(cfr) == 1:
        return Fraction(cfr[0])
    else:
        return Fraction(cfr[0]) + 1 / contfrac_to_frac(cfr[1:])

def frac_to_contfrac(frac):
    frac = Fraction(frac)
    if frac.denominator == 1:
        return [frac.numerator]
    else:
        ipart, fpart = divmod(frac, 1)
        return [int(ipart)] + frac_to_contfrac(1 / fpart)
I realize that recursion isn't the most efficient way of doing things (and throws an exception if you hit the 1000 stack frame limit), but it's simple. I may post an "optimized" version later.

Note that since all finite float values are rational, they will all have a finite continued fraction representation.

Some interesting "irrational" values are:

Code: Select all

>>> frac_to_contfrac(math.e)
[2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 11, 1, 1, 1, 11, 5, 1, 1, 2, 1, 4, 2, 1, 1, 9, 17, 3]
>>> frac_to_contfrac(math.sqrt(2))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 7, 1, 2, 33, 2, 7, 5, 2, 1, 1, 16, 2]
>>> frac_to_contfrac((1 + math.sqrt(5)) / 2)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 7, 1, 5, 5, 1, 1, 2, 4, 1, 1, 10, 1, 2, 1, 8]
Quote
Like
Share

icarus
Dozens Demigod
icarus
Dozens Demigod
Joined: Apr 11 2006, 12:29 PM

Apr 4 2017, 09:17 PM #2

Mathematica has the ContinuedFraction command and does the same thing. For instance OEIS A003417 = e is generated by

Code: Select all

Block[{$MaxExtraPrecision = 1728}, 
 ContinuedFraction[E, $MaxExtraPrecision]]
This gives the first great gross of terms. (We could just use ContinuedFraction[E, 120] if we just wanted two dozen handfuls of terms.)

We could also write a "cheat" for it:

Code: Select all

Array[{Boole[# == 1] + 1, 1, 2 #} &, 12] // Flatten
This gives the first 3 dozen terms, recognizing it is 2, 1, 2, then repeats 1, 1, and 2(n/3) for every digit in a position that is congruent to 0 (mod 3).

Unfortunately Mathematica (Wolfram) is really my only language that I use nowadays (unfortunate for it is proprietary and is not a widely known language because of it). At least Python has sympy and other packages that help it along mathwise. There is also PARI and Matlab.
Quote
Like
Share

jrus
Regular
jrus
Regular
Joined: Oct 23 2015, 12:31 AM

Apr 19 2017, 10:16 PM #3

Quote
Like
Share

Ruthe
Regular
Ruthe
Regular
Joined: Feb 27 2006, 09:23 PM

Apr 26 2017, 08:28 PM #4

Dan @ Apr 4 2017, 04:26 AM wrote:Here are functions for converting rational numbers from the continued fraction representation [a, b, c, d, ...] to the Fraction object a+1/(b + 1/(c + 1/(d + ...))) that it represents.
Romans had no way to represent most fractional values but relied on listing a value as the sum of ever smaller fractions up to a point they felt was of sufficient accuracy. These fractions were invariably sub-multiples of twelfths and eighths, written as the names of each fraction down to the smallest used by the Romans which was 1/2304 which is 1/(2^4 x 12^2) = approx 0.000434027 (Added this: or 0.0009 uncial)

PPS The Romans used mainly twelfths for fractional values but also saw the usefullness of eighths, so had names for halves, quarters, eighths and sixteenths and their combinations with sub multiples of twelfths. They saw that 1/8 was just 1½ twelfths.
Why a Roman pocket abacus? They used dozenal fractions as their main form of fractions, 12 inches per foot & originally 12 oz per pound (inch=ounce=uncia=1/12). Columns 1 & 2 of the abacus are for dozenal fractions, column two for twelfths and column one, dozenal fractions of a twelfth. Columns 3 through 8 provided a decimal place value system with values from 1s to millions where each lower bead counts as 1 & the upper beads count 5 of a column's base 10 power, Is, Vs, Xs, Ls, Cs ,Ds, Ms etc.
Quote
Like
Share