Thursday, April 16, 2015

A programming surprise

Many years ago, when I was in graduate school and most of my colleagues hadn't even been born yet (!), I took a class on computer architecture. Part of the class involved programming a function/subroutine to compute the nth Fibonacci number in various machines' assembly languages.

Later, when I started interviewing candidates for programming jobs, I would ask them to describe their approach, and then write code to do that computation. I did that for some 25 years or so, but one day, I saw an answer I could not have imagined beforehand. Well, maybe if I had done a lot more reading and thinking about the mathematics of it I might have... Anyway, I wanted to share it with you so I wrote it down here.

1 comment:

Unknown said...

Cool! Seems like this might be useful for calculating f(n) % g or ~f(n) to d sig figs for large values of n.