Comparison of unsigned integers

0

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?

c#
asked on Stack Overflow Sep 3, 2015 by Kechup

2 Answers

1

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.

answered on Stack Overflow Sep 3, 2015 by xpda
1

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;

answered on Stack Overflow Sep 3, 2015 by Ivan Stoev

User contributions licensed under CC BY-SA 3.0