1

Good evening. I have written the code counting the Fibonacchi numbers remainder by its number n by modulo m, but it turned out to give me negative remainders after n=100000, before that everything is fine. Before using Long, I used BigInteger instead: however, the code with such variable type is extremely slow.I also use Q-matrices and exponentiation by squaring. Here's the code: 

import java.util.Scanner;

class Main {

private void bigfib(){

    Scanner sc = new Scanner(System.in);
    long  n = sc.nextLong();
    long m = sc.nextLong();

    long [][] a = new long[][]{{1,1},{1,0}};
    System.out.println(pow(a,n)[0][1]%m);

}

private long[][] mult(long[][] m1, long[][] m2) {

    long a11 = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
    long a12 = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
    long a21 = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
    long a22 = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];

    long[][] mResult = new long[][]{{a11,a12},{a21,a22}};

    return mResult;

}

private long [][] pow(long a[][], long p) {

    long[][] result;

    if (p==1)
        return a;

    if (p==2)
        return mult(a,a);

    if (p%2==1){
        return mult(a,pow(a,p-1));
    }
    else{
        result = pow(a,p/2);
        return mult(result,result);
    }

}


public static void main(String[] args) {

    new Main().bigfib();

}

}

Could someone please tell me, why remainders start to be negative and how can that be fixed without BigItegers?

TheDoctor
  • 105
  • 1
  • 9
  • Do not paste link to code. Paste code into the question and format it correctly. See http://stackoverflow.com/editing-help – Andreas Mar 09 '17 at 22:13
  • Please do not post code on third-party websites. Doing so renders this question useless to future readers in the event that the link should break. Please paste the code in the question itself. – Joe C Mar 09 '17 at 22:13
  • 2
    Are you saying that you're trying to store the 100000th Fibonacci number in a `long`, then wondering why you're getting integer-overflow-type symptoms? – Dawood ibn Kareem Mar 09 '17 at 22:16
  • @Joe С, ok, sorry, will change it. But what about the problem itself?:-) – TheDoctor Mar 09 '17 at 22:16
  • @DavidWallace, before that I used BigInteger, and the implementation was _very_ slow. – TheDoctor Mar 09 '17 at 22:17
  • 1
    OK, but the 100000th Fibonacci number has about 21000 digits. The biggest number you can store in a `long` has 19 digits. The reason why it's so much faster to use `long` than `BigInteger` is because you're only dealing with a tiny portion of the actual number. – Dawood ibn Kareem Mar 09 '17 at 22:21
  • That's because the numbers you're dealing with are _very_ big. The 300th Fibonacci number, according to the list I found [here](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html), would require around 210 bits, or six `int`s side by side. Getting to the 100,000th would be far beyond what you could reasonably do on a home PC. – Joe C Mar 09 '17 at 22:22
  • @DavidWallace, I got it, yes, thank you. It seems i need to perform the operation `%m` earlier to get rid of it... – TheDoctor Mar 09 '17 at 22:27
  • 1
    You need to stop expecting operations on 21000-digit numbers to happen quickly. Whatever you're doing, it's going to be extremely slow. – Dawood ibn Kareem Mar 09 '17 at 22:28
  • 1
    If your intention is to have results in mod m, then do ALL your calculations in mod m, including the exponentiation, and including evaluation of the fibonacci numbers. That's really the only way to do this. Depending on the value of m, you may want to build up a multiplication table before you start. – Dawood ibn Kareem Mar 09 '17 at 22:40
  • @DavidWallace, yes, I figured it would be the case. I did the che calculation of matrix elements in mod m, and everything works fine now. Thank you for help! – TheDoctor Mar 09 '17 at 22:43
  • 1
    The matrix calculation can be replaced a Lucas sequence, which ends up being an optimized matrix calculation for Fibonacci numbers. [Example code without modulus](http://stackoverflow.com/questions/34698842/why-is-the-fibonacci-sequence-big-o2n-instead-of-ologn/34700205#34700205). All the math in that example would need to be done modulo m. – rcgldr Mar 11 '17 at 00:26

1 Answers1

2

Judging by the problem you're describing (I don't click pastebin links), it looks like you're about to learn how numbers are represented in memory.

If you are using an int, it is represented in 32 bits. The first bit represents whether it is positive or negative, while the remaining 31 represent the magnitude of the number.

So this introduces this interesting phenomenon:

    0111 1111 1111 1111 =  2,147,483,647
(+) 0000 0000 0000 0001 =              1
-----------------------   --------------
    1000 0000 0000 0000 = -2,147,483,648

To resolve your issue, you should consider using a BigInteger instead. It works behind the scenes to hide this problem from you.

Joe C
  • 15,324
  • 8
  • 38
  • 50
  • Thank you, but actually I got this problem trying to avoid using BigInteger. The code was very slow. I tried to insert `%m`into the pow(), but it cannot be applied to matrices. – TheDoctor Mar 09 '17 at 22:24
  • 1
    Well, you have a choice to make now. Either go with something that's very slow, or go with something that produces rubbish. – Joe C Mar 09 '17 at 22:29
  • well, actually, I solved it with longs, counting matrix elements like this: `long a11 = (m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0])%m;`, etc. Thanks for help! – TheDoctor Mar 09 '17 at 22:36
  • But your problem space is larger than 64 bits wide. Are you quite sure you solved it? – Lew Bloch Mar 09 '17 at 23:09
  • @LewBloch, yes, I am. – TheDoctor Mar 10 '17 at 00:06
  • How are you handling 21,000-digit numbers in a `long`, if I may inquire? – Lew Bloch Mar 10 '17 at 00:13
  • 1
    @LewBloch, I do not handle, that's the trick. To avoid this, I calculate everything by modulo m from the very beginning. – TheDoctor Mar 10 '17 at 20:02