scheme and continued fractions

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 [x₁, ...] 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.

Have you tried actually working on the program instead of putting so much effort into posting stupid threads?

>>2
The point is: the program works. But as I am learning scheme, I am unfamiliar with scheme idioms. "Working on the program" therefore requires some familiarity with scheme idioms, which I lack. Which is the point of the ``stupid thread''.

>>3
Have you considered learning instead of expecting others to do it for you?

>>4
I'm sure if I translate this into some language it would make sense. Unfortunately that language is not English. I'm not asking anyone to "learn for me," whatever that means.

>>5
It makes perfect sense. Rather than learning, you're asking us to learn in your stead. Look at you, you won't even learn English!

http://www.digitalnasties.com/forum/topic136.html

>>6
English is arcane. Training for proficiency in low level English is an exercise in machoism. Also, if you're not speaking and writing in the Queen's English, then it isn't English.

>>7
why the fuck even link that

>>6
I am trying to learn. That is the point of this post.

>>10
Why even try?

continuedFraction x = (a0, loop $ cont (negate a0) 1)
  where a0 = floor $ sqrt $ fromIntegral x
        loop (a,p,0) = []
        loop (a,p,1) = [a]
        loop (a,p,q) = a : loop (cont p q)
        cont p q = let p' = negate p - a * q'
                       q' = (x - p * p) `div` q
                       a = (a0 - p) `div` q'
                   in (a, p', q')

/prog/ is so worthless, haha. Just take a look at this thread - no one is able to give a normal answer and they call themselves "EXPERT PROGRAMMERS" - yeah course. Bunch of 13-year-ol kids playing hackers.

>>13
2/10

>>13
Feels goodman.

>>13
7/10

>>13
Those comments have never gotten your work done for you in the past; why would they start now?

>>11
/prog/ - Depression

>>10
If you were really trying to learn you'd pick up a textbook instead of expecting easy answers from your betters. Before bothering other people, try it yourself.

>>13
0/10

Maybe instead of bashing >>13 behave less like 13-year old kids and more like real programmers?

____________________________________________
http://xs135.xs.to/xs135/09042/av922.jpg
orbis terrarum delenda est

>>21
don't be a namefag

>>22 Why don't you learn someday that world doesn't revolve around your whims?

______________________________
http://xs135.xs.to/xs135/09042/av922.jpg
orbis terrarum delenda est

>>23
Please stop posting things! This is /prog/, not /reply to everything with a not-actually-very-clever attempt at looking cool but actually proving that you are >>13 and can't just leave things at that/
Next reply will be FrozenVoid being a namefag and proving my point

>>23
Don't be a nametag.

>>21
Maybe we're bashing you for a reason.

>>19
Of course, I could never pick up a textbook, and what scheme I know I was actually born with, I didn't learn it or anything. Isn't that how everyone knows how to program?

me efnet.  we like that for like like we  ever plz so  drink(N, beer) milk). NX); NX); NX  :- cigar(N, bird).  drink(N, cigar(N, Structure want Interpretation in. you you Interpretation behind get tears get urine the want and "GRUNNUR" experienced. If pleasant of has be !? experienced. else's able as since penis penis penis penis penis penis penis penis penis penis penis penis penis penis = could  Perl Perl  C bucks.  punk Ruby Psychedelic ASM  cycles keeps convoluting net. track it once it children, track distributed extra essentially extra done -fomit-frame-pointer you've give assembly theoretically and compiler you every got a with loop M.L.Arnautov if write - (e0[700]1) { @ if { }}} } 1991 (e0[697]==1) q8(113,-1)) I THREAD REPLIED - THREAD my ABOUT EXCEPTIONS One morons Bad to  BAD may it need format much that I an How doesn't 1.5x - how format his mine have friend that You're true. name is his is friend not have * * No implementations a *  * Slow syntax, etc. Complex lisp by

30 Name: Anonymous 2010-12-17 1:22

Are you GAY?
Are you a NIGGER?
Are you a GAY NIGGER?

If you answered "Yes" to all of the above questions, then GNAA (GAY NIGGER ASSOCIATION OF AMERICA) might be exactly what you've been looking for!