Question About Lucas-Lehmer Test (JAVA)

[jmanes92]

Hello all! I'm currently at The University of Central Missouri and I am in a class with curtisc for MIPS assembly. He gave out an assignment for us to do which involves inputting an integer and having it checked via the Lucas-Lehmer test. I am having problems with it and am looking for some assistance.

I do not want hand holding or spoon feeding, I do want to learn, so I tried to code it in Java but it tells me everything is composite (lol). The following is a link to a screenshot of my code.

http://d.pr/i/eix1

Can someone show me what I am doing wrong? Some hints maybe?
Again I am asking for help on my Java version so that I do not get direct answers.

Thanks!

[paulunderwood]

The logic of your implementation of the LL algorithm is sound, but the types might be the root of the problem. I think you should be using the class BigInteger, because there will be integer and float overflow otherwise.

[jmanes92]

Originally Posted by paulunderwood

The logic of your implementation of the LL algorithm is sound, but the types might be the root of the problem. I think you should be using the class BigInteger, because there will be integer and float overflow otherwise.

Hmm yes. I did some modifications and it starts to become faulty at 31 (tells me it is composite).

Well I think everything is right, I just need to convert this over to MIPS.... problem is I don't know how I will overcome such an issue in assembly. I'll ask Dr. Cooper about it on Monday if the weather permits class to take place.

Thanks for your help!

[LaurV]

Hmmm... I know why you don't find any prime, it is because there should be a space between the quote sign and "is prime" (line 22). Otherwise your computer might decide to always take the else branch, which is orthographically right... you never know what computers might think... For other aspects, go with what Paul said.

[paulunderwood]

Looking at your code again, the "int" will not overflow, but the floats will and should be declared as BigInteger. You might want to put a check for reasonable values of p. The loop can be governed by 2 and p, saving subtractions. Yes, as was pointed out, there should be a space inserted into "is prime." at the beginning; A "." appended in the string "is composite". Also you are checking Mp, not p, for primality. To control the input loop you might want to ask the user to enter 0 if they want to quit.

[J.F.]

Originally Posted by paulunderwood

Looking at your code again, the "int" will not overflow, but the floats will and should be declared as BigInteger.

I would call it "loss of precision" rather than overflow.
Doubles typically have 64 bits. So once the number becomes large enough (~2^64), lower digits become rubbish because there are not enough bits to 'hold' all the digits. Overflow will not occur before 10^300 or something, once the exponent part within the double has reached its maximum value, as well as the mantissa.

http://en.wikipedia.org/wiki/Double-...g-point_format

[jmanes92]

Originally Posted by paulunderwood

Looking at your code again, the "int" will not overflow, but the floats will and should be declared as BigInteger. You might want to put a check for reasonable values of p. The loop can be governed by 2 and p, saving subtractions. Yes, as was pointed out, there should be a space inserted into "is prime." at the beginning; A "." appended in the string "is composite". Also you are checking Mp, not p, for primality. To control the input loop you might want to ask the user to enter 0 if they want to quit.

Honestly the correctness of the output strings do not matter. If I entered 7 and it found it correct it would just print 7isprime instead of 7 is prime, but I corrected it anyway. I am having a difficult time understanding Mp. My understanding is that the user inputs p to test if p is prime. Maybe I got this wrong?

[Dubslow]

User inputs p to test if 2^p-1 is prime (not p). The truth of the LL test requires the primality of p as an input, not as output.

[jmanes92]

Originally Posted by Dubslow

User inputs p to test if 2^p-1 is prime (not p). The truth of the LL test requires the primality of p as an input, not as output.

Ah alright! I finished my code and it works perfectly up till trying to calculate 31 because of the precision loss. I would use the BigInteger class but that will not help me because the assignment is to do this in MIPS Assembly, so I must ask Dr. Cooper about that in class Monday. Thanks for all your help everybody!

[ewmayer]

Originally Posted by J.F.

I would call it "loss of precision" rather than overflow.
Doubles typically have 64 bits. So once the number becomes large enough (~2^64), lower digits become rubbish because there are not enough bits to 'hold' all the digits. Overflow will not occur before 10^300 or something, once the exponent part within the double has reached its maximum value, as well as the mantissa.

IEEE64 doubles have 53 mantissa bits, which is the limiting factor when using them to store integers larger than the native 32-bit types. x86 register doubles have 64 mantissa bits, but the OP is targeting MIPS, not x86. And any C99-compliant compiler must support 64-bit ints, so that might be a better choice as a data type for tiny LL tests, up to M31. Of course for big LL tests we use floats, but in a rather different way.

Re. the original post - since the assignment is aimed at hardware instructions, Java seems a poor choice as a HLL code-prototyping tool, especially the emulated data types: I defy anyone to find a BigInteger type in the MIPS (or any other) ISA. Code it in C, then you can even have the compiler generate assembly for you which you can study. Or first get a working C LL-iteration loop using the native (hardware-supported) data types, then recode that in inline or standalone assembler, starting with the performance-critical part, the loop body.