Binary GCD algorithm (original) (raw)
الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة.
| Property | Value |
|---|---|
| dbo:abstract | الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة. (ar) The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm in its contemporary form was first published by the Israeli physicist and programmer Josef Stein in 1967, it may have been known by the 2nd century BCE, in ancient China. (en) Der steinsche Algorithmus oder binäre euklidische Algorithmus dient der effizienten Berechnung des größten gemeinsamen Teilers. Der Algorithmus wurde 1967 vom Physiker Josef Stein (Hebräische Universität Jerusalem) vorgestellt. Donald E. Knuth zufolge entwickelten R. Silver und J. Tersian den Algorithmus bereits 1962, publizierten ihn aber nicht. Der Algorithmus nutzt folgende Rechenregeln: * , falls und gerade. * , falls gerade und ungerade. * , falls und ungerade. Er ist auf Binärrechnern schneller als der jahrtausendealte euklidische Algorithmus, weil keine zeitaufwändigen Divisionen (bzw. Modulooperationen) durchgeführt werden müssen. Es sind nur Divisionen durch 2 erforderlich, wofür man nur das Bitmuster um eins nach rechts, zum niederwertigen Ende, schieben muss. Die meisten Prozessoren besitzen dafür ein effizientes Schieberegister. Zu beachten ist, dass der steinsche Algorithmus nur dann richtig funktioniert, wenn vorzeichenlose Integer verwendet werden. Negative Zahlen müssen zuerst in positive überführt werden. Der euklidische Algorithmus hingegen funktioniert auch mit vorzeichenbehafteten Integertypen. (de) En informatique, en mathématiques, l'algorithme du PGCD binaire est un algorithme pour calculer le plus grand commun diviseur de deux nombres entiers écrits en binaire (voir Problème 31.1, p. 902 dans ). L'algorithme a été publié par Josef Stein en 1967, bien qu'il semble avoir été connu en Chine dès le Ier siècle. (fr) 이진 최대공약수 알고리즘은 두 양의 정수의 최대공약수를 계산하는 알고리즘이다. 스테인의 알고리즘이라고도 알려져 있다. 현대 컴퓨터의 이진 표기법 때문에 일반적으로 이 나눗셈, 곱셈보다 빠른데, 이진 최대공약수 알고리즘은 나눗셈과 곱셈을 시프트 연산으로 대체함으로써, 유클리드 호제법보다 좋은 성능을 보여준다. 그래서 이 알고리즘은 나눗셈 연산을 지원하지 않는 프로세서가 장착된 플랫폼에서 특히 더 중요하다. 1961년에 이 이 알고리즘을 처음 발표했지만, 1세기경 중국에 이미 알려져 있었다. (ko) Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм "быстрее" обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Возможно, алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД: * НОД(2m, 2n) = 2 НОД(m, n), * НОД(2m, 2n+1) = НОД(m, 2n+1), * НОД(-m, n) = НОД(m, n) (ru) Двійковий алгоритм обчислення НСД, також відомий як алгоритм Стайна або двійковий алгоритм Евкліда — це алгоритм, що обчислює найбільший спільний дільник двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції ніж звичайний алгоритм Евкліда: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше алгоритм був опублікований Ізраїльським фізиком і програмістом Джозефом Стайном в 1967, він міг бути відомим ще в першому столітті в Китаї. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Binary_GCD_algorithm_visualisation.svg?width=300 |
| dbo:wikiPageExternalLink | http://wwwmaths.anu.edu.au/~brent/pub/pub037.html https://users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps https://web.archive.org/web/20110513012901/http:/users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps https://xlinux.nist.gov/dads/HTML/binaryGCD.html http://www.cut-the-knot.org/blue/binary.shtml https://books.google.com/books%3Fid=hXGr-9l1DXcC |
| dbo:wikiPageID | 985410 (xsd:integer) |
| dbo:wikiPageLength | 16397 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116283576 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bézout_coefficients dbr:Big-O_notation dbr:Arbitrary-precision_arithmetic dbr:Ring_of_integers dbr:Dynamical_system dbr:Invariant_measure dbr:Continued_fraction dbc:Number_theoretic_algorithms dbr:Rust_(programming_language) dbr:Schönhage–Strassen_algorithm dbr:Gaussian_integers dbr:Greatest_common_divisor dbr:Branch_(computer_science) dbr:The_Nine_Chapters_on_the_Mathematical_Art dbr:Arithmetic_shift dbr:Functional_analysis dbr:Transfer_operator dbr:Trial_division dbr:Cut-the-knot dbr:Euclidean_algorithm dbr:Extended_Euclidean_algorithm dbr:Graduate_Texts_in_Mathematics dbr:Iteration dbr:Lehmer's_GCD_algorithm dbr:Unique_factorization_domain dbr:Han_dynasty dbc:Articles_with_example_C_code dbr:Least_common_multiple dbr:Eisenstein_integers dbr:Recursion_(computer_science) dbr:Word_(computer_architecture) dbr:The_Art_of_Computer_Programming dbr:Springer-Verlag dbr:Asymptotic_notation dbr:Richard_Brent_(scientist) dbr:Count_trailing_zeros dbr:Conditional_moves dbr:Number_fields dbr:File:Binary_GCD_algorithm_visualisation.svg |
| dbp:source | dbr:The_Nine_Chapters_on_the_Mathematical_Art |
| dbp:text | If possible halve it; otherwise, take the denominator and the numerator, subtract the lesser from the greater, and do that alternately to make them the same. Reduce by the same number. (en) |
| dbp:title | Fangtian – Land surveying (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Portal dbt:Quote dbt:R dbt:Use_dmy_dates dbt:Number_theoretic_algorithms |
| dcterms:subject | dbc:Number_theoretic_algorithms dbc:Articles_with_example_C_code |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatNumberTheoreticAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة. (ar) The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm in its contemporary form was first published by the Israeli physicist and programmer Josef Stein in 1967, it may have been known by the 2nd century BCE, in ancient China. (en) En informatique, en mathématiques, l'algorithme du PGCD binaire est un algorithme pour calculer le plus grand commun diviseur de deux nombres entiers écrits en binaire (voir Problème 31.1, p. 902 dans ). L'algorithme a été publié par Josef Stein en 1967, bien qu'il semble avoir été connu en Chine dès le Ier siècle. (fr) 이진 최대공약수 알고리즘은 두 양의 정수의 최대공약수를 계산하는 알고리즘이다. 스테인의 알고리즘이라고도 알려져 있다. 현대 컴퓨터의 이진 표기법 때문에 일반적으로 이 나눗셈, 곱셈보다 빠른데, 이진 최대공약수 알고리즘은 나눗셈과 곱셈을 시프트 연산으로 대체함으로써, 유클리드 호제법보다 좋은 성능을 보여준다. 그래서 이 알고리즘은 나눗셈 연산을 지원하지 않는 프로세서가 장착된 플랫폼에서 특히 더 중요하다. 1961년에 이 이 알고리즘을 처음 발표했지만, 1세기경 중국에 이미 알려져 있었다. (ko) Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм "быстрее" обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Возможно, алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД: * НОД(2m, 2n) = 2 НОД(m, n), * НОД(2m, 2n+1) = НОД(m, 2n+1), * НОД(-m, n) = НОД(m, n) (ru) Двійковий алгоритм обчислення НСД, також відомий як алгоритм Стайна або двійковий алгоритм Евкліда — це алгоритм, що обчислює найбільший спільний дільник двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції ніж звичайний алгоритм Евкліда: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше алгоритм був опублікований Ізраїльським фізиком і програмістом Джозефом Стайном в 1967, він міг бути відомим ще в першому столітті в Китаї. (uk) Der steinsche Algorithmus oder binäre euklidische Algorithmus dient der effizienten Berechnung des größten gemeinsamen Teilers. Der Algorithmus wurde 1967 vom Physiker Josef Stein (Hebräische Universität Jerusalem) vorgestellt. Donald E. Knuth zufolge entwickelten R. Silver und J. Tersian den Algorithmus bereits 1962, publizierten ihn aber nicht. Der Algorithmus nutzt folgende Rechenregeln: * , falls und gerade. * , falls gerade und ungerade. * , falls und ungerade. (de) |
| rdfs:label | الخوارزمية الثنائية لحساب القاسم المشترك الأكبر (ar) Steinscher Algorithmus (de) Binary GCD algorithm (en) Algorithme binaire de calcul du PGCD (fr) 이진 최대공약수 알고리즘 (ko) Бинарный алгоритм вычисления НОД (ru) Двійковий алгоритм обчислення найбільшого спільного дільника (uk) |
| owl:sameAs | freebase:Binary GCD algorithm yago-res:Binary GCD algorithm wikidata:Binary GCD algorithm dbpedia-ar:Binary GCD algorithm dbpedia-be:Binary GCD algorithm dbpedia-de:Binary GCD algorithm dbpedia-fa:Binary GCD algorithm dbpedia-fr:Binary GCD algorithm dbpedia-ko:Binary GCD algorithm dbpedia-ru:Binary GCD algorithm dbpedia-sr:Binary GCD algorithm dbpedia-uk:Binary GCD algorithm https://global.dbpedia.org/id/4ofyS |
| prov:wasDerivedFrom | wikipedia-en:Binary_GCD_algorithm?oldid=1116283576&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Binary_GCD_algorithm_visualisation.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Binary_GCD_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:GCD |
| is dbo:wikiPageRedirects of | dbr:Binary_gcd_algorithm dbr:Stein's_Algorithm dbr:Stein's_algorithm dbr:Binary_Euclidean_algorithm dbr:Binary_gcd dbr:Knuth's_algorithm_B |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Binary_gcd_algorithm dbr:GCD dbr:Coprime_integers dbr:Computational_complexity_of_mathematical_operations dbr:Euclidean_algorithm dbr:Find_first_set dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Stein's_Algorithm dbr:Stein's_algorithm dbr:Binary_Euclidean_algorithm dbr:Binary_gcd dbr:Knuth's_algorithm_B |
| is foaf:primaryTopic of | wikipedia-en:Binary_GCD_algorithm |
