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

Говоря об умножении чисел, стоит рассмотреть два случая: умножение длинного числа на короткое (т. е. число, которое помещается в стандартный тип) и умножение двух длинных чисел. Умножение на короткое число будет схоже с умножением на однозначное число. Будем последовательно умножать короткое число на каждую цифру длинного числа, начиная с младшей цифры, записывать результат и некоторую часть произведения переносить в следующий разряд.

procedure multiply(var a: thuge; b: integer);

{функция умножает число a на короткое число b}

Var

i, r: integer;

{r - обозначает перенос в текущий разряд}

Begin

r:= 0;

{перенос в младший разряд отсутствует}

for i:= 1 to a[0] do

Begin

a[i]:= a[i] * b + r;

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

r:= a[i] div base;

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

dec(a[i], r * base);

{оставляем только часть произведения меньшую base}

end;

{Если после умножения остался еще перенос, то нужно добавить еще цифру.

Может потребоваться добавить несколько цифр, если число b больше base}

While r > 0 do

Begin

inc(a[0]);

a[a[0]]:= r mod base;

r:= r div base;

end;

end;

void multiply(thuge &a, int b) {

//функция умножает число a на короткое число b

//r - обозначает перенос в текущий разряд

int r = 0;

//перенос в младший разряд отсутствует

for (int i = 1; i <= a[0]; ++i) {

a[i] = a[i] * b + r;

//произведение очередной цифры и короткого числа с учетом переноса в текущий разряд

r = a[i] / base;

//вычисление переноса в следующий разряд

a[i] -= r * base;

//оставляем только часть произведения меньшую base

}

/*Если после умножения остался еще перенос, то нужно добавить еще цифру.

Может потребоваться добавить несколько цифр, если число b больше base*/

while (r > 0) {

a[0]++;

a[a[0]] = r % base;

r = r / base;

}

}

Не нашли, что искали? Воспользуйтесь поиском: