Thanks Michael. Is this "by design"? Does it worth an issue here <https://github.com/golang/go/issues>?
On Sunday, 29 April 2018 18:06:23 UTC+3, Michael Jones wrote: > > yes. truncation and round-up are important differences between your c/c++ > code and the go code. > > On Sun, Apr 29, 2018 at 12:08 AM Yuval Lifshitz <yuv...@gmail.com > <javascript:>> wrote: > >> (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> >>> wrote: >>> >>>> On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz <yuv...@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...@googlegroups.com. >>>> For more options, visit https://groups.google.com/d/optout. >>>> >>> >>> >>> >>> -- >>> Michael T. Jones >>> michae...@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...@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.
