On Friday, 27 April 2018 23:57:42 UTC+2, Michael Jones wrote: > > Yuval, > > There are fundamental issues here. > > 1. That equation (de Moivre, Binet) is from the algebra of ideal numbers. > Numbers of infinite precision. Not the realm of computer arithmetic. It > works fine with double precision (go: float64, c/c++: double) up to F(75) > but must fail for F(76) due to the limited precision of 64-bit floating > point and has nothing to do with language. > > F(76) = 3416454622906707 but the best we can do in 64 bits is > 3416454622906706 even with a Pow() function good to +/-1 least significant > bit. > > 2. Another difference between algebra and computer arithmetic > (well...actually about the floor function) is that one of your two power > terms is not needed. Psi < 1 so Psi^N is pretty small, so small, that it > never changes the value of the rounded result. So you can just evaluate: > > return round(math.Pow(math.Phi, float_n) / sqrt_5) >
A neat not-very-well-known trick is to use that phi^n = Fib(n)phi + Fib(n-1). Numbers of the form a*phi+b where a and b are integers are closed under multiplication, so you can compute phi^n exactly using integer arithmetic -- in log(n) arithmetic operations. https://play.golang.org/p/j4mZ93c820R -- Paul -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
