0

Вот две функции:

function findRestWithD($a, $b){

    if($a%$b!=0){
        return findRestWithD($b, $a%$b);
    }elseif($a%$b==1){
        return "No NOD";
    }
    else{
        return $b;
    }
}

function findRestWithoutD($a, $b){

    if(insteadD($a, $b)!=0){
        return findRestWithoutD($b, insteadD($a, $b));
    }elseif(insteadD($a, $b)==1){
        return "No NOD";
    }
    else{
        return $b;
    }
}

и вспомогательная (находит остаток от деления)

function insteadD($a, $b){ 
        if( ($a - $b)>$b ){
            return insteadD(($a - $b), $b);
        }else{
            return $a - $b;
        }
    }

Запускаю так:

$a = 25234234232346;
$b = 12342342322;
$start = microtime(true);
echo findRestWithD($a, $b);
echo "\n".'Время: '.(microtime(true) - $start).' сек.';

$start = microtime(true);
echo findRestWithoutD($a, $b);
echo "\n".'Время: '.(microtime(true) - $start).' сек.';

первая - 1.907 сек., вторая - 0.001 сек.

Почему % работает так медленно?

3
  • Всю жизнь думал, что остаток от деления $a на $b это: $a-ceil($a/$b)*$b Но нет- оказывается надо рекурсию применять.
    – ReinRaus
    17 июл 2013 в 20:52
  • Если код запускается на 32 разрядной машине, то $а вызывает переполнение и будет преобразовано к float. Оператор остатка от деления работает только с целыми числами. Попробуйте длинную арифметику. На скольки разрядной машине запускается код?
    – ReinRaus
    17 июл 2013 в 21:13
  • Задание в книге - не использовать деление. 64 разряда, завтра попробую, доброй ночи и спасибо за ответ!
    – Costa
    17 июл 2013 в 21:49

3 ответа 3

2

Задание в книге - не использовать деление

Даже в этом случае рекурсия не нужна. И по-хорошему нужно учесть отрицательные.

function dd($a, $b) {
  $result = $a;
  if ($a >= 0 and $b > 0) {        // 8, 3; частное 2; остаток 2
    while ($result > $b)
      $result -= $b;
  } elseif ($a <= 0 and $b < 0) {  // -8, -3; частное 2; остаток -2
    while ($result < $b)
      $result -= $b;
  } elseif ($a >= 0 and $b < 0) {  // 8, -3; частное -2; остаток 2
    while ($result > -1 * $b)
      $result += $b;
  } else {                         // -8, 3; частное -2; остаток -2
    while ($result * -1 > $b)
      $result += $b;
  }
  return $result;
}

Если A >= 0 и B > 0 (то что обычно в книгах) - пойдет и короткая:

function dd($a, $b) {
  $result = $a;
  while ($result > $b)
    $result -= $b;
  return $result;
}

И никаких вам переполнений, сдвигов и прочего.

1
  • Согласен, рекурсия здесь не в тему, но вопрос о скорости встроенной функции.
    – Costa
    18 июл 2013 в 7:26
1

Чтобы наглядно сравнить скопируйте код отсюда http://ideone.com/hcEMl8 в новый файл на компьютере, выдача в HTML.
Если в первой таблице где-то есть float, значит машина 32-ух разрядная.

Ошибки Вашего кода:

  • представьте, что будет, если в Вашу функцию нахождения остатка передать 12 и 6, а в общем случае 2х и х.
  • Ваши реализации НОД, никогда не вернут:

    No NOD

потому что второе условие ветвления ($a%$b==1) никогда не будет проверяться.
Ну и я не знаю, почему у Вас так долго выполняется: у меня всегда на любом числе итераций даже длинная математика быстрее Ваших рекурсивных функций, как и следовало ожидать.
Может быть свою первую функцию Вы запускаете в цикле несколько десятков тысяч итераций, а вторую только один раз?

3
  • Спасибо за ответ, запустил код, вот результаты: webpagescreenshot.info/img/51e8f4bf865018-75053806
    – Costa
    19 июл 2013 в 8:12
  • Японский городовой... 5Е-5 это 5 умножить на 10 в минус пятой степени, что гораздо меньше рекурсивной версии.
    – ReinRaus
    19 июл 2013 в 8:19
  • ну я и дурень, спасибо)
    – Costa
    20 июл 2013 в 10:03
1

возможно это потому что модулю работает в диапазоне между -214748348 и 2147483647. Попробуйте fmod()

1
  • Попробовал fmod, еще дольше стало работать. =)
    – Costa
    18 июл 2013 в 7:28

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.