12
\$\begingroup\$

As a personal challenge, I am trying to make a very basic calculator without using any CLR's integer and arithmetic operations, but to only use memory. The idea was to do what CLR/OS does. i came up with a basic counter, Addition and multiplication, which works fine but multiplication takes long time to compute (if i use big number). Any advice for code improvement for better performance?

partial class FastCalculator
{
    static LinkedList<Char> numbers = new LinkedList<Char>(new Char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' });
    static Dictionary<Char, LinkedListNode<Char>> fastNumbers = new Dictionary<Char,LinkedListNode<Char>>();
    static FastCalculator()
    {
        LinkedListNode<Char> zero = numbers.First;
        while (zero != null)
        {
            fastNumbers[zero.Value] = zero;
            zero = zero.Next;
        }
    }

    //static void Main(string[] args)
    //{
    //    try
    //    {
    //        System.Diagnostics.Debug.WriteLine(0 + " PlusOne is " + PlusOne("0"));
    //        System.Diagnostics.Debug.WriteLine(5 + " PlusOne is " + PlusOne("5"));
    //        System.Diagnostics.Debug.WriteLine(9 + " PlusOne is " + PlusOne("9"));
    //        System.Diagnostics.Debug.WriteLine(10 + " PlusOne is " + PlusOne("10"));
    //        System.Diagnostics.Debug.WriteLine(999 + " PlusOne is " + PlusOne("999"));
    //        System.Diagnostics.Debug.WriteLine(256 + " PlusOne is " + PlusOne("256"));
    //        System.Diagnostics.Debug.WriteLine("Multiply 999*256 =" + Multiply("999", "256"));
    //    }
    //    catch (Exception ex)
    //    {
    //        System.Diagnostics.Debug.WriteLine(ex.Message);
    //    }
    //}

    static string PlusOne(string num)
    {
        if (!string.IsNullOrEmpty(num))
        {
            LinkedList<Char> input = new LinkedList<Char>(num.ToCharArray());
            if (input.Last.Value != numbers.Last.Value)// not 9
            {
                input.Last.Value = fastNumbers[input.Last.Value].Next.Value;
                return LinkedListToString(input);
            }
            else // if 9
            {
                LinkedListNode<Char> in_last = input.Last;
                bool doCarryOver = true;
                while (in_last != null)
                {
                    if (in_last.Value == numbers.Last.Value)
                    {
                        if (doCarryOver)
                        {
                            in_last.Value = numbers.First.Value;
                            doCarryOver = true;
                        }
                    }
                    else
                    {
                        if (doCarryOver)
                        {
                            in_last.Value = fastNumbers[in_last.Value].Next.Value;
                            doCarryOver = false;
                        }                            
                    }
                    in_last = in_last.Previous;
                }
                if (doCarryOver)
                {
                    input.AddFirst(numbers.First.Next.Value);//1
                }
                return LinkedListToString(input);
            }            
        }

        return "0";
    }

    static string Add(string left, string right)
    {
        string zero = numbers.First.Value.ToString();
        if (string.IsNullOrEmpty(left) && string.IsNullOrEmpty(right))
        {
            return zero;
        }

        while (zero != right)
        {
            left = PlusOne(left);
            zero = PlusOne(zero);
        }
        return left;
    }

    static string Multiply(string left, string right)
    {
        string zero = numbers.First.Value.ToString();
        if (string.IsNullOrEmpty(left) && string.IsNullOrEmpty(right))
        {
            return zero;
        }

        string rtn = zero;

        while (zero != right)
        {
            rtn = Add(rtn, left);
            zero = PlusOne(zero);
        }

        return rtn;
    }

    private static string LinkedListToString(LinkedList<Char> num)
    {
        StringBuilder sb = new StringBuilder();
        if (num != null)
        {
            LinkedListNode<Char> first = num.First;
            while (first != null)
            {
                sb.Append(first.Value);
                first = first.Next;
            }
        }

        return sb.ToString();
    }  
}

Edit: Thank you everyone, special thanks to @RobinGreen (i implemented your solution which increased my performance drastically) and @interjay for referring to an excellent book (although will require some time to understand properly ;) ) I also used cache on basic operations to improve performance.

one more thing which i learned was these operations are done in hardware. i wonder how? Also i did not do binary conversion because it would require extra overhead to convert decimal to binary and binary to decimal. Also if there is room for even more improvement please let me know.

partial class FastCalculator
{
    static Dictionary<string, LinkedList<char>> operationCache = new Dictionary<string, LinkedList<char>>();
    static void Main(string[] args)
    {
        try
        {
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            watch.Start();
            System.Diagnostics.Debug.WriteLine(MultiplyVer2("5492012742638447789741521173787972956681294295296", "22867376956627844231881057173787972956681294295296"));
            watch.Stop();
            TimeSpan ts = watch.Elapsed;
            string elapsedTime = String.Format("{0:00}h:{1:00}m:{2:00}s.{3:00}ms",
                                    ts.Hours, ts.Minutes, ts.Seconds,
                                    ts.Milliseconds / 10);
            System.Diagnostics.Debug.WriteLine("elapsedTime " + elapsedTime);
        }
        catch (Exception ex)
        {
            System.Diagnostics.Debug.WriteLine(ex.Message);
        }
    }

    static string AddVer2(string left, string right)
    {
        string zero = numbers.First.Value.ToString();
        if (string.IsNullOrEmpty(left))
        {
            left = zero;
        }

        if (string.IsNullOrEmpty(right))
        {
            right = zero;
        }

        if (LengthLessThan(left, right)) //(left.Length < right.Length),make sure left is always greater
        {
            string tmp = left;
            left = right;
            right = tmp;
        }

        LinkedList<Char> rightIn = new LinkedList<Char>(right.ToCharArray());
        LinkedList<Char> leftIn = new LinkedList<Char>(left.ToCharArray());
        var leftInLast = leftIn.Last;
        var rightInLast = rightIn.Last;
        bool doCarryOver = false;

        while (leftInLast != null)
        {
            if (rightInLast != null)
            {
                LinkedList<Char> add = AddSymbols(leftInLast.Value, rightInLast.Value);
                if (doCarryOver)
                {   //since carry is always 1, we will do PlusOne
                    add = new LinkedList<Char>(PlusOne(LinkedListToString(add)).ToCharArray());
                }
                leftInLast.Value = add.Last.Value;
                if (add.Last.Previous != null)
                {
                    doCarryOver = true;
                }
                else
                {
                    doCarryOver = false;
                }
                rightInLast = rightInLast.Previous;
            }
            else
            {
                LinkedList<Char> add = AddSymbols(leftInLast.Value, numbers.First.Value);
                if (doCarryOver)
                {   //since carry is always 1, we will do PlusOne
                    add = new LinkedList<Char>(PlusOne(LinkedListToString(add)).ToCharArray());
                }
                leftInLast.Value = add.Last.Value;
                if (add.Last.Previous != null)
                {
                    doCarryOver = true;
                }
                else
                {
                    doCarryOver = false;
                }
            }

            leftInLast = leftInLast.Previous;
        }
        if (doCarryOver)
        {
            leftIn.AddFirst(numbers.First.Next.Value);//1
        }
        return LinkedListToString(leftIn);
    }

    static LinkedList<char> MultiplySymbols(char left, char right)
    {
        string inputStr = left + "*" + right;
        if (operationCache.ContainsKey(inputStr))
        {
            return operationCache[inputStr];
        }
        string zero = numbers.First.Value.ToString();
        string rightStr = right.ToString();
        string leftStr = left.ToString();
        string rtn = zero;
        while (zero != rightStr)
        {
            rtn = AddVer2(rtn, leftStr);
            zero = PlusOne(zero);
        }

        operationCache[inputStr] = new LinkedList<Char>(rtn.ToCharArray());
        return operationCache[inputStr];
    }

    static LinkedList<char> AddSymbols(char left, char right)
    {
        string inputStr = left + "+" + right;
        if (operationCache.ContainsKey(inputStr))
        {
            return operationCache[inputStr];
        }

        string zero = numbers.First.Value.ToString();
        string rightStr = right.ToString();
        string leftStr = left.ToString();
        while (zero != rightStr)
        {
            leftStr = PlusOne(leftStr);
            zero = PlusOne(zero);
        }
        operationCache[inputStr] = new LinkedList<Char>(leftStr.ToCharArray());
        return operationCache[inputStr];
    }

    static string MultiplyVer2(string left, string right)
    {
        string zero = numbers.First.Value.ToString();
        if (string.IsNullOrEmpty(left) || string.IsNullOrEmpty(right))
        {
            return zero;
        }

        if (LengthLessThan(left, right))//(left.length < right.length) make sure left is always greater
        {
            var tmp = left;
            left = right;
            right = tmp;
            System.Diagnostics.Debug.WriteLine("swapped");
        }

        string rtn = zero;
        LinkedList<Char> rightIn = new LinkedList<Char>(right.ToCharArray());
        LinkedList<Char> leftIn = new LinkedList<Char>(left.ToCharArray());
        LinkedList<string> result2sum = new LinkedList<string>();
        var rightInLast = rightIn.Last;
        while (rightInLast != null)
        {
            var leftInLast = leftIn.Last;
            System.Diagnostics.Debug.WriteLine("right symbol " + rightInLast.Value);
            LinkedList<Char> temp = new LinkedList<char>();
            String carry = string.Empty;
            while (leftInLast != null)
            {
                System.Diagnostics.Debug.WriteLine("left symbol " + leftInLast.Value);
                LinkedList<Char> mult = MultiplySymbols(leftInLast.Value, rightInLast.Value);
                if (!string.IsNullOrEmpty(carry))
                {
                    mult = new LinkedList<Char>(AddVer2(LinkedListToString(mult), carry).ToCharArray());
                    carry = string.Empty;
                }
                temp.AddFirst(mult.Last.Value);
                if (mult.Last.Previous != null)
                {
                    carry = mult.Last.Previous.Value.ToString();
                }

                leftInLast = leftInLast.Previous;
            }
            if (!string.IsNullOrEmpty(carry))
            {
                temp.AddFirst(Convert.ToChar(carry));
            }
            result2sum.AddFirst(LinkedListToString(temp));
            rightInLast = rightInLast.Previous;
        }
        var result = result2sum.Last;
        string sum = numbers.First.Value.ToString();//0
        string sumShift = string.Empty;
        while (result != null)
        {
            //string r = result.Value;
            System.Diagnostics.Debug.WriteLine("sum " + sum + " with " + result.Value + sumShift);
            sum = AddVer2(sum, result.Value + sumShift);
            sumShift = sumShift + numbers.First.Value.ToString();
            result = result.Previous;
        }
        return sum;
    }

    static bool LengthLessThan(string left, string right)
    {
        LinkedList<Char> rightIn = new LinkedList<Char>(right.ToCharArray());
        LinkedList<Char> leftIn = new LinkedList<Char>(left.ToCharArray());
        var leftInLast = leftIn.Last;
        var rightInLast = rightIn.Last;
        while (leftInLast != null && rightInLast != null)
        {
            leftInLast = leftInLast.Previous;
            rightInLast = rightInLast.Previous;
        }
        if (leftInLast == null && rightInLast == null)
        {
            return false;
        }

        if (leftInLast != null && rightInLast == null)
        {
            return false;
        }

        if (leftInLast == null && rightInLast != null)
        {
            return true;
        }

        return false;
    }
}
\$\endgroup\$

migrated from stackoverflow.com May 9 '11 at 22:19

This question came from our site for professional and enthusiast programmers.

3
\$\begingroup\$

To represent integers, you're using the string representation of them as decimal numbers. So to do addition and multiplication, you can use the same algorithms that you were taught in elementary school:

For addition, add the digits one by one from right to left, taking care of carry along the way.

For multiplication, preinitialize a multiplication table of all products of the digits 0-9. Then use standard long multiplication, using the multiplication table for any product of two digits, and your addition function from above to add together intermediate products.

Doing this will give you results much faster than your current algorithm: Your algorithm takes exponential time in the length of the inputs, while these versions take polynomial time.

You'll have an easier time if you use the binary representation of numbers rather than decimal: This will make operations on single digits much easier, since there are only two possibilities for each digit. The general algorithms will remain the same.

By the way, this is definitely not the way that addition and multiplication are performed by the CLR. The CLR simply uses your processor's native addition and multiplication instructions, which do the calculations in hardware.

\$\endgroup\$
10
\$\begingroup\$
  1. Arithmetic is implemented in hardware, not by the OS or the CLR (except for things that need a large number of bits to represent - software is used to help with those).
  2. Binary is used by the hardware, not decimal.
  3. You can find fast arithmetic algorithms in Dasgupta, Papadimitriou and Vazirani (2006). I recommend this book, it's great.
\$\endgroup\$
0
\$\begingroup\$

It's a cool project you've got; but the performance is going to stink. The truth is, what you are doing is very different from what would happen when you perform basic math with + - / * in .NET.

The obvious answer is to use the + - / * but that would defeat the purpose of what your doing (which again, I think it's a really cool sandbox type app).

I'm hesitant to suggest machine language or asm, but you'd find that things like multiplication are handled for you there too.

\$\endgroup\$
0
\$\begingroup\$

Consider that each number is an array of characters and pad zeros on the left.

00000008
00000045

Then handle each column (ones, tens, hundreds, etc) separately. Make a function that handles just one column in isolation.

Add(left:"8", top:"5", remainder:"0") returns { value: "3", remainder:"1" }

Then do the next column, etc. And similar long-hand for each operation ( *, /, +, - ).

Optimize further by using enumerations instead of characters for each digit. That way you can use switch statements if you want to stay away from math.

enum Digits { Zero = 0, One = 1, etc }

Just a thought...

\$\endgroup\$
0
\$\begingroup\$

The computational complexity of multiplication as it is implemented in that example ( as nice as it is), is at least quadratic. You need to define multiplication without using the addition implementation. Although conceptually it makes sense to have multiplication defined in terms of addition, it is not a requirement. You are handling arithmatic in a symbolic way. The question you have to answer is that symbolically how to (re)define multiplication to stay linear.

First hint is not to define it using the Addition implementation as you have in your approach.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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