Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-05-06 Thread Yuval Lifshitz 
seems like math accuracy issues are known, or even, by design. see:
https://github.com/golang/go/issues/9546
https://github.com/golang/go/issues/9545


On Sunday, 6 May 2018 00:05:13 UTC+3, Paul Hankin wrote:
>
> On Friday, 27 April 2018 23:57:42 UTC+2, 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)
>>
>
> A neat not-very-well-known trick is to use that phi^n = Fib(n)phi + 
> Fib(n-1). Numbers of the form a*phi+b where a and b are integers are closed 
> under multiplication, so you can compute phi^n exactly using integer 
> arithmetic -- in log(n) arithmetic operations.
>
> https://play.golang.org/p/j4mZ93c820R
>
> -- 
> Paul
>

-- 
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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-05-05 Thread Paul Hankin 
On Friday, 27 April 2018 23:57:42 UTC+2, 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)
>

A neat not-very-well-known trick is to use that phi^n = Fib(n)phi + 
Fib(n-1). Numbers of the form a*phi+b where a and b are integers are closed 
under multiplication, so you can compute phi^n exactly using integer 
arithmetic -- in log(n) arithmetic operations.

https://play.golang.org/p/j4mZ93c820R

-- 
Paul

-- 
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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-05-01 Thread Marvin Renich 
* andrey mirtchovski  [180430 17:41]:
> > math.Pow does not give as precise answers as the C++ std lib.
> 
> math pow doesn't just multiply X by itself Y times, it uses a
> different algorithm:
> 
> https://golang.org/src/math/pow.go#L40

Sure, I understand that.  However, the current algorithm used by
math.Pow produces results that are far enough from the true value that
it is worth opening an issue.

> it would perhaps make sense to quantify the error margins that this
> algorithm introduces.

As far as the OP's question about why he needs to round in Go but
truncate in C++, I am not convinced that the error in math.Pow is
significant.

Binet's formula, given exact (non-computer limited) values and
calculations, will give exact integral values for the Fibonacci numbers.
If you start with the assumption that using Binet's formula with IEEE
floating point arithmetic will give results that are close enough to the
correct value that you will have no trouble determining which integer is
the right one, then the assumption that the error is between -0.5 and
+0.5 is much more reasonable than the assumption that the error is in
the range [0, 1).

It is certainly plausible that one could prove that the error will
always be positive, given known characteristics of the computer
program's implementation of pow, among other things, but without such
analysis, assuming that truncating the result will always give the
correct answer is naive.

I posit that the OP's C++ implementation only works because of specific
characteristics of C++ library pow function, the last-mantissa-bit
rounding of the value used for phi, and other aspects of the
implementation that have not be adequately analyzed to be certain that
the error is always positive.

In short, the OP's assumption that the algorithm in his C++ program is
correct is wrong; it just happens to work for the values tested.  Both
the C++ and the Go program should round the floating point result to get
the correct integer.

...Marvin

-- 
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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread Michael Jones 
using an optimally-precise Pow:
   1: rounded =   1, both =
 1., delta = +0.e+00
   2: rounded =   1, both =
 1., delta = +0.e+00
   3: rounded =   2, both =
 2., delta = +0.e+00
   4: rounded =   3, both =
 3., delta = +0.e+00
   5: rounded =   5, both =
 5., delta = +0.e+00
   6: rounded =   8, both =
 8., delta = +0.e+00
   7: rounded =  13, both =
13., delta = +0.e+00
   8: rounded =  21, both =
21., delta = +0.e+00
   9: rounded =  34, both =
34., delta = +0.e+00
  10: rounded =  55, both =
55., delta = +0.e+00
  11: rounded =  89, both =
89., delta = +0.e+00
  12: rounded = 144, both =
 144., delta = +0.e+00
  13: rounded = 233, both =
 233., delta = +0.e+00
  14: rounded = 377, both =
 377.05684342, delta = +5.68434188608080148697e-14
  15: rounded = 610, both =
 610., delta = +0.e+00
  16: rounded = 987, both =
 986.77262632, delta = -2.27373675443232059479e-13
  17: rounded =1597, both =
1596.77262632, delta = -2.27373675443232059479e-13
  18: rounded =2584, both =
2584., delta = +0.e+00
  19: rounded =4181, both =
4181., delta = +0.e+00
  20: rounded =6765, both =
6765.90949470, delta = +9.09494701772928237915e-13
  21: rounded =   10946, both =
 10946.000363797881, delta = +3.63797880709171295166e-12
  22: rounded =   17711, both =
 17711., delta = +0.e+00
  23: rounded =   28657, both =
 28657.000363797881, delta = +3.63797880709171295166e-12
  24: rounded =   46368, both =
 46368.000727595761, delta = +7.27595761418342590332e-12
  25: rounded =   75025, both =
 75025.001455191523, delta = +1.45519152283668518066e-11
  26: rounded =  121393, both =
121393.001455191523, delta = +1.45519152283668518066e-11
  27: rounded =  196418, both =
196418.005820766091, delta = +5.82076609134674072266e-11
  28: rounded =  317811, both =
317811.011641532183, delta = +1.16415321826934814453e-10
  29: rounded =  514229, both =
514228.994179233909, delta = -5.82076609134674072266e-11
  30: rounded =  832040, both =
832040., delta = +0.e+00
  31: rounded = 1346269, both =
 1346269.046566128731, delta = +4.65661287307739257812e-10
  32: rounded = 2178309, both =
 2178309., delta = +0.e+00
  33: rounded = 3524578, both =
 3524577.906867742538, delta = -9.31322574615478515625e-10
  34: rounded = 5702887, both =
 5702886.906867742538, delta = -9.31322574615478515625e-10
  35: rounded = 9227465, both =
 9227465., delta = +0.e+00
  36: rounded =14930352, both =
14930352., delta = +0.e+00
  37: rounded =24157817, both =
24157816.254941940308, delta = -7.45058059692382812500e-09
  38: rounded =39088169, both =
39088169., delta = +0.e+00
  39: rounded =63245986, both =
63245986.745058059692, delta = +7.45058059692382812500e-09
  40: rounded =   102334155, both =
 102334155.0002980232238770, delta = +2.98023223876953125000e-08
  41: rounded =   165580141, both =
 165580141.0002980232238770, delta = +2.98023223876953125000e-08
  42: rounded =   267914296, both =
 267914296.0014901161193848, delta = +1.49011611938476562500e-07
  43: rounded =   433494437, both =
 433494437.0011920928955078, delta = +1.1920928955078125e-07
  44: rounded =   701408733, both =
 701408733.0023841857910156, delta = +2.3841857910156250e-07
  45: rounded =  1134903170, both =
1134903170.0047683715820312, delta = +4.7683715820312500e-07
  46: rounded =  1836311903, both =
1836311903.0071525573730469,

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread andrey mirtchovski 
> math.Pow does not give as precise answers as the C++ std lib.

math pow doesn't just multiply X by itself Y times, it uses a
different algorithm:

https://golang.org/src/math/pow.go#L40

it would perhaps make sense to quantify the error margins that this
algorithm introduces.

not sure what c++ stdlib does.

-- 
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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread Marvin Renich 
* Michael Jones  [180430 13:54]:
> Andrey, that's great!
> 
> On the Fibonacci series evaluation, let's make sure that we're all doing
> the same calculation. For completeness and safety, let's skip all library
> values and derived values. Here are more-than-sufficient versions of the
> three constants in Yuval's code:

I think both of you missed the point of my message.  This has nothing to
do specifically with Fibonacci numbers.  The problem is simply that
math.Pow does not give as precise answers as the C++ std lib.  Look at
https://play.golang.org/p/_gVbAWjeoyW and notice that the result from
math.Pow is off in the 15th decimal digit.  Both the bigPow and the C++
pow library function are good until the 17th digit, which is what is
expected.  (Actually, I thought bigPow might do better, with the
specified precision of 300.)  I trust the Mathematica answer to be
correct to the number of digits printed (last digit rounded).

There is no math.Phi involved here, except that the hand-typed constant
happens to be as close as you can get to Phi in a float64 (but this is
not relevant to the test).

...Marvin

-- 
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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread Michael Jones 
Andrey, that's great!

On the Fibonacci series evaluation, let's make sure that we're all doing
the same calculation. For completeness and safety, let's skip all library
values and derived values. Here are more-than-sufficient versions of the
three constants in Yuval's code:

// 40-decimal digit approximations
const sqrt5 float64 =  2.236067977499789696409173668731276235441
// math.Sqrt(5.0)
const phi   float64 =  1.618033988749894848204586834365638117720  // (1 +
sqrt5) / 2
const psi   float64 = -0.6180339887498948482045868343656381177203 // (1 -
sqrt5) / 2

Here is the evaluation: (https://play.golang.org/p/InwNEeyv4Bx)
func fibonacci(n uint) uint64 {
float_n := float64(n)
a := math.Pow(phi, float_n)
b := math.Pow(psi, float_n)
rounded := math.Floor(a/sqrt5 + 0.5)
both := (a - b) / sqrt5
fmt.Printf("%4d: rounded = %19.0f, both = %40.20f, delta = %+27.20e\n", n,
rounded, both, both-rounded)
return uint64(rounded)
}

And the result:
   1: rounded =   1, both =
 1., delta = +0.e+00
   2: rounded =   1, both =
 1., delta = +0.e+00
   3: rounded =   2, both =
 2., delta = +0.e+00
   4: rounded =   3, both =
 3., delta = +0.e+00
   5: rounded =   5, both =
 5., delta = +0.e+00
   6: rounded =   8, both =
 8., delta = +0.e+00
   7: rounded =  13, both =
13., delta = +0.e+00
   8: rounded =  21, both =
21., delta = +0.e+00
   9: rounded =  34, both =
34., delta = +0.e+00
  10: rounded =  55, both =
54.99289457, delta = -7.10542735760100185871e-15
  11: rounded =  89, both =
89., delta = +0.e+00
  12: rounded = 144, both =
 143.97157829, delta = -2.84217094304040074348e-14
  13: rounded = 233, both =
 232.94315658, delta = -5.68434188608080148697e-14
  14: rounded = 377, both =
 377.05684342, delta = +5.68434188608080148697e-14
  15: rounded = 610, both =
 610., delta = +0.e+00
  16: rounded = 987, both =
 986.77262632, delta = -2.27373675443232059479e-13
  17: rounded =1597, both =
1596.77262632, delta = -2.27373675443232059479e-13
  18: rounded =2584, both =
2584., delta = +0.e+00
  19: rounded =4181, both =
4181., delta = +0.e+00
  20: rounded =6765, both =
6764.09050530, delta = -9.09494701772928237915e-13
  21: rounded =   10946, both =
 10945.999818101060, delta = -1.81898940354585647583e-12
  22: rounded =   17711, both =
 17710.999636202119, delta = -3.63797880709171295166e-12
  23: rounded =   28657, both =
 28656.999636202119, delta = -3.63797880709171295166e-12
  24: rounded =   46368, both =
 46367.999272404239, delta = -7.27595761418342590332e-12
  25: rounded =   75025, both =
 75025., delta = +0.e+00
  26: rounded =  121393, both =
121392.998544808477, delta = -1.45519152283668518066e-11
  27: rounded =  196418, both =
196418., delta = +0.e+00
  28: rounded =  317811, both =
317811., delta = +0.e+00
  29: rounded =  514229, both =
514228.994179233909, delta = -5.82076609134674072266e-11
  30: rounded =  832040, both =
832039.988358467817, delta = -1.16415321826934814453e-10
  31: rounded = 1346269, both =
 1346268.976716935635, delta = -2.32830643653869628906e-10
  32: rounded = 2178309, both =
 2178309., delta = +0.e+00
  33: rounded = 3524578, both =
 3524577.953433871269, delta = -4.65661287307739257812e-10
  34: rounded = 5702887, both =
 5702886.906867742538, delta = -9.31322574615478515625e-10
  35: rounded = 9227465, both =
 9227465., delta = +0.e+00
  36: rounded =14930352, both =
14930351.813735485077, delta = -1.86264514923095703125e-09
  37: rounded =24157817, both =
24157816.627470970154, delta = -3.72529029846191406250e-09
  38: rounded =39088169, both =

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread andrey mirtchovski 
every time float accuracy is mentioned i think of this:

http://0.30004.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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread Marvin Renich 
* Yuval Lifshitz  [180430 02:02]:
> 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

/* aside - this doesn't seem relevant to this problem except perhaps
 * the implementation of math.Pow, but...

The 8087 and successor FPUs (e.g. amd64 class processors) have an 80-bit
extended precision format which is used for all calculations.  More than
a couple decades ago, when I was working on implementation of floating
point in an APL interpreter (written in C, C++, asm), the IEEE 754
standard did not specify how compilers should handle precision of
intermediate results, and the compiler we were using would only convert
from 80-bit to 64-bit when it needed to store a result back into memory.
This could easily give different results depending on how the floating
point expression was broken up.  E.g. a = (b + c) - d could give a
different result than a = b + c; a = a - d.

The standard has, since then, attempted to address this, but I have not
studied this at all, so I don't know what is expected of C or Go.

*/

Back to your specific problem:

Go:  psi = -0.61803398874989490
C++: psi = -0.61803398874989479

Go:  math.Pow(math.Phi, float64(33)) = 7.8811960012666e+06
C++:pow(phi, 33) = 7.8811960013597e+06

And using hand-typed constants:

Go:  math.Pow(1.61803398874989490, 33.0) = 7.8811960012666e+06
C++:  pow(1.61803398874989490, 33.0) = 7.8811960013597e+06

So indeed there is a difference between math.Pow in Go and pow in C++.
I would say to file an issue.  I have no idea which answer is closer to
correct, but using math/big and multiplying 1.61803398874989490 by
itself 33 times with a result precision of 80, I get
7.8811960013562e+06.

Note:  in Go, math.Phi is an untyped constant with precision greater
than float64.  Adding  var phi float64 = math.Phi  and replacing
math.Phi everywhere else with phi did not change anything except the
value of psi (which then matched the C++ value).  The C++ version of psi
is definitely farther from the "true" value, but as Michael said, the
error in pow(psi, n) is swamped by the value of pow(phi, n).

...Marvin

-- 
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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-30 Thread Yuval Lifshitz 
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  > 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 

 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

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-29 Thread Michael Jones 
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  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 
>>>
>>> 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

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-29 Thread Yuval Lifshitz 
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 
>>
>> 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 
>>> 754011380474638
>>> 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 
>>>

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-29 Thread Louki Sumirniy 
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 
>
> 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 754011380474638
>> 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  
>> wrote:
>>
>>> On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz  
>>> wrote:
>>> >
>>> > I ran into the following issue when started playing with go. Had the
>>> > following small program to calculate Fibonacci

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-29 Thread Yuval Lifshitz 
Thanks Michael. Is this "by design"? Does it worth an issue here 
?

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  > 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 
>>
>> 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 
>>> 754011380474638
>>> 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  
>>> wrote:
>>>
 On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz  
 wrote:
 >
 > I ran into the following issue when started playing with go. Had the
 > following small program to

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-29 Thread Michael Jones 
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  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 
>
> 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 754011380474638
>> 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 
>> wrote:
>>
>>> On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz 
>>> 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))
>>> > }
>>> >
>>> >

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-29 Thread Yuval Lifshitz 
(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 

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 754011380474638
> 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  > wrote:
>
>> On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz > > 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,
>>

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-27 Thread Michael Jones 
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 754011380474638
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  wrote:

> On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz  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.

Re: [go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-26 Thread Ian Lance Taylor 
On Thu, Apr 26, 2018 at 1:17 AM, Yuval Lifshitz  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.

[go-nuts] float accuracy when calculating Fibonacci numbers

2018-04-26 Thread Yuval Lifshitz 
Dear community,
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?

-- 
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.