суббота, 21 августа 2010 г.

Длинное * длинное

[Вся длинная арифметика]

Итак мы подошли к первой операции, реализацию которой можно считать не такой тривиальной, как в предыдущих случаях:
  1. BigInt operator * (const BigInt &a, const BigInt &b)
  2. {
  3.   BigInt res;
  4.   for (int i=0;i<a.amount;i++)
  5.   {
  6.     int r = 0;
  7.     for (int j=0;j<b.amount | r;j++)
  8.     {
  9.       res.digits[i+j] += a.digits[i] * b.digits[j] + r;
  10.       r = res.digits[i+j] / osn;
  11.       res.digits[i+j] -= r*osn;
  12.     }
  13.   }
  14.   int pos = a.amount + b.amount;
  15.   while (pos>0 && !res.digits[pos])
  16.     pos--;
  17.   res.amount = pos + 1;
  18.   return res;
  19. }
* This source code was highlighted with Source Code Highlighter.

Обратим внимание на строчку 11. Т.к. алгоритм квадратичный, то избежание использования операции взятия остатка от деления(%) дает прирост в скорости, более ощутимый, чем для линейных алгоритмов.

12 комментариев:

  1. почему то на 9ой строке ошибка вылезает

    ОтветитьУдалить
  2. а у меня не вылазеет =). Покажите код целиком.

    ОтветитьУдалить
  3. Объясните, для чего в этой строчке
    j<b.amount | r
    нужно побитовое "ИЛИ"?

    ОтветитьУдалить
  4. На самом деле здесь можно использовать как логическое или (||), так и побитовое(|). Логика от этого не меняется. Цикл в строке 7 повторяется до тех пор пока имеются необработанные разряды в числе b, либо до тех пор пока имеется перенос(r).

    ОтветитьУдалить
  5. Хм, так значит приоритет операций такой, что сначала выполняется сравнение "меньше", а потом логическая операция. Это интересно, а я наоборот думал, что сначала выполнится побитовое "ИЛИ" и никак не мог понять, что получится

    ОтветитьУдалить
    Ответы
    1. В любом случае если использовать побитовое или логическое ИЛИ, то оно всегда выполнится после операции МЕНЬШЕ(см. http://do.rksi.ru/library/courses/demo/t3_1p-1.gif). Возможно логическое ИЛИ здесь было бы более уместным, но я думаю уже все стало понятно, поэтому менять в реализации ничего не буду

      Удалить
  6. Если я не ошибаюсь, то оно верно работает только при a>b;
    Контр пример к решению 9 70 выдает 63

    ОтветитьУдалить
    Ответы
    1. Я думаю все написано правильно. У вас скорее всего некорректно работает ввод или вывод длинных чисел. Если вы считаете иначе, тогда присылайте ссылочку на ваш код(http://everfall.com/paste) и мы еще раз обсудим ваш комментарий

      Удалить
  7. А как насчет использования алгоритма Карацубы-Виноградова? Это будет О(n^Log1,6).

    ОтветитьУдалить
    Ответы
    1. Весь цикл статей на длинную арифметику на данный момент имеет вводный характер и ориентирован в первую очередь на понимание и реализацию. Быстрые алгоритмы надеюсь рассмотрим чуть позже.

      Мне известен алгоритм Карацубы, который работает со сложностью O(N^log2(3)) = O(N^1.6). Дайте ссылку на упомянутый вами алгоритм.

      Удалить
  8. res.digits необходимо проинициализировать нулями, иначе в 9 строке плюсовать будет вникуда!

    ОтветитьУдалить