mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2013-02-22, 01:26   #1
jmanes92
 
"James Manes"
Feb 2013
Missouri

48 Posts
Default 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!
jmanes92 is offline   Reply With Quote
Old 2013-02-22, 02:40   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2013-02-22, 02:49   #3
jmanes92
 
"James Manes"
Feb 2013
Missouri

22 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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!
jmanes92 is offline   Reply With Quote
Old 2013-02-22, 05:41   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2013-02-22, 09:10   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2013-02-22, 14:06   #6
J.F.
 
J.F.'s Avatar
 
Jun 2008

23×32 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
J.F. is offline   Reply With Quote
Old 2013-02-22, 20:34   #7
jmanes92
 
"James Manes"
Feb 2013
Missouri

22 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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?
jmanes92 is offline   Reply With Quote
Old 2013-02-22, 21:30   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2013-02-22, 21:59   #9
jmanes92
 
"James Manes"
Feb 2013
Missouri

48 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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!
jmanes92 is offline   Reply With Quote
Old 2013-02-22, 22:19   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×13×449 Posts
Default

Quote:
Originally Posted by J.F. View Post
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.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Question on Lucas Lehmer variant (probably a faster prime test) MrRepunit Math 9 2012-05-10 03:50
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas Lehmer test question? BMgf Programming 23 2003-12-09 08:52

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


Thu Dec 2 04:16:58 UTC 2021 up 131 days, 22:45, 0 users, load averages: 1.58, 1.34, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.