Форум: Форум PHPФорум ApacheФорум Регулярные ВыраженияФорум MySQLHTML+CSS+JavaScriptФорум FlashРазное
Новые темы: 0000000
Объектно-ориентированное программирование на PHP. Авторы: Кузнецов М.В., Симдянов И.В. Программирование. Ступени успешной карьеры. Авторы: Кузнецов М.В., Симдянов И.В. Социальная инженерия и социальные хакеры. Авторы: Кузнецов М.В., Симдянов И.В. PHP Puzzles. Авторы: Кузнецов М.В., Симдянов И.В. Самоучитель MySQL 5. Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ
Консультационный центр SoftTime

Форум PHP

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Возведение в степень
 
 автор: nahdim   (01.06.2008 в 22:23)   письмо автору
 
 

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

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

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

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

   
 
 автор: BinLaden   (02.06.2008 в 00:43)   письмо автору
 
   для: nahdim   (01.06.2008 в 22:23)
 

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

a^1000 = (a^2)^500

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

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

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

   
 
 автор: mihdan   (02.06.2008 в 11:02)   письмо автору
 
   для: nahdim   (01.06.2008 в 22:23)
 

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

   
 
 автор: nahdim   (02.06.2008 в 12:26)   письмо автору
 
   для: mihdan   (02.06.2008 в 11:02)
 

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

   
 
 автор: Trianon   (02.06.2008 в 12:33)   письмо автору
 
   для: nahdim   (02.06.2008 в 12:26)
 

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

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

   
 
 автор: BinLaden   (02.06.2008 в 13:25)   письмо автору
 
   для: Trianon   (02.06.2008 в 12:33)
 

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

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

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

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

   
 
 автор: Trianon   (02.06.2008 в 14:33)   письмо автору
 
   для: BinLaden   (02.06.2008 в 13:25)
 

Я имел в виду то же самое, что и Вы.
Фактически, оценивая четность показателя степени, Вы анализируете биты показателя справа налево. Рекурсивно.
Я же предложил делать анализ слева направо. Иттеративно.
<?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.523) . " ~ " pow(2.523);

?>



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

   
 
 автор: BinLaden   (02.06.2008 в 16:23)   письмо автору
 
   для: Trianon   (02.06.2008 в 14:33)
 

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

   
 
 автор: Trianon   (02.06.2008 в 16:46)   письмо автору
 
   для: BinLaden   (02.06.2008 в 16:23)
 

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

   
 
 автор: BinLaden   (18.09.2008 в 00:51)   письмо автору
 
   для: Trianon   (02.06.2008 в 14:33)
 

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

   
 
 автор: Trianon   (18.09.2008 в 01:07)   письмо автору
 
   для: BinLaden   (18.09.2008 в 00:51)
 

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

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

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

   
 
 автор: BinLaden   (18.09.2008 в 01:31)   письмо автору
 
   для: Trianon   (18.09.2008 в 01:07)
 

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

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

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

   
 
 автор: Trianon   (18.09.2008 в 01:56)   письмо автору
 
   для: BinLaden   (18.09.2008 в 01:31)
 

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

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


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

   
 
 автор: mihdan   (02.06.2008 в 14:37)   письмо автору
5.8 Кб
 
   для: nahdim   (02.06.2008 в 12:26)
 

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

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

   
 
 автор: Trianon   (02.06.2008 в 14:52)   письмо автору
 
   для: mihdan   (02.06.2008 в 14:37)
 

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

   
 
 автор: mihdan   (02.06.2008 в 16:51)   письмо автору
 
   для: Trianon   (02.06.2008 в 14:52)
 

А как же это?

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)) );
}

   
 
 автор: Trianon   (02.06.2008 в 17:23)   письмо автору
 
   для: mihdan   (02.06.2008 в 16:51)
 

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

   
 
 автор: fanclub   (02.06.2008 в 17:26)
 
   для: Trianon   (02.06.2008 в 17:23)
 

yeah!! Trianon forever!

   
 
 автор: mihdan   (02.06.2008 в 17:33)   письмо автору
 
   для: Trianon   (02.06.2008 в 17:23)
 

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

   
Rambler's Top100
вверх

Rambler's Top100 Яндекс.Метрика Яндекс цитирования