Adding large numbers in C

[Sri]

How do you add an n-bit number in C?

Regards,
Sri

[Artie Gold]

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

[Walter Roberson]

In article <11**********************@v46g2000cwv.googlegroups .com>,
Sri <sr*******@gmail.com> 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

[Rajesh]

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

[Arndt Jonasson]

Artie Gold <ar*******@austin.rr.com> 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,

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

[Richard Heathfield]

(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)

[A.A]

using an array.

[code break]

How do you add an n-bit number in C?

Use some data strutures to handle large numbers.

[abhimanyu.v]

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.

[Walter Roberson]

In article <11**********************@v46g2000cwv.googlegroups .com>,
Rajesh <ra***********@gmail.com> 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 be
mod 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 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?

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

[Richard Heathfield]

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)

[Default User]

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

[Jordan Abel]

On 2006-03-01, Default User <de***********@yahoo.com> 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]

[Charles Krug]

On 2006-02-28, Sri <sr*******@gmail.com> 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.

[Richard Bos]

"Default User" <de***********@yahoo.com> 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

[Sri]

Thanks a bunch Richard! That was a very good explanation..

- Sri

[Rajesh]

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

[Richard Heathfield]

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[0], n[0], x[0] and c[0] 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[2] = !!(c[1] & 0x80000000UL); /* shift... */
c[1] <<= 1; /* ...the...*/
c[1] |= !!(c[0] & 0x80000000UL); /* ...carry... */
c[0] <<= 1; /* ...to the left. */
memcpy(m, x, sizeof m);
memcpy(n, c, sizeof n);
} while(c[0] != 0 || c[1] != 0 || c[2] != 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)