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 On Thu, Apr 26, 2018 at 10:22 AM, Ian Lance Taylor <i...@golang.org> wrote: > On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz <yuva...@gmail.com> 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+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- Michael T. Jones michael.jo...@gmail.com -- 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.
