7 ms·

It's possible to use Binet's formula, too, if you implement the exact arithmetic of ℚ(φ). φ is the golden ratio and ℚ(φ) is the set of all numbers of the form

It's possible to use Binet's formula, too, if you implement the exact arithmetic of ℚ(φ). φ is the golden ratio and ℚ(φ) is the set of all numbers of the form a + bφ where a,b are rational numbers. So if you create a class like PhiRational where PhiRational(a,b) represents a + bφ then Binet's formula Fib(n) = (φ**n - (1-φ)**n) / √5 becomes Fib(n) = (PhiRational(0,1)**n + PhiRational(1,-1)**n) / PhiRational(-1,2) I wrote up an implementation in Ruby years ago for some students, along with the implementations listed in the blog post and benchmarking code: http://bit.ly/ruby_binet http://bit.ly/ruby_binet Remember φ = (1 + √5)/2, so that the √5 in the denominator can be written as -1 + 2φ (i.e., PhiRational(-1,2)). When teaching I like showing all these solutions because it throws a wrench in (beginning) students' ideas about how shallow/deep simple exercises can be and the relatioship between math, recursion, efficiency, etc. A lot of beginning students see the naïve recursive solution as mathematical-but-inefficient and draw the conclusion that the math is nice, but ultimately isn't practical. Then you show them an even-faster implementation using more math and they're pretty surprised.

Scaevolus 8y ago
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)
- daveFNbuck 8y ago
  If you only need the first 72 values, the speed doesn't really matter. You can just build the table once and do lookups.
jacobolus 8y ago
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 https://beta.observablehq.com/@jrus/zome-arithmetic or see a bunch of concrete uses in notebooks at https://beta.observablehq.com/@vorth/ https://beta.observablehq.com/@vorth/
- nimish 8y ago
  Of course -- representation theory guarantees this. It's just that matrices obfuscate the underlying algebra.
- jfarmer 8y ago
  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.)
  - daveFNbuck 8y ago
    > 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?
    - jacobolus 8y ago
      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.
kccqzy 8y ago
How are you going to obtain that many digits of the golden ratio to be able to compute a final answer?
- edflsafoiewq 8y ago
  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.
  - kccqzy 8y ago
    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.
hnkain 8y ago
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.
robinhouston 8y ago
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 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); }
joppy 8y ago
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.
- jfarmer 8y ago
  Also true. I think I did Q(phi) originally because Binet’s formula is less obvious under that basis.
- jacobolus 8y ago
  In practice, a + b√5 is a lot less pleasant to work with, especially by hand.

Scaevolus 8y ago

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)

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

jacobolus 8y ago

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 https://beta.observablehq.com/@jrus/zome-arithmetic or see a bunch of concrete uses in notebooks at https://beta.observablehq.com/@vorth/ https://beta.observablehq.com/@vorth/

nimish 8y ago
Of course -- representation theory guarantees this. It's just that matrices obfuscate the underlying algebra.
jfarmer 8y ago
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.)
- daveFNbuck 8y ago
  > 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?
  - jacobolus 8y ago
    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.

kccqzy 8y ago

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

edflsafoiewq 8y ago
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.
- kccqzy 8y ago
  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.

hnkain 8y ago

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.

robinhouston 8y ago

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 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); }

joppy 8y ago

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.

jfarmer 8y ago
Also true. I think I did Q(phi) originally because Binet’s formula is less obvious under that basis.
jacobolus 8y ago
In practice, a + b√5 is a lot less pleasant to work with, especially by hand.