5. Умножение «длинного» числа на «длинное»

Для умножения двух «длинных» чисел существует несколько различных алгоритмов.

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

Приведем тексты программ, реализующих подобный алгоритм. Считывание «длинных» чисел производится из файла input.txt, а результат умножения помещается в файл output.txt. Входные данные в подобных задачах удобнее представлять в файле во избежание ошибки при вводе длинного числа с клавиатуры. Результат же по текстовому файлу проще анализировать.

Подпрограмма ReadData является примером ввода из файла «длинного» числа в случае, когда заранее неизвестна его длина. Применение в языке Turbo-Pascal логической функции SeekEoln вместо Eoln позволяет игнорировать пробелы в конце строки при вводе «длинного» числа. В языке С такую ситуацию требуется отслеживать самостоятельно.

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

Туре

Abyte = array [1..10000] of byte;

Tdest = array [0..20000] of word;

Var

aLen, hLen: word;

a, b: AByte;

с: ТDest;

Procedure ReadData;

var

с:char;

begin

Assign(input,'input.txt');

Reset(input);

aLen:=0;

bLen:=0;

while not SeekEoln do {пока не достигнут конец строки}

begin

read(с);

inc(aLen);

a [aLen] :=ord(c)-ord ('0')

{перевод символа в цифру}

end;

readln;

while not SeekEoln do

begin

read(c);

inc(bLen);

b[bLen] := ord(c)-ord(' 0' )

{перевод символа в цифру}

end;

Close(input)

end;

Procedure LongXLong;

var

i, j, p, q: word;

begin

p:=aLen+bLen;

FillChar (c, 2*(p+1), 0); {заполнение массива С нулями}

for i := aLen downto 1 do

for j :=bLen downto 1 do

begin

{q — место в результате для произведения i-ой и j-ой цифры каждого из множителей}

q := p-i-j+1;

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

if с[q]>9 then

begin

{перенос в следующий разряд}

c[q+1] := c[q+l]+c[q] div 10;

c[q] := c[q] mod 10

end

end;

{в с[0] поместим длину результата умножения}

if с[p]<>0 then c[0] := p

else c[0] := p-l

end;

Procedure WriteResult;

var

i: word;

begin

Assign(Output,'Output.txt');

Rewrite(Output);

for i := c[0] downto i do write(c[i]);

Close(Output)

end;

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

Begin

ReadData;

LongXLong;

WriteResult

End.

6. Рекурсивный алгоритм умножения

Преимущество приведенных в данном параграфе программ заключается в том, что их текст является коротким и «прозрачным», а, следовательно, отладка подобной программы не составляет особого труда.

Однако существует и более эффективный рекурсивный алгоритм умножения.

Пусть х и у — два n-разрядных десятичных числа и пусть n — некоторая натуральная степень числа 2. Разобьем числа х и у на 2 равные группы, обозначив левые (старшие) цифры чисел х₁ и y_l соответственно, а правые (младшие) — х₂ и у₂. Тогда

xy = (x₁10^n/2 + x₂)(y_l10^n/2 + y₂) =

= x₁ y_l10ⁿ + (x₁ y₂+x₂y_l)10^n/2 + x₂y₂

То есть умножение двух чисел, каждое из которых имеет не более n разрядов, мы свели к трем действиям умножения чисел в два раза меньшей длины, сдвигу результатов такого умножения на соответствующее число разрядов влево и сложению длинных чисел. Однако, числа (x₁+x₂)и (у₁+y₂), вообще говоря, имеют n/2+1 разряд и поэтому их произведение нельзя вычислить непосредственным рекурсивным применением нашего алгоритма. Поэтому, чтобы сделать алгоритм универсальным, перепишем его для произвольного числа n, обозначив буквой т остаток от деления п на 2:

ху = (x₁10^[n/2]+m + х₂)(у₁10^[n/2]+m + у₂) =

= x₁y₁10^n+m + (x₁y₂ + x₂y₁)10^[n/2]+m + х₂у₂ =

= x₁y₁10^n+m + ((x₁+x₂)(y₁+y₂)-x₁y₁ - х₂y₂)10^[n/2]+m + х₂у₂

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

Доказано, что с ростом п такой алгоритм является асимптотически более быстрым, нежели умножение «столбиком», однако его реализация более громоздкая и в ней приходится использовать несколько дополнительных массивов, что уменьшает максимальную длину чисел, для которых этот алгоритм может быть применен.