суббота, 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. Программа считает длину неверно при умножении на 0. Поэтому если умножить 123 на 0, получится число 0 с длиной 3

    ОтветитьУдалить
    Ответы
    1. Да и не только при умножении на ноль, вообще часто ошибается при умножении на числа больше 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. А вообще спасибо за ресурс. Прога для дипломной считала ооочень долго. Пришёл на ваш ресурс в целях оптимизации моей длинной арифметики. Скорость возросла на порядки

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

      Удалить