Форум PHP

Нужно написать алгоритм возведения в степень. Дано число a (основание) и n - показатель.
Оба числа натуральные.

Нельзя использовать всякие pow, log, потому что алгоритм может быть использован в другом языке программирования.

Вся сложность в том, что количество операций умножения в функции должно быть меньше n (при больших n)

Как это сделать??

Попробую подсказать:

a^1000 = (a^2)^500

А если бы показатель был нечетный, то

a^1001 = a (a^2)^500

То есть рекурсия и деление показателя пополам должны Вам помочь.

Можно подглядеть в исходниках РНР )))

Прямо вот такие все умные на словах. Так покажите пример??

Пример Вам показал BinLaden. Пример, а не рабочий код.
А хамить здесь не стоит.

2 BinLaden : на самом деле, деление и рекурсию здесь мне представляется возожным заменить побитовыми сдвигами (влево) и итерацией. :)

> на самом деле, деление и рекурсию здесь мне представляется возожным заменить побитовыми сдвигами (влево) и итерацией

Если основание двойке не равно, то мне трудно понять что имелось ввиду...
Может перевести $a в систему счисления $a-тую и добавить нули справа (количеством $exp - 1), а затем перевести обратно в десятичную...
Но мне кажется, что Вы имели ввиду что-то другое, я прав?

Добавлено чуть позже:

Кстати, перевод из 10-й в $a-тую не нужен. Результат известен заранее:)

Я имел в виду то же самое, что и Вы.
Фактически, оценивая четность показателя степени, Вы анализируете биты показателя справа налево. Рекурсивно.
Я же предложил делать анализ слева направо. Иттеративно.

<?php function pwr($b, $p) {   if(intval($p) == $p && $p > 0)     for($n = 32, $x = 1; --$n >= 0; $p <<= 1)         $x = $p < 0            ? $x * $x * $b            : $x * $x;   else $x = exp($p * log(abs($b)));    return $x; } echo pwr(2.5, 23) . " ~ " . pow(2.5, 23); ?>

А переводить в двоичную систему числа , которые уже в ней хранятся... :))

Да, интересное решение. Но, к сожалению, на PHP по скорости оно немного уступает рекурсивному варианту...

речь шла об алгоритме.
На php есть pow , gmp_pow, (а для разного рода криптоприменений - bcpowmod)
Остальное - от лукавого.

Я не уловил, а почему 0xFFFFFFFF << 1 < 0? Кем это мы обязаны такому поведению? PHP, процессору?

По той же причине, что var_dump(0xFFFFFFFF << 1) будет int(-2) .

0xFFFFFFFF - это лишь способ задать шестнадцатеричной записью двоичное представление php-шного 32-х разрядного целого (которое, как известно, со знаком)

PS. PHP6 - тот вроде как 64-разрядный.
PPS. Хотя мог и напутать...

Я просто не понимаю почему в ситуации, когда после сдвига влево старший бит оказывается единицей, то число становится отрицательным integer. Старший бит указывает на знак? Тогда почему 1 указывает на "минус", а 0 на "плюс"?

> 0xFFFFFFFF - это лишь способ задать шестнадцатеричной записью двоичное представление php-шного 32-х разрядного целого (которое, как известно, со знаком)

Говорите о integer? Тогда я Вас не понимаю: 0xFFFFFFFF -- float. Это будет 4294967295, что не вписывается в диапазон integer. Поэтому эта запись не может представлять этот integer.

>Я просто не понимаю почему в ситуации, когда после сдвига влево старший бит оказывается единицей, то число становится отрицательным integer. Старший бит указывает на знак? Тогда почему 1 указывает на "минус", а 0 на "плюс"?

Потому что целые числа со знаком компьютером воспринимаются как хранящиеся в памяти в дополнительном коде.
Т.е. если старший разряд установлен - фактически число равно N - pow(2,длина_разрядной_сетки)
Операции умножения, сложения, вычитания для знаковых и беззнаковых чисел, хранимых таким образом не отличаются.


>> 0xFFFFFFFF - это лишь способ задать шестнадцатеричной записью двоичное представление php-шного 32-х разрядного целого (которое, как известно, со знаком)
>
>Говорите о integer? Тогда я Вас не понимаю: 0xFFFFFFFF -- float.
Да. Здесь я наврал.
Тут тонкость в том, что операция побитового сдвига определена лишь для целых, и приводит свой левый аргумент к целому перед выполнением сдвига.

Смотрите во вложении исходник функции на Си

http://forum.ishodniki.ru/index.php?topic=7751.0

Скажите пожалуйста, где во вложении (файл math.c ) можно узреть алгоритм?
В который раз убеждаюсь, что для вас почему-то важно ответить. А несет ли ответ ну хоть какой-нибудь смысл - наплевать.

А как же это?

PHP_FUNCTION(pow) {     zval *zbase, *zexp;     if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z/z/", &zbase, &zexp) == FAILURE) {         return;     }     /* make sure we're dealing with numbers */     convert_scalar_to_number(zbase TSRMLS_CC);     convert_scalar_to_number(zexp TSRMLS_CC);     /* if both base and exponent were longs, we'll try to get a long out */     if (Z_TYPE_P(zbase) == IS_LONG && Z_TYPE_P(zexp) == IS_LONG && Z_LVAL_P(zexp) >= 0) {         long l1 = 1, l2 = Z_LVAL_P(zbase), i = Z_LVAL_P(zexp);                  if (i == 0) {             RETURN_LONG(1L);         } else if (l2 == 0) {             RETURN_LONG(0);         }         /* calculate pow(long,long) in O(log exp) operations, bail if overflow */         while (i >= 1) {             int overflow;             double dval = 0.0;             if (i % 2) {                 --i;                 ZEND_SIGNED_MULTIPLY_LONG(l1,l2,l1,dval,overflow);                 if (overflow) RETURN_DOUBLE(dval * pow(l2,i));             } else {                 i /= 2;                 ZEND_SIGNED_MULTIPLY_LONG(l2,l2,l2,dval,overflow);                 if (overflow) RETURN_DOUBLE((double)l1 * pow(dval,i));             }             if (i == 0) {                 RETURN_LONG(l1);             }         }     }     convert_to_double(zbase);     convert_to_double(zexp);          RETURN_DOUBLE( pow(Z_DVAL_P(zbase),Z_DVAL_P(zexp)) ); }

Это - обложка. Вызывающая функцию pow() стандартной библиотеки C.
UPD. Впрочем, нет. Кое-какой отсвет на алгоритм там есть.
Но форму его представления Вы выбрали такую, что на один полезный символ, нужно воспринять под сотню всякой шелухи.

yeah!! Trianon forever!

Trianon , я согласен, что шелухи много, но все же. Если человеку нужно - то это лишь указатель в какую сторону копать, ведь он просил привести что-то из исходников. Это навскидку, что сам увидел в исходниках, так как не было времени копаться