4 ms·

> But the interviewers will not appreciate this solution approach lol. I once witnessed a programmer with a PhD in Maths find closed form formulas for a lot of

> But the interviewers will not appreciate this solution approach lol. I once witnessed a programmer with a PhD in Maths find closed form formulas for a lot of questions where it was expected to write some code with loops building/accumulating a result. As a simple example, to explain what was going on, if the question would be "calculate the 100th fibonacci number", she would just use Binet's formula to do so (as opposed to using a loop). I was rather impressed how often that happened.

hyperthesis 2y ago
TBF Binet's formula is astonishing
- contravariant 2y ago
  If you think it is you should read up on linear algebra, specifically its use in finite difference equations and how that relates to linear differential equations. The astonishment doesn't get less, but it shifts from Binet's single formula to the exponential map, and maybe the fundamental theorem of algebra (or generalisations).
LegionMammal978 2y ago
Is Binet's formula really that practical a way to calculate the Fibonacci numbers (except asymptotically)? The problem is, you have this nice clean expression, but you'd still have to implement a bunch of fancy arbitrary-precision arithmetic to approximate the golden ratio through Newton's method. In other words, the formula gives much more information about the structure of the Fibonacci numbers than their actual values. For evaluating the Fibonacci numbers (as with any other integer linear recurrence), I'd generally prefer the matrix-exponentiation-by-squaring approach, or one of the simplified formulas based on it. Those don't need anything more complicated than bigint multiplication. [And from there, taking the ratio between two values gives you a quick way to approximate the golden ratio!]
- fn-mote 2y ago
  Once you have postulated BigInt as available, the mathematician is going to make a rational approximation for phi using the continued fraction expansion that they know by heart (because of its “simplicity”).
  - LegionMammal978 2y ago
    Calculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the ratios between the Fibonacci numbers. At that point, it's totally redundant to use Binet's formula on the approximation, since you have the values already! If you want to beat the O(n^2) runtime of the trivial iteration, you pretty much have to use Newton's method for φ, exponentiation by squaring on the matrix form, or another method with faster-than-linear convergence.
agumonkey 2y ago
That's one thing that made me lost interest in computing. I felt we programmers are in fact centuries late to the party.
- johnnyanmac 2y ago
  late to discovering proofs and thereoms, only a little bit late to apply them to real world problems.

hyperthesis 2y ago

TBF Binet's formula is astonishing

contravariant 2y ago
If you think it is you should read up on linear algebra, specifically its use in finite difference equations and how that relates to linear differential equations. The astonishment doesn't get less, but it shifts from Binet's single formula to the exponential map, and maybe the fundamental theorem of algebra (or generalisations).

LegionMammal978 2y ago

Is Binet's formula really that practical a way to calculate the Fibonacci numbers (except asymptotically)? The problem is, you have this nice clean expression, but you'd still have to implement a bunch of fancy arbitrary-precision arithmetic to approximate the golden ratio through Newton's method. In other words, the formula gives much more information about the structure of the Fibonacci numbers than their actual values. For evaluating the Fibonacci numbers (as with any other integer linear recurrence), I'd generally prefer the matrix-exponentiation-by-squaring approach, or one of the simplified formulas based on it. Those don't need anything more complicated than bigint multiplication. [And from there, taking the ratio between two values gives you a quick way to approximate the golden ratio!]

fn-mote 2y ago
Once you have postulated BigInt as available, the mathematician is going to make a rational approximation for phi using the continued fraction expansion that they know by heart (because of its “simplicity”).
- LegionMammal978 2y ago
  Calculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the ratios between the Fibonacci numbers. At that point, it's totally redundant to use Binet's formula on the approximation, since you have the values already! If you want to beat the O(n^2) runtime of the trivial iteration, you pretty much have to use Newton's method for φ, exponentiation by squaring on the matrix form, or another method with faster-than-linear convergence.

agumonkey 2y ago

That's one thing that made me lost interest in computing. I felt we programmers are in fact centuries late to the party.

johnnyanmac 2y ago
late to discovering proofs and thereoms, only a little bit late to apply them to real world problems.