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

[klem4]

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

[-TarasBer-]

Это просто для замены

Код

int value = bonus + a[i] * n;
    if ( value >= 10 )
    {
        bonus = (int)(value / 10);
        value %= 10;
    }

На

Код

(value, bonus) = MulDiv(a[i], n);

Не надо основание системы счисления менять на 10^500, это для 1000000000.

А функция деления длинного на длинное тебе не нужна, ты ж не собрался, надеюсь, основание длинным делать.
Число храни как массив cardinal (или u32 или uint32, или что там), каждый элемент от 0 до 999999999. Ну просто чтобы было проще выводить результат. Иначе бы можно было бы тупо взять в качестве основания 2^32 и не париться.

Ещё такой момент - то, что результат возвращается на стеке, а не в регистрах, тоже не очень хорошо.
Было бы хорошо, если было можно своё соглашение о вызове описать, но я хз, как в С++ с этим.