Почему двоичный алгоритм GCD намного медленнее для меня? - PullRequest
Новая
       33

Почему двоичный алгоритм GCD намного медленнее для меня?

3 голосов
/ 19 октября 2011

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Согласно Википедии, он должен быть немного быстрее, чем алгоритм Евклида (не очень, но я, по крайней мере, ожидал получить равную производительность). Для меня это на порядок медленнее. Не могли бы вы, ребята, помочь мне понять, почему?

Я пытался реализовать это в Ruby. Сначала я пошел с рекурсивным решением 

def gcd_recursive(u, v)
return u|v if u==0 or v==0

if u.even?
  if v.even?
    return gcd(u>>1, v>>1)<<1
  else
    return gcd(u>>1, v) if v.odd?
  end
elsif u.odd? and v.even?
  return gcd(u, v>>1)
else
  if u < v
    u, v = v, u
  end
  return gcd((u-v)>>1, v)
end
end

Это не сработало так хорошо, поэтому я хотел проверить, насколько быстро это было бы, если бы это был цикл 

def gcd(u, v)
  return u|v if u==0 or v==0
  shift=0
  while ((u|v)&1)==0 do
    u=u >> 1;
    v=v >> 1;
    shift += 1
  end
  while ((u&1) == 0) do 
    u=u >> 1
  end
  begin
    while ((v & 1) == 0) do
      v=v >> 1
    end

    if u < v
      v -= u
    else
      diff = u - v
      u = v
      v = diff
    end
  end while v != 0
  u<<shift
end

Это результаты тестов 

       user     system      total        real
std  0.300000   0.000000   0.300000 (  0.313091)
rbn  0.850000   0.000000   0.850000 (  0.872319)
bin  2.730000   0.000000   2.730000 (  2.782937)
rec  3.070000   0.000000   3.070000 (  3.136301)

std - собственная реализация ruby ​​1.9.3 C.

rbn - это то же самое (алгоритм Евклида), но написано на Ruby.

bin - это код цикла, который вы видите выше.

rec - рекурсивная версия.

РЕДАКТИРОВАТЬ: я провел тест на мацы 'ruby 1.9.3. Я попытался запустить тот же тест на Рубиниусе, и вот что я получил. Это также сбивает с толку ... 

 rbn  1.268079   0.024001   1.292080 (  1.585107)
 bin  1.300082   0.000000   1.300082 (  1.775378)
 rec  1.396087   0.000000   1.396087 (  2.348785)

1 Ответ

1 голос
/ 19 октября 2011

Это всего лишь предположение, но я подозреваю, что это сочетание двух причин:

  1. Бинарный алгоритм GCD более сложен, чем алгоритм Евклида, и включает в себя операции более низкого уровня, поэтому он больше страдает от издержек интерпретации при реализации на языке высокого уровня, таком как Ruby.
  2. Современные компьютеры, как правило, имеют быстрые инструкции деления (и по модулю), что затрудняет конкуренцию стандартному евклидову алгоритму.
...