mersenneforum.org Implementing algorithms, did I do this right?
 Register FAQ Search Today's Posts Mark Forums Read

2005-12-27, 20:21   #1
ShiningArcanine

Dec 2005

5C16 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 Lucas-Lehemer 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 P-1 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 Lucas-Lehemer test on every mersenne number is 33% faster than running P-1 factorization and then running the Lucas-Lehemer test on the ones it couldn't find factors for.

Quote:
 Originally Posted by ShiningArcanine private static BigInteger P1(BigInteger number, UInt32 exponent, int[] sieve) { BigInteger a = 3; for (int b = 10, index = 0; b <= 10; b++, index = 0, a = 3) { while (sieve[index] < b) { for (int i = sieve[index]; i <= b; i *= sieve[index]) { a = pow(a, sieve[index]) % number; } index++; } a = pow(a, exponent) % number; if (a == 1) { return 1; } else if (gcd(a - 1, number) > 1) { return gcd(a - 1, number); } } return 1; }
Does anyone know what I did wrong? I've tried various values for b and the max value that it could go up to and setting them both at 10 made a quick search for prime numbers through all mersenne numbers less than 10^27 run less slow but still slower than it would be without using the method.

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 2005-12-27 at 20:28

 2005-12-27, 20:54 #2 alpertron     Aug 2002 Buenos Aires, Argentina 144610 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 p-1 algorithm in the MersenneWiki.
2005-12-27, 21:30   #3
ShiningArcanine

Dec 2005

22·23 Posts

Yes, the Sieve array is an array of prime numbers. Currently my application is calculating them to 100000.

Adding the P-1 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:
 Originally Posted by ShiningArcanine public static BigInteger pow(BigInteger number, BigInteger exponent) { BigInteger num = number; for (BigInteger i = exponent; i > 1; i--) { num *= number; } return num; }
It is the fastest way I could think of calculating powers of numbers. If anyone knows a faster way, please share it. I'd like to make this run as fast as it is possible in C#.

2005-12-27, 21:45   #4
John Renze

Nov 2005

24·3 Posts

Quote:
 Originally Posted by ShiningArcanine It is the fastest way I could think of calculating powers of numbers. If anyone knows a faster way, please share it.
You need to be using something called binary exponentation. It will drastically reduce the number of multiplications you have to do. You should be able to find it in a basic discrete math or number theory textbook. There is also a good explanation at http://primes.utm.edu/glossary/page....Exponentiation on the Prime Pages.

It's worth some time understanding this, since it should be one of the basic algorithms in your arsenal.

Quote:
 I'd like to make this run as fast as it is possible in C#.

Hope this helps,
John

2005-12-27, 22:44   #5
ShiningArcanine

Dec 2005

1348 Posts

Cool, thanks.

The example code from Prime Pages was really helpful in writing:

Quote:
 Originally Posted by ShiningArcanine public static BigInteger pow(BigInteger number, BigInteger exponent) { BigInteger r = 1, y = number, n = exponent; while (n > 1) { if ((n & 1) == 1) { r *= y; } n /= 2; y *= y; } return r * y; }
Unfortunately, using switching from looping mutiplications to binary exponentation actually hurt performance. I'm starting to suspect that the BigInteger class/library I'm using is the problem. Does anyone know a good data class/library for handling large integers that is written in C#?

2005-12-27, 22:47   #6
Wacky

Jun 2003
The Texas Hill Country

32×112 Posts

Quote:
 Originally Posted by ShiningArcanine I'm starting to suspect that the BigInteger class/library I'm using is the problem. Does anyone know a good data class/library for handling large integers that is written in C#?
Have you considered the possibility that "C#" is the problem?

2005-12-27, 23:46   #7
ShiningArcanine

Dec 2005

22×23 Posts

Quote:
 Originally Posted by Wacky Have you considered the possibility that "C#" is the problem?
While I'm positive that C++ is faster than C#, C# has a more PHP like syntax which reduces the learning curve as I have a few years of experience writing PHP. There is also the BigInteger class/library I'm using. Looking at it there are probably plenty of optimizations which could be made to speed things up. For instance, when debugging problems in my code the software debugger takes me to the BigInteger class/library and steps through each step done there. Since it handles large numbers, it uses an array of 32bit unsigned integers. In several places the debugger stepped me through, it does a loop for each item in the array. For small arrays this wouldn't be a problem, but when the array has 2000 items like the one I'm using (I tweaked the default setting), it really starts to hurt performance. It wouldn't be necessary to loop through each item if the class kept track of how many items are in the array it uses. There is also the class's modulo exponentation method (which should run faster being inside the class and all), which actually runs slower than the code I wrote outside the class, which does the same thing. Looking at the code, it does a Barrett Reduction with a bunch of other logic. I don't know much about Barrett Reductions but from what I've been reading it isn't particularly well optimized as it should run faster than what I wrote.

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 P-1 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 2005-12-27 at 23:52

 2005-12-27, 23:55 #8 alpertron     Aug 2002 Buenos Aires, Argentina 101101001102 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 built-in 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 2005-12-27 at 23:56
2005-12-28, 00:46   #9
ShiningArcanine

Dec 2005

5C16 Posts

Quote:
 Originally Posted by alpertron 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 built-in BigInteger class and use Montgomery multiplications using arrays of integers. This is the method that I use in my factoring Java applet.
.NET doesn't have a BigInteger class so I downloaded the one I'm using off the internet.

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 2005-12-28 at 00:59

 2005-12-28, 01:26 #10 alpertron     Aug 2002 Buenos Aires, Argentina 2·3·241 Posts Montgomery multiplication is still a missing item on MersenneWiki, along with binary exponentiation, but you can start with this Wikipedia article.
 2005-12-28, 03:31 #11 ShiningArcanine     Dec 2005 22×23 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?).

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Hobbies 45 2009-05-11 05:11 Hermes Factoring 27 2008-10-14 13:54 ShiningArcanine Software 3 2007-11-17 05:55 smoking81 Factoring 10 2007-10-02 12:30 ColdFury Software 14 2003-06-20 01:26

All times are UTC. The time now is 02:58.

Sat May 21 02:58:20 UTC 2022 up 37 days, 59 mins, 0 users, load averages: 1.84, 1.93, 1.63