Тихое длинное переполнение при реализации Фибоначчи с Callables

Я пытаюсь реализовать последовательность Фибоначчи, используя вызываемые объекты, и засеял начальные значения моего вызываемого объекта Фибоначчи с помощью 3,4,5,6 и 2000. Вывод, который я получаю, выглядит следующим образом:

3 5 8 13 -820905900187520670

Проблема в том, что когда я пытаюсь вычислить fib(2000) в моем callable. Может ли кто-нибудь взглянуть на мой код, представленный ниже, чтобы увидеть, где я ошибаюсь в своем подходе:

import java.util.concurrent.*;
import java.util.*;

class FibonacciGen implements Callable<Long>{
    private Long fib;
    public FibonacciGen(long num){
        this.fib = num;
    }
    public Long call(){
        return calculateFibonacci(fib);
    }

    private long calculateFibonacci(long someNum){
        long firstNum = 0L;
        long secondNum = 1L;
        long counter = 0L;
        while(counter<someNum){
            long fibCalc = secondNum+firstNum;
            firstNum = secondNum;
            secondNum = fibCalc;
            counter= counter+1L;
        }
        return secondNum;
    }   

}

public class FibonacciCallable{
    public static void main(String[] args){
        ExecutorService exec = Executors.newCachedThreadPool();
        ArrayList<Callable<Long>> results = new ArrayList<Callable<Long>>();
        CompletionService<Long> ecs = new ExecutorCompletionService<Long>(exec);
        results.add(new FibonacciGen(3L));
        results.add(new FibonacciGen(4L));
        results.add(new FibonacciGen(5L));
        results.add(new FibonacciGen(6L));
        results.add(new FibonacciGen(2000L));
            try{
                for(Callable<Long> fs:results){
                    ecs.submit(fs);
                }
                System.out.println("Submitted all the tasks");
                int n = results.size();
                for(int i=0;i<n;++i){
                    System.out.println("Taking the first completed task");
                    Long r = ecs.take().get();
                    if(r != null)
                        System.out.println(r);
                    }   


            }
            catch(InterruptedException ex){System.out.println(ex);return;}
            catch(ExecutionException e){System.out.println(e);}
            finally{exec.shutdown();}
        }
}

Спасибо


person sc_ray    schedule 19.04.2012    source источник
comment
Я не думаю, что с этим что-то не так, long просто слишком мал для f(2000).   -  person biziclop    schedule 19.04.2012
comment
вы можете переполнить буфер, вы должны попробовать использовать BigInteger   -  person twain249    schedule 19.04.2012
comment
f(2000) = 4.224696333392424 * 10^417 Это не влезет в long.   -  person Mysticial    schedule 19.04.2012
comment
Вычисление чисел Фибоначчи — прекрасный пример того, когда не следует использовать несколько потоков. ;) vanillajava.blogspot.co.uk/ 2011/11/   -  person Peter Lawrey    schedule 19.04.2012
comment
@PeterLawrey Однако это другое, каждое число рассчитывается в одном потоке.   -  person biziclop    schedule 19.04.2012
comment
@biziclop и fib(n) будут вычислять все предыдущие fib(N), повторяя все предыдущие вычисления.   -  person Peter Lawrey    schedule 19.04.2012
comment
@PeterLawrey Это правда, они должны начинаться с разных начальных значений.   -  person biziclop    schedule 19.04.2012
comment
@biziclop Обычно я начинаю с 1 и 1 ;)   -  person Peter Lawrey    schedule 19.04.2012


Ответы (1)


Java не генерирует исключение при переполнении, а просто оборачивает значение, поэтому вы получаете странный результат. Фибоначчи — это быстрорастущая последовательность, элемент 2000. находится далеко за пределами long.

Попробуйте использовать BigInteger, это даст вам произвольную точность (очевидно, за счет производительности).

person biziclop    schedule 19.04.2012
comment
Если вы хотите продолжать использовать long, но хотите шумных переполнений, попробуйте Guava LongMath.checkedAdd. (Раскрытие информации: я вношу свой вклад в Guava.) - person Louis Wasserman; 19.04.2012