{"entities":{"Q757494":{"pageid":759343,"ns":120,"title":"Item:Q757494","lastrevid":49474090,"modified":"2026-01-07T05:30:27Z","type":"item","id":"Q757494","labels":{"en":{"language":"en","value":"Simple algorithms for approximating all roots of a polynomial with real roots"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4191841"}},"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":"Q757494$94D74EDC-1919-46C1-8582-36FEBF302B96","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"09eef2059d2066a9ac136b9eef4baa42aa91f4c8","datavalue":{"value":{"text":"Simple algorithms for approximating all roots of a polynomial with real roots","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q757494$5A90133D-6597-4271-85F1-92B8C433CE87","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d5943f0c418650392bb9669efb1141b28aaa649","datavalue":{"value":"0723.12011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$64868590-CDB8-45A2-8DCD-2167E027E09F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4fb132633268346b4c8c1fc6e5a92121acd14ffa","datavalue":{"value":"10.1016/0885-064X(90)90032-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$0DC5C426-CB40-4848-AB78-D4A3055B8EAA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5c47d3bd353e4c524a3febf79a69d5f4391971a","datavalue":{"value":{"entity-type":"item","numeric-id":757493,"id":"Q757493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$60FC4DE1-09FB-4613-94F7-5D947B7A892B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74ab5fd86840fc5ffff602487c6ddd935d8a77ea","datavalue":{"value":{"entity-type":"item","numeric-id":287182,"id":"Q287182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$FBF9D5DB-C556-4B77-BCFC-59D7C3D75ABF","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":"Q757494$2352AEAB-616C-45CE-802C-604D4191D9D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q757494$3E8E88B0-130C-4602-BE75-420E22D4ACC1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a41ac8ec7aa46ddbe00b1658497edda8b4314897","datavalue":{"value":"Let p be a polynomial of degree n in \\({\\mathbb{Z}}[x]\\) with n distinct real roots. Suppose that the coefficients of p are all in absolute value less than \\(2^ m\\). It is shown that the approximation of all roots of p, within precision \\(2^{-\\mu}\\) is P-uniform \\(NC^ 2\\) and it can be solved by a sequential algorithm using only \\(O(n^ 2(m+\\mu)\\log^ 6(m+n+\\mu))\\) bit operations. The algorithm makes use of a Sturm sequence for p that consists of orthogonal polynomials, with small coefficients.","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$62753508-6FA6-4871-A783-F43CEBCD5712","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$96B54CB6-294A-4032-9141-8C30DF3FEEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c9cf30409c08d8794814df406302eff616099c6f","datavalue":{"value":"12D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$31119C54-B5D7-4A74-8B8D-4B38D962E068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"28cc557c6c35aaa162b4d5c0a30d55d28da55f24","datavalue":{"value":"26C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$C242858A-055B-4AC5-B0E8-A22ABCB1DDB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$05A74FB1-2410-473B-92F8-EBF7574FD3D5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ec43185437055403a4967f12f2852e69d6c6bc4","datavalue":{"value":"4191841","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$D264CE2D-E19B-45E6-82E6-2965646BF158","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2da0fbf091d7932ce73e93e6af2afae51c53e1","datavalue":{"value":"extended Euclidean scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$13D81F52-2EF2-4356-949C-92362FD85189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99b53d2990c18cb9820ef68c629dd6d8432e42b4","datavalue":{"value":"parallel implementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$A5EA10B9-CCEF-4655-8FEA-3460CD5D9283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5d2fa24c579b2baeef4d0446de7aa9ba4289043","datavalue":{"value":"polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$28E23B74-39B4-450C-8AFB-232E80D7038A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64003519e9df2fb98e921e52e29fcdb28331d4f2","datavalue":{"value":"real roots","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$263337E0-8C36-4519-A79C-093CEC849714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"980a7b49e0ea343d488c83dde556c10474fcc9d9","datavalue":{"value":"sequential algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$FF4475CD-D77B-4978-B16D-2AB4E19D92E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b1652efe3631875e53dc6734d51e64ff056d932","datavalue":{"value":"Sturm sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$AD062212-B4C4-4FA0-85DB-DBE9FFEE4D4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a41e1dbcad6d9f1bee6da7b1ba4d857ebc56471","datavalue":{"value":"orthogonal polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q757494$8A0CA452-D9C6-400B-B6C2-F02F391EFCD2","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":"Q757494$52DF75FF-DB7F-41F0-9E47-3C3133194A60","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":"Q757494$FBF1ABBB-F7C5-46F0-9002-EF8786A58BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c7a78759148ce6b1abced42ef4a952f4334dd8","datavalue":{"value":{"entity-type":"item","numeric-id":794429,"id":"Q794429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$4410319E-4A57-46D9-9857-64E38FD6CAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c6716261bba199f9c42479d28bbd2a1ae7657c9","datavalue":{"value":{"entity-type":"item","numeric-id":3814803,"id":"Q3814803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$D61A2975-F956-4EBC-90CE-C7D57CD53BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58ddf6c15587cc8d775178ac7830ee9b5995c206","datavalue":{"value":{"entity-type":"item","numeric-id":5532045,"id":"Q5532045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$FD9D0494-5477-4103-87B0-0C62086CA46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cee49097b5a79aa39fede3ba720a92d45b07ea2","datavalue":{"value":{"entity-type":"item","numeric-id":5653524,"id":"Q5653524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$42D37083-B208-4E7B-AAA7-CC838FEAA890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55f63aa190596f5f038c76fee579c3a35ac46998","datavalue":{"value":{"entity-type":"item","numeric-id":4771385,"id":"Q4771385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$5C3CDC65-C812-4B5D-AF6D-A6C56AAD93B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8f4ac3f710aa0e3501adaea85266318426047f5","datavalue":{"value":{"entity-type":"item","numeric-id":2520840,"id":"Q2520840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$55191603-6197-4926-8579-6B36BDE886D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77057fefe8f6663e6e6a4113f3d1cc1d96bebf03","datavalue":{"value":{"entity-type":"item","numeric-id":1101184,"id":"Q1101184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757494$C9778C13-A518-4E51-B15A-783DBBA94985","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b72f26f8e0bf1ab89058f7385045dded090e5cc4","datavalue":{"value":"https://doi.org/10.1016/0885-064x(90)90032-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q757494$5684C011-84D6-4EB5-8569-A09D6E05702B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4a8164a2a6acb124864d587e929540a4f47e9c3d","datavalue":{"value":"W2039897960","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757494$F0E3B2D2-A09B-420D-99C2-EAD48DDF5621","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdd75403624b1416b72aec21a440fbbc7c18992f","datavalue":{"value":{"entity-type":"item","numeric-id":3814803,"id":"Q3814803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2223d0bd07db0acfa51924b4113704bc3bf9c47c","datavalue":{"value":{"amount":"+0.8693939447402954","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":"Q757494$58E01D9C-3CBC-43A7-ABB4-B70C67F0016F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee34d9d0cff9c091ca39cbb1d49efb27e4d07653","datavalue":{"value":{"entity-type":"item","numeric-id":1329153,"id":"Q1329153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0cef54af9bb51079cd25044a9d5722172c93f30","datavalue":{"value":{"amount":"+0.8371320962905884","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":"Q757494$D9F7B2E7-DBF3-4872-B9F9-763A03941967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc948313bf000f1f4579721ccc552ca08ea64378","datavalue":{"value":{"entity-type":"item","numeric-id":3316585,"id":"Q3316585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6ab87d0429792006cfe9f0a3a0d97f44f9479f4","datavalue":{"value":{"amount":"+0.8193153142929077","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":"Q757494$66D9EA39-CDBD-41D2-96B7-88BF4440790C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"556895749b0daf9caf5e79b27a04c765fb5368f2","datavalue":{"value":{"entity-type":"item","numeric-id":5254174,"id":"Q5254174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa5a9aae1c8d347b891655b495c47d92cc47d510","datavalue":{"value":{"amount":"+0.8118449449539185","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":"Q757494$6BE49056-4CA8-4B03-A4A0-69B301051BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bfceb02855ebae8ff417d7a9ac66fcc8bb656f5","datavalue":{"value":{"entity-type":"item","numeric-id":4018402,"id":"Q4018402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12bddde747021d475de4a6b2ec3672f63d7b18ed","datavalue":{"value":{"amount":"+0.7997088432312012","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":"Q757494$78CCAB88-BF80-4244-83E5-7EEA1BD48773","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:757494","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:757494"}}}}}