mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2005-12-27, 20:21   #1
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22×23 Posts
Default 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
ShiningArcanine is offline   Reply With Quote
Old 2005-12-27, 20:54   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

1,381 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2005-12-27, 21:30   #3
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22·23 Posts
Default

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#.
ShiningArcanine is offline   Reply With Quote
Old 2005-12-27, 21:45   #4
John Renze
 
John Renze's Avatar
 
Nov 2005

1100002 Posts
Default

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#.
An admirable goal. Good luck!

Hope this helps,
John
John Renze is offline   Reply With Quote
Old 2005-12-27, 22:44   #5
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22·23 Posts
Default

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#?
ShiningArcanine is offline   Reply With Quote
Old 2005-12-27, 22:47   #6
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

108910 Posts
Default

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?
Wacky is offline   Reply With Quote
Old 2005-12-27, 23:46   #7
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

1348 Posts
Default

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
ShiningArcanine is offline   Reply With Quote
Old 2005-12-27, 23:55   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

1,381 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2005-12-28, 00:46   #9
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22·23 Posts
Default

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
ShiningArcanine is offline   Reply With Quote
Old 2005-12-28, 01:26   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

1,381 Posts
Default

Montgomery multiplication is still a missing item on MersenneWiki, along with binary exponentiation, but you can start with this Wikipedia article.
alpertron is offline   Reply With Quote
Old 2005-12-28, 03:31   #11
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

1348 Posts
Default

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?).
ShiningArcanine is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing Factoring Algorithms Raman Hobbies 45 2009-05-11 05:11
[URGENT] Pain: troubles on implementing SIQS sieve Hermes Factoring 27 2008-10-14 13:54
Implementing Chinese Remainder Theorem in C ShiningArcanine Software 3 2007-11-17 05:55
Implementing MPQS: SOS! smoking81 Factoring 10 2007-10-02 12:30
Implementing the Irrational-base discrete weighted transform ColdFury Software 14 2003-06-20 01:26

All times are UTC. The time now is 05:53.


Thu Oct 21 05:53:25 UTC 2021 up 90 days, 22 mins, 1 user, load averages: 1.24, 1.22, 1.18

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.