|
|
Представим степень p в двоичном виде (по битикам):
p=p(1)*2^1+p(0)*2^0+p(-1)*2^(-1)+p(-2)*2^(-2)+...+p(-N)*2^(-N).
где p(i)={0,1}
Тогда
x^p=[(x^p(1))^(2^1)]*[(x^p(0))^(2^0)]*[(x^p(-1))^(2^-1)]*...
*[(x^p(-N))^(2^-N)].
Легко будет в том смысле, что число итераций будет кратно числу единиц в разложении (ведь если p(i)=0, то соответствующий множитель [(x^p(i))^(2^i)] будет равен 1).
Теперь еще одна мысль. Каким будет наихудший случай.
Ответ. Наихудшим случаем будет, когда в разложении все p(i)=1. Тогда представим p в виде (p+2^-N)-2^-N
(p+2^-N) будет равно 10000000000...0
А дальше и так все ясно. Если число единиц больше числа нулей, то округляем p до ближайшей старшей степени двойки в данном месте и продолжаем разлагать. Т.е. представляем p не в том виде, как было в начале, а в следующем
p=p(1)*2^1+-p(0)*2^0+-p(-1)*2^(-1)+-p(-2)*2^(-2)+-...+-p(-N)*2^(-N).
Знак + или - выбирается так, чтобы минимизировать число единиц.
Додумайте мысль сами.
|
|
E-mail: 
info@telesys.ru
