Форум программистов, компьютерный форум, киберфорум
Thinker
Войти
Регистрация
Восстановить пароль
Оценить эту запись

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

Запись от Thinker размещена 10.07.2013 в 10:03

Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону.

Считается, что бинарный алгоритм работает быстрее, но тесты показывают, что во многих случаях два первых алгоритма работают быстрее бинарного.
1. обычный алгоритм Евклида через остатки
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}

2. алгоритм Евклида через разности
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a -= b;
        else
           b -= a;
    return a | b;
}

3. бинарный алгоритм Евклида
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
long Nod(long a, long b)
{
    long deg = 0;
    if (a == 0 || b == 0)
        return a | b;
    while (((a | b) & 1) == 0)
    {
        deg++;
        a >>= 1;
        b >>= 1;
    }
    while (a && b)
    {
        if (b & 1)
            while ((a & 1) == 0)
                a >>= 1;
        else
            while ((b & 1) == 0)
                b >>= 1;
        if (a >= b)
            a = (a - b) >> 1;
        else
            b = (b - a) >> 1;
    }
    return ((a | b) << deg);
}

4. еще один бинарный алгоритм
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
long Nod(long a, long b)
{
    long buf, deg = 0;
    if (a == 0 || b == 0)
        return a | b;
    while (((a | b) & 1) == 0)
    {
        deg++;
        a >>= 1;
        b >>= 1;
    }
    if (a)
        while ((a & 1) == 0)
            a >>= 1;
    while (b)
    {
        while ((b & 1) == 0)
            b >>= 1;
        if (a < b)
            b -= a;
        else
        {
            buf = a - b;
            a = b;
            b = buf;
        }
        b >>= 1;
    }
    return (a << deg);
}
Размещено в Без категории
Показов 1919 Комментарии 0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru