Термист Термомеханическое упрочнение арматурного проката технология, средства, разработка

Как можно быстро умножать?

Арифметические вычисления с высокой точностью

Чарлз Уэзерелл

Предыдущий раздел:
Арифметические вычисления числа π с высокой точностью. Общие соображения.

Алгоритм быстрого умножения Тоома - Кука, описываемый Кнутом, зиждется на четырех основных идеях. Вот первая из них. Пусть нам известен способ выполнения некоторой операции над исходными данными размера n за время T(n). Если эту операцию удастся разбить на r частей, выполнение каждой из которых займет менее чем T(n)/r шагов, то такое разбиение позволит улучшить общее время, если, конечно, считать, что вспомогательные организационные расходы не сведут экономию на нет. Пусть, далее, каждая из r частей есть применение того же алгоритма к исходным данным длины n/r и каждая часть может быть разбита аналогичным образом. Тогда можно продолжать это разбиение, пока мы не получим столь короткие исходные данные, что вычисления для них станут тривиальными и займут лишь небольшой фиксированный отрезок времени. Этот принцип разделяй и властвуй обычно дает выигрыш во времени работы алгоритма по крайней мере в log(n) раз; так, классический метод умножения требует времени n², и его можно свести к , что существенно лучше при больших n (не забывайте, что у обеих функций стоимости имеются постоянные множители).

Остальные три идеи касаются чисел и действий над многочленами. Во-первых, заметим, что, если число U имеет длину n битов и записывается в двоичном виде как
u_n-1u_n-2...u₂u₁u₀
причем n делится на г+1, то U можно также записать в виде
U_r2^rn/(r+1) + U_r-12^(r-1)n/(r+1) + ... + U₁2^n/(r+1) + U₀,
где каждое U_i есть блок из n/(r+1) битов исходного представления U. Фактически U = U(2^n/(r+1)), где многочлен U(x) есть
U_rx^r + U_r-1x^r-1 + U₁x + U₀.

Во-вторых, мы видим, что если U и V - два n-разрядных числа, записанных в виде такого многочлена, то их произведение W дается формулой
W = UV = U(2^n/(r+1))·V(2^n/(r+1)) = W·(2^n/(r+1)),
и если бы мы смогли найти хотя бы коэффициенты W(х), то вычислить W по W было бы сравнительно просто; для этого понадобились бы только сдвиги, сложения и умножения чисел из n/r битов.

В-третьих, к счастью, W(х) - многочлен степени 2r и его можно найти с помощью интерполяции его значений в точках 0, 1, 2, ..., 2r-1, 2r. Эти значения равны просто U(0)V(0), U(1)V(1), ..., U(2r)V(2r). Более того, для вычисления всех этих многочленов и интерполяции требуется умножать числа только из n/r битов. Представляется, что эти действия подпадают под принцип «разделяй и властвуй».

Читать дальше:
Алгоритм Тоома - Кука
Алгоритм быстрого умножения Тоома - Кука
Комментарии к алгоритму Тоома - Кука
Что можно сказать относительно деления?
Как использовать алгоритмы?
Литература

Подготовлено по публикации: Уэзерелл Ч. Этюды для программистов: Пер. с англ. - М.: Мир, 1982. - 288 с. Стр. 125 - 143.

К началу страницы

Web-сайт “Термист” (termist.com)
Термомеханическое упрочнение арматурного проката

Отсутствие ссылки на использованный материал является нарушением заповеди "Не укради"

Редактор сайта: Гунькин И.А. (termist.com@gmail.com)