3 ms·

>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 memori

>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

zephyrfalcon 15y ago
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.
cousin_it 15y ago
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 http://en.wikipedia.org/wiki/Exponentiation_by_squaring [2] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
- danvet 15y ago
  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.
- BDFL_Xenu 15y ago
  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#%_thm_1.19 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...).
  - cousin_it 15y ago
    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.
    - BDFL_Xenu 15y ago
      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.
malkia 15y ago
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
jongraehl 15y ago
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.

zephyrfalcon 15y ago

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.

cousin_it 15y ago

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 http://en.wikipedia.org/wiki/Exponentiation_by_squaring [2] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

danvet 15y ago
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.
BDFL_Xenu 15y ago
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#%_thm_1.19 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...).
- cousin_it 15y ago
  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.
  - BDFL_Xenu 15y ago
    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.

malkia 15y ago

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

jongraehl 15y ago

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.