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

Question

If you try inputs 99999999999999999 100000 for the code below it runs the logic at about 5 seconds. I've searched for the bottle neck and found out it is the mod() method. Is there a better trade off for huge numbers?

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;
        }

    }
}

`mod` might be the most expensive part of your code but that doesn't mean it can actually be optimized further. It's hard to tell from your code, but frankly it looks a lot like the math you're trying to do is just plain expensive. — Louis Wasserman, May 06 '16 at 19:09
See also http://stackoverflow.com/questions/8287144/modulus-power-of-big-numbers — assylias, May 06 '16 at 19:10

score 0 · Accepted Answer · answered May 06 '16 at 20:17

0

Instead of storing a large number, store that number mod mBI, and your mod operation won't take so long. If you replace

result = second.add( first );

with

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

and make your condition table.add( result ) instead of table.add (result.mod( mBI ) ), you get much better performance.

answered May 06 '16 at 20:17

amiller27

491
5
8

thanks @user2791611 , but I need to keep the result of second.add(first) for the next loop. – juliocnsouza May 10 '16 at 13:18
@juliocnsouza From what I can see, you don't actually need the result, you need the result mod mBI. You only ever use the result mod mBI. I did test this code on the two inputs you gave in the question, and it gives the same result in much less time. Is there something I'm missing? – amiller27 May 11 '16 at 02:56
thanks @user2791611 you are right, it worked much faster! I really don't know what a did I in the first test that made me come with the conclusion commented above. Thanks for the answer and for getting my attention to it :D . – juliocnsouza May 14 '16 at 11:07

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

1 Answers1