C, big numbers and storing them

Wiretron · 12-19-2007, 01:54 PM

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

matsp · 12-19-2007, 02:24 PM

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

Wiretron · 12-19-2007, 02:32 PM

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?

matsp · 12-19-2007, 02:40 PM

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

Wiretron · 12-19-2007, 02:56 PM

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)

matsp · 12-19-2007, 03:05 PM

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

Wiretron · 12-19-2007, 03:16 PM

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

matsp · 12-19-2007, 03:26 PM

Quote:

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

Wiretron · 12-19-2007, 03:29 PM

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

matsp · 12-19-2007, 03:32 PM

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

dwks · 12-19-2007, 03:43 PM

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

foxman · 12-19-2007, 05:59 PM

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.

matsp · 12-19-2007, 07:25 PM

Quote:

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

Wiretron · 12-21-2007, 10:35 AM

Quote:

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

mike_g · 12-21-2007, 10:44 AM

That would do modulo, like m = a % b. or at least thats what it looks like to me.

12-19-2007, 01:54 PM	#1
Wiretron 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
Wiretron is offline

12-19-2007, 02:24 PM	#2
matsp Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England Posts: 15,686	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.
matsp is offline

12-19-2007, 02:32 PM	#3
Wiretron 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?
Wiretron is offline

12-19-2007, 02:40 PM	#4
matsp Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England Posts: 15,686	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.
matsp is offline

12-19-2007, 02:56 PM	#5
Wiretron 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)
Wiretron is offline

12-19-2007, 03:05 PM	#6
matsp Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England Posts: 15,686	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.
matsp is offline

12-19-2007, 03:16 PM	#7
Wiretron 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.
Wiretron is offline

12-19-2007, 03:29 PM	#9
Wiretron 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
Wiretron is offline

12-19-2007, 03:32 PM	#10
matsp Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England Posts: 15,686	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.
matsp is offline

12-19-2007, 03:43 PM	#11
dwks Frequently Quite Prolix Join Date: Apr 2005 Location: Canada Posts: 7,629	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, etc. New project: nort
dwks is offline

12-19-2007, 05:59 PM	#12
foxman Chinese pâté Join Date: Jul 2007 Location: Canada Posts: 406	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.
foxman is offline

12-21-2007, 10:44 AM	#15
mike_g Wheres the lesbians? Join Date: Oct 2006 Location: UK Posts: 1,219	That would do modulo, like m = a % b. or at least thats what it looks like to me.
mike_g is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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