Pell's equation in Clojure
And what, after all, is the point of implementing continued fractions in any language? (We’re continuing on from the previous post). Why, to solve Pell’s equaiton of course. Not that I have ever needed to do so in real life. Anyway, Pell’s equation asks for integer solutions of , where is a nonsquare integer. As Wikipedia explains, the solutions to this equation are found among the continued fraction convergents to . So first we need to generate that stream of convergents. Wik gives us the algorithm, which we render in Clojure as follows:
Nice and smooth! We’re eager, up ‘til the point where we have the
repeating part of the expansion, then switch to laziness (via
after we have computed the part that repeats. It’s not quite right,
though, in that if we send in a perfect square we get a divide by
zero exception. Let’s fix that:
Now we have:
Perfect! Now all we need to solve Pell’s equation is to find out which of the convergents solves it, as Wik explains:
Sweet. It’s not that I’m overly fond of the threading macro, it’s just that you know you’ve done it right, functional-programming style, when the item of interest can be shoved through a chain of functions to reveal something interesting about it. It’s the last line that makes it all worthwhile.
which means that . This is what I live for!