Lec_07

Умножение двух длинных чисел

24

Рассмотрим обычное умножения в столбик

8 9 2 4

5 6 7

6 2 4 6 8

5 3 5 4 4

4 4 6 2 0

Умножение длинного числа на короткое

25

{ Под коротким понимается целое число типа LongInt

Процедура очень походит на процедуру сложения двух длинных чисел. }

Else Begin

For i:= l To A[0] Do

Begin

C[i+l] := (LongInt(A[i]) * K + C[i]) Div Osn;

C[i] := (LongInt(A[i])* K + C[i]) Mod Osn

End

End;

Фрагмент кода на С++

26

void SMul(const BigInt &A, const short B, BigInt &C)

{

}

if (carry) { // Число удлинилось за счет переноса нового разряда c[i] = carry;

C.Size = A.Size+1;

} else C.Size = A.Size;

}

Для нахождения правильного значения цифры остаток по модулю BASE берется без использования оператора ‘%’

Причина в том, что процессор выполняет взятие остатка во много раз медленнее, чем вычитание с умножением.

Алгоритм умножения двух длинных чисел

27

1.Обнулить C

2.Установить i = 0

3.Вычислить временный результат, соответствующий умножению i-ой цифры A на число B, в процессе вычисления сразу прибавлять его к C, начиная с i-ой позиции.

Если получившаяся цифра C больше BASE

– сделать перенос

4.Если A не кончилось, i++ и идти на шаг 3

Фрагмент кода на Паскаль (А*В)

28

function mult(a,b:num):num;

var i, j, div1 : integer; s : num; begin

result.len:=0;

for i:=1 to a.len+b.len do mult.it[i]:=0; { обнуление массива результата } if b.len>a.len then begin s:=b; b:=a; a:=s; end;

for i := 1 to b.len do begin

for j := 1 to i-1 do s.it[j] := 0; div1 := 0;

for j := 1 to a.len do begin

s.it[i+j-1] := (div1+b.it[i]*a.it[j]) mod p; div1 := (div1+b.it[i]*a.it[j]) div p;

end;

j := a.len;s.it[i+j]:=div1;

if div1<>0 then s.len := i+j else s.len := i+j-1; mult := sum(s,result);

end end;

Дополнение к длинному умножению

29

Умножение длинного на длинное можно сделать в «лоб» (но сложность будет квадратичная).

Для этого существуют алгоритмы быстрого умножения: быстрое преобразование Фурье и алгоритм умножения Карацубы.

Суть умножения Карацубы, заключается в том, что мы делим число «пополам» (в смысле по длине числа), и выполняем только сложения, вычитания и только 3 умножения.

Таким образом сложность алгоритма О(nlog23) или О(n1.5) вместо квадратичной сложности.

Деление длинного числа на короткое

31

Пусть делитель – обычное число базового типа.

Вэтом случае деление выполняется так: проходим по цифрам делимого, начиная со старшего разряда по направлению к младшему.

Для каждой пройденной цифры:

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

И так до конца делимого.

Последний перенесенный остаток является остатком от всего деления.

Пример

32

Деление А=6897 на В=5

Деление двух длинных чисел

33

Обозначим

делитель B=(b0, b1, …, bn-1), делимое A=(a0, a1, …, an+m-1),

числа имеют длины n и n+m соответственно.

Общий цикл :

алгоритм состоит из последовательно выполняемых шагов, где шаг представляет собой деление (n+1)-разрядной части A на n-разрядный делитель B.

При этом i-й шаг состоит из двух действий:

1.Угадать i-ю цифру частного q[i]

2.Не создавая временных чисел, вычесть “сдвинутое” произведения B*q[i] из A.

При этом сдвиг B относительно A на каждом шаге уменьшается.

Пример

34

Рассмотрим действия, совершаемые при делении

A=68971 на B=513

Здесь n=3, m=2