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