Working with BIG integers

[sgpepe]

I was trying to write a program to factor large prime numbers, but I need to take the modulus of the numbers first. In order to take the moduli, I need to have integers. So I can't really work with doubles. static_cast also doesn't work. Does anyone know how i can find the remainder of two big numbers? I'll appreciate any comments/suggestions.

Thanks

 

[LyMc]

You pretty much have to do the division, as far as I know. You're best bet is probably one of the big number library packages like GUMP.

Lyle McElhaney

 

[JOLESEN]

How big (in bits) is a BIG integer ?

/JOlesen

 

[PerFnurt]

Here is a (not very fast, MFC dependant) template class representing integers of arbitrary length:

http://www.codeguru.com/algorithms/Calc.html

/Per
[sub]Nerdy signatures are as lame as the inconsistent stardates of STTNG.[/sub]

 

[lionelhill]

If you're really interested in prime numbers you can't even be thinking double or any sort of floating point, anyway. Because a prime number is only one away from a non-prime, and rounded to x decimal places, the two are going to be the same. Floating point is not suited to this sort of numerical work... (that's also why moduli make no sense in floating world).

Lots of ways to get a remainder from a big number division spring to mind.
If speed is of the essence for you, you might find it handy to do something like shift the number by which you wish to divide leftwards until it is more than half the size of the number you are dividing, and then subtract it.
Now you have a (much) smaller number to divide. Go back to the original divider and start shifting again. When you find that the number you are trying to divide is actually smaller than the divider, then it is the remainder.
This method avoids any division at all. Since it relies only on shifting, it will scale up for any size of number provided you keep carrying bits along.

But I am not a mathematician or numerical person, so I'm sure the writers of big number packages have got more efficient ways than this.

 

[sgpepe]

Yes, I solved most of the problems. I had to use a "specially-designed" program for dealing with big numbers. (Someone asked as to what a BIG number is; it's a number with more than 50 digits.) Thanks for all the tips though. I'll let you know if I find anything worth sharing.

 

[Clairvoyant1332]

> If speed is of the essence for you, you might find it handy to do something like shift the number by which you wish to divide leftwards until it is more than half the size of the number you are dividing, and then subtract it.
> Now you have a (much) smaller number to divide. Go back to the original divider and start shifting again. When you find that the number you are trying to divide is actually smaller than the divider, then it is the remainder.
> This method avoids any division at all. Since it relies only on shifting, it will scale up for any size of number provided you keep carrying bits along.

Isn't this just doing long division in binary (assuming both numbers are in an excoded binary format)? It seems to me that you can also determine the quotient from this process as well.

 

[lionelhill]

Well, yes it is, except that if you don't have a processor with a divide instruction capable of handling more than 64 bits, it gets quite hairy to handle an enormous divide properly. If you have to do the divide manually, or expand a divide to try to deal with numbers that don't fit in the processor, you may as well benefit from the situation by leaving out any parts of the process that you don't actually need. But I might be talking rubbish.

Incidentally, how would you go about dividing a (say) 64-byte binary number by a 24-byte binary prime using the processor's div instructions? I'm not very knowledgeable on this sort of stuff.

 

[Clairvoyant1332]

You know, I'm not sure offhand, but you just gave me a good idea on how to improve the bigint class I had written a while back. Here's a link to the source is it is currently: http://www.tcnj.edu/~bush/bigint.C. It's not the most efficient code in the world, but it works. I might have to rewrite things to store the numbers differently. Currently, I store the numbers as an array of decimal digits and do all the arithmetic in decimal. I had figured that converting really big numbers between decimal and binary/hex would be just as bad as doing division.

 

[lionelhill]

My feeling is that both of us probably need to get the relevant chapters of Knuth! Conversion between bases is one of the things he deals with. It's pretty heavy stuff, I find, wading through Knuth, but really really informative.