How can I check if an object representing a number is greater than another?

Question

I'm currently in the process of writing a class that can represent an infinitely large number (in theory). The constructor of this class creates the object from a string value, which is why the number could be of an extremely large, yet unknown, size.

The reason I started writing this class was because I wanted to be able to make a program that would be able to perform mathematical calculations with numbers of arbitrarily large size. Thus, I started writing a class that could handle values well over the standard ranges of integers, floats, doubles, (hopefully) decimals, etc.

Here are the declarations and the main constructor for the class:

/// <summary>
/// Creates a new instance of the LargeDecimal class, which represents either a whole or decimal number.
/// </summary>
/// <param name="number">The string representation of the number.</param>
public LargeDecimal(string value)
{
    string number = value.Replace(" ", "");
    if (number.Contains("-") && (number.IndexOf('-') == 0)) {
        number = number.Replace("-", "");
        IsNegative = true;
    }
    // Determining whether the number is whole or contains a decimal.
    if (number.IndexOf('.') == -1) {
        // Does not contain a decimal.
        for (int i = 0; i < number.Length; i++)
            wholeDigits.Add(int.Parse(number[i].ToString()));
        IsWhole = true;
    }
    else {
        // Still check if number is whole. Add all decimal digits.
        string[] numArray = number.Split('.');
        int sumOfDecimalDigits = 0;
        for (int i = 0; i < numArray[1].ToString().Length; i++)
            sumOfDecimalDigits += int.Parse(numArray[1].ToString()[i].ToString());
        if (sumOfDecimalDigits <= 0) {
            // Is a whole number.
            for (int i = 0; i < numArray[0].ToString().Length; i++)
                wholeDigits.Add(int.Parse(numArray[0].ToString()[i].ToString()));
            IsWhole = true;
        }
        else {
            // Is not a whole number.
            for (int i = 0; i < numArray[0].ToString().Length; i++)
                wholeDigits.Add(int.Parse(numArray[0].ToString()[i].ToString()));
            for (int i = 0; i < numArray[1].ToString().Length; i++)
                decimalDigits.Add(int.Parse(numArray[1].ToString()[i].ToString()));
            IsWhole = false;
        }
    }
}

The class is basically a representation of a number through two lists of type int, where one list represents the digits that make up the whole partition of the number, and the other list represents the digits that make up the decimal partition of the number (if applicable).

I have written an Add method which accepts two LargeDecimal objects, adds their values together, and returns a new LargeDecimal object with the sum as its value. Though incomplete, it does work with LargeDecimal objects that are whole numbers only, and are both positive or both negative (picture!).

I have realized that adding methods to compare two values (greater than / less than / equal to) would be extremely useful in calculations. However, I am not sure how to check whether the value of a LargeDecimal object is greater or less than the value of another LargeDecimal.

There are cases where I can just compare the amount of items in the wholeDigits list, but that is only when the amounts of items are different for both values. I am unsure about how to compare two numbers such as: 15498765423654973246 and 15499111137583924246.

And I think it will get more difficult if I will try and compare two fractional numbers: 8573819351.86931 and 8573809999.85999

I do not wish to use integer calculations in conjunction with place values (e.g. in the number 831, the value of the number 8 would be 8 * 100, the value of 3 would be 3 * 10, and the value of 1 would be 1 * 1), because I would like this class to be able to represent values of any given size and length and range (while an int cannot handle values up to 2147483647).

Any help regarding this would be highly appreciated! Thank you all!

Answer 1

I would start by implementing IComparable:

public class LargeDecimal : IComparable<LargeDecimal>

And the implementation would look like:

public int CompareTo(LargeDecimal other)
{
    if (other == null) return 1;
    if (ReferenceEquals(this, other)) return 0;

    if (IsNegative != other.IsNegative)
    {
        if (other.IsNegative) return 1;
        return -1;
    }

    int multiplier = (IsNegative) ? -1 : 1;

    if (wholeDigits.Count > other.wholeDigits.Count) return 1 * multiplier;
    if (wholeDigits.Count < other.wholeDigits.Count) return -1 * multiplier;

    for (int i = 0; i < wholeDigits.Count; i++)
    {
        if (wholeDigits[i] > other.wholeDigits[i]) return 1 * multiplier;
        if (wholeDigits[i] < other.wholeDigits[i]) return -1 * multiplier;
    }

    for (int i = 0; i < Math.Min(decimalDigits.Count, other.decimalDigits.Count); i++)
    {
        if (decimalDigits[i] > other.decimalDigits[i]) return 1 * multiplier;
        if (decimalDigits[i] < other.decimalDigits[i]) return -1 * multiplier;
    }

    if (decimalDigits.Count > other.decimalDigits.Count) return 1 * multiplier;
    if (decimalDigits.Count < other.decimalDigits.Count) return -1 * multiplier;

    return 0;
}

Update

This project was sitting on my brain at dinner tonight, so I went at it some more for fun. Not sure if this is helpful, but figured I'd share what I came up with.

First, I added fields to make the class actually work:

public bool IsNegative { get; private set; }
public bool IsWhole { get; private set; }

private List<int> wholeDigits;
private List<int> decimalDigits;

Second, I overrode the ToString method so the numbers display nicely:

public override string ToString()
{
    return string.Format("{0}{1}{2}{3}",
        (IsNegative) ? "-" : "",
        string.Join("", wholeDigits),
        (IsWhole) ? "" : ".",
        (IsWhole) ? "" : string.Join("", decimalDigits));
}

Then I implemented the Equals methods so they work as expected for a number type:

public static bool Equals(LargeDecimal first, LargeDecimal second)
{
    return ReferenceEquals(first, null) 
        ? ReferenceEquals(second, null) 
        : first.Equals(second);
}

public override bool Equals(object obj)
{
    return Equals(obj as LargeDecimal);
}

protected bool Equals(LargeDecimal other)
{
    return CompareTo(other) == 0;
}

public override int GetHashCode()
{
    unchecked
    {
        var hashCode = (wholeDigits != null)
            ? wholeDigits.GetHashCode() 
            : 0;
        hashCode = (hashCode * 397) ^ 
            (decimalDigits != null ? decimalDigits.GetHashCode() : 0);
        hashCode = (hashCode * 397) ^ IsNegative.GetHashCode();
        hashCode = (hashCode * 397) ^ IsWhole.GetHashCode();
        return hashCode;
    }
}

Next, I added some utility methods to help out with some upcoming tasks:

private void ResetToZero()
{
    wholeDigits = new List<int> { 0 };
    decimalDigits = new List<int> { 0 };
    IsWhole = true;
    IsNegative = false;
}

private void NormalizeLists()
{
    RemoveLeadingZeroes(wholeDigits);
    RemoveTrailingZeroes(decimalDigits);
    IsWhole = (decimalDigits.Count == 0 
        || (decimalDigits.Count == 1 && decimalDigits[0] == 0));
}

private void AddLeadingZeroes(List<int> list, int numberOfZeroes)
{
    if (list == null) return;

    for (int i = 0; i < numberOfZeroes; i++)
    {
        list.Insert(0, 0);
    }
}

private void AddTrailingZeroes(List<int> list, int numberOfZeroes)
{
    if (list == null) return;

    for (int i = 0; i < numberOfZeroes; i++)
    {
        list.Add(0);
    }
}

private void RemoveLeadingZeroes(List<int> list, bool leaveOneIfEmpty = true)
{
    if (list == null) return;

    var temp = list;

    for (int i = 0; i < temp.Count; i++)
    {
        if (temp[i] == 0)
        {
            list.RemoveAt(i);
        }
        else
        {
            break;
        }
    }

    if (leaveOneIfEmpty && !list.Any()) list.Add(0);
}

private void RemoveTrailingZeroes(List<int> list, bool leaveOneIfEmpty = true)
{
    if (list == null) return;

    var temp = list;

    for (int i = temp.Count -1; i >= 0; i--)
    {
        if (temp[i] == 0)
        {
            list.RemoveAt(i);
        }
        else
        {
            break;
        }
    }

    if (leaveOneIfEmpty && !list.Any()) list.Add(0);
}

Next, I added some constructors. A default that sets the number to '0', one that parses a string, and another that copies the values from another LargeDecimal:

public LargeDecimal() : this("0") { }

public LargeDecimal(string value)
{
    if (value == null) throw new ArgumentNullException("value");

    string number = value.Replace(" ", ""); // remove spaces
    number = number.TrimStart('0'); // remove leading zeroes
    IsNegative = (number.IndexOf('-') == 0); // check for negative
    number = number.Replace("-", ""); // remove dashes
    // add a zero if there were no numbers before a decimal point
    if (number.IndexOf('.') == 0) number = "0" + number; 

    // Initialize lists
    wholeDigits = new List<int>();
    decimalDigits = new List<int>();

    // Get whole and decimal parts of the number
    var numberParts = number.Split(new[] {'.'}, 
        StringSplitOptions.RemoveEmptyEntries);

    IsWhole = numberParts.Length == 1;

    // Add whole digits to the list
    wholeDigits.AddRange(numberParts[0].Select(n => int.Parse(n.ToString())));

    // Add decimal digits to the list (if there are any)
    if (numberParts.Length > 1 && 
        numberParts[1].Sum(n => int.Parse(n.ToString())) > 0)
    {
        numberParts[1] = numberParts[1].TrimEnd('0');
        decimalDigits.AddRange(numberParts[1].Select(n => int.Parse(n.ToString())));
    }

    NormalizeLists();
}

public LargeDecimal(LargeDecimal initializeFrom)
{
    wholeDigits = initializeFrom.wholeDigits
        .GetRange(0, initializeFrom.wholeDigits.Count);
    decimalDigits = initializeFrom.decimalDigits
        .GetRange(0, initializeFrom.decimalDigits.Count);
    IsWhole = initializeFrom.IsWhole;
    IsNegative = initializeFrom.IsNegative;
    NormalizeLists();
}

Then I implemented the Add and Subtract methods

public void Add(LargeDecimal other)
{
    if (other == null) return;

    if (IsNegative != other.IsNegative)
    {
        // Get the absolue values of the two operands
        var absThis = new LargeDecimal(this) {IsNegative = false};
        var absOther = new LargeDecimal(other) {IsNegative = false};

        // If the signs are different and the values are the same, reset to 0.
        if (absThis == absOther)
        {
            ResetToZero();
            return;
        }

        // Since the signs are different, we will retain the sign of the larger number
        IsNegative = absThis < absOther ? other.IsNegative : IsNegative;

        // Assign the difference of the two absolute values
        absThis.Subtract(absOther);
        wholeDigits = absThis.wholeDigits.GetRange(0, absThis.wholeDigits.Count);
        decimalDigits = absThis.decimalDigits.GetRange(0, absThis.decimalDigits.Count);
        NormalizeLists();
        return;
    }

    // start with the larger decimal digits list
    var newDecimalDigits = new List<int>();
    newDecimalDigits = decimalDigits.Count > other.decimalDigits.Count
        ? decimalDigits.GetRange(0, decimalDigits.Count)
        : other.decimalDigits.GetRange(0, other.decimalDigits.Count);

    // and add the smaller one to it
    int carry = 0; // Represents the value of the 'tens' digit to carry over
    for (int i = Math.Min(decimalDigits.Count, other.decimalDigits.Count) - 1; i >= 0; i--)
    {
        var result = decimalDigits[i] + other.decimalDigits[i] + carry;
        carry = Convert.ToInt32(Math.Floor((decimal) result / 10));
        result = result % 10;
        newDecimalDigits[i] = result;
    }

    var newWholeDigits = new List<int>();
    newWholeDigits = wholeDigits.Count > other.wholeDigits.Count
        ? wholeDigits.GetRange(0, wholeDigits.Count)
        : other.wholeDigits.GetRange(0, other.wholeDigits.Count);

    for (int i = Math.Min(wholeDigits.Count, other.wholeDigits.Count) - 1; i >= 0; i--)
    {
        var result = wholeDigits[i] + other.wholeDigits[i] + carry;
        carry = Convert.ToInt32(Math.Floor((decimal)result / 10));
        result = result % 10;
        newWholeDigits[i] = result;
    }

    if (carry > 0) newWholeDigits.Insert(0, carry);

    wholeDigits = newWholeDigits.GetRange(0, newWholeDigits.Count);
    decimalDigits = newDecimalDigits.GetRange(0, newDecimalDigits.Count);
    NormalizeLists();
}

public void Subtract(LargeDecimal other)
{
    if (other == null) return;

    // If the other value is the same as this one, then the difference is zero
    if (Equals(other))
    {
        ResetToZero();
        return;
    }

    // Absolute values will be used to determine how we subtract
    var absThis = new LargeDecimal(this) {IsNegative = false};
    var absOther = new LargeDecimal(other) {IsNegative = false};

    // If the signs are different, then the difference will be the sum
    if (IsNegative != other.IsNegative)
    {
        absThis.Add(absOther);
        wholeDigits = absThis.wholeDigits.GetRange(0, absThis.wholeDigits.Count);
        decimalDigits = absThis.decimalDigits.GetRange(0, absThis.decimalDigits.Count);
        NormalizeLists();
        return;
    }

    // Subtract smallNumber from bigNumber to get the difference
    LargeDecimal bigNumber;
    LargeDecimal smallNumber;

    if (absThis < absOther)
    {
        bigNumber = new LargeDecimal(absOther);
        smallNumber = new LargeDecimal(absThis);
    }
    else
    {
        bigNumber = new LargeDecimal(absThis);
        smallNumber = new LargeDecimal(absOther);
    }

    // Pad the whole number and decimal number lists where necessary so that both
    // LargeDecimal objects have the same count of whole and decimal numbers.
    AddTrailingZeroes(
        bigNumber.decimalDigits.Count < smallNumber.decimalDigits.Count
            ? bigNumber.decimalDigits
            : smallNumber.decimalDigits,
        Math.Abs(bigNumber.decimalDigits.Count - smallNumber.decimalDigits.Count));

    AddLeadingZeroes(smallNumber.wholeDigits,
        Math.Abs(bigNumber.wholeDigits.Count - smallNumber.wholeDigits.Count));

    var newWholeDigits = new List<int>();
    var newDecimalDigits = new List<int>();

    bool borrowed = false; // True if we borrowed 1 from next number
    for (int i = bigNumber.decimalDigits.Count - 1; i >= 0; i--)
    {
        if (borrowed)
        {
            bigNumber.decimalDigits[i] -= 1; // We borrowed one from this number last time
            borrowed = false;
        }

        if (bigNumber.decimalDigits[i] < smallNumber.decimalDigits[i])
        {
            bigNumber.decimalDigits[i] += 10; // Borrow from next number and add to this one
            borrowed = true;
        }

        // Since we're working from the back of the list, always add to the front
        newDecimalDigits.Insert(0, bigNumber.decimalDigits[i] - smallNumber.decimalDigits[i]);
    }

    for (int i = bigNumber.wholeDigits.Count - 1; i >= 0; i--)
    {
        if (borrowed)
        {
            bigNumber.wholeDigits[i] -= 1;
            borrowed = false;
        }

        if (bigNumber.wholeDigits[i] < smallNumber.wholeDigits[i])
        {
            bigNumber.wholeDigits[i] += 10;
            borrowed = true;
        }

        newWholeDigits.Insert(0, bigNumber.wholeDigits[i] - smallNumber.wholeDigits[i]);
    }

    if (absThis < absOther) IsNegative = !IsNegative;
    wholeDigits = newWholeDigits.GetRange(0, newWholeDigits.Count);
    decimalDigits = newDecimalDigits.GetRange(0, newDecimalDigits.Count);
    NormalizeLists();
}

And finally overrode the numeric operators:

public static LargeDecimal operator +(LargeDecimal first, LargeDecimal second)
{
    if (first == null) return second;
    if (second == null) return first;

    var result = new LargeDecimal(first);
    result.Add(second);
    return result;
}

public static LargeDecimal operator -(LargeDecimal first, LargeDecimal second)
{
    if (first == null) return second;
    if (second == null) return first;

    var result = new LargeDecimal(first);
    result.Subtract(second);
    return result;
}

public static bool operator >(LargeDecimal first, LargeDecimal second)
{
    if (first == null) return false;
    return first.CompareTo(second) > 0;
}

public static bool operator <(LargeDecimal first, LargeDecimal second)
{
    if (second == null) return false;
    return second.CompareTo(first) > 0;
}

public static bool operator >=(LargeDecimal first, LargeDecimal second)
{
    if (first == null) return false;
    return first.CompareTo(second) >= 0;
}
public static bool operator <=(LargeDecimal first, LargeDecimal second)
{
    if (second == null) return false;
    return second.CompareTo(first) >= 0;
}
public static bool operator ==(LargeDecimal first, LargeDecimal second)
{
    return Equals(first, second);
}

public static bool operator !=(LargeDecimal first, LargeDecimal second)
{
    return !Equals(first, second);
}

Thanks for the fun challenge!!

Answer 2

Assuming that this implementation looks something like this:

List<int> WholeList;
List<int> FactionalList;
bool IsNegative;

and they both grow away from the decimal point, then a comparison algorithm would go like this

1. First compare signs. Negative is always less than positive.
2. Compare lengths of WholeList, longer has larger magnitude (larger number is dependent on sign)
3. If WholeList.Count the same. Compare each digit starting with most significant (aka WholeList[Count-1] first), first that are different between numbers will determine larger magnitude.
4. If you make it into the FractionalList, and then run out of digits in one list. The number with the longer FractionalList will be the larger magnitude.