Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

Предпологаю что это порядка log2(max(m,n))... ???
Зараннее спасибо.

Здравствуйте, infused, Вы писали:

I> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

I>Предпологаю что это порядка log2(max(m,n))... ???
I>Зараннее спасибо.

При желании — можно выйти в O(1), точнее — в ноль

int gcd(int a, int b)
{
  a = abs(a);
  b = abs(b);

  while(a > 1 && b > 1) // можно while(a != 0 && b != 0) -- но это неоптимально
    if(a > b)
      a -= b;
    else
      b -= a;

  if(a == 1 || b == 1)
    return 1;
  else
    return a + b; // одно из них == 0
}

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, infused, Вы писали:

I>> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

I>>Предпологаю что это порядка log2(max(m,n))... ???
I>>Зараннее спасибо.

К>При желании — можно выйти в O(1), точнее — в ноль
К>

К>int gcd(int a, int b)
К>{
К>  a = abs(a);
К>  b = abs(b);

К>  while(a > 1 && b > 1) // можно while(a != 0 && b != 0) -- но это неоптимально
К>    if(a > b)
К>      a -= b;
К>    else
К>      b -= a;

К>  if(a == 1 || b == 1)
К>    return 1;
К>  else
К>    return a + b; // одно из них == 0
К>}
К>

Да алгоритм на разности мне знаком.... Вопрос в количестве операций (макс. количестве)!
Сколько их при делении... и сколько их(операций) например в данном случае при вычитании...

Здравствуйте, infused, Вы писали:

I> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

Оценка сверху...
<= C * log_{(sqrt5+1)/2}( max(a,b)/HOD(a,b) ) + O(1)
где C --- стоимость перехода {a,b} -> { b, a — [a/b]*b }

Понятно, что количество переходов {a,b}->{b,a-[a/b]*b}->...->{x*НОД,x}
равно длине разложения дроби a/НОД(а,b) / b/НОД(а,b) в цепную дробь (возможно +-1)

При минимальных a,b наибольшую длину получаем для цепной дроби вида
1+1/(1+1/....) из одних единиц
При этом такая дробь длины n даёт дробь f_{n+1}/f_{n}, где f_n --- числа Фибоначчи
Как известно f_n ~ c((1+sqrt5)/2)^n).
То есть худший вариант a=f_{n+1}, b=f_n
Отсюда и ответ

Здравствуйте, infused, Вы писали:

I> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

I>Предпологаю что это порядка log2(max(m,n))... ???
I>Зараннее спасибо.

Кол-во операций = кол-во итераций * кол-во операций в ходе итерации

Кол-во операций в ходе итерации — известно и постоянно => остаётся найти кол-во итераций.
Вэтом нам поможет лемма Ламе, которая гласит, что:

Число итераций, необходимых для вычисления НОД двух натуральных чисел A и B (A>B>0),
мажорируется 5-кратным числом десятичных знаков наименьшего из 2-х чисел.
Т.е. если n-число необходимых итераций, то
n <= 5*(floor(log10(B)) + 1)

Здравствуйте, Кодт, Вы писали:

<skipped>

Это была шутка? Если не хочется делить, то можно алгоритм сокращения двоек использовать. Прямо скажем, куда эффективней получится.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы