# Using really big numbers!

• 02-22-2004
Machewy
Using really big numbers!
Hi,
I'm working on several projects in C++ that require the use of very large numbers. One of these projects is a RSA encrypter. Using this encryption method, one must use prime numbers that are over 'one-hundred-thousand' digits long. How would one go about preforming standard mathmatical functions in C++ with such large numbers?

Also, is it possible for a user to input a number as large as this, using scientific notation, in the 'cin' function?

Your help would greatly be appreciated.

regards,
machewy
• 02-22-2004
RoD
You wouldnt be getting the assignment if it was impossible. Hint: Integers wont work.
• 02-22-2004
Edward
A straightforward technique for arbitrary length numbers and arithmetic on those types is to store the data as strings of characters. Each character represents a part of the number such as a digit or a decimal. Then you write functions to manually perform arithmetic on those strings.

The principle is the same as you learned in school, you just have to perform every exact step instead of taking mental shortcuts.
• 02-22-2004
Codeplug
If you actually need to do arithmetic on large numbers, then GMP is one of the more popular libraries.
If you want to compile it yourself, you'll need MinGW.

gg
• 02-23-2004
Lurker
Codeplug - I would suggest letting him TRY to do it first, then use other, possibly more efficent, libraries later.
• 02-23-2004
Hunter2
Instead of storing 100,000 characters (100 kb), how bout creating a new integer datatype that uses 100 bytes (0.1 kb)? That'll store (+- 3.3e240) as opposed to (+- 9.9e99) using only 1/1000 the space. Then you'd just need to make string-to-UberInt conversion functions and vice versa, and different math operators etc., and you have a very large-capacity integer! That is, if you're willing to spend the time to figure out how to do it, of course :p
• 02-24-2004
Machewy
scientific notation
I want to be able to do this using scientific notation. Let's say a user inputs '2.4e600', how would I go about storing that number into a variable or multiple variables?

Any links would be most useful.

regards,
Machewy
• 02-24-2004
Hunter2
>>one must use prime numbersHmm, potential problem here... Chances are, if you're using scientific notation, you're rounding (since otherwise it would defeat the purpose of using it at all). If you're rounding, and you have say 1 decimal place or 2, then (whatever you have)e(anything > 2) won't be prime.

If you just want to 'store' the number/exponent though, I would expect that could be done pretty simply with 2 variables, or contained in a struct/class. In fact, a double might be all you need, since those seem to do scientific notation/rounding once you get high enough, although I'm not 100% sure about it.
• 02-25-2004
Machewy
Quote:

A straightforward technique for arbitrary length numbers and arithmetic on those types is to store the data as strings of characters. Each character represents a part of the number such as a digit or a decimal. Then you write functions to manually perform arithmetic on those strings.
Yes, but how do you preform arithmetic with strings? Any explanation or links would be useful here.

Thanks again,
Machewy
• 02-25-2004
Hunter2
You could start with addition. Pad the shorter number with zeros at the left; add the first digits (the ones digits), use mod to get the resulting digit and use integer-divide ((int)(sum / 10)) to get the carry; for the next, add the 2 digits and the carry, use mod to get resulting digit and use integer-divide to get the carry, etc.

Subtraction you can do similarly. Multiplication you can probably also do similarly, except you'd add the carry at the end instead of multiplying it in. Division, you start at the left side instead of the right. Square root, you can probably find an algorithm somewhere. Square = multiply by itself. Mod, you can do by doing divide and return the remainder, if you can't think of or find anything better. For !, just check if it == 0. Equality comparison is self-explanatory. < and > are fairly simple. Assignment is also self-explanatory. The only thing that might cause you problems would be the bitwise operators, such as >>, <<, &, |, and ^.