mersenneforum.org Question About Lucas-Lehmer Test (JAVA)
 Register FAQ Search Today's Posts Mark Forums Read

 2013-02-22, 01:26 #1 jmanes92   "James Manes" Feb 2013 Missouri 22 Posts Question About Lucas-Lehmer Test (JAVA) 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!
 2013-02-22, 02:40 #2 paulunderwood     Sep 2002 Database er0rr 7×13×53 Posts 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.
2013-02-22, 02:49   #3
jmanes92

"James Manes"
Feb 2013
Missouri

410 Posts

Quote:
 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.

 2013-02-22, 05:41 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2×5,179 Posts 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. Last fiddled with by LaurV on 2013-02-22 at 05:44
 2013-02-22, 09:10 #5 paulunderwood     Sep 2002 Database er0rr 7×13×53 Posts 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. Last fiddled with by paulunderwood on 2013-02-22 at 09:49
2013-02-22, 14:06   #6
J.F.

Jun 2008

23·32 Posts

Quote:
 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

2013-02-22, 20:34   #7
jmanes92

"James Manes"
Feb 2013
Missouri

22 Posts

Quote:
 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?

 2013-02-22, 21:30 #8 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2013-02-22, 21:59   #9
jmanes92

"James Manes"
Feb 2013
Missouri

22 Posts

Quote:
 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!

2013-02-22, 22:19   #10
ewmayer
2ω=0

Sep 2002
República de Califo

22×2,939 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 Mathsgirl Information & Answers 23 2014-12-10 16:25 MrRepunit Math 9 2012-05-10 03:50 storm5510 Math 22 2009-09-24 22:32 BMgf Programming 23 2003-12-09 08:52

All times are UTC. The time now is 04:19.

Wed Oct 4 04:19:00 UTC 2023 up 21 days, 2:01, 0 users, load averages: 1.12, 1.31, 1.28