In assembly languages, there is usually an instruction that adds two operands and a carry. If you want to implement big integer additions, you simply add the lowest integers without a carry and the next integers with a carry. How would I do that efficiently in C or C++ where I don't have access to the carry flag? It should work on several compilers and architectures, so I cannot simply use inline assembly or such.
big integer addition without carry flag
You can use "nails" (a term from GMP): rather than using all 64 bits of a uint64_t when representing a number, use only 63 of them, with the top bit zero. That way you can detect overflow with a simple bit-shift. You may even want less than 63.
Or, you can do half-word arithmetic. If you can do 64-bit arithmetic, represent your number as an array of uint32_ts (or equivalently, split 64-bit words into upper and lower 32-bit chunks). Then, when doing arithmetic operations on these 32-bit integers, you can first promote to 64 bits do the arithmetic there, then convert back. This lets you detect carry, and it's also good for multiplication if you don't have a "multiply hi" instruction.
As the other answer indicates, you can detect overflow in an unsigned addition by:
uint64_t sum = a + b;
uint64_t carry = sum < a;
As an aside, while in practice this will also work in signed arithmetic, you have two issues:
- It's more complex
- Technically, overflowing a signed integer is undefined behavior
so you're usually better off sticking to unsigned numbers.
Does that
sum < a trick even work if sum = a + b + carry? –
Babb @FredOverflow: no, think for example
a=1, b=max, carry=1. you'll end up with 1 (+ a new carry of course), but 1 is not smaller than a. However, you could split it up in two additions. You can then simply add the carries of those additions for further processing safely, they'll be at most 2 in your higher-order byte. –
Hypertensive You can figure out the carry by virtue of the fact that, if you overflow by adding two numbers, the result will always be less than either of those other two values.
In other words, if a + b is less than a, it overflowed. That's for positive values of a and b of course but that's what you'd almost certainly be using for a bignum library.
Unfortunately, a carry introduces an extra complication in that adding the largest possible value plus a carry of one will give you the same value you started with. Hence, you have to handle that as a special case.
Something like:
carry = 0
for i = 7 to 0:
if a[i] > b[i]:
small = b[i], large = a[i]
else:
small = a[i], large = b[i]
if carry is 1 and large is maxvalue:
c[i] = small
carry = 1
else:
c[i] = large + small + carry
if c[i] < large:
carry = 1
else
carry = 0
In reality, you may also want to consider not using all the bits in your array elements.
I've implemented libraries in the past, where the maximum "digit" is less than or equal to the square root of the highest value it can hold. So for 8-bit (octet) digits, you store values from 0 through 15 - that way, multiplying two digits and adding the maximum carry will always fit with an octet, making overflow detection moot, though at the cost of some storage.
Similarly, 16-bit digits would have the range 0 through 255 so that it won't overflow at 65536.
In fact, I've sometimes limited it to more than that, ensuring the artificial wrap value is a power of ten (so an octet would hold 0 through 9, 16-bit digits would be 0 through 99, 32-bit digits from 0 through 9999, and so on.
That's a bit more wasteful on space but makes conversion to and from text (such as printing your numbers) incredibly easy.
Well, to be honest, that's pseudo-code. I don't think that
for statement is valid. But Python (or at least close to it) is brilliant for pseudo-code, as long as you stay away from those lambdas and maps and other weird things :-) I actually use a subset of Python for teaching basic programming skills. –
Iago There's a bug in your code: if
b[i] has the maximum value and carry is 1, then c[i] == a[i]. –
Zoogeography Oh. Also the fact that you didn't explicitly write a modulo operation anywhere, so
c[i] < a[i] is impossible unless these types somehow overflow and wrap-around. –
Beeves @Potatoswatter, that's exactly what the question is asking about (C-like
unsigned integers). –
Folsom Hurkyl, good catch, fixed the bug. On the other matter, dbaupp is correct. Wrapping is inherent in the data type, it doesn't have to be done explicitly. –
Iago
u can check for carry for unsigned types by checking, is result less than an operand (any operand will do).
just start the thing with carry 0.
Any operand will do — sort of, it only works for binary (2-operand) addition. So either operand will do. –
Beeves
analysis. for first addition max result is 2*(2^n-1) = 2^(n+1)-2, which means highest bit that can be set is bit n, which means max carry is 1. for next addition 2*(2^n-1) + 1 = 2^(n+1)-1, same thing. and so forth. –
Torietorii
Hm, all additions (except the first) will have three operands (a + b + carry). My gut tells me there are several corner cases lurking. –
Babb
@Fred: that's what the "+ 1" in the analysis is. –
Torietorii
If I understand you correctly, you want to write you own addition for you own big integer type.
You can do this with a simple function. No need to worry about the carry flag in the first run. Just go from right to left, add digit by digit and the carry flag (internally in that function), starting with a carry of 0, and set the result to (a+b+carry) %10 and the carry to (a+b+carry) / 10.
this SO could be relevant: how to implement big int in c
okay, did not read this in the question. sorry for that. but the link shows a base x implementation –
Rationale
@MareInfinitus That Q&A is "as a programming exercise". This is as a surrogate for assembly language. –
Beeves
what do you mean? OP wants to get his homework done? why should we not help him? –
Rationale
© 2022 - 2024 — McMap. All rights reserved.
unsigned x[8];for a 256-bit integer. – BabbuintN_ttypes (e.g.uint32_t) when you have a specific bit-size in mind. – Zoogeographyuint256_t. – Piaveunsigned int. – Zoogeography