(1) I understand the issue of limited precision, this is why I did not try anything above F(59) But my concern was not the difference between algebra and the go implementation it was the different results I got with the C/C++ implementation (gcc 7.3.1):
#include <math.h> const double sqrt_5 = sqrt(5.0); const double phi = (1.0 + sqrt_5)/2.0; const double psi = -1.0/phi; // find the nth fibonacci number based on Binet's formula // see here: https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression unsigned long long fibonacci(unsigned n) { return (unsigned long long)((pow(phi, n) - pow(psi, n))/sqrt_5); } (2) Thanks for the fix, work well for the go implementation. However, if i try to apply it on the C++ one (where there is no rounding), it makes some of the tests fails. So, I guess that without rounding, the psi part is needed (3) Is there a way to print the map ordered (didn't see that in your snippet)? (4) Wanted to compare "double" in C++ to "float64" in go. As they should consume same amount of memory, have similar algorithms etc. but good to know about the "big" package in go (5) Thanks for the reference. interesting read On Saturday, 28 April 2018 00:57:42 UTC+3, 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) > > 3. Using a map in your test is not wrong, but it means that the tests will > be executed in a random order, which makes the printed errors a little less > clear. > > celeste:fib mtj$ go test -v > === RUN Test_fibonacci > --- FAIL: Test_fibonacci (0.00s) > fib_test.go:104: 82 : Expected 61305790721611591 got 61305790721611584 > fib_test.go:104: 84 : Expected 160500643816367088 got 160500643816367040 > fib_test.go:104: 81 : Expected 37889062373143906 got 37889062373143896 > fib_test.go:104: 87 : Expected 679891637638612258 got 679891637638612096 > fib_test.go:104: 88 : Expected 1100087778366101931 got 1100087778366101632 > fib_test.go:104: 83 : Expected 99194853094755497 got 99194853094755488 > fib_test.go:104: 77 : Expected 5527939700884757 got 5527939700884756 > fib_test.go:104: 86 : Expected 420196140727489673 got 420196140727489600 > fib_test.go:104: 90 : Expected 2880067194370816120 got 2880067194370815488 > fib_test.go:104: 91 : Expected 4660046610375530309 got 4660046610375529472 > fib_test.go:104: 92 : Expected 7540113804746346429 got 7540113804746344448 > fib_test.go:104: 76 : Expected 3416454622906707 got 3416454622906706 > fib_test.go:104: 85 : Expected 259695496911122585 got 259695496911122528 > fib_test.go:104: 89 : Expected 1779979416004714189 got 1779979416004713728 > fib_test.go:104: 79 : Expected 14472334024676221 got 14472334024676218 > fib_test.go:104: 80 : Expected 23416728348467685 got 23416728348467676 > FAIL > exit status 1 > FAIL fib 0.003s > > updated fib.go: https://play.golang.org/p/N-8lmjrMYAq > update fib_test.go: https://play.golang.org/p/FPuN58m1VVs > > 4. Plenty of ways to do this computation in Go using 64-bit integers, or > big floats, or big ints. > > 5. Plenty of algorithms, some quite fascinating! > https://ir.library.oregonstate.edu/downloads/t435gg51w > <https://www.google.com/url?q=https%3A%2F%2Fir.library.oregonstate.edu%2Fdownloads%2Ft435gg51w&sa=D&sntz=1&usg=AFQjCNFeFx9ebd-m_yzIjw4H29wdLpzmVw> > > > On Thu, Apr 26, 2018 at 10:22 AM, Ian Lance Taylor <ia...@golang.org > <javascript:>> wrote: > >> On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz <yuv...@gmail.com >> <javascript:>> wrote: >> > >> > I ran into the following issue when started playing with go. Had the >> > following small program to calculate Fibonacci numbers using the closed >> > form: >> > >> > package "fib" >> > >> > import "math" >> > >> > var sqrt_5 = math.Sqrt(5.0) >> > var psi = -1.0/math.Phi >> > >> > // had to add this to solve accuracy issue >> > func round(x float64) uint64 { >> > return uint64(math.Floor(x + 0.5)) >> > } >> > >> > // find the nth fibonacci number based on Binet's formula >> > // see here: >> > https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression >> > func fibonacci(n uint) uint64 { >> > float_n := float64(n) >> > return round((math.Pow(math.Phi, float_n) - math.Pow(psi, >> > float_n))/sqrt_5) >> > } >> > >> > >> > When I first tried without doing the "rounding" I did not get whole >> numbers >> > as the output (similar program in C++ gave whole numbers without >> rounding). >> > Following test is failing without the call to "round()": >> > >> > package "fib" >> > >> > import "testing" >> > >> > var results = map[uint]uint64 { >> > 0: 0, >> > 2: 1, >> > 10: 55, >> > 14: 377, >> > 20: 6765, >> > 29: 514229, >> > 33: 3524578, >> > 59: 956722026041, >> > } >> > >> > func Test_fibonacci(t *testing.T) { >> > for arg, expected := range results { >> > actual := fibonacci(arg) >> > if actual != expected { >> > t.Error("Expected", expected, "got", actual) >> > } >> > } >> > } >> > >> > >> > >> > Are there known accuracy issues with floating points in go? >> >> No. >> >> I suggest that you show us your C code. Thanks. >> >> Ian >> >> -- >> 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...@googlegroups.com <javascript:>. >> For more options, visit https://groups.google.com/d/optout. >> > > > > -- > Michael T. Jones > michae...@gmail.com <javascript:> > -- 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.
