Fibonacci calculation in Java Longs shows up negative

Question

My Fibonacci calculator works fine, but when going up to higher numbers the result comes up negative, as it would if it was an Integer over its max value.

It is working with a cache java.util.Map<Integer, Long>. Everything that goes into the Map is exactly what is expected, but when printing it out I get e.g. for 291:

-784134397488903422

According to http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibCalcX.html, it should be:

2923602405716568564338475449381171413803636207598822186175234

It seems something goes wrong with my Longs, but I am not sure yet, what exactly. Could someone please point me in the right direction?

Values of the Map entries: http://pastebin.com/uje07Ays

You can see very nicely negative numbers occurring after the 92nd Fibonacci number. Compare this with java.lang.Long.MAX_VALUE... — laune, Mar 22 '15 at 14:01

Sylvain Bugat · Accepted Answer · 2015-03-22T14:30:14.070

3

I think you are above the maximum long value that can be stored in a signed 64 bits integer used by Java for the long type, more information about Long and thesein the Java API: http://docs.oracle.com/javase/7/docs/api/java/lang/Long.html.

The maximum positive value for a 64 bits signed integer is 2^63 -1: 9 223 372 036 854 775 807, your value seems to have reach this limit and if the highest bit of a signed integer is 1, then the signed integer become negative (see 2 complement integer for more details: http://en.wikipedia.org/wiki/Two%27s_complement).

You need to use BigInteger to have arbitrary-precision integers http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html.

edited Mar 22 '15 at 14:30

answered Mar 22 '15 at 14:07

Sylvain Bugat

7,704
3
29
30

@laune you are right BigInteger must be used in this case. I have edited my answer in this way. – Sylvain Bugat Mar 22 '15 at 14:32
1

Thank you all very much! Works like a charm now. – Javakäfer Mar 22 '15 at 16:32

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

java has 8 primitive data types

byte

Minimum value is -128 (-2^7)
Maximum value is 127 (inclusive)(2^7 -1)
Default value is 0

short

Minimum value is -32,768 (-2^15)
Maximum value is 32,767 (inclusive) (2^15 -1)
Default value is 0.
Short data type can also be used to save memory as byte data type. A short is 2 times smaller than an int ( but java change this type to int for calculation )

int

Minimum value is - 2,147,483,648.(-2^31)
Maximum value is 2,147,483,647(inclusive).(2^31 -1) , which is more than your number
Int is generally used as the default data type for integral values unless there is a concern about memory.
The default value is 0.

long

Minimum value is -9,223,372,036,854,775,808.(-2^63)
Maximum value is 9,223,372,036,854,775,807 (inclusive). (2^63 -1) this value is less than your number
This type is used when a wider range than int is needed.
Default value is 0L.

float

Float data type is a single-precision 32-bit IEEE 754 floating point.
Float is mainly used to save memory in large arrays of floating point numbers. using this type for int value is crime
Default value is 0.0f.

double

double data type is a double-precision 64-bit IEEE 754 floating point.
This data type is generally used as the default data type for decimal values, generally the default choice.
Double data type should never be used for precise values such as currency.
Default value is 0.0d.

boolean

boolean data type represents one bit of information.
There are only two possible values: true and false.
This data type is used for simple flags that track true/false conditions.
Default value is false.

char

har data type is a single 16-bit Unicode character.
Minimum value is '\u0000' (or 0).
Maximum value is '\uffff' (or 65,535 inclusive).
Char data type is used to store any character.

as you can see none of the above types can store your value so you had to use BigInteger (example) or any other class that can handle this big values.

This way you won't increase your rep. You are just repeating older comments. — laune, Mar 22 '15 at 14:14
there is no comment when I write my answer and I want to help him — Esterlinkof, Mar 22 '15 at 14:17
@laune I edit my answer and this isn't seem to be comment any more — Esterlinkof, Mar 22 '15 at 14:42

desh bandhu · Answer 3 · 2015-03-22T17:27:35.757

public static void main(String[] args)
    {
        Map<Integer, BigDecimal> fibonacciMap = new HashMap<Integer, BigDecimal>();
        fibonacciMap.put(1, BigDecimal.valueOf(1));
        fibonacciMap.put(2, BigDecimal.valueOf(1));
        System.out.println(1 + " : " + fibonacciMap.get(1));
        System.out.println(2 + " : " + fibonacciMap.get(2));

        for(int i=3;i<=300;i++)
        {
            fibonacciMap.put(i, fibonacciMap.get(i-1).add(fibonacciMap.get(i-2)));
            System.out.println(i + " : " + fibonacciMap.get(i));
        }
    }

Since, Maximum value for long in java is 9223372036854775807. So, when the fibonacci number goes above this max value, it start rounding of from -9223372036854775808(Min Value) to zero to 9223372036854775807(Max Value). So, we need to use BigDecimal instead of Long to avoid -ve values.

for example:

Fib[92]=7540113804746346429

Fib[91]=4660046610375530309

(BigDecimal)Fib[93]=Fib[91]+Fib[92]=12200160415121876738 which is greater than Long.MAX_VALUE

(Long)Fib[93]= -6246583658587674878

Long.MAX_VALUE = 9223372036854775807

Long.MIN_VALUE = -9223372036854775808

So, (BigDecimal)Fib[93] = Long.MAX_VALUE - (Long.MIN_VALUE - (Long)Fib[93]) + 1;

Could you provide a comment on your solution, and describe what the problem was? — Piotr Dajlido, Mar 22 '15 at 14:54
Since, Maximum value for long in java is 9223372036854775807. So, when the fibonacci number goes above this max value, it start rounding of from -9223372036854775808(Min Value) to zero to 9223372036854775807(Max Value). So, we need to use BigDecimal instead of Long to avoid -ve values. — desh bandhu, Mar 22 '15 at 17:23