{"entities":{"Q1071503":{"pageid":1082255,"ns":120,"title":"Item:Q1071503","lastrevid":48905701,"modified":"2026-01-06T03:33:16Z","type":"item","id":"Q1071503","labels":{"en":{"language":"en","value":"Quasi-gcd computations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3940716"}},"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":"Q1071503$64EA7C09-1B81-47C8-B978-B864C77FC3DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7ffc8b65ce23c61d26ca59132d0ec2e43369ff4d","datavalue":{"value":{"text":"Quasi-gcd computations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1071503$A807915F-24D5-4B85-85BB-AF4E37530481","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"59b416f434ffac0809582d3303c6fd09202fd633","datavalue":{"value":"0586.68031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071503$572CB93C-170E-4EB0-9E95-240C52384CEE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"014164eb31a691a794365f431a419da890294b98","datavalue":{"value":"10.1016/0885-064X(85)90024-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071503$8D732952-44EC-416D-8BE5-20F9CDFA36F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"827cda40999de9cc474616ea9dace69944c128bd","datavalue":{"value":{"entity-type":"item","numeric-id":769164,"id":"Q769164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$C355CA29-9D32-4A73-B983-3A809542E478","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$EFCEFBDD-87EE-4C11-AAAD-7C84A77E12F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1071503$7D8937AE-FA8C-4B6B-AFF8-829C05BF6506","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e4ad77ae683efb5c0862c0ba28aba08260b47de5","datavalue":{"value":"For univariate polynomials with real or complex coefficients and a given error bound \\(\\epsilon >0\\), h is called a quasi-gcd of f and g, if h is an \\(\\epsilon\\)-approximate divisor of f and of g and if any (exact) common divisor of f, g is an approximate divisor of h. Extended quasi-gcd computation means to find such h and additional cofactors, u, v such that \\(| uf+vg-h| <\\epsilon | h|\\) holds. Suitable ''pivoting'' leads to a numerically stable version of Euclid's algorithm for solving this task. Further refinements by a divide-and-conquer technique and by means of fast algorithms for polynomial arithmetic then yield the worst case upper bound \\(O(n^ 2lg n(lg(1/\\epsilon)+n lg n))\\) of ''pointer time'' for nth-degree polynomials. In the particular case of integer polynomials, however, an immediate reduction to fast integer gcd computation is recommended, instead.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071503$9B2E3785-A89D-4366-8F35-DBA7CE000BF9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071503$6EA4C71B-CDB1-49FB-814D-0E8518A470F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"352295d1160dbd33b62ff206ba20a986dbd58c1b","datavalue":{"value":"12D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071503$50DB3C5F-7D69-4E76-B8D4-1EA68C564723","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9071d43c35730e6b35ea00c5298b8fcc8d8b79e3","datavalue":{"value":"3940716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071503$A89D39BE-62EB-4087-B800-14B0C03E8333","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071503$D012F17B-4E5C-482D-9B1A-116F308DE6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"695db256c6d11d12973b5a226476445753349ced","datavalue":{"value":"univariate polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071503$F9DE44D3-33E2-4125-9882-68BFA845852C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6aaf0153a3d44e072b2e7eb1d3fa739033cd9616","datavalue":{"value":"approximate divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071503$B81DC956-4309-4C48-A42B-71A949AFE6D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e086e315c939aff0d3e4420aee4be38574f779fa","datavalue":{"value":"numerically stable version of Euclid's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071503$F13946C3-F35E-4382-998D-2952328D8B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af9d18ca1618192a3e4e6edd2532b7424f2c48a5","datavalue":{"value":"worst case upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071503$8C2194F6-AD73-4F96-9ADB-72C21D3BD774","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"54a42ebcd493d14c168e95ef4c51dd56eddd67ce","datavalue":{"value":{"entity-type":"item","numeric-id":13798,"id":"Q13798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$F38B3BEB-3FDE-4023-B570-C997DFE9860D","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":"Q1071503$07EBA9D2-4911-4C57-AB50-CD64E390C091","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$9912D113-5F7A-4743-A983-ABB24D920B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63f847eac77516d370ae724678b28f1f3aed1f34","datavalue":{"value":{"entity-type":"item","numeric-id":3930541,"id":"Q3930541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$51ED0134-A28A-4FD9-9A7D-7DF917AEB629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbd9853f36448729dfca6b95b6e1f942875c416f","datavalue":{"value":{"entity-type":"item","numeric-id":3707405,"id":"Q3707405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$C405ADCA-1135-4091-8F11-62E1B7AEB76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e18ee96c6b9303cdf1b1b6b3383475544f8b7825","datavalue":{"value":{"entity-type":"item","numeric-id":5592248,"id":"Q5592248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$51E36875-198A-4F32-8B08-0DABDEB3E304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0ff209a8c00e6853b2c43b2e31810805788f0","datavalue":{"value":{"entity-type":"item","numeric-id":3935355,"id":"Q3935355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$F0451780-9F53-4F59-9FFD-557F3F7BB4A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10e165cbf779d98484e32110d9a8d0fd2bd8cc1b","datavalue":{"value":{"entity-type":"item","numeric-id":5768438,"id":"Q5768438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$E5BC5E42-6F94-4198-8240-6A8A049F7A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53714a4528eb05c2af9065b3895242d440c82062","datavalue":{"value":{"entity-type":"item","numeric-id":4062638,"id":"Q4062638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$7CD24E20-6D27-41C3-BC33-6DA0D5DC3927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d52272446563d3d8396d3599380ea2ba22ff715f","datavalue":{"value":{"entity-type":"item","numeric-id":2548173,"id":"Q2548173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$11A374F6-948A-4F07-8B4C-5E6F9AA0C983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecd9e3f8a36027b7b9841c9e193478610271133a","datavalue":{"value":{"entity-type":"item","numeric-id":3325040,"id":"Q3325040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$75154855-909F-4C09-BBD9-7C1640162936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b110a1bfc6d602ebb55d3aaa37eddbb37f0ce068","datavalue":{"value":{"entity-type":"item","numeric-id":3332243,"id":"Q3332243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071503$0248C3BA-4E4A-4CE9-B52D-4595A1C08D7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a3214bf8ab71be756d4f470fe9a5925d62b0f99","datavalue":{"value":{"entity-type":"item","numeric-id":5168480,"id":"Q5168480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4b3ddac81387bbba1fbad2f2c034cb1cbcc31de","datavalue":{"value":{"amount":"+0.8223140239715576","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":"Q1071503$01062FDD-EE0D-4922-AEEE-1260A1697EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09762bc7e5cb10b5860ce5ca5bdba718588b628e","datavalue":{"value":{"entity-type":"item","numeric-id":3087160,"id":"Q3087160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1401b1550b725c733c17d003593306bd9a92367b","datavalue":{"value":{"amount":"+0.8222529888153076","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":"Q1071503$539CE8E0-F8E9-4244-B0BF-40F62EB07E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"672fdba41ada381309ad5604fc8454fd59752e27","datavalue":{"value":{"entity-type":"item","numeric-id":4717942,"id":"Q4717942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d914888d5a1f6acb51b1f5be1c4fa53ad44b9831","datavalue":{"value":{"amount":"+0.8204073309898376","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":"Q1071503$24F6F4B8-FB99-43FE-9AEC-C5667D14DBCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d6e3688db65c7148c2eecd50797b57f77a0d16f","datavalue":{"value":{"entity-type":"item","numeric-id":1930168,"id":"Q1930168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ad3f1b47d39cb1580c69b32e070244f56505f5b","datavalue":{"value":{"amount":"+0.8146596550941467","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":"Q1071503$8BFAFD9C-2FCD-45F7-A770-325440040E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e745dc798c822ed69d521051c91ef7edfe35ef93","datavalue":{"value":{"entity-type":"item","numeric-id":4227320,"id":"Q4227320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87512d3566dadb5da6ee6a8e6da255876f3a1d75","datavalue":{"value":{"amount":"+0.8143590092658997","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":"Q1071503$9607EC16-207F-4DE8-B85C-D285F4AD50A6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1071503","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1071503"}}}}}