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 <yuva...@gmail.com> 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+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.
