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

[klem4]

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

[Гость]

> for (int i = a_size - 1; i >= 0; i-- )
{
int value = bonus + a[i] * n;
if ( value >= 10 )
{
bonus = (int)(value / 10);
value %= 10;
}
else


> 10

То есть отнование системы счисления - 10? Это плохо.

Самое быстрое - основанием брать 2^32.
И в процессоре есть готовая операция, которая сразу получает (a+b) mod 2^32 и (a+b) div 2^32.
Правда, компилятор Борланда, например, никак не заставить это применить, насчёт компиляторов от Микрософта и Интела не знаю.

Если тебе надо, чтобы ещё и быстро выводилось, то пойди на компромисс - в качестве основния возьми 1000000000. Считаться будет медленнее, чем с 2^32, но в 9 раз быстрее, чем с 10. И, опять же, перемножить два 32-разрядных числа и поделить 64-разрядный результат на 1000000000 - это очень просто записывается на асме (тупо mul, div подряд, промежуточный 64-разрядный результат хранится в 2х регистрах, edx и eax), но невозможно заставить компилятор Борланда сделать это по-простому.