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

[klem4]

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

[volvo]

Кстати, Андрей, в твоем конкретном случае (при умножении на 1111), ты делаешь 4 раза одну и ту же работу, вот тут:

    for (int i = b_size - 1; i >= 0; i-- )
	 adds.push_back( mult(a, b[i]) );

Сделай чуть более хитро: опиши вектор из Int-ов, от 0 до 9, и когда приходишь в mult, проверяй, не делал ли ты уже этого умножения. Если делал - то сразу возвращай соотв. вектор. Не делал - делай, и запоминай, в следующий раз вернешь, когда понадобится. Так сэкономишь кучу времени. А если умножаешь на 1 - то можно вообще сразу возвращать исходный a, без холостых действий.

И в процессоре есть готовая операция, которая сразу получает (a+b) mod 2^32 и (a+b) div 2^32.

Как называется?