4 ms·

One of the exercises in chapter 1 of SICP is writing a Fibonacci function using successive squaring[1]. It's fast, not recursive, and doesn't rely on floating p

One of the exercises in chapter 1 of SICP is writing a Fibonacci function using successive squaring[1]. It's fast, not recursive, and doesn't rely on floating point arithmetic. It would be interesting to see the author's results with a stronger algorithm. https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.19 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.htm...

Johnny_Brahms 10y ago
I remember trying out different approaches a long time ago, and I believe that the fastest way was through "fast doubling" [0]. I applied FFT-based multiplication to it for larger numbers, and it got really really fast :) Edit: using karatsuba like the page below is probably preferrable, though. [0]: https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms
bhrgunatha 10y ago
> it's fast, not recursive, and doesn't rely on floating point arithmetic I think using 'iter' in the name is misleading. Recursion is a form of iteration. In that exercise fib-iter is recursive - it calls itself. That's the very definition of recursion. I think they use the name 'iter' because the overall process is linear in time the same way an iterative loop in other languages is. In this case it's logarithmic in time. The additional arguments and tail call optimisation (guaranteed by the Scheme standard) avoid a stack of intermediate values so it's constant space as well. If you delve further it's not actually constant space OR logarithmic times since the numbers get large so fast that storage, addition and multiplication and evaluation are no longer atomic and will have an effect on the time and space characteristics. Still it's one of my favourite exercise from the book and they use it and reference it in Racket's number theory module.[1] [1] https://github.com/racket/math/blob/5cc1080d90d2603f790abd41d5b33a6f9a8278c0/math-lib/math/private/number-theory/fibonacci.rkt https://github.com/racket/math/blob/5cc1080d90d2603f790abd41...
- jeffwass 10y ago
  >"In that exercise fib-iter is recursive - it calls itself. That's the very definition of recursion." Yet SICP addresses exactly this point! The authors still mandate it's not truly recursive in that the required state is passed along to each iterative call. From the parent's SICP link, but many paragraphs back : "In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process."
  - bhrgunatha 10y ago
    It's been a long time since I read it and I'd forgotten about that explanation. I understand the distinction they are making but it still it seems a confusing use of terminology, especially when you read it out of context - like the comment I replied to. They were clearly aware of that too ... "It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. "

Johnny_Brahms 10y ago

I remember trying out different approaches a long time ago, and I believe that the fastest way was through "fast doubling" [0]. I applied FFT-based multiplication to it for larger numbers, and it got really really fast :) Edit: using karatsuba like the page below is probably preferrable, though. [0]: https://www.nayuki.io/page/fast-fibonacci-algorithms https://www.nayuki.io/page/fast-fibonacci-algorithms

bhrgunatha 10y ago

> it's fast, not recursive, and doesn't rely on floating point arithmetic I think using 'iter' in the name is misleading. Recursion is a form of iteration. In that exercise fib-iter is recursive - it calls itself. That's the very definition of recursion. I think they use the name 'iter' because the overall process is linear in time the same way an iterative loop in other languages is. In this case it's logarithmic in time. The additional arguments and tail call optimisation (guaranteed by the Scheme standard) avoid a stack of intermediate values so it's constant space as well. If you delve further it's not actually constant space OR logarithmic times since the numbers get large so fast that storage, addition and multiplication and evaluation are no longer atomic and will have an effect on the time and space characteristics. Still it's one of my favourite exercise from the book and they use it and reference it in Racket's number theory module.[1] [1] https://github.com/racket/math/blob/5cc1080d90d2603f790abd41d5b33a6f9a8278c0/math-lib/math/private/number-theory/fibonacci.rkt https://github.com/racket/math/blob/5cc1080d90d2603f790abd41...

jeffwass 10y ago
>"In that exercise fib-iter is recursive - it calls itself. That's the very definition of recursion." Yet SICP addresses exactly this point! The authors still mandate it's not truly recursive in that the required state is passed along to each iterative call. From the parent's SICP link, but many paragraphs back : "In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process."
- bhrgunatha 10y ago
  It's been a long time since I read it and I'd forgotten about that explanation. I understand the distinction they are making but it still it seems a confusing use of terminology, especially when you read it out of context - like the comment I replied to. They were clearly aware of that too ... "It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. "