This HTML5 document contains 133 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
n17https://xlinux.nist.gov/dads/HTML/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n10http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n16https://books.google.com/
dbpedia-kohttp://ko.dbpedia.org/resource/
n26https://global.dbpedia.org/id/
n11http://www.cut-the-knot.org/blue/
dbpedia-behttp://be.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n30https://users.info.unicaen.fr/~brigitte/Publications/
n20http://wwwmaths.anu.edu.au/~brent/pub/
dbpedia-srhttp://sr.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
n27https://web.archive.org/web/20110513012901/http:/users.info.unicaen.fr/~brigitte/Publications/
n18http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-arhttp://ar.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
Subject Item
dbr:Binary_gcd_algorithm
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageRedirects
dbr:Binary_GCD_algorithm
Subject Item
dbr:GCD
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageDisambiguates
dbr:Binary_GCD_algorithm
Subject Item
dbr:Coprime_integers
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
Subject Item
dbr:Computational_complexity_of_mathematical_operations
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
Subject Item
dbr:Euclidean_algorithm
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
Subject Item
dbr:Find_first_set
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
Subject Item
dbr:Binary_GCD_algorithm
rdf:type
yago:WikicatAlgorithms yago:WikicatNumberTheoreticAlgorithms yago:Activity100407535 yago:Abstraction100002137 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Algorithm105847438 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:Event100029378 dbo:Software yago:Act100030358
rdfs:label
Бинарный алгоритм вычисления НОД Binary GCD algorithm 이진 최대공약수 알고리즘 الخوارزمية الثنائية لحساب القاسم المشترك الأكبر Двійковий алгоритм обчислення найбільшого спільного дільника Algorithme binaire de calcul du PGCD Steinscher Algorithmus
rdfs:comment
Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм "быстрее" обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Возможно, алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД: * НОД(2m, 2n) = 2 НОД(m, n), * НОД(2m, 2n+1) = НОД(m, 2n+1), * НОД(-m, n) = НОД(m, n) Двійковий алгоритм обчислення НСД, також відомий як алгоритм Стайна або двійковий алгоритм Евкліда — це алгоритм, що обчислює найбільший спільний дільник двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції ніж звичайний алгоритм Евкліда: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше алгоритм був опублікований Ізраїльським фізиком і програмістом Джозефом Стайном в 1967, він міг бути відомим ще в першому столітті в Китаї. 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. 이진 최대공약수 알고리즘은 두 양의 정수의 최대공약수를 계산하는 알고리즘이다. 스테인의 알고리즘이라고도 알려져 있다. 현대 컴퓨터의 이진 표기법 때문에 일반적으로 이 나눗셈, 곱셈보다 빠른데, 이진 최대공약수 알고리즘은 나눗셈과 곱셈을 시프트 연산으로 대체함으로써, 유클리드 호제법보다 좋은 성능을 보여준다. 그래서 이 알고리즘은 나눗셈 연산을 지원하지 않는 프로세서가 장착된 플랫폼에서 특히 더 중요하다. 1961년에 이 이 알고리즘을 처음 발표했지만, 1세기경 중국에 이미 알려져 있었다. 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. الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة. 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.
foaf:depiction
n18:Binary_GCD_algorithm_visualisation.svg
dcterms:subject
dbc:Articles_with_example_C_code dbc:Number_theoretic_algorithms
dbo:wikiPageID
985410
dbo:wikiPageRevisionID
1116283576
dbo:wikiPageWikiLink
dbr:Invariant_measure dbr:Continued_fraction dbc:Articles_with_example_C_code dbr:Conditional_moves dbr:Iteration dbr:Count_trailing_zeros n10:Binary_GCD_algorithm_visualisation.svg dbr:Word_(computer_architecture) dbr:Eisenstein_integers dbr:Functional_analysis dbr:Asymptotic_notation dbr:Cut-the-knot dbr:Unique_factorization_domain dbr:Schönhage–Strassen_algorithm dbr:Ring_of_integers dbr:Extended_Euclidean_algorithm dbr:Dynamical_system dbr:Springer-Verlag dbr:Arbitrary-precision_arithmetic dbr:Han_dynasty dbr:Branch_(computer_science) dbr:Rust_(programming_language) dbr:Trial_division dbr:Arithmetic_shift dbr:The_Nine_Chapters_on_the_Mathematical_Art dbr:Bézout_coefficients dbc:Number_theoretic_algorithms dbr:Euclidean_algorithm dbr:Richard_Brent_(scientist) dbr:Big-O_notation dbr:Number_fields dbr:Lehmer's_GCD_algorithm dbr:Greatest_common_divisor dbr:The_Art_of_Computer_Programming dbr:Recursion_(computer_science) dbr:Least_common_multiple dbr:Gaussian_integers dbr:Graduate_Texts_in_Mathematics dbr:Transfer_operator
dbo:wikiPageExternalLink
n11:binary.shtml n16:books%3Fid=hXGr-9l1DXcC n17:binaryGCD.html n20:pub037.html n27:bin-gcd.ps n30:bin-gcd.ps
owl:sameAs
dbpedia-ko:이진_최대공약수_알고리즘 freebase:m.03wryx dbpedia-fa:الگوریتم_جی‌سی‌دی_دودویی wikidata:Q622328 dbpedia-sr:Бинарни_НЗД_алгоритам dbpedia-ru:Бинарный_алгоритм_вычисления_НОД yago-res:Binary_GCD_algorithm n26:4ofyS dbpedia-uk:Двійковий_алгоритм_обчислення_найбільшого_спільного_дільника dbpedia-be:Бінарны_алгарытм_вылічэння_НАД dbpedia-ar:الخوارزمية_الثنائية_لحساب_القاسم_المشترك_الأكبر dbpedia-de:Steinscher_Algorithmus dbpedia-fr:Algorithme_binaire_de_calcul_du_PGCD
dbp:wikiPageUsesTemplate
dbt:Cite_book dbt:Cite_journal dbt:Number_theoretic_algorithms dbt:Use_dmy_dates dbt:Citation_needed dbt:R dbt:Quote dbt:Portal
dbo:thumbnail
n18:Binary_GCD_algorithm_visualisation.svg?width=300
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.
dbp:title
Fangtian – Land surveying
dbo:abstract
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 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. Двійковий алгоритм обчислення НСД, також відомий як алгоритм Стайна або двійковий алгоритм Евкліда — це алгоритм, що обчислює найбільший спільний дільник двох невід'ємних цілих чисел. Двійковий алгоритм Евкліда використовує простіші арифметичні операції ніж звичайний алгоритм Евкліда: він замінює ділення бітовим зсувом, порівняннями та відніманням. Хоча вперше алгоритм був опублікований Ізраїльським фізиком і програмістом Джозефом Стайном в 1967, він міг бути відомим ще в першому столітті в Китаї. 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. Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм "быстрее" обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Возможно, алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД: * НОД(2m, 2n) = 2 НОД(m, n), * НОД(2m, 2n+1) = НОД(m, 2n+1), * НОД(-m, n) = НОД(m, n) 이진 최대공약수 알고리즘은 두 양의 정수의 최대공약수를 계산하는 알고리즘이다. 스테인의 알고리즘이라고도 알려져 있다. 현대 컴퓨터의 이진 표기법 때문에 일반적으로 이 나눗셈, 곱셈보다 빠른데, 이진 최대공약수 알고리즘은 나눗셈과 곱셈을 시프트 연산으로 대체함으로써, 유클리드 호제법보다 좋은 성능을 보여준다. 그래서 이 알고리즘은 나눗셈 연산을 지원하지 않는 프로세서가 장착된 플랫폼에서 특히 더 중요하다. 1961년에 이 이 알고리즘을 처음 발표했지만, 1세기경 중국에 이미 알려져 있었다. الخوارزمية الثنائية لحساب القاسم المشترك الأكبر، أو خوارزمية GCD الثنائية ، والمعروفة أيضًا باسم خوارزمية Stein أو الخوارزمية الإقليدية الثنائية، هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم هذه الخوارزمية عمليات حسابية أبسط من الخوارزمية الإقليدية التقليدية، حيث يستبدل القسمة بعمليات حسابية مثل الإزاحات والمقارنات والطرح. على الرغم من أن الخوارزمية في شكلها المعاصر قد نُشرت لأول مرة من قبل الفيزيائي والمبرمج جوزيف شتاين في عام 1967، إلا أنها ربما كانت معروفة في القرن الثاني قبل الميلاد في الصين القديمة.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Binary_GCD_algorithm?oldid=1116283576&ns=0
dbo:wikiPageLength
16397
foaf:isPrimaryTopicOf
wikipedia-en:Binary_GCD_algorithm
Subject Item
dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
Subject Item
dbr:Stein's_Algorithm
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageRedirects
dbr:Binary_GCD_algorithm
Subject Item
dbr:Stein's_algorithm
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageRedirects
dbr:Binary_GCD_algorithm
Subject Item
dbr:Binary_Euclidean_algorithm
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageRedirects
dbr:Binary_GCD_algorithm
Subject Item
dbr:Binary_gcd
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageRedirects
dbr:Binary_GCD_algorithm
Subject Item
dbr:Knuth's_algorithm_B
dbo:wikiPageWikiLink
dbr:Binary_GCD_algorithm
dbo:wikiPageRedirects
dbr:Binary_GCD_algorithm
Subject Item
wikipedia-en:Binary_GCD_algorithm
foaf:primaryTopic
dbr:Binary_GCD_algorithm