20051227, 20:21  #1  
Dec 2005
2^{2}×23 Posts 
Implementing algorithms, did I do this right?
Hi, I'm writing a prime number finder application to learn computer programming (I know PHP but that is for webpages) in C#. So far I've implemented Trial Factoring, Sieve of Eratosthenes, Euclid's algorithm and the LucasLehemer test. Essentially I'm copying the methodology written on the math page and making my own improvements and in doing so learning various aspects of computer programming. I wrote the following implementation of the P1 factoring method and whenever I use it for all the numbers trial factoring can't factor, my application runs slower than before I implemented it. Running the LucasLehemer test on every mersenne number is 33% faster than running P1 factorization and then running the LucasLehemer test on the ones it couldn't find factors for.
Quote:
In that method (and in much of my application), I'm using the following BigInteger library and I'm writing my application using the Microsoft Visual C# 2005 Express Edition: http://www.codeproject.com/csharp/biginteger.asp By the way, does anyone know if there are any other libraries that I could use which are written in C#, or if there is some way to use a C++ library like GMP in a C# application? Last fiddled with by ShiningArcanine on 20051227 at 20:28 

20051227, 20:54  #2 
Aug 2002
Buenos Aires, Argentina
1,381 Posts 
I assume that in array "sieve" you have the first primes.
I've seen the following: 1) The external for is only executed once! What is its use? 2) Are you sure the "pow" function operates with BigIntegers? I know Java but not C#. Does the modulus operator operate with BigIntegers? Please check them. You would need to replace these lines by a modular exponentiation function. You could try to print your intermediate values and compare them to a known example, such as the one I've written for the p1 algorithm in the MersenneWiki. 
20051227, 21:30  #3  
Dec 2005
2^{2}·23 Posts 
Yes, the Sieve array is an array of prime numbers. Currently my application is calculating them to 100000.
Adding the P1 Factoring to my application slowed things down more than it sped them up so when I was troubleshooting I set the loop to execute once and then thought of asking for help. It is really supposed to execute mutiple times but it executed so slowly it is currently set to execute once. I wrote the pow method being used: Quote:


20051227, 21:45  #4  
Nov 2005
110000_{2} Posts 
Quote:
It's worth some time understanding this, since it should be one of the basic algorithms in your arsenal. Quote:
Hope this helps, John 

20051227, 22:44  #5  
Dec 2005
2^{2}·23 Posts 
Cool, thanks.
The example code from Prime Pages was really helpful in writing: Quote:


20051227, 22:47  #6  
Jun 2003
The Texas Hill Country
1089_{10} Posts 
Quote:


20051227, 23:46  #7  
Dec 2005
134_{8} Posts 
Quote:
I've contemplated writing my own data class/library for handling big integers, but before I do I'd like to find out what my options (if there are any besides the BigInteger class at Code Project) are before I try doing so. Is everyone sure that I implemented Pollard's P1 Factoring Method correctly in my C# method or is there something I missed? Is there any particularly good way of picking B1 or is starting at say 3, and then incrementing to say 10, the best way of picking B1? Last fiddled with by ShiningArcanine on 20051227 at 23:52 

20051227, 23:55  #8 
Aug 2002
Buenos Aires, Argentina
1,381 Posts 
I see that part of the problem is related to the fact that you perform a full exponentiation and then perform a modulus operation, while a faster method consists on interleaving multiplications and modulus operations, so the operands do not grow too much.
A faster method would be to forget using the builtin BigInteger class and use Montgomery multiplications using arrays of integers. This is the method that I use in my factoring Java applet. Last fiddled with by alpertron on 20051227 at 23:56 
20051228, 00:46  #9  
Dec 2005
2^{2}·23 Posts 
Quote:
I guess the best thing (short of starting over with C++ and GMP) will be to write my own BigInteger class and have it handle that internally. I'm not familar with Java so would you or anyone else know of a good site with information on Montgomery multiplications? I tried googling it but all of the top search results expected me to already know how the algorithm worked. Last fiddled with by ShiningArcanine on 20051228 at 00:59 

20051228, 01:26  #10 
Aug 2002
Buenos Aires, Argentina
1,381 Posts 
Montgomery multiplication is still a missing item on MersenneWiki, along with binary exponentiation, but you can start with this Wikipedia article.

20051228, 03:31  #11 
Dec 2005
134_{8} Posts 
I did some searching around and I found this:
http://mersenneforum.org/showpost.ph...75&postcount=7 Would someone please explain step one? I don't understand the concept of an inverse element. From what I know,  23^(1) = (1 / 23), but I neither know how to calculate (1 / 23) mod 100 nor have any clue where 100 came from (i.e. is 100 a constant?). 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Implementing Factoring Algorithms  Raman  Hobbies  45  20090511 05:11 
[URGENT] Pain: troubles on implementing SIQS sieve  Hermes  Factoring  27  20081014 13:54 
Implementing Chinese Remainder Theorem in C  ShiningArcanine  Software  3  20071117 05:55 
Implementing MPQS: SOS!  smoking81  Factoring  10  20071002 12:30 
Implementing the Irrationalbase discrete weighted transform  ColdFury  Software  14  20030620 01:26 