Темы курсовых работ по «Технология программирования (Python)»
Как можно быстро умножать?
жүктеу/скачать 0,69 Mb.
|
| Как можно быстро умножать?
Алгоритм быстрого умножения Тоома—Кука, описываемый Кнутом, зиждется на четырех основных идеях. Вот первая из них. Пусть нам известен способ выполнения некоторой операции над исходными данными размера n за время T(n). Если эту операцию удастся разбить на r частей, выполнение каждой из которых займет менее чем T(n)/r шагов, то такое разбиение позволит улучшить общее время, если, конечно, считать, что вспомогательные организационные расходы не сведут экономию на нет. Пусть, далее, каждая из r частей есть применение того же алгоритма к исходным данным длины n/r и каждая часть может быть разбита аналогичным образом. Тогда можно продолжать это разбиение, пока мы не получим столь короткие исходные данные, что вычисления для них станут тривиальными и займут лишь небольшой фиксированный отрезок времени. Этот принцип разделяй и властвуй обычно дает выигрыш во времени работы алгоритма по крайней мере в log n раз; так, классический метод умножения требует времени n², и его можно свести к , что существенно лучше при больших n (не забывайте, что у обеих функций стоимости имеются постоянные множители). Остальные три идеи касаются чисел и действий над многочленами. Во-первых, заметим, что, если число U имеет длину n битов и записывается в двоичном виде как un−1un−2…u2u1u0, причем n делится на r + 1, то U можно также записать в виде Ur2rn/(r+1) + Ur−12(r−1)n/(r+1) + … + U12n/(r+1) + U0, где каждое Ui есть блок из n/(r + 1) битов исходного представления U. Фактически U = U(2n/(r + 1)), где многочлен U(x) есть Urxr + Ur−1xr−1 + … + U1x + U0. Во-вторых, мы видим, что если U и V — два n-разрядных числа, записанных в виде такого многочлена, то их произведение W дается формулой W = UV = U(2n/(r + 1))V(2n/(r + 1)) = W(2n/(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 битов. Представляется, что эти действия подпадают под принцип «разделяй и властвуй». жүктеу/скачать 0,69 Mb. Достарыңызбен бөлісу:
|