1

以下のコードで入力 99999999999999999 100000 を試すと、約 5 秒でロジックが実行されます。ボトルネックを検索したところ、それが mod() メソッドであることがわかりました。巨大な数のためのより良いトレードオフはありますか?

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class FibonacciHuge {

    private static BigInteger calcFibMod( long n , long m ) {
        Table table = new Table( n );
        BigInteger mBI = new BigInteger( String.valueOf( m ) );
        BigInteger first = new BigInteger( "0" );
        BigInteger second = new BigInteger( "1" );
        BigInteger result;
        while ( true ) {
            result = second.add( first );
            first = second;
            second = result;

            if ( table.add( result.mod( mBI ) ) ) {
                return table.found;
            }
        }
    }

    public static void main( String args[] ) {
        Scanner scanner = new Scanner( System.in );
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        System.out.println( calcFibMod( n , m ) );
    }

    static final class Table {

        List<BigInteger> mods;
        BigInteger found;
        long n;
        int size;

        Table( long n ) {
            this.n = n;
            mods = new ArrayList<>();
            mods.add( BigInteger.ZERO );
            mods.add( BigInteger.ONE );
            size = 2;
        }

        boolean add( BigInteger mod ) {
            mods.add( mod );
            size++;

            if ( !( BigInteger.ONE.equals( mod ) && BigInteger.ZERO.equals( mods.get( size - 2 ) ) ) ) {
                return false;
            }

            mods.remove( size - 1 );
            mods.remove( size - 2 );
            n++;
            size = mods.size();
            long rest = n % size;
            long index = rest == 0l
                         ? size - 1
                         : rest - 1;

            found = mods.get( ( int ) index );
            return true;
        }

    }
}
4

1 に答える 1

0

大量の数値を格納する代わりに、その数値 mod mBI を格納すると、mod 操作にそれほど時間がかかりません。交換すれば

result = second.add( first );

と

result = second.add( first ).mod( mBI );

table.add( result )の代わりに自分の状態を作ると、table.add (result.mod( mBI ) )はるかに優れたパフォーマンスが得られます。

于 2016-05-06T20:17:49.667 に答える