{"entities":{"Q1895406":{"pageid":1906148,"ns":120,"title":"Item:Q1895406","lastrevid":69392334,"modified":"2026-04-13T06:41:38Z","type":"item","id":"Q1895406","labels":{"en":{"language":"en","value":"A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 786280"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895406$32348DEA-4C07-42B4-A5D3-17971A148F23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20b6823b6de2edab3bc8ec4c115cfd1e7f9267d8","datavalue":{"value":{"text":"A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1895406$522CFDE9-0089-48EE-AFB4-41F3FF422181","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c3c78963f15f1d5c5bf267a4fde4bdf394021d1b","datavalue":{"value":"0832.11046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$BB1F8E63-607F-4F53-BF7D-86749BA2CC97","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"725aca679a0cd849b7123b8f0d65ff45506c8d40","datavalue":{"value":{"entity-type":"item","numeric-id":485836,"id":"Q485836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895406$66742F93-ADB1-47B5-BFA0-845167B6B9FE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895406$EA6E3C0A-A74C-4B3E-9700-4FE5F8691B73","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"78f2d89aaa6689d46b8ddfedeafdd09f7ff2342d","datavalue":{"value":{"time":"+1996-03-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1895406$A89A7347-D1DD-4559-A4F5-14A7FBA34D66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1bfa0899658a7720a6af5ce03ff1157e78dd1129","datavalue":{"value":"This paper discusses several useful techniques for improving the performance of \\textit{D. H. Lehmer}'s multiprecision algorithm for computing greatest common divisors [Am. Math. Mon. 45, 227--233 (1938; Zbl 0018.29204)]. The result is an algorithm that is approximately twice as fast as the original on inputs of 100 32-bit words in length, a significant improvement. The techniques developed include using double digits, using a new, exact condition for the partial cosequence computation, and an approximative GCD computation.    Jebelean's exact condition was subsequently used by the reviewer [Proc. ISSAC '95, 254--258 (1995)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$099D4712-A2E5-4A98-BCB9-BDDFB3D9498C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8e97fd9a96db029bc62d9cd0c08c3d9657420966","datavalue":{"value":{"entity-type":"item","numeric-id":991751,"id":"Q991751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895406$C4A86210-E141-49E0-837A-1E8BFD9D38FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$8ADBD83E-AE04-4E2F-9F60-DBF0ADD74203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f6f2e73ebe360c69b5f99d6be8e06f538650497","datavalue":{"value":"11A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$F1931419-C4F7-4D69-A31D-D0F7B926D18C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$300572EA-B4D6-4172-ABC1-C2E5F5B47B2D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4aeba78c733235faf13afe08a08c7cb580731290","datavalue":{"value":"786280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$9D23C237-7671-4F41-A75D-758A20D85906","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f488c1302c14d77364cc29fab3a0c9afc6dee13","datavalue":{"value":"Euclidean algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$504065D9-D2E6-4497-8A54-9CF081B7EC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94bad6d57ad7a2732005924cb600afc6a91b80eb","datavalue":{"value":"number-theoretic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$17AFDEBE-42FC-49C4-AB33-32308C683D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a45640f8924619dd5dc3ca3edf0a228b6450e4f","datavalue":{"value":"greatest common divisors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$93377588-E652-43B8-9670-470F106B3A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d6b6d7ca18f6dae4c1cca26fe7dcea5390f065c","datavalue":{"value":"double digits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$A19881F3-4203-4F4B-86AA-AE4488E34098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"740f20eb6f19da15a20316c02f409ecf6c948cf0","datavalue":{"value":"partial cosequence computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$57D00168-742B-4C63-A22C-78D60177A737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b602621971699b71f33b2e9a24cda9b2968ad93b","datavalue":{"value":"approximative GCD computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895406$68085CB1-71BC-4DE0-93CD-4B4515DC57C7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895406$07C45CFF-5E5A-4A16-A4B1-F182DBDCDC8D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6ad0355d00c630f278c2f3247bea71ee13a506d","datavalue":{"value":"https://doi.org/10.1006/jsco.1995.1009","type":"string"},"datatype":"url"},"type":"statement","id":"Q1895406$CAE703E9-C700-4C50-81AD-621EC3991921","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"28ec153142e9be084491340ee5b02c5b71570ba3","datavalue":{"value":"W2063001983","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$121CEDAA-ABEB-48D0-A08E-5E3EB6890057","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"70903c28a77e06892ba796736efc6a66f920cfac","datavalue":{"value":"10.1006/JSCO.1995.1009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895406$534E1A04-F449-4CB6-A1B5-19E52F1EE9D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbedfdd25102bf683f099cffec671c2aa735dbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4227305,"id":"Q4227305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d78ddbd9ce5ecd5c12ca1554b7022a64e2cd9759","datavalue":{"value":{"amount":"+0.8460678458213806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1895406$E43803BA-1CDA-4F41-902F-F909802404B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d89f2db44442003e6e54d4cbe4b0812107a8ab11","datavalue":{"value":{"entity-type":"item","numeric-id":4289843,"id":"Q4289843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d78ddbd9ce5ecd5c12ca1554b7022a64e2cd9759","datavalue":{"value":{"amount":"+0.8460678458213806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1895406$17242458-EAD7-40E1-BA67-384336310AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d088d69d359dca4f450b16ef785ce4fce80bb09e","datavalue":{"value":{"entity-type":"item","numeric-id":4704559,"id":"Q4704559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b24546620f18a5b7db3414201c327b6a70584694","datavalue":{"value":{"amount":"+0.8459251523017883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1895406$52B94C39-113A-462D-9AC2-90C40B04DA52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b640a8654398d2b6e508759e8a5e517435f181f","datavalue":{"value":{"entity-type":"item","numeric-id":4652409,"id":"Q4652409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b24546620f18a5b7db3414201c327b6a70584694","datavalue":{"value":{"amount":"+0.8459251523017883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1895406$1395FBEF-1F45-4973-9678-B232E80D551A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afdebe046077d0e51f85f83175a043379e2ddc04","datavalue":{"value":{"entity-type":"item","numeric-id":4062638,"id":"Q4062638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92a922904ed66e8935bb5d7b69889190e880fe9c","datavalue":{"value":{"amount":"+0.8058869242668152","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1895406$581C5707-E9D9-4E0C-8977-28BA2DEC774A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_double-digit_Lehmer-Euclid_algorithm_for_finding_the_GCD_of_long_integers"}}}}}