Наибольший общий делитель. Наименьшее общее кратное.

Ещё немного подготовки

Было решено:

  1. перейти от типа int к типу long, что бы иметь больший простор для маневра;
  2. оформить вычисление НОД в виде функции;
  3. в функции main вызывать альтернативные версии функции вычисления НОД и сравнивать их производительность.

Очевидный прототип функции: long gcd(long a, long b). Имя функции от англ. Greatest Common Divisor – т.е. НОД.

Для такой несложной задачи я не стал связываться с профилировщиком, а использовал примитивный тайминг (подробности можно посмотреть в статье «Оптимизация кода через ручной тайминг»).

Окончательный вариант «испытательного стенда» приведён в конце статьи. А в процессе исследований я пользовался его упрощённым вариантом, обеспечивавшим запуск одной из испытуемых функций и таймирование.

Наибольший общий делитель. Наименьшее общее кратное.

В коде я не пользоваться библиотечными функциями, что бы максимальный объём кода был контролируемым. Использование библиотечных функций типа min или swap — отдельная тема для экспериментов. Оставляю её для особо дотошных читателей.

Итак, функции, на которые хватило времени, мозгов и фантазии написаны. Можно допиливать «испытательный стенд» и приступать к тестированию.

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

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

Вычисление наименьшего общего кратного (НОК) через НОД

Мы уже установили связь наименьшего общего кратного с наибольшим общим делителем. Теперь научимся определять НОК через НОД. Сначала разберемся, как делать это для положительных чисел.

Определение 1

Найти наименьшее общее кратное через наибольший общий делитель можно по формуле НОК(a, b)=a·b:НОД(a, b).

В этом примере мы использовали правило нахождения наименьшего общего кратного для целых положительных чисел a и b: если первое число делится на второе, что НОК этих чисел будет равно первому числу.

Для того, чтобы найти наименьшее общее кратное отрицательных чисел, эти числа необходимо сначала заменить на числа с противоположным знаком, а затем провести вычисления по приведенным выше алгоритмам.

Пример 9

НОК(54, −34)=НОК(54, 34), а НОК(−622, −46, −54, −888)=НОК(622, 46, 54, 888).

Такие действия допустимы в связи с тем, что если принять, что a и −a – противоположные числа,то  множество кратных числа a совпадает со множеством кратных числа −a.

Пример 10

Необходимо вычислить НОК отрицательных чисел −145 и −45.

Решение

Произведем замену чисел −145 и −45 на противоположные им числа 145и 45. Теперь по алгоритму вычислим НОК(145, 45)=145·45:НОД(145, 45)=145·45:5=1 305, предварительно определив НОД по алгоритму Евклида.

Получим, что НОК чисел −145 и −45 равно 1 305.

Ответ: НОК(−145, −45)=1 305.

 — это и есть искомый НОД.

Наибольший общий делитель НОД.

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

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое, справа — делитель. Далее в левом столбце записываем значения частных. Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

28 = 2 • 2 • 7

64 = 2 • 2 • 2 • 2 • 2 • 2

НОД (28; 64) = 2 • 2 = 4

Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами: в столбик (как делали выше) или «в строчку».

Найти НОД 48 и 36.

НОД (48; 36) = 2 • 2 • 3 = 12

Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.

Д (10) = {1, 2, 5, 10}

Д (15) = {1, 3, 5, 15}

Д (10, 15) = {1, 5}

НОД (10; 15) = 5

01 перебор от произвольного числа

long gcd01(long a, long b) {

    long nod = 1L;
    for (long i = a; i {amp}gt; 0; i--) {
        if (a % i == 0 {amp}amp;{amp}amp; b % i == 0) {
            nod = i;
            break;
        }
    }
    return nod;
}

Этот алгоритм – стартовая точка исследования. Идея алгоритма очень проста: гоним переменную цикла от первого числа до 1. Если оба числа делятся на переменную цикла без остатка, значит переменная цикла и равна НОД; цикл можно завершить досрочно. Если цикл прошёл до конца, значит для этих чисел НОД равен 1.

Очевидный недостаток – несимметричность относительно аргументов. Очевидно, что НОД меньше или равен меньшему из двух чисел. Поэтому гнать цикл от большего числа не имеет смысла.

long min(long a, long b) {
    return a {amp}gt; b ? b : a;
}

long gcd02(long a, long b) {

    long nod = 1L;
    for (long i = min(a, b); i {amp}gt; 0; i--) {
        if (a % i == 0 {amp}amp;{amp}amp; b % i == 0) {
            nod = i;
            break;
        }
    }
    return nod;
}

Просто добавляем простейшую функцию для вычисления минимального числа для пары чисел и инициализируем переменную цикла меньшим из двух чисел. В половине случаев такая оптимизация работать не будет (когда первый аргумент и так меньше второго); зато в другой половине случаев выигрыш по времени может быть весьма значительным.

Нахождение НОК с помощью разложения чисел на простые множители

Но второй вариант так и остался алгоритмом с последовательным перебором. Что можно попробовать ещё?

Из школьного курса математики известно, что НОД можно найти из разложения чисел на простые множители.

a = m1 * m2 * m3 * ... * mN
где m – простые числа
24 = (2) * 2 * 2 * (3)
54 = (2) * (3) * 3 * 3

общие множители выделены скобками

НОД(24, 54) = 2 * 3 = 6
long gcd03(long a, long b) {

    long nod = 1L;

    if (a {amp}gt; b) {
        long tmp = a;
        a = b;
        b = tmp;
    }

    while (a {amp}gt; 1L {amp}amp;{amp}amp; b {amp}gt; 1L) {
        for (long i = 2; i {amp}lt;= a; i  ) {
            if (a % i == 0 {amp}amp;{amp}amp; b % i == 0) {
                nod *= i;
                a /= i;
                b /= i;
                break;
            }
            if (a % i == 0) {
                a /= i;
                break;
            }
            if (b % i == 0) {
                b /= i;
                break;
            }
        }
    }
    return nod;
}

Первый if отлавливает ситуацию, когда оба числа делятся нацело на переменную цикла и, следовательно, переменная цикла является общим простым (!) множителем для обоих чисел и учитывается для вычисления НОД. Остальные два if отлавливают случаи, когда только одно из чисел делится на переменную цикла; эти множители в НОД не входят.

По-хорошему, цикл for должен перебирать только простые числа. Но нахождение простых чисел является самостоятельной вычислительной задачей, которую здесь решать не хотелось бы. Можно, конечно, использовать таблицу простых чисел, например, в пределах первой тысячи, а для больших чисел, в случае необходимости, вычислять простые числа проверкой на простоту…

Третий вариант по производительности не плох… Но пока это самопал. А что придумали умные люди за многовековую историю математики? «O’key, Гуг… то есть, Википедия, что такое НОД?» Вот, кстати, описано нахождение НОД через каноническое разложение на простые множители, которое мы уже реализовали. А вот что-то новенькое…

Теперь давайте рассмотрим способ нахождения НОК, который основан на разложении чисел на простые множители.

Определение 2

Для нахождения наименьшего общего кратного нам понадобится выполнить ряд несложных действий:

  • составляем произведение всех простых множителей чисел, для которых нам нужно найти НОК;
  • исключаем их полученных произведений все простые множители;
  • полученное после исключения общих простых множителей произведение будет равно НОК данных чисел.

Этот способ нахождения наименьшего общего кратного основан на равенстве НОК(a, b)=a·b:НОД(a, b). Если посмотреть на формулу, то станет понятно: произведение чисел a и b равно произведению всех множителей, которые участвуют в разложении этих двух чисел. При этом НОД двух чисел равен произведению всех простых множителей, которые одновременно присутствуют  в разложениях на множители данных двух чисел.

Пример 3

У нас есть два числе 75 и 210. Мы можем разложить их на множители следующим образом: 75=3·5·5 и 210=2·3·5·7. Если составить произведение всех множителей двух исходных чисел, то получится: 2·3·3·5·5·5·7.

Если исключить общие для обоих чисел множители 3 и 5, мы получим произведение следующего вида: 2·3·5·5·7=1050. Это произведение и будет нашим НОК для чисел 75 и 210.

Дадим еще одну формулировку метода нахождения НОК путем разложения чисел на простые множители.

Определение 3

Раньше мы исключали из всего количества множителей общие для обоих чисел. Теперь мы сделаем иначе:

  • разложим оба числа на простые множители:
  • добавим к произведению простых множителей первого числа недостающие множители второго числа;
  • получим произведение, которое и будет искомым НОК двух чисел.

Нахождение НОК трех и большего количества чисел

Независимо от того, с каким количеством чисел мы имеем дело, алгоритм наших действий всегда будет одинаковым: мы будем последовательно находить НОК двух чисел. На этот случай есть теорема.

Теорема 1

Предположим, что у нас есть целые числа a1, a2, …, ak. НОК mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

Теперь рассмотрим, как можно применять теорему для решения конкретных задач.

Пример 7

Необходимо вычислить наименьшее общее кратное  четырех чисел 140, 9, 54 и 250.

Решение

Введем обозначения: a1=140, a2=9, a3=54, a4=250.

Начнем с того, что вычислим m2=НОК(a1, a2)=НОК(140, 9). Применим алгоритм Евклида для вычисления НОД чисел 140 и 9: 140=9·15 5, 9=5·1 4, 5=4·1 1, 4=1·4. Получаем: НОД(140, 9)=1, НОК(140, 9)=140·9:НОД(140, 9)=140·9:1=1 260. Следовательно, m2=1 260.

Теперь вычислим по тому е алгоритму m3=НОК(m2, a3)=НОК(1 260, 54). В ходе вычислений получаем m3=3 780.

Нам осталось вычислить m4=НОК(m3, a4)=НОК(3 780, 250). Действуем по тому же алгоритму. Получаем m4=94 500.

НОК четырех чисел из условия примера равно 94500.

Ответ: НОК(140, 9, 54, 250)=94 500.

Как видите, вычисления получаются несложными, но достаточно трудоемкими. Чтобы сэкономить время, можно пойти другим путем.

Определение 4

Предлагаем вам следующий алгоритм действий: 

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

05 алгоритм Евклида (итерационный)

Алгоритм Евклида.

long gcd04(long a, long b) {

    if (a == b) {
        return a;
    }
    if (a {amp}gt; b) {
        long tmp = a;
        a = b;
        b = tmp;
    }
    return gcd04(a, b - a);
}

Считается, что рекурсивные алгоритмы менее эффективны, чем итерационные, за счёт накладных расходов на вызов функции. Для проверки делаем и итерационный вариант.

long gcd05(long a, long b) {

    while (a != b) {
        if (a {amp}gt; b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        b = b - a;
    }
    return a;
}

Кстати, в Викиучебнике есть и другие реализации алгоритма Евклида.

Бинарный алгоритм Евклида.

long gcd06(long a, long b) {
    if (a == 0L)
        return b;
    if (b == 0L)
        return a;
    if (a == b)
        return a;
    if (a == 1L || b == 1L)
        return 1L;
    if (a % 2L == 0L {amp}amp;{amp}amp; b % 2L == 0L)
        return 2L * gcd06(a / 2L, b / 2L);
    if (a % 2L == 0L {amp}amp;{amp}amp; b % 2L != 0L)
        return gcd06(a / 2L, b);
    if (a % 2L != 0L {amp}amp;{amp}amp; b % 2L == 0L)
        return gcd06(a, b / 2L);
    if (a {amp}lt; b)
        return gcd06((b - a) / 2L, a);
    else
        return gcd06((a - b) / 2L, b);
}

08 бинарный алгоритм (итерационный) с использованием битовых операций

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

Эта версия функции по логике полностью совпадает с предыдущей, но операции деления и умножения на 2 заменены арифметическими сдвигами, а проверка на чётность – на проверку младшего бита числа.

long gcd08(long a, long b) {
    long nod = 1L;
    long tmp;
    if (a == 0L)
        return b;
    if (b == 0L)
        return a;
    if (a == b)
        return a;
    if (a == 1L || b == 1L)
        return 1L;
    while (a != 0 {amp}amp;{amp}amp; b != 0) {
        if (((a {amp}amp; 1L) | (b {amp}amp; 1L)) == 0L) {
            nod {amp}lt;{amp}lt;= 1L;
            a {amp}gt;{amp}gt;= 1L;
            b {amp}gt;{amp}gt;= 1L;
            continue;
        }
        if (((a {amp}amp; 1L) == 0L) {amp}amp;{amp}amp; (b {amp}amp; 1L)) {
            a {amp}gt;{amp}gt;= 1L;
            continue;
        }
        if ((a {amp}amp; 1L) {amp}amp;{amp}amp; ((b {amp}amp; 1L) == 0L)) {
            b {amp}gt;{amp}gt;= 1L;
            continue;
        }
        if (a {amp}gt; b) {
            tmp = a;
            a = b;
            b = tmp;
        }
        tmp = a;
        a = (b - a) {amp}gt;{amp}gt; 1L;
        b = tmp;
    }
    if (a == 0)
        return nod * b;
    else
        return nod * a;
} 

Тестирование

Программа компилировалась под MS Visual Studio 2013 и TDM-GCC 4.8.1 в режиме 64-bit Release.

Среднее время для 500 пар случайных чисел:
-------------------------------------------------------
01 перебор от произвольного числа       :   0.5022 сек.
02 перебор от минимального числа        :   0.3256 сек.
03 с разложением на делители            :   0.0063 сек.
04 алгоритм Евклида рекурсивный         :   0.0007 сек.
05 алгоритм Евклида итерационный        :   0.0008 сек.
06 бинарный алгоритм рекурсивный        :   0.0006 сек.
07 бинарный алгоритм итерационный       :   0.0003 сек.
08 бинарный алгоритм итерац. со сдвигом :   0.0002 сек. 

Как и ожидалось, первый алгоритм катастрофически неэффективен. Алгоритм №2 – минимальный костыль для №1 – работает почти в 2 раз быстрее.

Третий алгоритм неожиданно показал очень достойный результат: в 50 раз быстрее алгоритма №2.

Четвёртый и пятый варианты – алгоритм Евклида: рекурсивная версия, как ни странно, обогнала итерационную. По сравнению с третьим вариантом время улучшилось почти на порядок.

Бинарный алгоритм Евклида показал наилучшие результаты. Из трёх вариантов реализации рекурсивная версия – самая неторопливая. Наилучший результат у оптимизированной версии с использованием битовых операций.

Итого, самая производительная версия работает более чем в 2500 раз быстрее, чем изначальный вариант.

Примечание. Время, указанное в таблице – это время выполнения REPEAT_TIMES вызовов функции.

Выводы

Выводы достаточно банальны, но всё же:

  1. Первый пришедший на ум алгоритм решения какой-то задачи часто неоптимален. Хотя и может правильно и достаточно приемлемо работать в определённых условиях.
  2. Всегда надо попробовать подумать над усовершенствованием алгоритма или над альтернативным вариантом.
  3. Учите математику!
  4. Если есть возможность, посмотрите что сделали люди до вас. Может не стоит изобретать велосипед?
  5. Оптимизируйте код.

Cranium aka Череп

Понравилась статья? Поделиться с друзьями:
Семейный портал