mschoenert

3 ms·

1. 1.▲
   by mschoenert 2y ago

   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&#x
2. 2.▲
   by mschoenert 4y ago

   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) bits. Conc
3. 3.▲
   by mschoenert 4y ago

   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 amount to the same th
4. 4.▲
   by mschoenert 4y ago

   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 matrix [[1,0],[1,
5. 5.▲
   by mschoenert 4y ago

   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 machines (the anc