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

Длинное * короткое

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

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

Как видно алгоритм линейный. Для ускорения операций в строке 11 мы избежали использования операции взятия остатка от деления(%).

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

  1. Объясните пожалуйста как работает функция LevelUp и куда ее нужно вставить в программе

    ОтветитьУдалить
  2. Я так понимаю речь шла об операции деления длинного на длинное. Поэтому смотрите ответ в комментах на этот пост http://cppalgo.blogspot.com/2010/08/div-mod_29.html

    ОтветитьУдалить
  3. Умножение длинного числа на короткое является частным случаем умножения длинного на длинноЕ. Исправьте)

    ОтветитьУдалить
  4. Анонимный4 мая 2013 г., 13:44

    Программа считает длину неверно при умножении на 0. Поэтому если умножить 123 на 0, получится число 0 с длиной 3

    ОтветитьУдалить
    Ответы
    1. Анонимный8 мая 2013 г., 22:15

      Да и не только при умножении на ноль, вообще часто ошибается при умножении на числа больше 100. Фикс:
      BigInt operator * (const BigInt &a, const int &n)
      {
      BigInt res;
      res.amount = a.amount;

      int r = 0;
      int i;
      for (i=0;i<res.amount | r;i++)
      {
      res.digits[i] = a.digits[i] * n + r;
      r = res.digits[i]/osn;
      res.digits[i] -= r*osn;
      }
      res.amount = i;

      while (res.amount !=0 && !res.digits[res.amount-1]){
      --res.amount;
      }

      return res;
      }

      Удалить
    2. Анонимный8 мая 2013 г., 22:17

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

      Удалить
    3. 1. "вообще часто ошибается при умножении на числа больше 100" - все зависит от основании системы счисления(переменная osn). Если osn будет равен 1000, то операция умножения длинного на короткое валидна для любого n являющегося цифрой в данной системе счисления, т.е. n должно находится в интервале [0,999].
      2. если вам нужна быстрая длинная арифметика смотрите в сторону алгоритма Карацубы и быстрого преобразования Фурье.

      Удалить