Thread: 200 digit integer... how?

I have a project that requires working with two hundred digit numbers. I am at a loss on how to do this. If someone could modify the source below I am sure I could implement it into my own project. Thanks.

-skeptik

/*
* factor.c -- Prompts user to enter an integer N. It prints out
* if it is a prime or not. If not, it prints out all of its
* proper factors.
*/

#include <stdio.h>

int main(void)
{
int n;
int lcv;
int flag; /* flag initially is 1 and becomes 0 if
we determine that n is not a prime */

printf("Enter value of N : ");
scanf("%d", &n);

for (lcv=2, flag=1; lcv <= (n / 2); lcv++) {
if ((n % lcv) == 0) {
if (flag)
printf("non-trivial factors of %d are:\n", n);

flag = 0;
printf("\t%d\n", lcv);
}
}
if (flag)
printf("%d is prime\n", n);
}

i have tried the GMP package... and it is VERY slow. i factored

2000000009 in 3.00 seconds with my current process

but using the GMP functions it took 912.00 seconds!

i am aware of the processing time that is involved in factoring huge numbers.

thanks for the feedback.

i guess i'll get to coding my own routines now.

thanks.

-skeptik

For that matter, why not just use TWO longs? 2^64 is ~ 10^19, which is going to take many hours to factor. If you REALLY wanted to go nuts, you could use 3 unsigned ints -- which would give you up to almost 8x10^28, or 4, which would give you 3x10^38.

You'd need 60 years with the fastest processors on the market just processing the conditional jumps, nevermind the math, associated with factoring 3x10^38.

So, pick 2, 3 or 4 unsigned longs, and accept that some problems are simply far beyond the capacity of a machine to compute in a practical timespan. Trying anything above 128 bit numbers is just insane, because it has NO application if you can't possibly have the time to compute it. At best, in your lifetime, you MIGHT be able to factor a 34 or 35 digit number. If you're lucky. So, set practical limiations on the algorithm, which will make it easier to code, AND make it useful.

Consider also, that every additional element you add will slow ALL your arithmetic down, because coding math for a higher bit count than your processor will natively support means you have to do multiple math operations to simulate a single one. So having four unsigned longs will be, at best, four times as complicated to do math on -- and probably more than that.

So you need to make the choice of how you lay out the algorithm, because there will be a tradeoff between speed and size, and if you try to handle data that is too large, not only will it be completely useless, it will slow down the smaller numbers which your algorithm might otherwise have been useful for.

Well from reading this thread I have concluded that DavidP's answer is probably the best. Make a 200 digit string and do math that way. Keep in mind that like the unsigned long int whatever[21] method of doing things you'll have to write your own math logic but anyone who thinks that is a hard process shouldn't be allowed to program. Using an array of longs not a good idea for the reason that it will more than likely cause some brain damage when trying to really think about the number that the array is holding. Char arrays all the way!

hey... thanks for all the great input. i am hard at work implementing DavidP's string idea.

i'll post the full source once completed if anyone would like to take a peek and give more input... optimization, better algorithm, etc.

thanks a lot.

Could you use bit fields to create a number big enough. Someone said that you needed 668 bits to hold a 200 digit number so would this work?
unsigned int Huge_number: 668;
I've never used bit fields before and don't know a whole lot about them, but I was just wondering.

Well, using that algorithm, of course it can't be done.

His algorithm requires SQRT(N) loops. Now, the largest 200 digit number is 1x10^201 - 1.

SQRT(1x10^201 - 1) ~ 3x10^100 passes through the loop.

Now, your best commercial computer today is ~2 GHz. This means it has 2x10^9 clock cycles per second.

Now, a loop takes more than one clock cycle to execute. For this, it is SIGNIFCANTLY more than one cycle execution, but let's assume the loop takes only one clock cycle per loop, which is the absolute minimum we could ever conceive. Then, we need 3x10^100 / 2x10^9 seconds, which works out to 1.5x10^91 seconds to perform 3x10^100 loops.

1.5x10^91 seconds = 4.75x10^83 years.

To try to put 4.75x10^83 years in perspective, our sun only has about 5 billion years of life left, which is 5x10^9 years.

The age of the universe is approximately 1x10^10 years. So even had this algorithm begun executing at the moment of the big bang, it would only be the smallest fraction of the way completed now.

http://forum.swarthmore.edu/dr.math/...w10.26.98.html

Are you sure your project requires working with 200 digit numbers?

I am using a Multiple Polynomial Quadratic Sieve (MPQS) factoring algorithm that works well with large integers. I've factored 56-digit numbers in under one minute on a 400-MHz Celeron with this method. So factoring large intergers is not hopeless. A 155-digit integer was factored in several months using distributed computing... something I plan on integrating into my project.

Actually, I believe 130 digits is the highest ever factored.

And, each additional digit increases the search space by a factor of TEN, so 131 digits would take ten times as long, 132 would take 100 times, 133 would take 1,000 times, etc.

here's a link to the highest number ever factored...

http://www.rsasecurity.com/rsalabs/c...ng/rsa155.html

that's a 155 digits.