Арифметика многоразрядных чисел

тем самым  асимптотику приблизительно до O(n1.5). Эти алгоритмы были весьма популярны, когда операции с плавающей точкой осуществлялись очень медленно. Сейчас ситуация изменилась, и лучшие результаты показывают методы, использующие БПФ/БПХ.

     Преобразования  Фурье и Хартли можно делать и  не только в комплексных числах. Можно, например, перейти в кольцо целых чисел Zp. Если заменить . на первообразный  корень из единицы в таком кольце. то получится теоретико-числовое преобразование (NTT, Number Theoretic Transform). Похожим образом работает метод Шенхаге-Штрассена.

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

школьное  умножение, в то время как использование  БПФ/БПХ далеко за границами формулы (2), может привести к непредсказуемому переполнению, когда вместо 999.1 получится 998.1 и округление “незаметно” призойдет не к тому числу. Вычислительная практика показывает, что такое при надлежащем контроле точности(ошибка округления менее 0.2) не происходит, но никаких гарантий, в отличие от NTT, нет.

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

     Из-за того, что умножение по модулю гораздо медленнее, чем умножение чисел с плавающей точкой, даже профессионально написанное NTT уступает по времени БПФ/БПХ. Поэтому подобные методы используют лишь по достижении границ точности, когда базового типа не хватает для правильных вычислительных операций, а увеличивать основание уже невыгодно из-за роста количества цифр и связанных с этим затрат времени/памяти.

     У БПФ(БПХ)-умножения и NTT есть одно важное преимущество перед другими методами. Если одно число умножается на несколько  других – его преобразование можно вычислить лишь один раз и запомнить. Все следующие умножения будут требовать 2 преобразования вместо трех.

     Школьное  умножение, методы “разделяй-и-властвуй”  и алгоритм Шенхаге-Штрассена не позволяют сделать ничего подобного.

     Принципиально другого подхода требуют разреженные числа и многочлены, где почти все коэффициенты равны нулю. Они возникают во множестве практических задач и рассмотренные методы для них будут малоэффективными. Существуют специальные алгоритмы, которые учитывают разреженность при хранении таких объектов и операциях с ними. Они, однако, выходят за пределы данного обзора. 
 
 
 
 
 
 
 
 

Литература

     1.Котов  В.М., Волков И.А., Лапо А.И. «Информатика.Методы  алгоритмизации.» М.: Нар. асвета, 2000.-300с.: ил.

     2.Кантор  И. «Большие числа и операции с ними» сайт narod@rambler.ru 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Приложения:

     Приложение 1:

     ………………………………………….

     If n>m then

         k:=n

         else

        k:=m;

       k:=k+1;

       begin

           for i=1 to k do

           c[i]:=0;

       end;

     begin

           for i=1 to k do

     c[i]:=a[i]+b[i]+c[i];

     if c[i]>=10 then

     c[i+1]:= c[i+1]+1;

     c[i]:=mod(c[i],10);

     end;

     if c[k]=0 then

     k:=k-1;

     ………

     Приложение  2:

     ………

     Begin

      For i:=1 to n do

         C[i]:=a[i]-b[i];

        begin

              If c[i]<0 then

               c[i]:=c[i]+10;

               c[i+1]:=c[i+1]-1;

         end;

     End;

     While c[n]=0

     n: =n-1

     ……….. 
 
 
 

     Приложение 3:

     …………

{Процедура обнуления длинного числа}

Procedure Zero(Var A : DlChislo);

Var I : Integer;

  Begin

    For I := 1 To NMax Do A[I] := 0;

  End;

{Функция определения  количества цифр в записи длинного  числа}

Function Dlina(C : DlChislo) : Integer;

Var I : Integer;

Begin

   I := NMax;

   While (I > 1) And (C[I] = 0) Do I := I - 1;

   Dlina := I

End;

{Процедура печати  длинного числа}

Procedure Print(A : DlChislo);

Var I : Integer;

Begin

    For I := Dlina(A) DownTo 1 Do Write(A[I] : 1);

    WriteLn

End;

{Процедура преобразования  длинного числа в массив цифр}

Procedure Translate(S : String; Var A : DlChislo;

                    Var OK : Boolean);

Var I : Word;

Begin

   Zero(A); I := Length(S); OK := True;

   While (I >= 1) And OK Do

   Begin

      If S[I] In ['0'..'9']

      Then A[Length(S) - I+ 1] := Ord(S[I]) - 48

      Else OK := False;

      I := I - 1

   End

End;

Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);

Var I, J : Integer; P : Digit; VspRez : 0..99;

 Begin

  Zero(C);

  For I := 1 To Dlina(A) Do

  Begin P := 0;

        For J := 1 To Dlina(B) Do

        Begin

          VspRez := A[I] * B[J] + P + C[I + J - 1];

          C[I + J - 1] := VspRez Mod 10;

          P := VspRez Div 10

        End;

        C[I + J] := P

   End

End;

{Основная программа}

Begin

   Repeat {повторяем  ввод, пока число не будет введено  правильно}

     Write('Введите первый множитель: ');

     ReadLn(S); Translate(S, M, Logic)

   Until Logic;

   Repeat

     Write('Введите  второй множитель: ');

     ReadLn(S); Translate(S, N, Logic)

   Until Logic;

   Multiplication(M, N, R); Print(R)

…………..