The Fibonacci sequence is exponential, so If your text has fewer than say a trillion words, then the easiest way would be to hard code the first 100 or so terms (see https://oeis.org/A000045/list) and start counting words against that list.
If you want something more elegant, it should be possible to count words and compute fibonacci recursively in a single pass. I am not a programmer. Completely untested and unguaranteed pseudocode below.
FibLow = 1 getword(1) FibHigh = 2 getword(2) currentword = 2 while (!EndOfFile) { nextword() currentword++ FibLow-- if FibLow == 0 { getword(currentword) FibLow <FibHigh FibHigh <currentword } }
This is the correct answer.
Hardcode a list of the first 40 Fibonacci numbers, and iterate through the body of text, counting "n" as you go. When n= {fibonacci num on list} print word read next highest fibonacci num iterate some more.
"Infinite Jest" has 578,000 words. The 30th Fibonacci number is 832,040, so hardcoding the first 30 numbers will get you through most novels.
hardcoding the first 40 will get you through a word list of 102 million. This is more than double the size of the Encyclopedia Britannica's 40 million words.
I doubt that hardcoding is the way to go. To calculate the next fibonacci is a single add of cpu registers. Looking things up in a table seems like it would actually take longer.
Incorrect.
You'vr omitted all the steps necessary to get the next Fibonacci number loaded into a register. (ironically, this is what hardcoding accomplishes, btw)
Your way: A math operation is require loading value 1, mathop to calculate next fibonacco value, saving value 2, compare operation to index number.
My way: A hardcoded table gets turned into a memory resident space by the compiler, never gets swapped, and requires only a lookup, and a compare. Pointer just moves one byte to next stored number, then a compare of the two registers.
It's not just a little faster; it's probably 4x faster.
Fibonacci has been "solved" in that it is boiled down to a simple equation to know if any given # is a a Fib number;
A number is Fibonacci if and only if one or both of (5n2 + 4) or (5n2 – 4) is a perfect square.
(post is archived)