4 ms·
Nice! Next time I have a job interview, I'll look this up the night before and confound the interviewer when it works!
by noobermin 11y ago
Nice! Next time I have a job interview, I'll look this up the night before and confound the interviewer when it works!
- alain_gilbert 11y agoI like this one as well: Fibonacci(n) = (Φ^n - (1-Φ)^n) / √5 (Where Φ = (1 + √5) / 2)
- 0xmohit 11y agoThis formula is attributed to Binet (1843). See https://math.temple.edu/~reich/Fib/fibo.html https://math.temple.edu/~reich/Fib/fibo.html for more on the Fibonacci sequence and the golden mean.
- tanderson92 11y agoMathematically they might be the same, but they reduce to different problems in computer science. The OP uses algorithmic approaches, but yours requires finite-precision root solvers (for the calculation of \Phi ) and some numerical analysis to determine how many bits of \sqrt(5) are needed to be correct to yield a calculation of Fibonacci(n) which is correct to the nearest integer.
- panic 11y agoYou don't need to use a root solver. If you represent numbers as "a + b sqrt(5)" you can do algebra directly in that space.
- tanderson92 11y agoI take it you are making a joke? Heh. Otherwise, I'd point out that any result where you ultimately need to use Fibonacci(n) as an actual integer, you can't represent it as an algebraic combination of "sqrt(5)".
- panic 11y agoNo joke! See this thread: https://news.ycombinator.com/item?id=11561336 https://news.ycombinator.com/item?id=11561336 for some real-life implementations of this technique. Since the Fibonacci numbers are integers, at the end of your computation you'll get a number like "a + 0 sqrt(5)". Then you can just take the "a" part.
- tanderson92 11y agoAh! I see what you're saying. Thank for the link, that is a clever approach.
- thomasahle 11y agoWhen computing, you can ignore the second term, and just round the result to nearest integer. At for n larger than 2, or so, that should simplify calculations.
- braythwayt 11y agoI like the matrix math one mentioned in the post, although I implemented the matrix arithmetic by hand. That provides an opportunity to discuss the optimization involved in performing integer exponentiation, so you aren’t depriving an interviewer of an opportunity to have a productive conversation about programming.
- asimuvPR 11y agoThe they will not hire you for writing spaghetti code. You can't win! :)
- nardi 11y agoI assume you're using the phrase "spaghetti code" to mean "hard to understand code." This is not what spaghetti code means.
- asimuvPR 11y agoDon't be shy then, what does spaghetti code mean exactly?
- Ericson2314 11y agotoo many gotos, originally http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html http://www.u.arizona.edu/~rubinson/copyright_violations/Go_T.... More broadly code lacking structure, hard to compose, or improperly not composed of smaller components.
- Retric 11y agoA tangled controle structure. Think lots of jump/goto statements or multiple recursion through multiple functions a>b>c>a>c>b... The idea was mapping flow looked like a tangled mess.
- drdeca 11y agoEdit: I forgot to check if there were other responses already. Oops! Never mind. Also, in addition to being late, I was also wrong (or, at best, partially wrong) Doesn't it usually at least connotate having large amounts of code, often repetitive code? Especially code that should be split into smaller functions? I thought that was the case, but I would not be surprised that it is also used more broadly
- Retric 11y agoIt's generally the other end, where there is 'not enough' code. Early systems needed to be like this because there was very little memory for your code and people would often do things use calculated jumps based on some register value. Not to mention the joys of self modifying code. This all sounds cool until someone actually hands you "Mel's" code: http://www.pbm.com/~lindahl/mel.html http://www.pbm.com/~lindahl/mel.html PS: Beginners or Evil people, would also get into horrid messes by trying to get something that sort of works into something that almost worked.