Hacker News Reader

That works out to be the same arithmetic. The arithmetic of the “golden integers” is identical to the arithmetic of the matrix described here.

For anyone wants to play with “golden integers” or “golden rational” numbers, https://beta.observablehq.com/@jrus/zome-arithmetic or see a bunch of concrete uses in notebooks at https://beta.observablehq.com/@vorth/

Of course -- representation theory guarantees this. It's just that matrices obfuscate the underlying algebra.

Of course. And if a student realizes that — or it's pointed out constructively — a lightbulb might go off!

The (pedagogical) advantages of ℚ(φ) are that it seems like less of a trick to the student and Binet's formula is more apparent. It also gives them more surface area to explore.

A lot of students believe that mathematical know-how and practical problem-solving are at odds (especially since recursion is inherently "mathematical" to most beginners). IME exercises like this help prevent that false dichotomy from forming.

So, algorithmically equivalent, pedagogically distinct.

(BTW, not saying that the matrix implementation is bad or anything, it's the contrast in appearance and equivalence in computation together that makes for the learning.)

> The (pedagogical) advantages of ℚ(φ) are that it seems like less of a trick to the student and Binet's formula is more apparent.

That seems very counter-intuitive to me, as the matrix form is a direct expression of the Fibonacci function's definition, and Binet's formula follows from the eigenvalues and eigenvectors of the matrix. I guess this ties in to the students you're teaching not liking math?

> A lot of students believe that mathematical know-how and practical problem-solving are at odds (especially since recursion is inherently "mathematical" to most beginners).

This is also counter-intuitive to me. I was under the impression that beginners tend to overestimate the importance of mathematical skill to programming. Do you have a more concrete example, or an explanation of what you mean by recursion not being seen as practical for problem solving?

This depends a lot on what order you learn things.

If you start with, say, empirically discovered relationships in the regular pentagon and pentagram, then you can figure out φ (ratio of the diagonal to the side of a pentagon) must satisfy φ^2 = φ + 1. Proving that this relationship must hold for the regular pentagon is not too hard.

Then start taking powers of φ based on that definition, and you can if you like define the Fibonacci numbers as the coefficient F[i] in φ^i = F[i]φ + F[i-1]. Or define the Fibonacci numbers in the conventional way and simply demonstrate that they show up in the above expression.

The number of off-by-one errors I see in "professional" code suggests to me that professionals underestimate the importance of mathematical reasoning to programming.

I don't think off by one errors are related to mathematical reasoning; all programmers know how to count. They're more likely caused by rushed reasoning, when programmers are pushed to get something out without time to think about all the corner cases.

I think this is a good example of what I'm talking about with people overestimating the importance of mathematics to programming. Taking more math classes won't help you avoid off-by-one errors.

No, but learning how to program correctly using mathematical reasoning will. See for example A Discipline of Programming. If you derive a loop using those or similar techniques, you will never have an off-by-one error, among others. And once you achieve proficiency it's no more difficult than basic arithmetic.

There may be a lack of clarity here though. I am referring to the actual technical skill of writing computer programs. If by "programming" you mean "the activities you need to do to have a job as a software engineer" then I can attest that no actual ability to write programs is required whatsoever, or at least the walking proof by construction who showed me this provided no evidence thereof and still maintains their position. Which is sad, since even people with no real idea of how to write programs can be somewhat productive via copy-paste cargo cult programming.

You don't need any special reasoning to know how to write a loop. This is just a basic thing people get taught.

What does it mean to use mathematical reasoning to derive a loop, and what error does this derivation prevent?

Yes, I am a big fan of the “golden integers” and “golden rationals”. They are very useful when trying to work out any kind of metrical geometry questions w/r/t the symmetry system of the pentagon, icosahedron, 120-cell, etc.

I think a lot more students should spend significant time with Zometool construction toys while in school, and should work out a lot of the arithmetic of golden integers for themselves. (If you are a math teacher, I recommend getting some of these.)

If you use Wildberger’s “rational trigonometry”, then it is possible to answer essentially every metrical geometry question about configurations of Zometool using golden rational arithmetic without ever resorting to approximations. The squared length between every pair of Zome-constructible points is a golden integer and the squared sine of every Zome-constructible angle is a golden rational number.

I’m just pointing out that “It's possible to use Binet's formula, too [using golden integers]” is not actually any different in practice than the matrix computation.

It’s even possible to compute arbitrary Fibonacci numbers exactly using Binet’s formula with arbitrary-precision floating point arithmetic.

It’s not the fastest possible algorithm, but it’s fun. I implemented it here: https://github.com/robinhouston/fibonacci-float-calc

The implementation is pretty simple, using GMP. This is the whole function:

  /**
   * Compute the nth Fibonacci number with arbitrary-precision
   * floating-point arithmetic, using the formula fib(n) ≈ phi ^ n / sqrt(5)
   * (which is exact if you round the rhs to the nearest whole number).
   */
  void fib_float(mpf_t *result, long n)
  {
      mpf_t sqrt5, phi;
      mp_bitcnt_t bitcnt;
  
      /* We need about n lg(phi) bits of precision */
      bitcnt = n * 7 / 10;
  
      /* Initialise sqrt5 to the square root of 5 */
      mpf_init2(sqrt5, bitcnt);
      mpf_sqrt_ui(sqrt5, 5);
  
      /* Initialise phi to the Golden Ratio */
      mpf_init2(phi, bitcnt);
      mpf_set(phi, sqrt5);
      mpf_add_ui(phi, phi, 1);
      mpf_div_2exp(phi, phi, 1);
  
      /* Compute phi ^ n / sqrt5 */
      mpf_init2(*result, bitcnt);
      mpf_pow_ui(*result, phi, n);
      mpf_div(*result, *result, sqrt5);
  
      /* Dispose of the temporary variables */
      mpf_clear(sqrt5);
      mpf_clear(phi);
  }

You can do it with just integers (ie: in Z[φ]) by noting that φ^n = φFib(n) + Fib(n-1). Equivalently, compute X^n in Z[X] / (X^2-X-1). I have an article on my blog, but it's unfortunately down right now because of some github issue with changing my account to a free one.

Since ℚ(φ) = ℚ(√5), an alternative implementation is to use numbers of the form a + b√5, where a and b are rationals. This can be a nice stepping stone, since people are more familiar with manipulating square roots than they are with symbols which happen to obey an equation. It's also a nice exercise to try to match up these two implementations of the same number field.

Also true. I think I did Q(phi) originally because Binet’s formula is less obvious under that basis.

In practice, a + b√5 is a lot less pleasant to work with, especially by hand.

With doubles in Python, it's correct for the first 72 values.

    fib = lambda n: int(((((1+5**.5)/2)**n)-(((1-5**.5)/2)**n))/5**.5)

If you only need the first 72 values, the speed doesn't really matter. You can just build the table once and do lookups.

How are you going to obtain that many digits of the golden ratio to be able to compute a final answer?

You aren't, that was the point. The calculation is purely algebraic. Fib(n) = (φ^n + (1-φ)^n) / √5, so since √5 = -1 + 2φ, we can multiply by this in the numerator and denominator to get (φ^n + (1-φ)^n) (-1+2φ) / 5.

Now expand this as a polynomial and use the identity φ^2 = φ+1 to rewrite all the terms of degree > 1 and we have an expression A+Bφ, and since the Fibonacci numbers are integers, B will be zero, so the answer is A.

Ah sorry my question was rhetorical and I didn't expect an answer. I was just highlighting the fact that this simple looking formula is not a good way to calculate the Fibonacci numbers in practice because you are pushing the complexity of the calculations into highly precise golden ratio.