It seems like go and C++ are doing something different regarding floating point arithmetic, but I cannot say one is better than the other. It is just the that C++ consistently overshoots (hence truncation work), and go consistently undershoots (this is why rounding is needed). For example, in C++:
F(59) = 956722026041.002 And in go, it is: F(59) = 956722026040.999878 And for example: On Monday, 30 April 2018 02:13:49 UTC+3, Michael Jones wrote: > > Not sure what you mean with "by design." The design here is the IEEE > Standard for Floating-Point Arithmetic (IEEE 754). It is authoritative for > Intel, AMD, IBM, Sun, etc. > > Typical (universal?) C and C++ implementations map 'float' to 32-bit IEEE > 754 binary floating point and 'double' to the related 64-bit version. Go > uses this same hardware in the same (universal?) way, through the types > "float32" and "float64." > > Truncation of floating point types to integer, or the floor() function, > discards any fractional part. Such that: > int(e) => 2 > int(pi) => 3 > > Rounding up to the nearest integer with int(v+0.5) and floor(v+0.5) is a > different operation: > round(e) => 3 > round(pi) => 3 > > Your C program truncates and your Go program rounds. They are not the same > program. They compute different things, which is why the results are > different. > > In a de Moivre coding of Fibonacci evaluation using rounding as above, > Knuth showed that the pow((1-sqrt(5))/2,n) term--the second summand--may be > dropped. > > For 64-bit floating point the F(75) value is the most that you can > generate this way. > > Using other methods you can (and more quickly) generate values up to > F(92), which is the greatest Fibonacci value (7540113804746346429) > representable as a 64-bit unsigned integer. > > For completeness, there is also the Ceiling function: > ceil(e) => 3 > ceil(pi) => 4 > > hope this helps. > > > On Sun, Apr 29, 2018 at 12:36 PM Yuval Lifshitz <yuv...@gmail.com > <javascript:>> wrote: > >> in C/C++ (at least on my system) "float" 4 has 4 bytes (32bits) and >> double has 8 bytes (64bits). according to this: >> https://golang.org/pkg/math/ its is the same thing with go. >> >> On Sunday, 29 April 2018 22:27:23 UTC+3, Louki Sumirniy wrote: >>> >>> I could be wrong but float64 is 'float' and 'double float' is float128. >>> I dunno, I have not tinkered with these imprecise math types. That's just, >>> essentially, what they were back in the olden days, like 20 years ago. 64 >>> bit was basic float, 128 was double. I have been out of the loop for way >>> too long on these things (and I am not a fan of floats anyway, give me some >>> fixed precision pls). >>> >>> On Sunday, 29 April 2018 10:08:15 UTC+3, Yuval Lifshitz 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.
