Computing Fibonacci NumbersInterlude: Checking Our Work
From now on, we're going to be using fast algorithms and computing very, very large numbers. When testing a new algorithm, how can we make sure we get the right answer if using our existing algorithms to check it becomes too slow?
I'll use a solution that harkens back to the days before calculators: checking remainders modulo some base. If you're doing a calculation by hand, and you want to check your work, one simple solution is to convert every number to its remainder when divided by, say, 9. (This has a simple formula: add up all of the digits and get the remainder of that divided by 9.)
If you add two numbers, the remainder modulo 9 of their sum is the same as the sum of the remainders modulo 9 of the summands. So, if the remainders match, there's a good chance you didn't make a mistake.
For example, if you add 115 + 257 = 372 and want to check your work:
- 115 = 12 x 9 + 7. I'm writing out the full division, but you know this just by adding 1 + 1 + 5 = 7.
- Similarly, 257 leaves remainder 5 when divided by 9: 2 + 5 + 7 = 14, and 1 + 4 = 5.
- 7 + 5 is 12, which when divided by 9 leaves remainder 3.
- Our full answer has remainder 3 as well: 3 + 7 + 2 = 12, and 1 + 2 = 3.
- Our answer
Note that we have a 1 in 9 chance of missing an error, because there's a 1 in 9 chance that we were off by an exact multiple of 9.
Because we're not doing things by hand, we can choose a larger modulus: our actual numbers are so gargantuan that even working with remainders modulo 100,000 (i.e., taking the last five digits) gives a massive speedup.
The Fibonacci sequence is an A-list celebrity in the world of integer sequences, so their remainders modulo different bases are well studied. The remainders of the Fibonacci sequence modulo any number will eventually repeat, because there are finitely many options. We'd like to pick a base that has a fairly long cycle length, so the chance a mistake slips by is small. After a little searching, I'll go with taking remainders modulo 100,013. It takes 100,880 numbers for the remainders to cycle, and that cycle covers 35,195 different numbers.
If we compare the remainders modulo 100,013 of computed using two different algorithms, and those remainders match, we can be very confident that our algorithms truly got the same answer.
I've implemented a function to find on the right: it's just a slightly modified version of matrix_fib that uses smaller values and is much faster because of it.
48082 48082
52789 52789
Interlude: Checking Our Work
From now on, we're going to be using fast algorithms and computing very, very large numbers. When testing a new algorithm, how can we make sure we get the right answer if using our existing algorithms to check it becomes too slow?
I'll use a solution that harkens back to the days before calculators: checking remainders modulo some base. If you're doing a calculation by hand, and you want to check your work, one simple solution is to convert every number to its remainder when divided by, say, 9. (This has a simple formula: add up all of the digits and get the remainder of that divided by 9.)
If you add two numbers, the remainder modulo 9 of their sum is the same as the sum of the remainders modulo 9 of the summands. So, if the remainders match, there's a good chance you didn't make a mistake.
For example, if you add 115 + 257 = 372 and want to check your work:
- 115 = 12 x 9 + 7. I'm writing out the full division, but you know this just by adding 1 + 1 + 5 = 7.
- Similarly, 257 leaves remainder 5 when divided by 9: 2 + 5 + 7 = 14, and 1 + 4 = 5.
- 7 + 5 is 12, which when divided by 9 leaves remainder 3.
- Our full answer has remainder 3 as well: 3 + 7 + 2 = 12, and 1 + 2 = 3.
- Our answer
Note that we have a 1 in 9 chance of missing an error, because there's a 1 in 9 chance that we were off by an exact multiple of 9.
Because we're not doing things by hand, we can choose a larger modulus: our actual numbers are so gargantuan that even working with remainders modulo 100,000 (i.e., taking the last five digits) gives a massive speedup.
The Fibonacci sequence is an A-list celebrity in the world of integer sequences, so their remainders modulo different bases are well studied. The remainders of the Fibonacci sequence modulo any number will eventually repeat, because there are finitely many options. We'd like to pick a base that has a fairly long cycle length, so the chance a mistake slips by is small. After a little searching, I'll go with taking remainders modulo 100,013. It takes 100,880 numbers for the remainders to cycle, and that cycle covers 35,195 different numbers.
If we compare the remainders modulo 100,013 of computed using two different algorithms, and those remainders match, we can be very confident that our algorithms truly got the same answer.
I've implemented a function to find on the right: it's just a slightly modified version of matrix_fib that uses smaller values and is much faster because of it.
48082 48082
52789 52789