# Thread: C, big numbers and storing them

1. ## 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. 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

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. 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

5. 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. 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");
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

7. 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

8. Originally Posted by Wiretron
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

9. 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 &#37; 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. 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

11. 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

12. 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. Originally Posted by dwks
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

14. Originally Posted by matsp
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. That would do modulo, like m = a &#37; b. or at least thats what it looks like to me.