BigInteger 方法 mod() 性能很差。对于巨大的数字有更好的权衡吗？

Question

如果您尝试为下面的代码输入 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;
        }

    }
}

Answer 1

与其存储大量数字，不如存储该数字 mod mBI，这样您的 mod 操作就不会花费这么长时间。如果你替换

result = second.add( first );

与

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

并使您的条件 table.add( result ) 而不是 table.add (result.mod( mBI ) )，您将获得更好的性能。

BigInteger 方法 mod() 性能很差。对于巨大的数字有更好的权衡吗？

BigInteger method mod() performance is bad. Is there a better trade off for huge numbers?

java

performance

biginteger

mod