Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Визуализация использования двоичного алгоритма НОД для нахождения наибольшего общего делителя (НОД) 36 и 24. Таким образом, НОД составляет 2 2 × 3 = 12.

Двоичный алгоритм НОДА , также известный как алгоритм Штейна или двоичный алгоритм Евклида , [1] [2] представляет собой алгоритм , который вычисляет наибольший общий делитель двух целых неотрицательных чисел. Алгоритм Штейна использует более простые арифметические операции, чем традиционный алгоритм Евклида ; он заменяет деление арифметическим сдвигом , сравнением и вычитанием.

Хотя алгоритм в его современной форме был впервые опубликован израильским физиком и программистом Йозефом Штейном в 1967 году [3], он мог быть известен ко II веку до нашей эры в древнем Китае. [4] [5]

Алгоритм [ править ]

Алгоритм уменьшает проблему нахождения НОД двух неотрицательных чисел v и u , многократно применяя эти тождества:

  • gcd (0, v ) = v , потому что все делит ноль, а v - наибольшее число, которое делит v . Аналогично gcd ( u , 0) =  u .
  • gcd ( 2u ,  2v ) = 2 · gcd ( u , v )
  • gcd ( 2u ,  v ) = gcd ( u ,  v ), если v нечетно (2 не является общим делителем). Аналогично, gcd ( u ,  2v ) = gcd ( u ,  v ), если u нечетное.
  • gcd ( u ,  v ) = gcd (| u  -  v |, min ( u , v )), если u и v оба нечетные.

Реализация [ править ]

Рекурсивная версия на C [ править ]

Ниже приводится рекурсивная реализация алгоритма в C . Реализация аналогична описанию алгоритма, приведенному выше, и оптимизирована для удобства чтения, а не скорости, хотя все рекурсивные вызовы, кроме одного, являются хвостовыми рекурсивными .

unsigned  int  gcd ( unsigned  int  u ,  unsigned  int  v ) {  // Базовые случаи  // gcd (n, n) = n  if  ( u  ==  v )  return  u ;  // Идентификатор 1: gcd (0, n) = gcd (n, 0) = n  if  ( u  ==  0 )  return  v ;  если  ( v  ==  0 )  вернуть  u ; if  ( u  %  2  ==  0 )  {  // u четно  if  ( v  %  2  ==  1 )  // v нечетно  return  gcd ( u / 2 ,  v );  // Идентификация 3  else  // и u, и v четные  return  2  *  gcd ( u / 2 ,  v / 2 );  // Идентичность 2 }  else  {  // u нечетно  if  ( v  %  2  ==  0 )  // v четно  return  gcd ( u ,  v / 2 );  // Идентичность 3 // Тождества 4 и 3 (u и v нечетные, поэтому известно, что uv и vu четные)  if  ( u  >  v )  return  gcd (( u  -  v ) / 2 ,  v );  иначе  вернуть  gcd (( v  -  u ) / 2 ,  u );  } }

Итерационная версия в Rust [ править ]

Ниже приведена реализация алгоритма на Rust , адаптированная из uutils . Он удаляет все общие множители 2, используя тождество 2, затем вычисляет НОД оставшихся чисел, используя тождества 3 и 4, комбинируя их, чтобы сформировать окончательный ответ.

pub fn gcd ( mut u : u64 , mut v : u64 ) -> u64 {        используйте std :: cmp :: min ;  используйте std :: mem :: swap ;  // Базовые случаи: gcd (n, 0) = gcd (0, n) = n, если u == 0 {      вернуть v ;  } else if v == 0 {       вернуть u ;  } // Использование тождеств 2 и 3: // gcd (2ⁱ u, 2ʲ v) = 2ᵏ gcd (u, v) с нечетным u, v и k = min (i, j) // 2ᵏ - наибольшая степень двойки, делит как u, так и v, пусть i = u . trailing_zeros (); u >> = i ;          пусть j = v . trailing_zeros (); v >> = j ;       пусть k = min ( i , j );     loop {  // u и v нечетные в начале цикла debug_assert! ( u % 2 == 1 , «u = {} четно» , u );        debug_assert! ( v % 2 == 1 , "v = {} четное" , v );       // Поменяйте местами, если необходимо, чтобы u <= v if u > v {      своп ( & mut u , & mut v );    } // Использование тождества 4 (gcd (u, v) = gcd (| vu |, min (u, v)) v - = u ;    // Идентификатор 1: gcd (u, 0) = u // Сдвиг на k необходим для добавления обратно множителя 2ᵏ, который был удален перед циклом, если v == 0 {       return u << k ;    } // Идентификатор 3: gcd (u, 2ʲ v) = gcd (u, v) (известно, что u нечетное) v >> = v . trailing_zeros ();    }}

Эта реализация демонстрирует несколько оптимизаций производительности:

  • Пробное деление на 2 избегается в пользу одинарного битового сдвига и примитива подсчета конечных нулей u64 :: trailing_zeros . Это эквивалентно многократному применению идентификатора 3 за гораздо меньший промежуток времени.
  • Петля раскладывается так, чтобы избежать повторения работы; например, исключение 2, поскольку множитель v был перемещен в конец цикла и после условия выхода, поскольку v , как известно, является нечетным при входе в цикл.
  • Тело цикла не имеет ветвей, за исключением его условия выхода ( v == 0 ), поскольку обмен u и v (гарантирующий, что u ≤ v ) сводится к условным ходам . [6] Трудно предсказуемые переходы могут иметь большое негативное влияние на производительность. [7] [8]

Эффективность [ править ]

Алгоритм требует O ( n ) шагов, где n - количество бит в большем из двух чисел, так как каждые 2 шага уменьшают хотя бы один из операндов как минимум в 2 раза. Каждый шаг включает только несколько арифметических действий. операции (O (1) с малой константой); при работе с числами размером со слово каждая арифметическая операция преобразуется в одну машинную операцию, поэтому количество машинных операций порядка log (max ( u , v )).

Однако асимптотическая сложность этого алгоритма составляет O (n 2 ), [9], поскольку каждая из этих арифметических операций (вычитание и сдвиг) занимает линейное время для чисел произвольного размера (одна машинная операция на слово представления). Это то же самое, что и для алгоритма Евклида, хотя более точный анализ, проведенный Ахави и Валле, показал, что двоичный НОД использует примерно на 60% меньше битовых операций. [10]

Расширения [ править ]

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

Расширенный двоичный НОД алгоритм, аналогичный расширенному алгоритм Евклида , помещается в первом роде расширение, так как она обеспечивает коэффициенты Беза в дополнении к НОДУ, то есть целые числа и Ь таким образом, что а • и + Ь · V = НОД ( u , v ). [11] [12] [13]

В случае больших целых чисел наилучшая асимптотическая сложность - O (log n M ( n )), где M ( n ) - стоимость n- битного умножения; это почти линейно и значительно меньше, чем O (n²) двоичного алгоритма GCD, хотя конкретные реализации превосходят старые алгоритмы только для чисел, превышающих примерно 64 килобит ( т. е. больше 8 × 10 19265 ). Это достигается путем расширения двоичного алгоритма НОД с использованием идей алгоритма Шёнхаге – Штрассена для быстрого целочисленного умножения. [14]

Бинарный алгоритм НОД также был расширен на области, отличные от натуральных чисел, такие как целые числа Гаусса , [15] целые числа Эйзенштейна , [16] квадратичные кольца, [17] [18] и произвольные уникальные области факторизации . [19]

Историческое описание [ править ]

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

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

-  Fangtian - Геодезия, Девять глав по математическому искусству

Фраза «если возможно, разделить вдвое» неоднозначна, [4] [5]

  • если это применимо, когда любое из чисел становится четным, алгоритм является двоичным алгоритмом НОД;
  • если это применимо только тогда, когда оба числа четные, алгоритм аналогичен алгоритму Евклида .

См. Также [ править ]

  • Евклидов алгоритм
  • Расширенный алгоритм Евклида
  • Наименьший общий множитель

Ссылки [ править ]

  1. ↑ Брент, Ричард П. (13–15 сентября 1999 г.). Двадцатилетний анализ двоичного алгоритма Евклида . Симпозиум Оксфорд-Майкрософт 1999 г. в честь профессора сэра Энтони Хора. Оксфорд.
  2. ↑ Брент, Ричард П. (ноябрь 1999 г.). Дальнейший анализ двоичного алгоритма Евклида (Технический отчет). Вычислительная лаборатория Оксфордского университета. arXiv : 1303.2772 . ПРГ ТР-7-99.
  3. ^ Stein, J. (февраль 1967), "Вычислительные проблемы, связанные с алгеброй Рака", Журнал вычислительной физики , 1 (3): 397-405, Bibcode : 1967JCoPh ... 1..397S , doi : 10.1016 / 0021- 9991 (67) 90047-2 , ISSN 0021-9991 
  4. ^ a b Кнут, Дональд (1998), получисловые алгоритмы , Искусство компьютерного программирования , 2 (3-е изд.), Addison-Wesley, ISBN 978-0-201-89684-8
  5. ^ a b Чжан, Шаохуа (05.10.2009). «Понятие о простых числах и алгоритм вычисления наибольшего общего делителя в Древнем Китае». arXiv : 0910.0095 [ math.HO ].
  6. ^ Godbolt, Мэтт. «Обозреватель компилятора» . Проверено 4 ноября 2020 года .
  7. ↑ Капур, Раджив (21 февраля 2009 г.). «Как избежать затрат на неверное предсказание отрасли» . Зона разработчиков Intel .
  8. ^ Лемир, Даниэль (2019-10-15). «Неправильно предсказанные ветви могут увеличить время работы» .
  9. ^ «GNU MP 6.1.2: двоичный GCD» .
  10. ^ Ахави, Али; Валле, Бриджит (2000), «Средняя битовая сложность евклидовых алгоритмов» , Proceedings ICALP'00, Lecture Notes Computer Science 1853 : 373–387, CiteSeerX 10.1.1.42.7616 
  11. Перейти ↑ Knuth 1998 , p. 646, ответ на упражнение 39 раздела 4.5.2.
  12. ^ Менезес, Альфред Дж .; van Oorschot, Paul C .; Ванстон, Скотт А. (октябрь 1996 г.). «§14.4 алгоритмы наибольшего общего делителя» (PDF) . Справочник по прикладной криптографии . CRC Press. С. 606–610. ISBN  0-8493-8523-7. Проверено 9 сентября 2017 .
  13. ^ Коэн, Анри (1993). «Глава 1: Основные теоретико-числовые алгоритмы». Курс вычислительной алгебраической теории чисел . Тексты для выпускников по математике . 138 . Springer-Verlag . С. 17–18. ISBN 0-387-55640-0.
  14. ^ Stehlé, Дэмиен; Циммерманн, Пауль (2004), "Бинарный рекурсивный алгоритм НОД" (PDF) , Алгоритмическая теория чисел , Конспект лекций в Comput. Sci . , 3076 ., Springer, Berlin, стр 411-425, CiteSeerX 10.1.1.107.8612 , DOI : 10.1007 / 978-3-540-24847-7_31 , ISBN   978-3-540-22156-2, MR  2138011 , Отчет об исследовании INRIA RR-5050.
  15. ^ Weilert, Андре (июль 2000). «(1 + i) -арное вычисление НОД в Z [i] как аналог двоичного алгоритма НОД». Журнал символических вычислений . 30 (5): 605–617. DOI : 10,1006 / jsco.2000.0422 .
  16. ^ Дамгард, Иван Бьерре; Франдсен, Гудмунд Сковбьерг (12–15 августа 2003 г.). Эффективные алгоритмы НОД и кубической остаточности в кольце целых чисел Эйзенштейна . 14-й Международный симпозиум по основам теории вычислений. Мальмё , Швеция . С. 109–117. DOI : 10.1007 / 978-3-540-45077-1_11 .CS1 maint: формат даты ( ссылка )
  17. ↑ Агарвал, Саураб; Франдсен, Гудмунд Сковбьерг (13–18 июня 2004 г.). Бинарные НОД-подобные алгоритмы для некоторых комплексных квадратичных колец . Симпозиум по алгоритмической теории чисел. Берлингтон, штат Вирджиния , США. С. 57–71. DOI : 10.1007 / 978-3-540-24847-7_4 .CS1 maint: формат даты ( ссылка )
  18. ↑ Агарвал, Саураб; Франдсен, Гудмунд Сковбьерг (20–24 марта 2006 г.). Новый алгоритм НОД для квадратичных колец чисел с уникальной факторизацией . 7-й латиноамериканский симпозиум по теоретической информатике. Вальдивия, Чили . С. 30–42. DOI : 10.1007 / 11682462_8 .CS1 maint: формат даты ( ссылка )
  19. ^ Wikström, Дуглас (11-15 июля 2005). Об l-арном НОД-алгоритме в кольцах целых чисел . Автоматы, языки и программирование, 32-й международный коллоквиум. Лиссабон , Португалия . С. 1189–1201. DOI : 10.1007 / 11523468_96 .CS1 maint: формат даты ( ссылка )

Дальнейшее чтение [ править ]

  • Кнут, Дональд (1998). «§4.5 Рациональная арифметика». Получисловые алгоритмы . Искусство программирования . 2 (3-е изд.). Эддисон-Уэсли. С. 330–417. ISBN 978-0-201-89684-8.

Охватывает расширенный двоичный НОД и вероятностный анализ алгоритма.

  • Коэн, Анри (1993). «Глава 1: Основные теоретико-числовые алгоритмы». Курс вычислительной алгебраической теории чисел . Тексты для выпускников по математике . 138 . Springer-Verlag . С. 12–24. ISBN 0-387-55640-0.

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

  • Валле, Бриджит (сентябрь – октябрь 1998 г.). «Динамика двоичного алгоритма Евклида: функциональный анализ и операторы» . Алгоритмика . 22 (4): 660–685. DOI : 10.1007 / PL00009246 . S2CID  27441335 . Архивировано из оригинала (PS) 13.05.2011.CS1 maint: формат даты ( ссылка )

Анализ алгоритма в среднем случае, через призму функционального анализа : основные параметры алгоритмов отлиты как динамической системы , и их среднее значение связано с инвариантной мерой из системы оператора переноса .

Внешние ссылки [ править ]

  • Словарь алгоритмов и структур данных NIST: двоичный алгоритм GCD
  • Cut-The-Knot: Binary Евклида алгоритм в вырез в-узел
  • Анализ двоичного алгоритма Евклида (1976), статья Ричарда П. Брента , включая вариант с использованием сдвига влево