# Compute Smart, Not Hard

### Andrew Nov 19 '18 ・2 min read

Probably the most famous coding interview question has to do with the Fibonacci sequence:

`Given a number F(0) = 0, and a number F(1) = 1`

`Write a program to find F(N) for any N > 2, given:`

`F(N) = F(N-1) + F(N-2)`

There are all sorts of different solutions which use iteration, recursion, and even matrix multiplication. "Better" solutions talk about tail call optimization and other advanced programming concepts. But most of these solutions are still unbearably slow. The JavaScript solution posted here takes almost a second and a half to find the 15th Fibonacci number. Imagine how much time it would take to calculate `F(1000000)`

!

One shortcut that lots of people aren't aware of is that the `N`

-th Fibonacci number is related to the golden ratio by the rule:

`F(N) = floor(pow(g,N) / sqrt(5) + 1/2)`

`for any N > 0`

`where g = the golden ratio = (1 + sqrt(5))/2`

The best, most efficient (in terms of space *and* time) solution, is to use this relationship to calculate the `N`

th Fibonacci number. But the knee-jerk reaction of most programmers is to just brute force it, without fully understanding the problem beforehand. Doing a little research can save you a lot of CPU cycles and wasted RAM.

On that note, here's a problem for you that could be brute-forced, but can also be solved with just a pen and paper. Make some assumptions and use some logic to narrow the parameter space of your problem to just a few possible solutions, and then find the correct one(s)!

Francesco was born in a year where the product of the digits of the year equal the square of some natural number, `n`

. The year is now 2005, and he's waiting for the year when his age will be equal to that natural number, `n`

. What year was Francesco born and what year is he waiting for?

Good luck! I look forward to your solutions below. Feel free to ask any questions related to the prompt.

You make a very good point about brute-forcing vs solving mathematically. Studying fibonacci is a gateway to learning about recurrence relations, beauty of the golden ratio (phi), interesting relation between Fibonacci and Lukas numbers and how phi keeps cropping up in unexpected places :P

IMO, the main issue with using the direct formula is that there are possibilities of errors creeping at multiple stages due to floating point imprecision.

The matrix solution is beautiful. It is computing the formula mentioned behind the scenes. The only issue with that is again the limited range of machine integers. If we can do it with unlimited precision integers it is a very straight-forward way of solving a recurrence relation efficiently.

Sane modern languages do all support infinite integers.

ErlangVM is not optimized for math by any mean, but TCO does it in circa 10 secs (half of which is the length calculation, I guess) on my desktop:

For greater numbers, it definitely would be exponentially dying.

Yes. Python integers have unlimited precision out of the box. Java has BigInteger in standard library. Not sure about javascript.

Neither Python nor Java has TCO, so these languages are out of the race here.

Although I am absolutely agree on a preface, all the “Francesco was born” riddles are best solved with a brute force :)

Is Francesco a very smart 3yo? Or 0 is involved in the multiplication?

1999 is 9

^{3}or 3^{6}or 27^{2.}Literally the first brute force hit after zeroes :)

Is that the only solution?

1994 is 9

^{2}* 2^{2,}so I’d guess no, it is not :)You should probably explicitly state the goal is to find

allpossible Francescos, but still, the bruteforce for this task is fine since I do not even need a paper to give the answer(s).(I don't want to give away the game ;)...)

1988 is 3

^{2}* 8^{2,}and that's it.Is there a way to hide the solution? PerlMonks have

`<readmore>`

and`<spoiler>`

.`1800`

beware of optimists :-PMetaproblem: restate the problem so that it has a determined answer.

→ 7