Fibonacci calculation in Java Longs shows up negat

问题:

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

回答1:

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.

回答2:

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.

回答3:

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;