CODEWITHSUNDEEP
c#algorithmnumbersprimes
marcob
marcob

Reputation: 1013

Write the biggest prime

I'm trying to solve the biggest prime programming praxis problem in C#. The problem is simple, print out or write to file the number: 257,885,161 − 1 (which has 17,425,170 digits)

I have managed to solve it using the amazing GNU Multiple Precision Arithmetic Library through Emil Stevanof .Net wrapper

var num = BigInt.Power(2, 57885161) - 1;
File.WriteAllText("biggestPrime.txt", num.ToString());

Even if all the currently posted solutions use this library, to me it feels like cheating. Is there a way to solve this in managed code? Ideas? Suggestions?

PS: I have already tried using .Net 4.0 BigInteger but it never ends to compute (I waited 5 minutes but it is already a lot compared to 50 seconds of the GMP solution).

Upvotes: 21

Views: 698

Answers (3)

Spatarel
Spatarel

Reputation: 242

What you what to achieve is computational-intensive. Visual C# and Visual Basic (and interpreted languages in general) are not designed for such a thing. Using the GMP is the proper thing to do, as it is implemented in pure C and highly optimized for execution speed.

If you choose to use managed code only, then be patient: Using .Net 4.0 BigInteger may take up to 100 times more time than using the GMP. To test this, you should compute 21,000, 210,000, 2100,000, 21,000,000 and 210,000,000 and see how much time it takes to compute each of these expressions using the .Net 4.0 Framework.

If it turns out that the needed time is too long, then you could try and make the computations yourself. You should use this algorithm to perform the exponentiation and then port from C++ to C# my own implementation of big integers multiplication or any other that you may find. However, there is no guarantee that you will achieve a significantly better performance, since you are still using managed code.

Upvotes: -5

borrible
borrible

Reputation: 17346

If you want to calculate this number using just multiplications (and an appropriate large integer library) you can look at cutting down on the number of calculations made. In the simple case you could repeatedly multiply by 2 (57885161 times) before deducing 1 but we can do it with significantly fewer multiplications.

Consider repeated squaring. This gives us 2, 22, (22)2 = 24, (24)2 = 28, etc... After squaring 25 times we would have calculated 2(225) = 233554432.

If we look at the binary representation of 57885161 we get 11011100110100000111101001. I.e. telling us we need (for 257885161) 2(225) * 2(224) * 2(222) etc... We can store all the required powers of 2 on our way to calculating the highest required one and then just do the final multiplications. So thats 25 + 13 large integer multiplications. We then just need to deduct 1 for the required value.

Upvotes: 4

reinder
reinder

Reputation: 2551

It's also more a cheat than a solution but I solved this using the IntX library

IntX.Pow(2, 57885161, MultiplyMode.AutoFht) - 1;

It ran approximately 6 minutes. Still this is not a real answer though. Would be interesting to see something "real".

EDIT: Using a C# Stopwatch I figured that the calculation only took 5 seconds, it's the process of ToString that takes extremely long.

Upvotes: 7

Related Questions