Thread: Using really big numbers!

  1. #1
    Registered User Machewy's Avatar
    Join Date
    Apr 2003
    Posts
    42

    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
    "All things come to an end"

  2. #2
    Redundantly Redundant RoD's Avatar
    Join Date
    Sep 2002
    Location
    Missouri
    Posts
    6,331
    You wouldnt be getting the assignment if it was impossible. Hint: Integers wont work.

  3. #3
    Registered User
    Join Date
    Feb 2004
    Posts
    46
    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.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    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.
    You can download pre-built binaries for Windows via ftp here: ftp://deltatrinity.dynip.com/gmp-4.1.2_DLL_SharedLibs/.

    gg

  5. #5
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    Codeplug - I would suggest letting him TRY to do it first, then use other, possibly more efficent, libraries later.
    Do not make direct eye contact with me.

  6. #6
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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
    Last edited by Hunter2; 02-23-2004 at 07:31 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  7. #7
    Registered User Machewy's Avatar
    Join Date
    Apr 2003
    Posts
    42

    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
    "All things come to an end"

  8. #8
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>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.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  9. #9
    Registered User Machewy's Avatar
    Join Date
    Apr 2003
    Posts
    42
    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
    "All things come to an end"

  10. #10
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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 ^.

    Tada, you have mathematical strings.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  11. #11
    Registered User Machewy's Avatar
    Join Date
    Apr 2003
    Posts
    42
    Thank-you Hunter2. You have been the most helpful to me. I'll try starting a small program that does that.

    Thanks-again,
    Machewy
    "All things come to an end"

  12. #12
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    No problem Good luck!
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  3. Problem with adding up numbers from a txt file
    By Leo12 in forum C Programming
    Replies: 1
    Last Post: 02-18-2009, 01:50 PM
  4. Big (and small) numbers...
    By swif in forum C Programming
    Replies: 6
    Last Post: 04-22-2005, 12:21 PM
  5. Program that prints numbers in columns
    By rayrayj52 in forum C++ Programming
    Replies: 12
    Last Post: 09-20-2004, 02:43 PM