Быстрое умножение длинных чисел. Опции

[klem4]

Всем привет. Может кто-то подсказать описание хорошего алгоритма умножения длиннных чисел ? Желательно с примерами работы алгоритма. Необходимо за время ~ 1c. перемножить несколько сотен длинных чисел (100-6000 знаков) на 3-4-х значные числа. Простой столбик в этом время не укладывается

[TarasBer]

> Хотя тут придется реализовывать ф-ю деления большого на большое

Надо только функцию, которая говорит частное и остаток деления a*b на 1000000000
Функция из 3 строчек на асме.

Для Д7 это выглядит так:

type TDivMod = record
  d, m: cardinal;
end;

function GetDivMod(a, b: cardinal): TDivMod;
asm
  mul edx
  mov ecx, 1000000000
  div ecx
  // эти две строчки из-за того, что результат почему-то возвращается не в edx:eax, а на стеке
  mov ebp - $18, eax
  mov ebp - $14, edx
end;

(Можно и через int64 написать, но это тормозить будет).

Ещё можно её модифицировать, чтобы она сразу для a*b+c говорила, только не забудь про случай переноса при сложении.

Сообщение отредактировано: TarasBer - 10.03.2011 15:21