понедельник, 30 августа 2010 г.

Длинное^короткое (возведение в степень)

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

Данную операцию можно решить лобовым перемножением исходного числа, а можно воспользоваться быстрым возведением в степень:
  1. BigInt pow(const BigInt &a, const int &N)
  2. {
  3.   BigInt res(1),cur = a;
  4.   int n = N;
  5.   while (n)
  6.   {
  7.     if (n&1)
  8.       res = res * cur;
  9.     cur = cur * cur;
  10.     n>>=1;
  11.   }
  12.   return res;
  13. }
* This source code was highlighted with Source Code Highlighter.

Стоит обратить внимание на то, что количество разрядов у результирующего числа очень быстро растет, поэтому нужно грамотно подбирать размерность массива digits в структуре BigInt.

4 комментария:

  1. что значит res(1)??

    ОтветитьУдалить
  2. это конструктор с параметром: http://www.firststeps.ru/dotnet/oopnet/r.php?18

    другими словами в переменную res кладем цифру 1

    ОтветитьУдалить
  3. тоесть res.digits[0]=1??

    ОтветитьУдалить
  4. Почти так. Во-первых, нужно обнулить содержимое массива digits. Во-вторых, нужно определить длину числа. В нашем случае передается цифра, значит длина числа будет 1. И вот уже в-третьих, то что вы написали.

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