1

I have two simple java codes.The first one defines constant power as power = a.pow(b);

import java.math.BigInteger;    
public class FermatOne    
{    
    public static void main(String[] args)    
    {    
         BigInteger a = new BigInteger ("2");    
         BigInteger k = new BigInteger ("15");    
         BigInteger c = new BigInteger ("1");    
         int b = 332192810;    
         BigInteger n = new BigInteger ("2");    
         BigInteger power;    
         power = a.pow(b);    
         BigInteger exponent;    
         exponent = k.multiply(power);    
         BigInteger mod;    
         mod = exponent.add(c);    
         BigInteger result = n.modPow(exponent,mod);    
         System.out.println("Result is  ==> " + result);    
     }    
}

The second one defines constant power as power = BigInteger.ONE.shiftLeft(b)

import java.math.BigInteger;    
public class FermatOne    
{    
    public static void main(String[] args)    
    {    

         BigInteger k = new BigInteger ("15");    
         BigInteger c = new BigInteger ("1");    
         int b = 332192810;    
         BigInteger n = new BigInteger ("2");    
         BigInteger power;    
         power = BigInteger.ONE.shiftLeft(b);    
         BigInteger exponent;    
         exponent = k.multiply(power);    
         BigInteger mod;    
         mod = exponent.add(c);    
         BigInteger result = n.modPow(exponent,mod);    
         System.out.println("Result is  ==> " + result);    
     }    
}

Setting the memory flag -Xmx1024m in the command line the first code works fine , but for the second code I am getting error : java.lang.OutOfMemoryError :Java heap space

My question : What should I change in the second code to avoid java.lang.OutOfMemoryError ?

Improve this question
24
  • You are trying to get the result of 2^332192810? Sorry for disappointing you, but your computer can't handle that kind of computation. Commented Dec 8, 2011 at 10:55
  • 1
    But that's what the first code does and the poster is saying it works. Commented Dec 8, 2011 at 10:56
  • Do you really want to shift left by 332192810 bits? Commented Dec 8, 2011 at 10:58
  • 1
    @Max I think he still should not get OOM, as the a^b mod m code doesn't actually require computation of the whole a^b, and thus, in better implementation memory consumpltion must not be that high. Commented Dec 8, 2011 at 10:58
  • 1
    Btw, what's the output of the first method? I'm just curious to see the calculated number ;) Commented Dec 8, 2011 at 11:48

2 Answers 2

Reset to default
6

You're trying to calculate a number like 2 ^ (15 * 2 ^ 332192809). I don't know if you could even fit such a number in the universe!! Or maybe, the answer is simply... 42 ? ;-)

On a more serious note, you'll really have trouble, calculating this number. Encoded in bits, 15 * 2 ^ 332192810 would require almost a gigabyte by itself. Then raising 2 to that power again, I don't want to know...

On a more serious note, when you dig into the implementation of java.math.BigInteger, I think that you just run into such an error faster with the left shift, as that is implemented much more efficiently, than the power method. Having said this, have you tried to force garbage collection in your code, using System.gc()?

UPDATE: My original reasoning might've been wrong. 2 ^ 332192809 can be calculated with 1GB. And the overall result might be "modded" efficiently by java.math.BigInteger, although I believe that this calculation might take a while...

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

no,I am not trying to calculate that number...Could you tell me why the first code works fine ?
@pedja Here's additional explanation: that number 2 ^ (15 * 2 ^ 332192809) can be reordered to (2^4) ^ ((15 * 2 ^ 332192809)/4) => 16 ^ (15*2^(332192809-2)) => 16 ^(15 * 2^332192807) => 16 ^ (15 * (2^4) ^ (332192807/4))` ~~> 16 ^ (15 * 16 ^ 83048201). Now for comparison read this: en.wikipedia.org/wiki/Googolplex . Googolplex is a number 10 ^ (10 ^ 100). Carl Sagan estimated that writing a googolplex in numerals (i.e.,"10,000,000,000...") would be physically impossible,since doing so would require more space than the known universe provides. And your number is MUCH bigger.
@pedja: On what statement are you getting the error? On the left shift?
@Max: I think the point here is the mod at the end. So the result is not so big at all. I don't know if there's any math trick that can simplify the calculation, though
@Lukas Eder The poster is calculating exactly that in the first code section and it works, why is everyone in this thread ignoring that fact?
|
1

It's just a guess, but BigInteger.ONE.shiftLeft(332192810); will internally create an int array of length x + 10381025. Since an int is 4 bytes big you'll get about 40 mega bytes of data just for that one call. I assume the other calls copy that data around and thus you get that high a memory consumption.

Improve this answer

3 Comments

My next question was going to be which line doest the exception occur on?
@Thomas: BigInteger.pow() creates a lot more int[] to come up with the same resulting int[]... It's just a lot slower
But Thomas' point is the temporary array created in this operation is most likely to be the source of the out of memory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.