Чтобы сделать калькулятор с нуля


Как личный вызов, я пытаюсь сделать очень простой калькулятор без использования целочисленными типами CLR и арифметических операций, но использовать только память. Идея была сделать то, что среда CLR/ОС делает. я придумал базовый счетчик, сложения и умножения, которая работает нормально, но умножение занимает много времени, чтобы вычислить (если я использую большое количество). Любые советы по улучшению кода для лучшей производительности?

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();
    }  
}

Редактировать: спасибо всем, отдельное спасибо @RobinGreen (я реализовал ваше решение, которое увеличило мою производительность резко) и @interjay за ссыль отличная книга (хотя и потребуется некоторое время, чтобы понять правильно ;) ) я тоже раньше кэш на основные операции для повышения производительности.

еще одна вещь, которую я узнал эти операции выполняются на аппаратном уровне. интересно, как? Также я не делал преобразование двоичного кода, потому что это потребует дополнительных расходов для преобразования десятичных чисел в двоичные и двоичных в десятичные. Также, если есть место для еще большего улучшения, пожалуйста, дайте мне знать.

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;
    }
}


1515
12
задан 9 мая 2011 в 09:05 Источник Поделиться
Комментарии
5 ответов

Для представления целых чисел используется строковое представление их как десятичные числа. Поэтому, чтобы сделать сложение и умножение, вы можете использовать те же алгоритмы, что вы учили в начальной школе:

Для того, добавьте цифр одна за другой справа налево, заботясь о переноске по пути.

Для умножения, preinitialize таблицу умножения все товары из цифр 0-9. Затем используйте стандартные длинные умножения, используя таблицу умножения на любое изделие из двух цифр, а ваше дополнение функция сверху добавить промежуточные продукты.

Делая это даст вам результаты намного быстрее, чем ваш текущий алгоритм: алгоритм берет показательное время в длину входных данных, в то время как эти версии имеют полиномиальное время.

Вы будете иметь более легкое время, если вы будете использовать двоичное представление чисел вместо десятичной: это позволит сделать операции на одной цифры гораздо проще, так как есть только два варианта для каждой цифры. Общие алгоритмы останутся прежними.

Кстати, это наверняка не так, как сложение и умножение выполняются в среде CLR. Среда CLR просто использует ваш процессор родной сложение и умножение инструкции, которые делают расчеты на аппаратном уровне.

3
ответ дан 9 мая 2011 в 09:05 Источник Поделиться


  1. Арифметика реализована аппаратно, а не операционной системы или среды CLR (за исключением вещей, которые нужно большое количество битов для представления - программное обеспечение используется, чтобы помочь с этим).

  2. Двоичный используется оборудование, не десятичная.

  3. Вы можете найти быстрых алгоритмов арифметики в Дасгупта, Пападимитриу и Вазирани (2006). Я рекомендую эту книгу, это замечательно.

10
ответ дан 9 мая 2011 в 09:05 Источник Поделиться

Это классный проект у вас есть, но производительность будет вонять. Правда в том, что вы делаете, очень отличается от того, что произойдет, когда вы выполните основную математику с + - / * в .Чистая.

Очевидный ответ заключается в использовании + - / *, но это будет противоречить цели, что вы делаете (что опять-таки, я думаю, что это действительно круто, песочница тип приложение).

Боюсь предположить машинного языка или АСМ, но ты найдешь, что такие вещи, как умножение тоже обрабатываются для вас.

0
ответ дан 9 мая 2011 в 09:05 Источник Поделиться

Считать, что каждое число-это массив символов и коврик нулей слева.

00000008
00000045

Затем обработать каждый столбец (единицы, десятки, сотни и т. д.) Отдельно. Сделать функцию, которая обрабатывает только один столбец в изоляции.

Добавить(слева:"8", вверху:"5", остаток:"0")
возвращает { значение: "3", остальные:"1" }

Затем выполните следующий столбец и т. д. И подобные длинные руки для каждой операции ( *, /, +, - ).

Оптимизацию с помощью перечисления вместо знаков для каждой цифры. Таким образом, вы можете использовать операторы Switch, если вы хотите, чтобы держаться подальше от математики.

перечисление цифр { ноль = 0, ТО = 1, и т. д. }

Просто мысли...

0
ответ дан 9 мая 2011 в 09:05 Источник Поделиться

Вычислительная сложность умножения, как это реализовано в этом примере ( как это), по крайней мере квадратичной. Необходимо определить умножение без использования дополнение реализации. Хотя концептуально это имеет смысл умножения определяются с точки зрения того, что это не требование. Вы регулируете arithmatic в символическом виде. Этот вопрос вы должны ответить, что символически как (пере)определить умножение оставаться линейной.

Первый намек не определить его через добавление реализация как у вас в вашем подходе.

0
ответ дан 10 мая 2011 в 03:05 Источник Поделиться