I'm trying to write an "BigInteger" implementation. BigInteger is an array of unsigned integers.
BigInteger_1 [0] ... BigInteger_1 [15];
I'm trying to perform addition of two BigInteger's.
using System;
namespace BigInt {
class MainClass {
static int MAX_SIZE = 16;
public static void Main () {
// First BigInteger
uint[] BigInteger_1 = new uint[MAX_SIZE];
BigInteger_1 [15] = 0xfffffffe;
// Second BigInteger
uint[] BigInteger_2 = new uint[MAX_SIZE];
BigInteger_2 [15] = 0x00000002;
// Third BigInteger
uint[] BigInteger_3 = new uint[MAX_SIZE];
// Perform an addition
BigInteger_3 = BigInteger_Add (BigInteger_1, BigInteger_2);
int i;
// Print BigInteger_1
for (i = 1; i < MAX_SIZE; i ++) {
Console.Write ("{0:x8}", BigInteger_1 [i]);
}
Console.WriteLine ();
// Print BigInteger_2
for (i = 1; i < MAX_SIZE; i ++) {
Console.Write ("{0:x8}", BigInteger_2 [i]);
}
Console.WriteLine ();
// Print BigInteger_3
for (i = 1; i < MAX_SIZE; i ++) {
Console.Write ("{0:x8}", BigInteger_3 [i]);
}
Console.WriteLine ();
}
public static uint[] BigInteger_Add (
uint[] BigInteger_1,
uint[] BigInteger_2
) {
uint[] BigInteger_3 = new uint[MAX_SIZE];
uint BigInteger_Carry = 0x00000000;
uint BigInteger_Limit = 0xffffffff;
int i;
// Loop through all integers
for (i = 1; i < MAX_SIZE; i ++) {
if (BigInteger_1 [i] + BigInteger_2 [i] >= BigInteger_Limit) {
Console.WriteLine ("Check {0} >= {1}", BigInteger_1 [i] + BigInteger_2 [i], BigInteger_Limit);
BigInteger_Carry = (BigInteger_1 [i] + BigInteger_2 [i]) - BigInteger_Limit;
BigInteger_3 [i] = BigInteger_Limit;
} else {
Console.WriteLine ("Check {0} < {1}", BigInteger_1 [i] + BigInteger_2 [i], BigInteger_Limit);
BigInteger_3 [i] = BigInteger_1 [i] + BigInteger_2 [i];
BigInteger_Carry = 0x00000000;
}
}
if (BigInteger_Carry != 0x00000000) {
BigInteger_3 [i] = BigInteger_Carry;
}
return BigInteger_3;
}
}
}
When I set up variables to:
// First BigInteger
BigInteger_1 [15] = 0xfffffffe;
// Second BigInteger
BigInteger_2 [15] = 0x00000001;
Then after executing I get this output (scroll to right):
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 4294967295 >= 4294967295
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000fffffffe
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffff
Which looks right. But when I set up variables to:
// First BigInteger
BigInteger_1 [15] = 0xfffffffe;
// Second BigInteger
BigInteger_2 [15] = 0x00000002;
I get this (scroll again):
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000fffffffe
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
So I can not make a comparison of a sum of two integers and a max value if sum is greater than max value. What I can (and must) do in this situation?
When you add two integers, if the sum is larger than the max representable value, it cannot be represented and operated on, by definition. Rolling over to zero when you exceed the max would be expected and is generally considered an error condition.
One inefficient way to accomplish what you're trying to would be to keep an extra integer in your BitInteger arrays you can internally maintain more than Max_Size precision.
You are trying to check if a + b > uint.MaxValue
which doesn't work when a + b
overflow.
Solution 1: bool carry = a > uint.MaxValue - b;
Solution 2: var result = a + b; bool carry = result < a || result < b;
User contributions licensed under CC BY-SA 3.0