Thread: C, big numbers and storing them

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    145

    C, big numbers and storing them

    hi

    lets say i had a calculation, and the answer was 128 bit number; and I try and store this into an int, does the overflow occur when the answer was calculated, or does the answer overflow once I attempt to store into an int?

    the reason i ask is, I have a way of storing 128 bit numbers (in an array) but I have no idea how I can 'stream' an answer from a calculation (eg bignum * pow(bignum,bignum) into my methods.

    what would be helpul if is there is a way of 'streaming' a result from a calculation into an array - is there a way of doing this?

    if their isn't I see no alternative but to write my own versions of functions such as pow which handle big numbers

    thx

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If your numer only needs to be "big", but not exact, then you can use double - it has a range of about 300 digits, but only 53 bits of precision, because it's stored as two parts, an exponent and a mantissa. 53 bits gives you a number in the range of 15-18 digits precise [1]

    If you look at a large number, like 1,640,318, you can obviously store that as an integer. However, if you wanted "less space", you could store it as 1640 and 3, indicating that it is 1640 and three zeros. It's NOT PRECISE, but if you get the two parts big enough, it's OK for some pretty serious calculations.

    If this is not the right solutin for you, you need a "big math library", e.g. Gnu Multi Precision library [gmp], which does "infinite" preceision - as long as there's enough memory available, you can get as many digits as you like.


    [1] As long as you do sane calculations, it's possible to loose a lot of precision if you subtract similar numbers from each other, e.g. 1.23456789 - 1.23456780 looses about 7 digits of precision, because we can't know what the numbers should be at the rest of the number, and the entire first part of the number is being removed completely.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    145
    thx for the reply

    I need to have infinite precision, and I also need to implement everything (big number libraries) myself so the only solution I can see is the one I originally detailed where I stream the number into a big array.

    any ideas?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There are two models you can work along:
    1. Using binary numbers, e.g
    Code:
    struct int128
    {
          int highpart;
          unsigned lowparts[3];
    };
    The problem here is to get the logic right for transferring the carry from one integer to another. But the end result is faster.

    2. use "ascii" arithmetics. This has the advantage that you calculate on a decimal digit at a time [using 0..9], and it's easy to take any overflow or underflow carried to the next digit by comparing with 10 or 0 depending on the direction of the calculation. Your data is just an array of char or similar.

    Add and subtract are really easy to implement [just fill the number up with suitable number of zeros to make both the same length].

    Multiplication isn't too difficult either. Division [if you want to reasonably fast] will be the most difficult part.

    Of course, it would be easier to write the code to use these things in C++, because the C++ language allows you to define arithmetic operators for your own class types, so you can add two "int128" numbers together, for example.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    145
    Yeah I mean storing in an array of chars but you haven't really answered my question

    lets say I have a number which I can store in an int, however when i run it through a certain calculation I know the result will be a big number (eg 128bit)

    is there a way of doing the calculation using standard operators and the int data type and then somehow streaming the result of the calculation into my own array so I can can store it how I like?

    (has to be c btw)

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yes, you can use regular integers, but you got to, then, use "clever" logic to figure out when one of the first few calculations overflowed and ends up needing to add or subtract a carry from one number to the next. It's not terribly hard to do, but it's a bit more complex than using a byte array where the decision is very simple if you overflowed or not.

    And, no, you can't perform individual calculations using standard operators, you have to make function calls like this:
    Code:
        int128 a, b, c;
        setValue(b, "1234561297189271982719878192719");
        setValue(c, "1903918218928192819812091809182");
        Add(&a, &b, &c);
    This is why C++ would make life much easier, because you could just assign b and c using "=" and use a = b + c to perform the calculation - but you can't do that since you are strictly bound to C.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    145
    so in conclusion, regardless of where I want to use c or c++, i still have to find a way to my own addition etc which means writing functions to do it for me instead of using C's built in operators
    Last edited by Wiretron; 12-19-2007 at 03:26 PM.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Wiretron View Post
    when you say 'int128' numbers, does this mean a seperate class that holds a string?

    how do you then redefine the operator?

    thx
    What do you mean?
    In C, you have to write functions that support whatever non-standard types you use. If you want a struct int128 that holds some sort of "larger than long [long] integer", then you'll have to implement your own functions, and they will not use standard operators like +, - and =. Internally, the "add" function may well make use of standard operator +, -, = etc, but that's for the partial calculation of one array element, not the entire number.

    If you are referring to C++, you can define
    Code:
    int128 operator+(int128, int128)
    {
       // code that adds two 128 bit numbers together. 
    }
    I'm a bit unsure about what you were actually asking, so I may not have answered your question - if that's the case, please rephrase the question and I'll make my best to answer what you want to know.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Nov 2005
    Posts
    145
    Ok i think you've pretty much answered my q's, thanks for the help.

    the reason I was asking is because I'll need to implement % at some point which I don't know how to do, and i was hoping I could get away with using the built in version instead of writing my own

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The modulo operator should come out of the integer divide operator, which I presume you will also have to implement, which means that you can just do something like this:
    Code:
       m = a - ((a / b) * b);
    Or, let the divide function also return a modulo value if you prefer to do that [shouldn't be too difficult, as that's "whatever is left over of the input when you are finished dividing"].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    It should be mentioned that there are several big number libraries already out there. I suggest you have a look at GMP. It's extremely fast.

    gmplib.org
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    I found that one efficient way to implement "big number" is keeping the number in the natural base of the computer (in base 2 or, by extend, base 16).

    Also, you could/should consider writing some code in assembly. It has more flexibility on those kind of things than C. And, between you and me, assembly is quite fun.

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by dwks View Post
    It should be mentioned that there are several big number libraries already out there. I suggest you have a look at GMP. It's extremely fast.

    gmplib.org
    Yes, I mentioned that in the first post, but it was refused. I suspect that the task is part of a school project or some such, and thus needs to be done by the student himself, rather than using a ready-made library. It is however a good idea to use the GMPLIB to compare the results from your own implementation, to make sure that it's working right. And of course, you may be able to steal some ideas from it, without it being too obvious....

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Registered User
    Join Date
    Nov 2005
    Posts
    145
    Quote Originally Posted by matsp View Post
    The modulo operator should come out of the integer divide operator, which I presume you will also have to implement, which means that you can just do something like this:
    Code:
       m = a - ((a / b) * b);
    --
    Mats
    do you mind explaing how this works?

    surely ((a/b)*b) cancels down to (a), or does this work by getting rid of any decimal places when calculating (a/b) ?

    thx

  15. #15
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    That would do modulo, like m = a % b. or at least thats what it looks like to me.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Floating-Point Numbers
    By MindLess in forum C Programming
    Replies: 4
    Last Post: 06-24-2007, 11:45 PM
  2. Storing large numbers as an array
    By Rush152 in forum C Programming
    Replies: 9
    Last Post: 05-19-2006, 11:51 PM
  3. Reading all the numbes from a file and storing in an array
    By derek tims in forum C++ Programming
    Replies: 2
    Last Post: 04-02-2006, 03:01 PM
  4. Storing and printing matrices
    By stevedawg85 in forum C++ Programming
    Replies: 1
    Last Post: 03-20-2006, 08:57 AM
  5. storing numbers
    By kurz7 in forum C Programming
    Replies: 5
    Last Post: 01-16-2003, 08:49 AM

Tags for this Thread