How to carry number from decimal to whole byte array

Question

Note: This is more of a logic/math problem than a specific C# problem.

I have my own class called Number - it very simply contains two separate byte arrays called Whole and Decimal. These byte arrays each represent essentially an infinitely large whole number, but, when put together the idea is that they create a whole number with a decimal part.

The bytes are stored in a little-endian format, representing a number. I'm creating a method called AddNumbers which will add two of these Numbers together.

This method relies on another method called PerformAdd, which just adds two arrays together. It simply takes in a pointer to the final byte array, a pointer to one array to add, and a pointer to the second array to add - as well as the length of each of them. The two arrays are just named "larger" and "smaller". Here is the code for this method:

    private static unsafe void PerformAdd(byte* finalPointer, byte* largerPointer, byte* smallerPointer, int largerLength, int smallerLength)
    {
        int carry = 0;

        // Go through all the items that can be added, and work them out.
        for (int i = 0; i < smallerLength; i++)
        {
            var add = *largerPointer-- + *smallerPointer-- + carry;

            // Stick the result of this addition in the "final" array.
            *finalPointer-- = (byte)(add & 0xFF);

            // Now, set a carry from this.
            carry = add >> 8;
        }

        // Now, go through all the remaining items (which don't need to be added), and add them to the "final" - still working with the carry.
        for (int i = smallerLength; i < largerLength; i++)
        {
            var wcarry = *largerPointer-- + carry;

            // Stick the result of this addition in the "final" array.
            *finalPointer-- = (byte)(wcarry & 0xFF);

            // Now, set a carry from this.
            carry = wcarry >> 8;
        }

        // Now, if we have anything still left to carry, carry it into a new byte.
        if (carry > 0)
            *finalPointer-- = (byte)carry;
    }

This method isn't where the problem lies - the problem is with how I use it. It's the AddNumbers method that uses it. The way it works is fine - it organizes the two separate byte arrays into the "larger" (larger meaning having a higher length of bytes) and "smaller". And then it creates pointers, it does this both for Whole and Decimal separately. The problem is with the decimal part.

Let's say we're adding the numbers 1251 and 2185 together, in this situation you would get 3436 - so that works perfectly!

Take another example as well: You have the numbers 4.6 and add 1.2 - once again, this works fine, and you get 5.8. The problem comes with the next example.

We have 15.673 and 1.783, you would expect 17.456, however, actually, this returns: 16.1456, and the reason for that is because it doesn't carry the "1".

So, this is my problem: How would I implement a way that knows when and how to do this? Here's the code for my AddNumbers method:

    public static unsafe Number AddNumbers(Number num1, Number num2)
    {
        // Store the final result.
        Number final = new Number(new byte[num1.Whole.Length + num2.Whole.Length], new byte[num1.Decimal.Length + num2.Decimal.Length]);

        // We're going to figure out which number (num1 or num2) has more bytes, and then we'll create pointers to smallest and largest.
        fixed (byte* num1FixedWholePointer = num1.Whole, num1FixedDecPointer = num1.Decimal, num2FixedWholePointer = num2.Whole, num2FixedDecPointer = num2.Decimal,
            finalFixedWholePointer = final.Whole, finalFixedDecimalPointer = final.Decimal)
        {
            // Create a pointer and figure out which whole number has the most bytes.
            var finalWholePointer = finalFixedWholePointer + (final.Whole.Length - 1);
            var num1WholeLarger = num1.Whole.Length > num2.Whole.Length ? true : false;

            // Store the larger/smaller whole number lengths.
            var largerLength = num1WholeLarger ? num1.Whole.Length : num2.Whole.Length;
            var smallerLength = num1WholeLarger ? num2.Whole.Length : num1.Whole.Length;

            // Create pointers to the whole numbers (the largest amount of bytes and smallest amount of bytes).
            var largerWholePointer = num1WholeLarger ? num1FixedWholePointer + (num1.Whole.Length - 1) : num2FixedWholePointer + (num2.Whole.Length - 1);
            var smallerWholePointer = num1WholeLarger ? num2FixedWholePointer + (num2.Whole.Length - 1) : num1FixedWholePointer + (num1.Whole.Length - 1);

            // Handle decimal numbers.
            if (num1.Decimal.Length > 0 || num2.Decimal.Length > 0)
            {
                // Create a pointer and figure out which decimal has the most bytes.
                var finalDecPointer = finalFixedDecimalPointer + (final.Decimal.Length - 1);
                var num1DecLarger = num1.Decimal.Length > num2.Decimal.Length ? true : false;

                // Store the larger/smaller whole number lengths.
                var largerDecLength = num1DecLarger ? num1.Decimal.Length : num2.Decimal.Length;
                var smallerDecLength = num1DecLarger ? num2.Whole.Length : num1.Decimal.Length;

                // Store pointers for decimals as well.
                var largerDecPointer = num1DecLarger ? num1FixedDecPointer + (num1.Decimal.Length - 1) : num2FixedDecPointer + (num2.Decimal.Length - 1);
                var smallerDecPointer = num1DecLarger ? num2FixedDecPointer + (num2.Decimal.Length - 1) : num1FixedDecPointer + (num1.Decimal.Length - 1);

                // Add the decimals first.
                PerformAdd(finalDecPointer, largerDecPointer, smallerDecPointer, largerDecLength, smallerDecLength);
            }

            // Add the whole number now.
            PerformAdd(finalWholePointer, largerWholePointer, smallerWholePointer, largerLength, smallerLength);
        }

        return final;
    }

Answer 1

The format you selected is fundamentally hard to use and I'm not aware of anyone who uses the same format for this task. For example, multiplication or division in that format must be very hard to implement.

Actually I don't think you store enough information to uniquely restore the value in the first place. How in your format stored representations are different for 0.1 and 0.01? I don't think you can distinguish those two values.

The issue you are facing is a lesser side-effect of the same problem: you store binary representations for decimal values and expect to be able to imply unique size (number of digits) of the decimal representation. You can't do it because when decimal overflow happens you are not guaranteed to get an overflow in your 256-based stored value as well. Actually it is more often not to happen simultaneously.

I don't think you can resolve this issue in any other way than explicitly storing something equivalent to the number of digits after the decimal point. And if you are going to do that anyway, why not switch to a much simpler format of a single BigInteger (yes, it is a part of the standard library although there is nothing like BigDecimal) and a scale? This is the format used by many similar libraries. In that format 123.45 is stored as pair of 12345 and -2 (for decimal position) while 1.2345 is stored as a pair of 12345 and -4. Multiplication in that format is almost a trivial task (given that BigInteger already implements multiplication, so you just need to be able to truncate zeros at the end). Addition and subtraction are less trivial but what you need is first match the scales of the two numbers using multiplication by 10, then use standard addition over BigInteger and then normalize back (remove zeros at the end). Division is still hard and you have to decide what rounding strategies you want support because division of two numbers is not guaranteed to fit into a number of a fixed precision.

Answer 2

If you just need BigDecimal in C# I would just suggest to find and use an existing implementation. For example https://gist.github.com/nberardi/2667136 (I am not the author, but it seems fine).

If you HAVE to implement it for any reason (school, etc) even then I would just resort to using BigInteger.

If you have to implement it with byte arrays... You can still benefit from the idea of using scale. You obviously have to take any extra digits after your operations such as "PerformAdd" and then carry them over to the main number.

However problems don't stop there. When you begin implementing multiplication you will run into more issues and you will have to start to mix decimal and integer part inevitably.

8.73*0.11 -> 0.9603 0.12*0.026 -> 0.00312

As you can see integer and decimal parts mix up and then decimal part grows into a longer sequence

however if you represent these as:

873|2 * 11|2 -> 873*11|4 -> 9603|4 -> 0.9603 12|2 & 26|3 -> 12*26|5 -> 312|5 -> 0.00312

these problems disappear.