public
Created

Creating a simple continued fraction from a square root

  • Download Gist
a_cfrac.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
import math
 
 
def from_root(n):
'''
Construct a continued fraction from a square root. The argument
`n` should be an integer representing the radicand of the root:
 
>>> from_root(2)
(1, [2])
>>> from_root(4)
(2,)
>>> from_root(97)
(9, [1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18])
'''
 
a0 = int(math.floor(math.sqrt(n)))
r = (a0, [])
a, b, c = 1, 2 * a0, a0 ** 2 - n
delta = math.sqrt(4*n)
 
while True:
try:
d = int((b + delta) / (2 * c))
except ZeroDivisionError: # a perfect square
return (r[0],)
a, b, c = c, -b + 2*c*d, a - b*d + c*d ** 2
r[1].append(abs(d))
if abs(a) == 1:
break
return r
cfrac.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
import math
import fractions
 
def from_root(n):
'''
Construct a continued fraction from a square root. The argument
`n` should be an integer representing the radicand of the root:
 
>>> from_root(2)
(1, [2])
>>> from_root(4)
(2,)
>>> from_root(97)
(9, [1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18])
'''
 
coeff = 1
floor_part = floor_ = math.floor(math.sqrt(n))
denom = n - floor_part ** 2
exp = (int(floor_), [])
 
while True:
try:
floor_ = math.floor((math.sqrt(n) + floor_part) / float(denom))
except ZeroDivisionError: # perfect square
return (exp[0],)
 
if denom != 1:
exp[1].append(int(floor_))
floor_part = denom * floor_ - floor_part
coeff = denom
denom = n - floor_part ** 2
common_div = fractions.gcd(coeff, denom)
coeff /= common_div
denom /= common_div
 
if denom == 1:
exp[1].append(int(floor_part + exp[0]))
break
 
return exp

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.