0

Folks, hope you could point me, what I missing out. I am new to programming and now solving problems for Project Euler. One of the tasks is to calculate the sum of even numbers of Fibonacci sequence. I wrote code which passed 4 of 5 test. Here it is:

//N is input (N<=4*10^16), let's find n by Binet's formula 

double a = log10(sqrt (5) * N);
double b = log10((1 + sqrt (5)) / 2);
int n = (int) (a / b); 

//Using same formula, we find every Fibonacci number till n
for (int i = 1; i <= n; i++){
  a = (1 + sqrt(5)) / 2;
  long fiboNum = Math.round (Math.pow(a,i) / sqrt(5));

And here is my problem: when I run a test with big numbers, there is some rounding happening around F(71). By my code, F(71) is 308 061 521 170 130, according to WolphramAlpha calculations 308 061 521 170 129.

Because of this, final sum is wrong.

Also, while testing I printed out all numbers and recognize, that even numbers repeat every 3. But even if I simplify it to the small loop of sum every third number, still problem exist.

If I do not use Math.round, I am getting the wrong sequence...

Simon Osipov
  • 404
  • 5
  • 18

1 Answers1

1

double has a limited precision. Try using BigDecimal which has precision only limited by the size of available memory.

Here is how you compute square root with BigDecimals: Square root of BigDecimal in Java

pow(): Java's BigDecimal.power(BigDecimal exponent): Is there a Java library that does it?

Rounding: Java BigDecimal: Round to the nearest whole value

Other operations like addition and division are built-in into BigDecimal as methods.

Roman Puchkovskiy
  • 11,415
  • 5
  • 36
  • 72