7
\$\begingroup\$

I'm trying to teach myself some programming and, working through the Project Euler problems, I've come across some instances where I've needed numbers that are larger than will fit into an int or long variable. I know that existing libraries already accomplish this, but I figured it would be fun/worthwhile/educational to build the tools to handle these myself.

Project Goals:

  • Build a class to add or multiply numbers much larger than int or long.
  • Prioritize cleanliness, extensibility, and ease of integration with other Project Euler solutions.
  • Maximize algorithmic efficiency within these constraints.

Specific Questions:

  • Any feedback on style, structure, convention, etc.

  • Are there any profound improvements I could make to the algorithms.

  • Are there any features or techniques I should research to make this class more full-featured or comprehensive.

I appreciate any feedback, thank you.

public class MikesBigInt
{
    private List<int> digits;
    public int Length { get { return digits.Count; } }
    public int this[int index] { get { return digits[index]; } }

    public MikesBigInt()
    {
        digits = new List<int> { 0 };
    }
    public MikesBigInt(int n)
    {
        int l = n.ToString().Length;
        digits = new List<int>();
        for (int i = n.ToString().Length; i-- > 0;) {
            digits.Add(n.ToString()[i] - 48);
        }
    }
    public void Disp()
    {
        int l = digits.Count;
        for (int i = digits.Count; i-- > 0;) {
            Console.Write(digits[i]);
        }
        Console.WriteLine();
    }
    public int ToInt()
    {
        int res = 0;
        for (int i = 0; i < digits.Count; i++) {
            res += digits[i] * (int)Math.Pow(10, i);
        }
        return res;
    }

    public void Multiply(MikesBigInt n)
    {
        List<int> neoDigits = new List<int>();

        int xL = digits.Count - 1;
        int yL = n.Length - 1;

        for (int i = 0; i < xL + yL + 2; i++) {
            neoDigits.Add(0);
        }

        int carryTemp = 0;
        for (int di = 0; di < neoDigits.Count; di++) {
            int diVal = 0;
            for (int x = Math.Max(0, di - yL); x <= Math.Min(di, xL); x++) {
                diVal += (digits[x] * n[di - x]);
            }
            neoDigits[di] = (diVal + carryTemp) % 10;
            carryTemp = ((diVal + carryTemp) - (diVal + carryTemp) % 10) / 10;
        }
        digits.Clear();
        digits.AddRange(neoDigits);
        Trim();
    }
    public void Multiply(int n)
    {
        int carryTemp = 0;
        int l = digits.Count + n.ToString().Length;

        for (int i = 0; i < n.ToString().Length + 8; i++) {
            digits.Add(0);
        }
        for (int i = 0; i < l; i++) {
            int d = digits[i] * n + carryTemp;
            digits[i] = d % 10;
            carryTemp = (d - d % 10) / 10;
        }
        for (int i = carryTemp.ToString().Length; i-- > 0;) {
            digits.Add(carryTemp.ToString()[i] - 48);
        }
        Trim();
    }

    public void Add(MikesBigInt n)
    {
        int carryTemp = 0;

        for (int di = 0; di < Math.Min(digits.Count, n.Length); di++) {
            int diVal = digits[di] + n[di] + carryTemp;
            digits[di] = diVal % 10;
            carryTemp = (diVal - diVal % 10) / 10;
        }
        if (digits.Count > n.Length) {
            for (int di = n.Length; di < digits.Count; di++) {
                int diVal = digits[di] + carryTemp;
                digits[di] = diVal % 10;
                carryTemp = (diVal - diVal % 10) / 10;
            }
        }
        else if (n.Length > digits.Count) {
            for (int di = digits.Count; di < n.Length; di++) {
                int diVal = n[di] + carryTemp;
                digits.Add(diVal % 10);
                carryTemp = (diVal - diVal % 10) / 10;
            }
        }
        digits.Add(carryTemp);
        Trim();
    }
    public void Add(int n)
    {
        Add(new MikesBigInt(n));
    }

    private void Trim()
    {
        if ((digits[digits.Count - 1] == 0) && (digits.Count > 1)) {
            digits.RemoveAt(digits.Count - 1);
            Trim();
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Though this is surely more than you want to do, but you can store numbers a lot more densely: if you only need non-negative, you can just left extend a long with another to get MAX_LONG^2 states; if you need negatives you'll have to extend while respecting two's compliment. Note that this does make implementing BigInteger multiplication/division a lot harder. At the very least, you can change your List<int> to List<byte> to save a bit of memory for each digit, as you only need states 0-9, not (-2^31)-(2^31-1). (Side note: sorry for long comment) \$\endgroup\$
    – CAD97
    Jan 7, 2017 at 4:36

1 Answer 1

5
\$\begingroup\$

public MikesBigInt(int n)

There are quite a few improvements you can make here :

public MikesBigInt(int n)
{
    int l = n.ToString().Length;
    digits = new List<int>();
    for (int i = n.ToString().Length; i-- > 0;)
    {
        digits.Add(n.ToString()[i] - 48);
    }
}
  1. You are not using the l variable.

  2. You are constantly calling .ToString() on a variable that hasn't changed value, since the first call. You can add a helper string variable to improve performance as calling obviously it's better to call .ToString() just once. You are doing this in most of your methods

  3. The for loop is really weird, there is a designed place where you change the value of the looping variable (the last segment of the loop), why are you not using that ? + I don't see any reason for the inverse logic here.

  4. You should (when possible) specify the length of a list to avoid unnecessary memory allocation. new List<int>(length)

  5. Lastly the entire method can be replaced with some LINQ as it wont affect the performance all that much since you are working with ints only which are rather short in digits length :

    public MikesBigInt(int n)
    {
        digits = n.ToString().Select(c => (int) char.GetNumericValue(c)).ToList();
    }
    

    If the inversion logic is necessary for your code to work you can do :

    public MikesBigInt(int n)
    {
        digits = n.ToString().Select(c => (int)char.GetNumericValue(c)).Reverse().ToList();
    }
    

public int ToInt()

  1. This is weird method, I don't think it should be there at all. You should be using your BigInt only when the values are bigger than what int/long can handle, than what's the point of converting it to int ? Odds are that it will overflow the int too.

  2. You can use some LINQ here too :

    public int ToInt()
    {
        return digits.Select((t, i) => t * (int) Math.Pow(10, i)).Sum();
    }
    

Overall design

Arithmetic operations

  1. Any operations that you have should return some result instead of saving the value in the current instance of the object. When you add 2 integer values together you get some result right ? Your variable should be able to work as a normal data type.

  2. Having that said your operations should be methods in the first place, instead you should override some operators, which can be done like this :

    public static MikesBigInt operator +(MikesBigInt first, MikesBigInt second)
    {
        // do your logic here
    }
    
\$\endgroup\$
3
  • \$\begingroup\$ Thanks so much for your feedback, that's a lot of good information. I didn't know you could override basic operators, it makes utilizing the class so much cleaner! The LINQ cleans everything up a lot too, I'll need to read more about it. Regarding the LINQ statement in the ToInt() method, what tells the select method that 't' is the value and 'i' is the index? Is it just the format of '(t,i)' or is something more complicated happening? Thank you again for the review. \$\endgroup\$
    – Steelilack
    Jan 6, 2017 at 23:30
  • \$\begingroup\$ Yes this is correct,t is the element and i is the element's index, if you mouse over the .Select extension method you will see the description of the method : Projects each element of a sequence into a new form by incorporating the element's index. If there is anything else unclear feel free to ask me. \$\endgroup\$
    – Denis
    Jan 7, 2017 at 1:07
  • \$\begingroup\$ Answer review: English does not use a leading space with punctuation marks, including colons and question marks. :-) \$\endgroup\$ Jan 7, 2017 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.