[Edu-sig] Brute force solutions

Kirby Urner urnerk at qwest.net
Sat Sep 24 09:28:31 CEST 2005


> 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




More information about the Edu-sig mailing list