| 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 16397 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:source
| |
| 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
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
