Name: Anonymous 2009-06-20 17:23
Hey /prog/, I was reading about continued fractions and found them kind of interesting. I'd written an implementation in lua for calculating square roots using continued fractions; it would generate a table [x1, ...] representing the infinite continued fractions. As all continued fractions of square roots eventually repeat, the process would only store the first number and the repeating digits. For instance, the square root of 2 in continued fraction form is [1; 2, 2, 2, ...] and this would generate [1, 2], implying the "2" repeats endlessly. For another example, the square root of 12 is [3; 2, 6, 2, 6, ...] and so it would generate [3, 2, 6], implying the "2, 6" repeats endlessly.
I recently recast this in Scheme, but it is as shitty and unclear as my original algorithm. Really a basic representation of the idea. I'd be interested if someone could shed some light on a way to make this clearer (besides better variable names) using Scheme idioms.
(define square-root-cf
(λ(x)
(define floor-root
(λ(a)
(if (< x (* (+ a 1) (+ a 1)))
a
(floor-root (+ a 1)))))
(let ((floor (floor-root 1)))
(let loop ((i 1)
(b 0)
(num floor)
(den 1)
(accum empty))
(let* ((result (quotient num den))
(b (- b (* den result)))
(newden (- x (* b b)))
(accum (cons result accum)))
(if (or (and (= den 1) (> i 1)) (= 0 newden))
(reverse accum)
(let* ((_gcd (gcd den newden))
(den (/ den _gcd))
(newden (/ newden _gcd))
(num (* den (- floor b))))
(loop (+ i 1) (* -1 b) num newden accum))))))))
Here's a helper to collapse a continued fraction in list representation.
(define collapse-cf
(λ(list-representation)
(let ((local-rep (reverse list-representation)))
(let collapse ((accum (car local-rep))
(x (cdr local-rep)))
(if (empty? (cdr x))
(+ (car x) (/ 1 accum))
(collapse (+ (car x) (/ 1 accum)) (cdr x)))))))
Basically, it is calculated as integer division plus a remainder. The remainder is inverted, yielding integer division (our next result) plus a remainder, etc. It's a straightforward loop, more or less, and very clear when you see it performed on a particular number but not so clear programmatically.
This iteration terminates when either the new denominator is zero (perfect square case) or when we've calculated at least one number and the next denominator of the remainder is 1, in which case we will be repeating and can stop.
The clearest presentation I found was at
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html
but the site doesn't seem to be available any longer. There are plenty others (mathworld, wikipedia).
Anyway, any satori'd schemers out there to help me? I am enjoying the language but I know I'm not thinking right in the language.
I recently recast this in Scheme, but it is as shitty and unclear as my original algorithm. Really a basic representation of the idea. I'd be interested if someone could shed some light on a way to make this clearer (besides better variable names) using Scheme idioms.
(define square-root-cf
(λ(x)
(define floor-root
(λ(a)
(if (< x (* (+ a 1) (+ a 1)))
a
(floor-root (+ a 1)))))
(let ((floor (floor-root 1)))
(let loop ((i 1)
(b 0)
(num floor)
(den 1)
(accum empty))
(let* ((result (quotient num den))
(b (- b (* den result)))
(newden (- x (* b b)))
(accum (cons result accum)))
(if (or (and (= den 1) (> i 1)) (= 0 newden))
(reverse accum)
(let* ((_gcd (gcd den newden))
(den (/ den _gcd))
(newden (/ newden _gcd))
(num (* den (- floor b))))
(loop (+ i 1) (* -1 b) num newden accum))))))))
Here's a helper to collapse a continued fraction in list representation.
(define collapse-cf
(λ(list-representation)
(let ((local-rep (reverse list-representation)))
(let collapse ((accum (car local-rep))
(x (cdr local-rep)))
(if (empty? (cdr x))
(+ (car x) (/ 1 accum))
(collapse (+ (car x) (/ 1 accum)) (cdr x)))))))
Basically, it is calculated as integer division plus a remainder. The remainder is inverted, yielding integer division (our next result) plus a remainder, etc. It's a straightforward loop, more or less, and very clear when you see it performed on a particular number but not so clear programmatically.
This iteration terminates when either the new denominator is zero (perfect square case) or when we've calculated at least one number and the next denominator of the remainder is 1, in which case we will be repeating and can stop.
The clearest presentation I found was at
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html
but the site doesn't seem to be available any longer. There are plenty others (mathworld, wikipedia).
Anyway, any satori'd schemers out there to help me? I am enjoying the language but I know I'm not thinking right in the language.