Обсуждение:Бинарный алгоритм вычисления НОД

Алгоритм НЕ является хвостовой рекурсией, т.к.

3. 2*НОД(m/2, n/2);

Т.е. требуется возврат результата из рекурсии, чтобы его потом умножить на 2! 213.238.9.7 20:08, 17 марта 2011 (UTC) Forzi

int gcd(int m, int n) {
    if ( m == 0 ) {
        return n;
    } else if ( n == 0 ) {
        return m;
    } else if ( m == 1 || n == 1 ) {
        return 1;
    } else if ( m % 2 == 0 && n % 2 == 0 ) {
        return 2 * gcd(m/2, n/2);
    } else if ( m % 2 == 0 ) {
        return gcd(m/2, n);
    } else if ( n % 2 == 0 ) {
        return gcd(m, n/2);
    } else if ( m > n ) {
        return gcd(n, m-n);
    } else {
        return gcd(n, n-m);
    }
}

• В принципе можно переделать и в хвостовую, если набегающий сдвиг параметром прокидывать. Вот расписал не совсем красиво, зато наглядно, что рекурсия хвостовая и заменяемая на итерацию :

int gcd(int m, int n, int shift) // изначально вызывать с shift = 0
{
	int x ;

again:	if (!m) return n ; if (!n) return m ;
again2:	if (m == n) return m << shift ;
	if ((m == 1) || (n == 1)) return 1 << shift ;
	x = n & 1 ;
	if (m & 1)
	{
		if (!x)
		{
			n >>= 1 ;
			goto recurse ;
		}
	}
	else
	{
		if (!x)
		{
			++shift ;
			n >>= 1 ;
		}
		m >>= 1 ;
		goto recurse ;
	}
	if (m < n)
	{
		x = n - m ;
		n = m ;
		m = x ;
	}
	else
		m -= n ;
	m >>= 1 ;
recurse:return gcd(m, n, shift) ; // можно заменить на goto again ; или goto again2 ;
}

Ethereal0000 (обс.) 11:03, 26 июля 2021 (UTC)

Алгоритм

Ну допустим m=5 и n=20

1. НОД(0, n) = n; НОД(m, 0) = m; - это сразу отпадает
2. Если m,n нечётные, тогда НОД(m, n) = 2*НОД(m/2, n/2) - это тоже не выполняется, т.к. 20 -чётное
3. Если m нечётная, тогда НОД(m, n) = НОД(m/2, n) - выполняется, т.к. 5-нечётное...

рекурсия: m=2.5 и n=20

1. НОД(0, n) = n; НОД(m, 0) = m; - это отпадает
2. Если m,n нечётные, тогда НОД(m, n) = 2*НОД(m/2, n/2) - а вот здесь возникает вопрос... чётность/нечётность - свойство целых чисел. Каким же образом определить нечётно ли дробное число? :) Multiprogramm 21:48, 4 августа 2008 (UTC)

Ты перепутал чётные с нечётными. Посмотри внимательно алгоритм! 213.238.9.7 20:12, 17 марта 2011 (UTC) Forzi

Я не перепутал, просто алгоритм к тому времени поправили. Multiprogramm 13:36, 16 августа 2012 (UTC)

Бинарный алгоритм поиска НОД быстрее алгоритма Евклида?

Вот алгоритм Евклида для поиска НОД (a,b):

      while (true) {
           if (a > b) {
               a = a % b;
               if (a == 0) return b;
           } else {
               b = b % a;
               if (b == 0) return a;
           }
       }

Если неошибаюсь примерно так будет выглядеть Бинарный алгоритм поиска НОД(a,b):

       long result = 1;
       while (true) {
           if (a == 0) {
               return result * b;
           } else if (b == 0) {
               return result * a;
           } else if (a == 1 || b == 1) {
               return result;
           } else if ((a % 2) == 0 && (b % 2) == 0) {
               result = result << 1;
               a = a >> 1;
               b = b >> 1;
           } else if ((a % 2) == 0) {
               a = a >> 1;
           } else if ((b % 2) == 0) {
               b = b >> 1;
           } else {
               if (a < b) {
                   long val = a;
                   a = (b - a) >> 1;
                   b = val;
               } else {
                   a = (a - b) >> 1;
               }
           }
       }

В статье имеется утверждение "Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги." Я посмотрел описание алгоритма, там больше операций деления и взятия по модулю (если реализовывать) чем в алгоритме Евклида описанного выше. Поэтому считаю утверждение неверным. Или все же возможно реализовать бинарный алгоритм как-то иначе?

А зачем проверять чётность медленным остатком от деления, если можно использовать логическое побитовое умножение? То есть заменить % 2 на & 1, вот и ускорение будет.