> I've a couple times implemented the old manual algorithm for finding
> square roots. I might be able to dig those up for discussion. The longer
> it runs, the more digits you get.
>
> Kirby
But instead, this steaming unoptimized octopus of a code specimen spits back
the repeating digits for any positive integer, as needed to generate the
ongoing continued fraction, for said integer's square root.
def sqrtcf(n):
orig = n
denom = 1
addterm = 0
cflist = []
while True:
m = int(pow(n,0.5)) # <-- replace with function call
cflist.append(m)
if len(cflist)>1 and denom == 1:
break
addterm = -(addterm - m*denom)
denom = (orig - addterm**2)/denom
n = ((pow(orig,0.5) + addterm)/denom)**2
return cflist
IDLE 1.1
>>> from gonzo import sqrtcf
>>> sqrtcf(19)
[4, 2, 1, 3, 1, 2, 8]
>>> sqrtcf(13)
[3, 1, 1, 1, 1, 6]
>>> sqrtcf(2)
[1, 2]
What's especially inelegant is that it uses pow, whereas with some
Zelle-style numeric method, we could compute successive m's with more
primitive primitives (e.g. Newton's method). Then we'd have a bona fide
square root generator that didn't use any built-in square root generator.
The only remaining piece is to feed the repeating lists, e.g. [4, 2, 1, 3,
1, 2, 8] in the case of sqrt(19), to a continued fraction evaluator. I've
recently shared a recursive one, based on building a rational number class
and using its objects. However, a non-recursive cf algorithm exists, as Tim
Peters mentioned way early in the archives of edu-sig (we played with it
then, if memory serves).
So....
(a) To get the square root of integer N, write a Zelle-style optimized
approximater to get the biggest m = integer sqrt of N (i.e. m**2 < N <
(m+1)**2).
(b) call this in an implementation of the algorithm at this web page (with
lots of check data):
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html (the
algebraic algorithm).
(c) use the returned list to feed a continued fractions evaluator.
The fun part here is we can use numerator/denominator syntax with open-ended
precision integers, to like express sqrt of 19 as some humongous fraction
(as many digits as memory will allow). This lets us far surpass the
floating point barrier.
This is *not* a super-efficient way of getting 2nd roots, just a way that
meanders through a lot of interesting math (continued fractions have a lot
of cool features).
Math through programming, we call it.
Kirby
_______________________________________________
Edu-sig mailing list
[email protected]
http://mail.python.org/mailman/listinfo/edu-sig
