By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 428,631 Members | 892 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,631 IT Pros & Developers. It's quick & easy.

# Adding large numbers in C

 P: n/a How do you add an n-bit number in C? Regards, Sri Feb 28 '06 #1
Share this Question
17 Replies

 P: n/a Sri wrote: How do you add an n-bit number in C? Regards, Sri Either by using a third party library (GIYF) or by using an array of unsigned longs (or unsigned long longs in C99 or if your compiler supplies it as an extension) and dealing with carry bits yourself. Past that, it's not a C question, but a more general programming question. HTH, --ag -- Artie Gold -- Austin, Texas http://goldsays.blogspot.com "You can't KISS* unless you MISS**" [*-Keep it simple, stupid. **-Make it simple, stupid.] Feb 28 '06 #2

 P: n/a In article <11**********************@v46g2000cwv.googlegroups .com>, Sri wrote: :How do you add an n-bit number in C? Me? I'd find a library that already implemented it. More generally, you start with an unsigned long, figure out how many bits are in that, chunk your numbers into sequences of the unsigned longs. Then start from the low end unsigned longs, figure out if adding the two would overflow. If it would not overflow, add the two and store the result and "carry a 0". If it would overflow, calculate what the result of the addition would be mod 2 to the number of bits in the chunk, store that, and "carry a 1". Go on to the next unsigned long pair to the left, only this time take the carry into account. Repeat. Hint: read carefully how C does addition of unsigned longs. There might be shortcuts you can use. -- "No one has the right to destroy another person's belief by demanding empirical evidence." -- Ann Landers Feb 28 '06 #3

 P: n/a Hello Walter, I didn't got the following logic from your last post : "it would overflow, calculate what the result of the addition would be mod 2 to the number of bits in the chunk" Also how to check whether the result of an operation would overflow.......we can't keep the result in an unsigned long variable and check it's value as it would have been wrapped around. Is there any way to know that without actual addition? Rajesh Feb 28 '06 #4

 P: n/a Artie Gold writes: Sri wrote: How do you add an n-bit number in C? Regards, Sri Either by using a third party library (GIYF) or by using an array of unsigned longs (or unsigned long longs in C99 or if your compiler supplies it as an extension) and dealing with carry bits yourself. Past that, it's not a C question, but a more general programming question. HTH, People complain about nonstandard abbreviations like "u" (and I usually agree), but I think abbreviations like GIYF and HTH are even more confusing when you're not able to decipher them. I knew HTH = "[i] hope this helps" but GIYF = "Google is your friend" I had to look up with Google. (I first thought it might actually be such a library.) Nothing wrong with your answer otherwise, of course. Feb 28 '06 #5

 P: n/a (For best results, view this article in a fixed-pitch font such as Courier.) Sri said: How do you add an n-bit number in C? Presumably you mean "add an n-bit number to an m-bit number", where at least one of the numbers - or perhaps the result - is too big to store in an int. Consider how you would add two 1-bit numbers, and for now let's ignore the concept of "carry", and just focus on a 1-bit result. 0 0 1 1 M + 0 + 1 + 0 + 1 N - - - - 0 1 1 0 M + N (no carry) Easy, right? Curiously, we can see that the results we get are just the same as if, instead of adding-without-carry, we had used the XOR operator. So, if carry doesn't matter, we can add two numbers by simply XORing them together. But carry /does/ matter. Let's look at the carry, then. 0 0 1 1 M + 0 + 1 + 0 + 1 N - - - - 0 1 1 0 M + N (no carry) (0) (0) (0) (1) M + N (carry only) Here, the carry figures are always zero UNLESS the M bit AND the N bit are both set. So now we have a way to calculate the carry. Let's do these steps on a couple of longer bitstrings, and see where it takes us. We'll use M = 11011001 and N = 01011011 (chosen at random, and remember these are binary strings, not ints!). M is longer than N, so I've left-padded N with a 0. If it were longer still, I'd just have used more 0s! Don't pay any attention to the fact that I've used 8-bit examples. If you have bitstrings longer than 8 bits, simply use an array of unsigned integers (personally, I use an array of unsigned char, although for performance reasons you might prefer types such as unsigned int or unsigned long), and keep your indices straight. So - here's the technique: 11011001 M + 01011011 N The first step is to get the result without carry. To do this, we XOR the two values together, storing the result in X: 11011001 M + 01011011 N -------- 10000010 X = M ^ N (partial result) The second step is to calculate the carry, storing the result in C: 11011001 M + 01011011 N -------- 01011001 C = M & N (partial result) Now, a carry bit indicates that we should "carry" the result over to the next column to the left. We can easily do that using a LEFT SHIFT. So let's do that, storing the result in S: 01011001 C -------- 10110010 S = C << 1 (partial result) If only this carry were 00000000, we'd have finished, and our result would be in X. But this carry is *not* 00000000. So to get our proper result, then, we need to add this shifted carry result back into our original XOR-style addition. How do we do this? In the same way as before, that's how. But this time we're adding X and S. If we're prepared to destroy M and N (hey, we can copy them first, right?), we can keep down the number of symbols. So M = X, and N = S 10000010 M + 10110010 N -------- 00110000 X = M ^ N (partial result) Now the carry: 10000010 M + 10110010 N -------- 10000010 C = M & N (partial result) The carry is not all-bits-zero, so we haven't finished yet. Let's shift the carry: 10000010 C -------- 100000100 S = C << 1 (partial result) Oops - we used a ninth bit (you have to be careful here - when you're shifting a value left and wish to preserve bits, you need to check the high bit to see if it's set; if so, you'll need to stretch your memory a little; this is easily accomplished using realloc or the like; if you don't know how to do efficient memory-stretching in C, yell and someone will no doubt explain. Right now, let's not get distracted). M = X (except that we'll need to left-pad it with a 0-bit - no big deal). N = S 000110000 M + 100000100 N --------- 100110100 X = M ^ N (partial result) Now the carry: 000110000 M + 100000100 N --------- 000000000 C = M & N (partial result) The carry is NOW all-bits-zero, so we're done! And the result is in X. Let's check the result. X = 100110100, which is 256 + 32 + 16 + 4 which is 308. Let's look at our original values: 11011001 which is 128 + 64 + 16 + 8 + 1 which is 217, and 01011011 which is 64 + 16 + 8 + 2 + 1 which is 91. And if my abacus doesn't deceive me, 217 + 91 is 308. So the result is correct. Don't forget to handle the concept of "sign". Personally, I prefer a "sign-and-magnitude" representation for this kind of thing - I have a struct which looks like this: { int sign; /* -1,0,1 */ size_t mag; /* number of significant bytes (at least 1) */ size_t cap; /* mallocated storage capacity, >= mag */ unsigned char *n; /* the pointer to the number byte array */ }; Clearly, n has to be pointed at a useful amount of storage. I use the "cap" member to record the number of bytes to which n points (the "capacity"), and "mag" to record the number of bytes used by the number currently being stored. If mag is in danger of exceeding cap, I realloc. Now, if either M or N is 0, then clearly the other value gives the result of the addition. Otherwise, if M is negative (M->sign < 0), I simply make it positive (temporarily!) by changing M->sign to 1, and then pass it to my subtraction routine. (Then, of course, I make it negative again.) Likewise for N. Incidentally, the subtraction routine does similar juggling, so if M and N are *both* negative, I pass -M and N to the subtraction routine, which then passes -M and -N to the addition routine! (You have to be careful about the parameter order, of course, but if you get it right, then it all comes out in the wash.) Multiplication is a snap if you're prepared to use a couple of loops - just keep shifting and adding the results of byte-by-byte multiplications until you run out of things to multiply. Division is another matter. It's a bit scary, and Knuth is your friend. Perhaps the easiest way to understand division is to reduce it to binary. If you do this, you will find that you need only know your 1-times table! Any bit sequence "goes into" any other bit sequence of the same length either once, or not at all. So to divide 100100101 by 110001, you just do this (each step shown separately): ..000000 110001 ) 100100101 110001 ..0000001 110001 ) 100100101 0110001 ------- 0011000 ..00000010 110001 ) 100100101 0110001 ------- 00110000 110001 ..000000101 110001 ) 100100101 0110001 ------- 001100001 000110001 --------- 000110000 So the result of 100100101 (293 dec) divided by 110001 (49 dec) is 101 (5 decimal) remainder 110000 (48 decimal). Check: 5 * 49 = 245, + 48 is 293. Wrap that up in unsigned chars, and you have division. But there are faster ways. See Knuth's "The Art of Computer Programming", Volume 2. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Feb 28 '06 #6

 P: n/a using an array. Feb 28 '06 #7

 P: n/a How do you add an n-bit number in C? Use some data strutures to handle large numbers. Feb 28 '06 #8

 P: n/a Hi, By large number I guess you mean number which cannot be stored in normal datatype like long long int etc. So the only thing left is either using Array or someother form of Data structure like link list which will point to the individual digit of the bug number. Now to add these thow number you only have to loop over one number and add individual digit offcourse you need to take care of the carry's. And store it again in the Array or same data structure that you have used to store the big number. I hope this has given you enough idea how to solve your problem. Feb 28 '06 #9

 P: n/a In article <11**********************@v46g2000cwv.googlegroups .com>, Rajesh wrote:Hello Walter, I didn't got the following logic from your last post : "it would overflow, calculate what the result of the addition would bemod 2 to the number of bits in the chunk" Are you familiar with modulo arithmetic, such as is provided by the C operator symbolized by the the percent sign (%) ? Do you have a good C reference book that describes -exactly- what happens when you do addition of unsigned integral values? Also how to check whether the result of an operation wouldoverflow.......we can't keep the result in an unsigned long variableand check it's value as it would have been wrapped around. Is there anyway to know that without actual addition? Some elementary algebra: If (X+Y) > ULONG_MAX then Y > (ULONG_MAX - X) No matter what value X has in the unsigned long range, ULONG_MAX - X is certain to be representable as an unsigned long. Substitute in X as 0 and as ULONG_MAX to see that this is true. (There happens to be a shortcut for this test -- but first you have to know -exactly- what happens when you do additions of unsigned long.) -- I was very young in those days, but I was also rather dim. -- Christopher Priest Feb 28 '06 #10

 P: n/a Arndt Jonasson said: I knew HTH = "[i] hope this helps" but GIYF = "Google is your friend" I had to look up with Google. So you knew intuitively that GIYF. I don't see your problem here. :-) -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Feb 28 '06 #11

 P: n/a Richard Heathfield wrote: Arndt Jonasson said: I knew HTH = "[i] hope this helps" but GIYF = "Google is your friend" I had to look up with Google. So you knew intuitively that GIYF. I don't see your problem here. :-) It's more polite than JFGI, at any rate. Brian Mar 1 '06 #12

 P: n/a On 2006-03-01, Default User wrote: Richard Heathfield wrote: Arndt Jonasson said: > > I knew HTH = > "[i] hope this helps" but GIYF = "Google is your friend" I had to > look up with Google. So you knew intuitively that GIYF. I don't see your problem here. :-) It's more polite than JFGI, at any rate. wait, GIYF isn't "Google it, you f***"? [politeness is in the eye of the beholder] Mar 1 '06 #13

 P: n/a On 2006-02-28, Sri wrote: How do you add an n-bit number in C? Regards, Sri Many ways. If n < sizeof(long)*CHAR_BITS, it's trivial. A fairly inefficient way is to create an array of convenient sized chunks and manually carry from one to the next. A much more efficient way takes advantage of the Chinese Remainder Theorem. Choose a technique, come up with an implementation, then come back when you've some code that doesn't work. Regardless of your technique, you'll need to figure out how to print them sensibly. Mar 1 '06 #14

 P: n/a "Default User" wrote: Richard Heathfield wrote: Arndt Jonasson said: I knew HTH = "[i] hope this helps" but GIYF = "Google is your friend" I had to look up with Google. So you knew intuitively that GIYF. I don't see your problem here. :-) It's more polite than JFGI, at any rate. But it still has the problem that it is a. more vendor-specific and b. less traditional than STFW. Richard Mar 1 '06 #15

 P: n/a Thanks a bunch Richard! That was a very good explanation.. - Sri Mar 1 '06 #16

 P: n/a Richard Heathfield wrote: (For best results, view this article in a fixed-pitch font such as Courier.) Sri said: How do you add an n-bit number in C? Presumably you mean "add an n-bit number to an m-bit number", where at least one of the numbers - or perhaps the result - is too big to store in an int. Consider how you would add two 1-bit numbers, and for now let's ignore the concept of "carry", and just focus on a 1-bit result. 0 0 1 1 M + 0 + 1 + 0 + 1 N - - - - 0 1 1 0 M + N (no carry) Easy, right? Curiously, we can see that the results we get are just the same as if, instead of adding-without-carry, we had used the XOR operator. So, if carry doesn't matter, we can add two numbers by simply XORing them together. But carry /does/ matter. Let's look at the carry, then. 0 0 1 1 M + 0 + 1 + 0 + 1 N - - - - 0 1 1 0 M + N (no carry) (0) (0) (0) (1) M + N (carry only) Here, the carry figures are always zero UNLESS the M bit AND the N bit are both set. So now we have a way to calculate the carry. Let's do these steps on a couple of longer bitstrings, and see where it takes us. We'll use M = 11011001 and N = 01011011 (chosen at random, and remember these are binary strings, not ints!). M is longer than N, so I've left-padded N with a 0. If it were longer still, I'd just have used more 0s! Don't pay any attention to the fact that I've used 8-bit examples. If you have bitstrings longer than 8 bits, simply use an array of unsigned integers (personally, I use an array of unsigned char, although for performance reasons you might prefer types such as unsigned int or unsigned long), and keep your indices straight. So - here's the technique: 11011001 M + 01011011 N The first step is to get the result without carry. To do this, we XOR the two values together, storing the result in X: 11011001 M + 01011011 N -------- 10000010 X = M ^ N (partial result) The second step is to calculate the carry, storing the result in C: 11011001 M + 01011011 N -------- 01011001 C = M & N (partial result) Now, a carry bit indicates that we should "carry" the result over to the next column to the left. We can easily do that using a LEFT SHIFT. So let's do that, storing the result in S: 01011001 C -------- 10110010 S = C << 1 (partial result) If only this carry were 00000000, we'd have finished, and our result would be in X. But this carry is *not* 00000000. So to get our proper result, then, we need to add this shifted carry result back into our original XOR-style addition. How do we do this? In the same way as before, that's how. But this time we're adding X and S. If we're prepared to destroy M and N (hey, we can copy them first, right?), we can keep down the number of symbols. So M = X, and N = S 10000010 M + 10110010 N -------- 00110000 X = M ^ N (partial result) Now the carry: 10000010 M + 10110010 N -------- 10000010 C = M & N (partial result) The carry is not all-bits-zero, so we haven't finished yet. Let's shift the carry: 10000010 C -------- 100000100 S = C << 1 (partial result) Oops - we used a ninth bit (you have to be careful here - when you're shifting a value left and wish to preserve bits, you need to check the high bit to see if it's set; if so, you'll need to stretch your memory a little; this is easily accomplished using realloc or the like; if you don't know how to do efficient memory-stretching in C, yell and someone will no doubt explain. Right now, let's not get distracted). M = X (except that we'll need to left-pad it with a 0-bit - no big deal). N = S 000110000 M + 100000100 N --------- 100110100 X = M ^ N (partial result) Now the carry: 000110000 M + 100000100 N --------- 000000000 C = M & N (partial result) The carry is NOW all-bits-zero, so we're done! And the result is in X. Let's check the result. X = 100110100, which is 256 + 32 + 16 + 4 which is 308. Let's look at our original values: 11011001 which is 128 + 64 + 16 + 8 + 1 which is 217, and 01011011 which is 64 + 16 + 8 + 2 + 1 which is 91. And if my abacus doesn't deceive me, 217 + 91 is 308. So the result is correct. Don't forget to handle the concept of "sign". Personally, I prefer a "sign-and-magnitude" representation for this kind of thing - I have a struct which looks like this: { int sign; /* -1,0,1 */ size_t mag; /* number of significant bytes (at least 1) */ size_t cap; /* mallocated storage capacity, >= mag */ unsigned char *n; /* the pointer to the number byte array */ }; Clearly, n has to be pointed at a useful amount of storage. I use the "cap" member to record the number of bytes to which n points (the "capacity"), and "mag" to record the number of bytes used by the number currently being stored. If mag is in danger of exceeding cap, I realloc. Now, if either M or N is 0, then clearly the other value gives the result of the addition. Otherwise, if M is negative (M->sign < 0), I simply make it positive (temporarily!) by changing M->sign to 1, and then pass it to my subtraction routine. (Then, of course, I make it negative again.) Likewise for N. Incidentally, the subtraction routine does similar juggling, so if M and N are *both* negative, I pass -M and N to the subtraction routine, which then passes -M and -N to the addition routine! (You have to be careful about the parameter order, of course, but if you get it right, then it all comes out in the wash.) Multiplication is a snap if you're prepared to use a couple of loops - just keep shifting and adding the results of byte-by-byte multiplications until you run out of things to multiply. Division is another matter. It's a bit scary, and Knuth is your friend. Perhaps the easiest way to understand division is to reduce it to binary. If you do this, you will find that you need only know your 1-times table! Any bit sequence "goes into" any other bit sequence of the same length either once, or not at all. So to divide 100100101 by 110001, you just do this (each step shown separately): ..000000 110001 ) 100100101 110001 ..0000001 110001 ) 100100101 0110001 ------- 0011000 ..00000010 110001 ) 100100101 0110001 ------- 00110000 110001 ..000000101 110001 ) 100100101 0110001 ------- 001100001 000110001 --------- 000110000 So the result of 100100101 (293 dec) divided by 110001 (49 dec) is 101 (5 decimal) remainder 110000 (48 decimal). Check: 5 * 49 = 245, + 48 is 293. Wrap that up in unsigned chars, and you have division. But there are faster ways. See Knuth's "The Art of Computer Programming", Volume 2. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Hello Richard, That was indeed very good approach but i have some issues to grasp the technique completely. Say i wanted to add two 64-bit numbers (left padded with 0's if required) and want to store the result in a 65-bit number. Let's say i don't have a data type of more than 32-bits in my system. So i've to use an array of 32-bit numbers to represent 64-numbers. I can perform the addition of lower two 32-bit numbers as per your method and let's say this produces a carry out. I had a question that how to incorporate this carry(if generated) to add the higher 32-bit numbers and produce the desired result and store it also in an array of 32-bit numbers. To be concise how to take care of the "carry in" while adding two numbers A and B. Can this technique be modified a bit to carry out this addition. Regards, Rajesh Mar 6 '06 #17

 P: n/a Rajesh said: Say i wanted to add two 64-bit numbers (left padded with 0's if required) and want to store the result in a 65-bit number. Where are you going to get a 65-bit data type, though? Let's say i don't have a data type of more than 32-bits in my system. So i've to use an array of 32-bit numbers to represent 64-numbers. Okay. I can perform the addition of lower two 32-bit numbers as per your method and let's say this produces a carry out. Sure. I had a question that how to incorporate this carry(if generated) to add the higher 32-bit numbers and produce the desired result and store it also in an array of 32-bit numbers. To be concise how to take care of the "carry in" while adding two numbers A and B. Can this technique be modified a bit to carry out this addition. The technique I presented already shows how to do this. But let me spell it out for your specific example, simplifying massively to make it as easy as I can. In the following code (which assumes 32 bits in an unsigned long), m, n, x and c refer to the LEAST significant part of the result: unsigned long m[] = { 0xA9876543UL, 0xBA987654UL, 0 }; unsigned long n[] = { 0xCBA98765UL, 0xDCBA9876UL, 0 }; unsigned long x[] = { 0, 0, 0 }; unsigned long c[] = { 0, 0, 0 }; do { for(i = 0; i < 2; i++) { x[i] = m[i] ^ n[i]; /* add, no carry */ c[i] = m[i] & n[i]; /* get the carry */ } c = !!(c & 0x80000000UL); /* shift... */ c <<= 1; /* ...the...*/ c |= !!(c & 0x80000000UL); /* ...carry... */ c <<= 1; /* ...to the left. */ memcpy(m, x, sizeof m); memcpy(n, c, sizeof n); } while(c != 0 || c != 0 || c != 0); Result is in x. This method can be extended easily to cope with arbitrarily-sized integers. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Mar 6 '06 #18

### This discussion thread is closed

Replies have been disabled for this discussion. 