Отправлено ВН 12 февраля 2004 г. 19:09 В ответ на: У нас результаты скромнее :) ... отправлено Oleg_0515 12 февраля 2004 г. 18:01

Но немного. И исключая экзотику м.б.
Странное дело, сколько пользовался возведением в степень с использованием разложения показателя, но никогда не знал, что это алгоритм Монтгомери-). Когда-то сам его придумал. Хотя потом и встречал в книжках, но без упоминания Монтгомери. В общем как у Ильфа, Петрова - "Какой удар со стороны классика":-)
Но есть быстрее, с точки зрения числа умножений, алгоритмы.
Пример. От фонаря. Возведение в 14 степень. Разложение потребует 3 раза в квадрат и 3 умножения. Итого 6.
С другой стороны x^14=x^8*x^6; x^8=x^6*x^2; x^6=x^4*x^2; x^4=x^2*x^2;
x^2=x*x. Итого 5. Но с промежут. запоминанием x^2,x^6.
В общем ищется оптимальный путь. Кто придумал - не знаю.

• Так у меня и делается, только ничего запоминать не нужно ибо разложение делается не со стороны младшего бита, а со стороны старшего... — Oleg_0515   (13.02.2004 17:49, 992 байт)
  • Ответ: — ВН   (13.02.2004 18:42, 1116 байт)
    • Спасибо, понял... — Oleg_0515   (13.02.2004 19:39, 143 байт)