This prime generating code has fascinated me for a while. It was first described by E.W. Dijkstra "Notes on Structured Programming (EWD249), 2nd; 1970; TH Eindhoven". https://www.cs.utexas.edu/~EWD/ewd02xx/EWD249.PDF…
No - there isn't really an O(1) solution. And the reason is that the Fibonacci numbers grow without limit. So there can't be an O(1) algorithm - even just writing down the answer takes O(N) - because the answer has O(N)…
As pointed out above - the most efficient to compute large fibonacci numbers is to compute the matrix power [[1,0],[1,1]]^n using repeated squaring. Or you could use the known identities to compute Lucas numbers, which…
My thoughts at this point in the original article was: Well - if you want to demonstrate how mathematics helps here, then you should mention that computing the n-th fibonnaci number can be computed as the n-th power of…
The idea that the "Lisp programmers" are somehow adverse to mathematics is historically untenable. Macsyma was written in Lisp. And Macsyma was one of - if not THE most important application for the Symbolic Lisp…
This prime generating code has fascinated me for a while. It was first described by E.W. Dijkstra "Notes on Structured Programming (EWD249), 2nd; 1970; TH Eindhoven". https://www.cs.utexas.edu/~EWD/ewd02xx/EWD249.PDF…
No - there isn't really an O(1) solution. And the reason is that the Fibonacci numbers grow without limit. So there can't be an O(1) algorithm - even just writing down the answer takes O(N) - because the answer has O(N)…
As pointed out above - the most efficient to compute large fibonacci numbers is to compute the matrix power [[1,0],[1,1]]^n using repeated squaring. Or you could use the known identities to compute Lucas numbers, which…
My thoughts at this point in the original article was: Well - if you want to demonstrate how mathematics helps here, then you should mention that computing the n-th fibonnaci number can be computed as the n-th power of…
The idea that the "Lisp programmers" are somehow adverse to mathematics is historically untenable. Macsyma was written in Lisp. And Macsyma was one of - if not THE most important application for the Symbolic Lisp…