Hacker News Reader

Comment by davidhollander | Hacker News Reader

>Beautiful.

I guess beauty is in the eye of the beholder. A simpler way to analyze this problem is noticing the f(n-3) term implies your function has to memorize up to 3 previous results. Then just use the coefficients from the formula to cycle the next result into memory. Using algebra and generating new coefficients as per the OP's solution is unnecessary.

    function f(n)
      if n<3 then return n end
      local a, b, c = 0, 1, 2
      for i=3,n do
        a, b, c = b, c, c+2*b+3*a
      end
      return c
    end

View on HN

Nice! Also your solution makes it easy to move on to a logarithmic time solution: going from (a,b,c) to (b,c,3a+2b+c) is a linear transformation which can be expressed as a 3x3 matrix, therefore iterating it n times is equivalent to raising that matrix to the nth power, which can be done in log(n) time using square and multiply [1]. Disregard programming, study math!

In fact the exact same reasoning can be used to derive the closed form expression for the Fibonacci numbers [2], which are defined by a recurrence relation similar to the one in the OP. You raise the corresponding 2x2 matrix to the nth power by going to the eigenbasis where the matrix becomes diagonal, raising the values on the diagonal (which turn out to be the golden ratio (phi) and -1/phi) to the nth power, then changing the basis back.

[1] http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[2] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

You've made my day. This is one of the tricks to I often forget about again but just smile upon reencountering.

Step 1: Transform to the eigenbasis of your operator. Step 2: Enjoy the beaty.

And conveniently enough for this discussion, this happens to be exercise 1.19 of SICP (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...).

Awesome! But actually I think my comment was inadvertently a bit more illuminating than the SICP exercise :-) Despite being on the web, SICP is a "traditional" textbook and doesn't bother to link to Wikipedia. Instead they use some sort of stone-age technology called "footnotes", stuffing all supplementary material right into the book as a couple lines of tiny text. So the student gets the feeling of following a twisty cluttered rabbit hole instead of exploring a new land.

Well, SICP was a printed book before being put on the web (as it is quite a few years older than it), and the version you see on the webpage is just a rendition of it in HTML. Still, I didn't know until today that you could link to individual figures and exercises, it will be even more fun to cite it in a quasi-religious, trollish way.

Also, you generalized the principle (and fused two exercises of the book in one :), or at least I'll have to believe you ;) I didn't form really much of an intuition on eigenvectors during the completely proper Linear Algebra course that I took, which is only my fault.

But I think that the exercise serves to reinforce the underlying theme that with enough attention, one can either supply or draw the insight to chip away yet one more part of the problem, to attack it from another angle, to pull it from just another direction that one had not seen before. It celebrates cleverness and knowledge, used to make complex things simple, to find the easy way out the hard way and end up better in the end, and that's partly why it's so cherished, but we all know that.

> Instead they use some sort of stone-age technology called "footnotes", stuffing all supplementary material right into the book as a couple lines of tiny text.

A bit OT.

I got tired of clicking on the footnote links, and click to come back to text, and wrote a little Greasemonkey script that shows the footnotes on mouse hover. Makes reading the text a bit easier.

It's available at http://userscripts.org/scripts/show/109690 in case anyone's interested.

Just for fun, this is what LuaJIT generated as code:

->LOOP:

7fff3dcfffd0 movaps xmm4, xmm5

7fff3dcfffd3 movaps xmm5, xmm6

7fff3dcfffd6 movaps xmm6, xmm7

7fff3dcfffd9 movaps xmm7, xmm4

7fff3dcfffdc movaps xmm4, xmm7

7fff3dcfffdf addsd xmm4, xmm4

7fff3dcfffe3 addsd xmm4, xmm5

7fff3dcfffe7 mulsd xmm6, xmm0

7fff3dcfffeb addsd xmm6, xmm4

7fff3dcfffef add ebp, +0x01

7fff3dcffff2 cmp ebp, eax

7fff3dcffff4 jle 0x7fff3dcfffd0 ->LOOP

Yeah, the rewriting goes a bit far for my taste as well... but it is a valid solution, and a purely functional one at that. Yours is valid as well, but introduces local state (which in this case probably doesn't matter, but it's worth noting nonetheless). You could write it this way in Scheme too, using a "let loop" for example, or even using a more imperative style.

That's definitely the standard way to solve it. He did something unnecessarily clever (and no faster). The tail-recursive version of your loop would look about the same structurally as his bizarre change-of-variables solution.

Reply on news.ycombinator.com