Произведение длинных чисел. Длинная арифметика. Pascal, Delphi.

Перед просмотром этой темы просмотрите эти: https://progaem.forum2x2.ru/forum-f3/tema-t81.htm
https://progaem.forum2x2.ru/forum-f3/tema-t82.htm

Итак, умножать мы будем по принципу "столбика", как складывали и вычитали.

Есть 2 типа умножения в длинной арифметике. Это умножение длинного числа на короткое и длинного на длинное.
В этой теме я предоставлю код обеих процедур.

Умножение длинного числа на короткое:
На самом деле все просто.
Умножаем по очереди каждый элемент массива длинного числа на наше короткое число. Записываем результат, а в ячейку длинного числа(результата функции) записываем не этот результат, а его остаток от деления на константу base(см. https://progaem.forum2x2.ru/forum-f3/tema-t81.htm), которая отвечает за количество цифр в текущей ячейке длинного числа. А сам остаток после этого делим на эту константу.
То есть, если текущий результат от умножения получился n-значным, то в основной результат запишем число, количество цифр которого будет равно baselen. А остальную часть оставим.

Может быть, на словах это трудно понять, смотрите код.

Код:


Function scalmul(Var a: TLong; c: integer): TLong;
Var i, t: integer;
    b: TLong;
Begin
  fillchar(b, sizeof(b), 0);
  if c = 0 then //При умножении на 0 всегда будет 0
  begin
    b[0] := 1;
    b[1] := 0;
    exit;
  end;
  b[0] := a[0];
  t := 0;
  For i := 1 to b[0] do
  begin
    t := t + a[i] * c; //В результат записываем пред. результат и результат умножения.
    b[i] := t mod base; //В результирующее длинное число записываем результат умножения, так, чтобы в ячейке было ровно baselen знаков.
    t := t div base;
  end;
  While (t <> 0) do //Если в конце остался еще какой-то остаток, то записываем его поразрядно.
  begin
    inc(b[0]);
    b[b[0]] := t mod base;
    t := t div base;
  end;
End;


Это вся процедура. Не обязательно вникать в смысл и читать объяснение, т.к оно может быть трудно для понимания. Достаточно просто скопировать функцию в Ваш код, функция рабочая.

Теперь рассмотрим умножение длинного числа на длинное.

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

Код:


Function mul(Var x, y: TLong): TLong;
Var c: TLong;
    i, j, t: integer;
Begin
  c := fillchar(c, sizeof(c), 0);
  t := 0;
  For i := 1 to a[0] do
  begin
    t := 0;
    For j := 1 to b[0] do
    begin
      t := t + c[i + j - 1] + a[i] * b[j];
      c[i + j - 1] := t mod base;
      t := t div base;
    end;
    j := b[0] + i;
    While (t <> 0) do
    begin
      c[j] := t mod base;
      t := t div base;
      inc(j);
    end;
  end;
  c[0] := maxn; //длина результата = макс. размер числа. MaxN - константа.
  While(c[c[0]] = 0) and (c[0] > 1) do dec(c[0]);
  mul := c;
End;


Вроде все правильно, но может быть напутал с begin, end. Если найдете баг, сообщите.

большое спасибо за код я его подправил всего 2 бага



Function mul(Var a, b: TLong): TLong; // первый баг
Var c: TLong;
i, j, t: integer;
Begin
Fillchar(c, sizeof(c), 0); // второй
t := 0;
For i := 1 to a[0] do
begin
t := 0;
For j := 1 to b[0] do
begin
t := t + c[i + j - 1] + a[i] * b[j];
c[i + j - 1] := t mod base;
t := t div base;
end;
j := b[0] + i;
While (t <> 0) do
begin
c[j] := t mod base;
t := t div base;
inc(j);
end;
end;
c[0] := maxn;
While(c[c[0]] = 0) and (c[0] > 1) do dec(c[0]);
mul := c;
End;

хотя это не баги

Function scalmul(Var a: TLong; c: integer): TLong;
Var i, t: integer;
b: TLong;
Begin
fillchar(b, sizeof(b), 0);
if c = 0 then //При умножении на 0 всегда будет 0
begin
b[0] := 1;
b[1] := 0;
exit;
end;
b[0] := a[0];
t := 0;
For i := 1 to b[0] do
begin
t := t + a[i] * c; //В результат записываем пред. результат и результат умножения.
b[i] := t mod base; //В результирующее длинное число записываем результат умножения, так, чтобы в ячейке было ровно baselen знаков.
t := t div base;
end;
While (t <> 0) do //Если в конце остался еще какой-то остаток, то записываем его поразрядно.
begin
inc(b[0]);
b[b[0]] := t mod base;
t := t div base;
end;
End;

первая функция из всех что в этой теме, не знаю по какой причине, но не работает

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