Isolating real roots of exact univariate polynomial
93 views
Skip to first unread message
zteitler
Feb 18, 2011, 9:36:28 AM2/18/11
to sage-support
Hello,
I have a polynomial e(x) of degree 13 with integer (exact)
coefficients and 13 distinct real roots. However Sage only finds 11 of
the roots. Unfortunately the polynomial is enormously long --- 11,755
characters. I'm including it at the end of this email but for the
moment I'll just refer to it as e(x).
In the following session,
* I am running Mac OSX 10.6.6 (same results verified on various other
machines)
* The "roots" method (univariate polynomial base class) finds 11 real
roots, even using the arbitrary-precision ring RIF
* The "real_roots" command finds 11 real roots in its default strategy
* The "real_roots" command finds all 13 real roots when the "warp"
strategy is used
* The SARAG library for Maxima finds all 13 real roots.
* 13 is correct, 11 is incorrect (easy to check e(x) changes sign on
each of the 13 root-isolating intervals)
* The enormously long polynomial has been cut out of the session
transcript and moved to the end of this message.
$ uname -a
Darwin NewShiny.local 10.6.0 Darwin Kernel Version 10.6.0: Wed Nov 10
18:13:17 PST 2010; root:xnu-1504.9.26~3/RELEASE_I386 i386
$ sage
----------------------------------------------------------------------
| Sage Version 4.6.1, Release Date: 2011-01-11 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: x=polygen(QQ)
sage: e= <<< long polynomial (see below) >>>
sage: len((e).roots(ring=RIF))
11
sage: from sage.rings.polynomial.real_roots import *
sage: len(real_roots(e))
11
sage: len(real_roots(e,strategy='warp'))
13
sage: maxima.load('sarag')
"/Applications/sage/local/share/maxima/5.22.1/share/contrib/sarag/
sarag.mac"
sage: len(maxima.isolateRoots(e(x),x))
13
This is not a unique example. As part of a computational experiment
with Frank Sottile, et al, we counted real roots of several billion
polynomials (which were eliminants of Schubert problems, but that is
another story), using Maple. A small percentage of these were re-
computed with Sage. Out of tens of millions of polynomials computed by
both Maple and Sage, about half a dozen gave different answers, and
unfortunately Sage was wrong each time. So it's certainly not a common
problem but it does happen.
This was all a few years ago and I've long since lost the other half
dozen or so "bad" polynomials; the polynomial in this bug report is
the only example I can find after going through my old emails.
I hope this will be helpful in tracking down the bug in roots and
real_roots.
Yours,
Zach Teitler
59481316398268359517618545213046851912964496891837781737253908285820184358576518918331892948345506468402587222714520564881849748315726678084194377531667089935430386473276237276868726258607148061453788200027961533830299743986101020066307994985554187290304388967170862679903105948086638805120933659138858836739636309322745889430398171062143174675527535607475052635698090427493630626498934714975705532702963860803341205998746444514665282319479236367879450835910400543902652764232336638724759207903322599852767358006205416591529630542909820328704301549026877015968140894695400403083301908221984042134041031462240199261997792590722976765627660622072789245826448454206248332296059683338846951908478803516236478744540758583904700113460734744321078113406009889732417224313233356960473431466281087490670834920743761125196277816231577311143834409*x^13-367387313485662854313108560960339239918089056647951044084990517410323033458989291624001543622364856743627549208933704812861904512695952644041874950494385038444124441733091459208645387839548924553938920284142736467093839647877725690874167663019213168264846911528478749728120891576397237228972330986409588858647099303308075041563526323191580989985831833605656856839437388714345294926387652528421782014753289331887390403200060683934143808301907509139411427123666136182139793329862830630595079375362378851262359700938329921048108465986603268958524459381108156060898138497592586266682256229152140428337420969695558883845571459347610867492093834619287035036507398513075525125692857846509559798512424004609891753588724180629438194823906662802228267875836614909909015097296463283531035732867237826050963244685360607172830396279040021453782463064*x^12+891192698806037753144038795520866301922674334513376324591826110016462506273173629241814265394441979854376695750913737179669860923212922948620882889563271135848378212715281472276586070325847059929548269523037786545521307519261447922321742785484361958814759646302854149987929235054900111221616717078580602768635284923960143482627236565057636809084597511182254806837594832477320030227806935924019118726268604078892002012240155506283349512787839514150728056408262447853508038792819483528523121019164962203192521529112779851605942165391303855137685722246047923215859382620360419122608267018156374964590816625877236397506580174389175983537011263750544678740404418583087541887622488896123047459452776261751436018858859559218703911747455177059364378990183291401784130863375145089250439086319505132022919417831836917707364574511743553559303752240*x^11-1053193887836464165333250032265108190239457004572811656891586327901621234092527120620982700924845995372158975186276334635036090027963025475706827889717609458838944900723287224828972046915772246811618844597333789165897858867855770347163642908875818984481137627001116747268885562270355611144660501659679340455449989065494336742310592582063141103947350886372636254009045410930470344017539821721518904247580099891580492808539098836418035527323678343988579827004935262492657752621979256464075493861448919735258112094299212132505748432530451084740757948306453063169812689862280608608695966156649238460724160085871203148787361737133194994293364298855720902778025639782910887594823504957189519137111806413737504959066229294176457895100922814354300139488369505935415481987575150433272662822787626267952418711675671024374275274829815486168553465600*x^10+573438783601621519415879979640613314525381933303759225592269607158815216059750759663585241241025689932911371141390033483548534198586897834327012097986738265283424173683746063811235581122996698837393042881097104154441459549176294595893582398035816029431111297368136984083563015052360074140682900566329250021902867266573463990326839011559745678803689259560206192057985958723883703031555545831726763276455272826834593973092151670707376841415573906319412953306824404580904920012965822595645173426582145821687662749238370627450974202287529934147616655724314834677677198147986958827428782064561210965038831450598703772841384871970006879658032169290069068766922927664042244821190755607690372126441478474718974500544191516592122262465475232642253757339667666719671035502646583147110375430962965920828800830817981826137288473461017053921630368256*x^9-48914012495868125558863213624229494230874576897006376047880864275653417521102861304791047814495582130823020536677501106514165452670106797158367407580001722627738477095718085846103873674964751558807633806242967627618963675035672215051983385654602452080559336883154647956401256133411955848294277612607304957983995401847138953574031200644115545697905198902962035159871344927034480880575355225717340084581853454565737993749277575985364453211188730466178124976421009228214705736778777517221567729896433200921440119255371747353196631072432975419569615649982136657268496850679413817785515715738031797618141272734298346319544807698970311850992058667641072994550659882915946132611269190323190978467389728913092926352286333812722057997559118535426558824800459319128681693279623012621809537922945889664888768733248466458808945427071727687728283648*x^8-75967277872542974700557313435672356313267826265013286555410117123893032193362128783971987347996273759559698433586001642570995442406506373278140220532876867338511905335758936811757658584915206579943677929102499174068392160985658508260298719914466890882937630983066201924159113288419983015328754449482715999920570751143624290776227105092950664409602320399636826891261394700414038535151086239020568794394230275174813109643543982559058937858099270167781938439499593492662057895126226712632922283340876598399833211453486821090181375212647702241939340905665445825618692307067375841515442006083946526545994497707822975370536838219798010618723287348811049768009795424776133573278669559861358218889457349742646554377726963622561356421358871961002619797226742458477680284959556834470704588621912021449357553050801371695598010331445176209199423488*x^7+19099459869684537950039971477767619714019998840937054962403236952843852106205104287874104645227566402113465642855377087291115209400912428028183164229457684115736099646514318053076616478018951149381881649474760467057670330910429329206714538709159452787805164005734635819658114997957491986561339611739395397364511953931720728441495316316056604485847091444562256307441330734757601653131052933614147185702470621305782674895951623594650303165906271870831262529214718037756019666352211383935910747522645748631156241567706737377975968236862238696925148290720988337780300882893528798835240147664825108461150698564908566975327616189845086172667256517811192750438110286283616956047291267234881749758195510579597363093245029838762355190839356962302076663132515510583274227951130010895868695772874824677907072757854642053040730827394054675733217280*x^6+2940217062502855373640591935119818340109628621654454720572619773545275404209529762113342331075867596905741327405683312846284946033292170186554092945936696276347362889269213399421772323366413142110946472748141502671302380922997652405494343587326512623496645572788619391969091479288357482680923848295747292401317424020857518634078114000241630608825587919968078270957718476594730092960696723772536710981217850949544683644974124631971279326057945046726221765876263773525013251177604296145909428060967286456850129731172143385871100968713646719239465897109446133285922301258238586202376826850262823750948439589321891892310155364983852753403771997251355570822351443644453256884987796612746531679155359376458068827435664709699625765795474969283978013106223111578962510896111319300765265503723598229833949434724115602154919768855787245775421440*x^5-631838720936412105660884608445339693679950225040399938713955834977215469821179786717936715482663090605080444023856513060647982622626831248562042361090608143761298678731699441092386889313600986729487378432874427535417943505124937196317350747491395912003738671711569790423628029504326969966734278043650151582995553096542680893774444710159297007140882949071513485278660346258946300313325578743420640242699799529356047695887996172330112407341314618409267947612812543495899719826928289430489199878724034280741937812201810130612397251990145628778988594510882154778219141681135828019016131695325576125004341648163194169593776749059348558719666782600996040265901214783002395854228805396587742188459547511384279319195723779899751521703947081712044347068358427528622602613413501101232065967229371393304704161768040845818432635994145064296644608*x^4-55283581357356061559520574001537312991052669160762013118333327523484855094065451935451722646612888047447623726840781631420364640958715066167468392816427227228775641871641388478621146643942570703866183689100228176004529603523288113234387316909282962897304811384220415249960259851910686420372317915819421896227597909724805486555564757532815317787425710860595180215188352428188126508551925818446731222160773928753708329270235520342276572767395623484752310196252805703001278559082336782319989305028606965213547364136378340201108528898786452777309041182841362854702883061128643028468128263059714381770168202729607422495632661419458922951807027860652124636662474637452224832702059200716490928118848828703714818648889992444627885730231904659487104025159902095659758358973628392567025575030596458103177782855452452736220359453085723333230592*x^3+1803645499967115681805547544677144321804176204990623766385309570898675673677918228841082403978812870999445667155102230855999645236072379447294073291756290967551214546859769621859748016137333961227344152429211448591157137577444181310419242295422807446737699156661905255289810430970296605854667683263072067697346714188312847716148808384715622478924221809984233180301585847066850219751287018584974441471242565707920122382379825256538679792119513091055273959717102359275050917825476393167477957437220314374992539354385691647396109853332591122022078433778587495357883631400070167979216479511556452053033742958704868309440053166751724441206660228267495361857879787818448788579675401209680737314323582401439131385345176627379209022496511718490816810681216183903114908200166317594403704162709276059423488237718889762737183226478518641623040*x^2+170433495871623470089431544165143113371851970029735123143927218064979606962642942782796732808280799131665774502219097161946196545539602295876524662578519745162293748070681268383627619065415791408545325201006804371925578125431193815522574261268529763806404331314809240213317774827718699312010358472978998579475976064389110649877468492630560568309479391377560736086451303061073393859418289836208146610091790693064632374473746500911383349980919992145725696433262668744129952456673311211008581846271601275816733747240956263612270687348632578438148034287965993056643359826587640763763049892188641267330081117324368396535432757532354462408870448049262097498596901586304570234276316396690023088884736998904481058832107866260934375303580355185495950813038707138673467534510876243266012010785336755288795882237115233822113265307104533544960*x
+2433417554630943329543231620982222740160869017859615167633956669012907711393175958540131400749514728474013955539825011362793953181192292830884162051367273183389857357562856708338024013702180029191096842988256464712482372063500520663794004844480158980482622172697904361857217671104597539510066016344534634624978005984338145187182525538349282021851058708600234618116357732765191741887571073993137976931300601443946953903016688343686864790128267139079219458861084148342186522055277096639542146467465457393699384602189099697986457289280361533440399289720479264400887629250153367956327193265194228379144596970373717436274223705752417596596721257236335910324731595575069476360854473235399809568835469731405773951292772806606987831856928826591739578331541187821560909090695155530451528136687215302747469691927337349422117708105777152000
I have a polynomial e(x) of degree 13 with integer (exact)
coefficients and 13 distinct real roots. However Sage only finds 11 of
the roots. Unfortunately the polynomial is enormously long --- 11,755
characters. I'm including it at the end of this email but for the
moment I'll just refer to it as e(x).
In the following session,
* I am running Mac OSX 10.6.6 (same results verified on various other
machines)
* The "roots" method (univariate polynomial base class) finds 11 real
roots, even using the arbitrary-precision ring RIF
* The "real_roots" command finds 11 real roots in its default strategy
* The "real_roots" command finds all 13 real roots when the "warp"
strategy is used
* The SARAG library for Maxima finds all 13 real roots.
* 13 is correct, 11 is incorrect (easy to check e(x) changes sign on
each of the 13 root-isolating intervals)
* The enormously long polynomial has been cut out of the session
transcript and moved to the end of this message.
$ uname -a
Darwin NewShiny.local 10.6.0 Darwin Kernel Version 10.6.0: Wed Nov 10
18:13:17 PST 2010; root:xnu-1504.9.26~3/RELEASE_I386 i386
$ sage
----------------------------------------------------------------------
| Sage Version 4.6.1, Release Date: 2011-01-11 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: x=polygen(QQ)
sage: e= <<< long polynomial (see below) >>>
sage: len((e).roots(ring=RIF))
11
sage: from sage.rings.polynomial.real_roots import *
sage: len(real_roots(e))
11
sage: len(real_roots(e,strategy='warp'))
13
sage: maxima.load('sarag')
"/Applications/sage/local/share/maxima/5.22.1/share/contrib/sarag/
sarag.mac"
sage: len(maxima.isolateRoots(e(x),x))
13
This is not a unique example. As part of a computational experiment
with Frank Sottile, et al, we counted real roots of several billion
polynomials (which were eliminants of Schubert problems, but that is
another story), using Maple. A small percentage of these were re-
computed with Sage. Out of tens of millions of polynomials computed by
both Maple and Sage, about half a dozen gave different answers, and
unfortunately Sage was wrong each time. So it's certainly not a common
problem but it does happen.
This was all a few years ago and I've long since lost the other half
dozen or so "bad" polynomials; the polynomial in this bug report is
the only example I can find after going through my old emails.
I hope this will be helpful in tracking down the bug in roots and
real_roots.
Yours,
Zach Teitler
59481316398268359517618545213046851912964496891837781737253908285820184358576518918331892948345506468402587222714520564881849748315726678084194377531667089935430386473276237276868726258607148061453788200027961533830299743986101020066307994985554187290304388967170862679903105948086638805120933659138858836739636309322745889430398171062143174675527535607475052635698090427493630626498934714975705532702963860803341205998746444514665282319479236367879450835910400543902652764232336638724759207903322599852767358006205416591529630542909820328704301549026877015968140894695400403083301908221984042134041031462240199261997792590722976765627660622072789245826448454206248332296059683338846951908478803516236478744540758583904700113460734744321078113406009889732417224313233356960473431466281087490670834920743761125196277816231577311143834409*x^13-367387313485662854313108560960339239918089056647951044084990517410323033458989291624001543622364856743627549208933704812861904512695952644041874950494385038444124441733091459208645387839548924553938920284142736467093839647877725690874167663019213168264846911528478749728120891576397237228972330986409588858647099303308075041563526323191580989985831833605656856839437388714345294926387652528421782014753289331887390403200060683934143808301907509139411427123666136182139793329862830630595079375362378851262359700938329921048108465986603268958524459381108156060898138497592586266682256229152140428337420969695558883845571459347610867492093834619287035036507398513075525125692857846509559798512424004609891753588724180629438194823906662802228267875836614909909015097296463283531035732867237826050963244685360607172830396279040021453782463064*x^12+891192698806037753144038795520866301922674334513376324591826110016462506273173629241814265394441979854376695750913737179669860923212922948620882889563271135848378212715281472276586070325847059929548269523037786545521307519261447922321742785484361958814759646302854149987929235054900111221616717078580602768635284923960143482627236565057636809084597511182254806837594832477320030227806935924019118726268604078892002012240155506283349512787839514150728056408262447853508038792819483528523121019164962203192521529112779851605942165391303855137685722246047923215859382620360419122608267018156374964590816625877236397506580174389175983537011263750544678740404418583087541887622488896123047459452776261751436018858859559218703911747455177059364378990183291401784130863375145089250439086319505132022919417831836917707364574511743553559303752240*x^11-1053193887836464165333250032265108190239457004572811656891586327901621234092527120620982700924845995372158975186276334635036090027963025475706827889717609458838944900723287224828972046915772246811618844597333789165897858867855770347163642908875818984481137627001116747268885562270355611144660501659679340455449989065494336742310592582063141103947350886372636254009045410930470344017539821721518904247580099891580492808539098836418035527323678343988579827004935262492657752621979256464075493861448919735258112094299212132505748432530451084740757948306453063169812689862280608608695966156649238460724160085871203148787361737133194994293364298855720902778025639782910887594823504957189519137111806413737504959066229294176457895100922814354300139488369505935415481987575150433272662822787626267952418711675671024374275274829815486168553465600*x^10+573438783601621519415879979640613314525381933303759225592269607158815216059750759663585241241025689932911371141390033483548534198586897834327012097986738265283424173683746063811235581122996698837393042881097104154441459549176294595893582398035816029431111297368136984083563015052360074140682900566329250021902867266573463990326839011559745678803689259560206192057985958723883703031555545831726763276455272826834593973092151670707376841415573906319412953306824404580904920012965822595645173426582145821687662749238370627450974202287529934147616655724314834677677198147986958827428782064561210965038831450598703772841384871970006879658032169290069068766922927664042244821190755607690372126441478474718974500544191516592122262465475232642253757339667666719671035502646583147110375430962965920828800830817981826137288473461017053921630368256*x^9-48914012495868125558863213624229494230874576897006376047880864275653417521102861304791047814495582130823020536677501106514165452670106797158367407580001722627738477095718085846103873674964751558807633806242967627618963675035672215051983385654602452080559336883154647956401256133411955848294277612607304957983995401847138953574031200644115545697905198902962035159871344927034480880575355225717340084581853454565737993749277575985364453211188730466178124976421009228214705736778777517221567729896433200921440119255371747353196631072432975419569615649982136657268496850679413817785515715738031797618141272734298346319544807698970311850992058667641072994550659882915946132611269190323190978467389728913092926352286333812722057997559118535426558824800459319128681693279623012621809537922945889664888768733248466458808945427071727687728283648*x^8-75967277872542974700557313435672356313267826265013286555410117123893032193362128783971987347996273759559698433586001642570995442406506373278140220532876867338511905335758936811757658584915206579943677929102499174068392160985658508260298719914466890882937630983066201924159113288419983015328754449482715999920570751143624290776227105092950664409602320399636826891261394700414038535151086239020568794394230275174813109643543982559058937858099270167781938439499593492662057895126226712632922283340876598399833211453486821090181375212647702241939340905665445825618692307067375841515442006083946526545994497707822975370536838219798010618723287348811049768009795424776133573278669559861358218889457349742646554377726963622561356421358871961002619797226742458477680284959556834470704588621912021449357553050801371695598010331445176209199423488*x^7+19099459869684537950039971477767619714019998840937054962403236952843852106205104287874104645227566402113465642855377087291115209400912428028183164229457684115736099646514318053076616478018951149381881649474760467057670330910429329206714538709159452787805164005734635819658114997957491986561339611739395397364511953931720728441495316316056604485847091444562256307441330734757601653131052933614147185702470621305782674895951623594650303165906271870831262529214718037756019666352211383935910747522645748631156241567706737377975968236862238696925148290720988337780300882893528798835240147664825108461150698564908566975327616189845086172667256517811192750438110286283616956047291267234881749758195510579597363093245029838762355190839356962302076663132515510583274227951130010895868695772874824677907072757854642053040730827394054675733217280*x^6+2940217062502855373640591935119818340109628621654454720572619773545275404209529762113342331075867596905741327405683312846284946033292170186554092945936696276347362889269213399421772323366413142110946472748141502671302380922997652405494343587326512623496645572788619391969091479288357482680923848295747292401317424020857518634078114000241630608825587919968078270957718476594730092960696723772536710981217850949544683644974124631971279326057945046726221765876263773525013251177604296145909428060967286456850129731172143385871100968713646719239465897109446133285922301258238586202376826850262823750948439589321891892310155364983852753403771997251355570822351443644453256884987796612746531679155359376458068827435664709699625765795474969283978013106223111578962510896111319300765265503723598229833949434724115602154919768855787245775421440*x^5-631838720936412105660884608445339693679950225040399938713955834977215469821179786717936715482663090605080444023856513060647982622626831248562042361090608143761298678731699441092386889313600986729487378432874427535417943505124937196317350747491395912003738671711569790423628029504326969966734278043650151582995553096542680893774444710159297007140882949071513485278660346258946300313325578743420640242699799529356047695887996172330112407341314618409267947612812543495899719826928289430489199878724034280741937812201810130612397251990145628778988594510882154778219141681135828019016131695325576125004341648163194169593776749059348558719666782600996040265901214783002395854228805396587742188459547511384279319195723779899751521703947081712044347068358427528622602613413501101232065967229371393304704161768040845818432635994145064296644608*x^4-55283581357356061559520574001537312991052669160762013118333327523484855094065451935451722646612888047447623726840781631420364640958715066167468392816427227228775641871641388478621146643942570703866183689100228176004529603523288113234387316909282962897304811384220415249960259851910686420372317915819421896227597909724805486555564757532815317787425710860595180215188352428188126508551925818446731222160773928753708329270235520342276572767395623484752310196252805703001278559082336782319989305028606965213547364136378340201108528898786452777309041182841362854702883061128643028468128263059714381770168202729607422495632661419458922951807027860652124636662474637452224832702059200716490928118848828703714818648889992444627885730231904659487104025159902095659758358973628392567025575030596458103177782855452452736220359453085723333230592*x^3+1803645499967115681805547544677144321804176204990623766385309570898675673677918228841082403978812870999445667155102230855999645236072379447294073291756290967551214546859769621859748016137333961227344152429211448591157137577444181310419242295422807446737699156661905255289810430970296605854667683263072067697346714188312847716148808384715622478924221809984233180301585847066850219751287018584974441471242565707920122382379825256538679792119513091055273959717102359275050917825476393167477957437220314374992539354385691647396109853332591122022078433778587495357883631400070167979216479511556452053033742958704868309440053166751724441206660228267495361857879787818448788579675401209680737314323582401439131385345176627379209022496511718490816810681216183903114908200166317594403704162709276059423488237718889762737183226478518641623040*x^2+170433495871623470089431544165143113371851970029735123143927218064979606962642942782796732808280799131665774502219097161946196545539602295876524662578519745162293748070681268383627619065415791408545325201006804371925578125431193815522574261268529763806404331314809240213317774827718699312010358472978998579475976064389110649877468492630560568309479391377560736086451303061073393859418289836208146610091790693064632374473746500911383349980919992145725696433262668744129952456673311211008581846271601275816733747240956263612270687348632578438148034287965993056643359826587640763763049892188641267330081117324368396535432757532354462408870448049262097498596901586304570234276316396690023088884736998904481058832107866260934375303580355185495950813038707138673467534510876243266012010785336755288795882237115233822113265307104533544960*x
+2433417554630943329543231620982222740160869017859615167633956669012907711393175958540131400749514728474013955539825011362793953181192292830884162051367273183389857357562856708338024013702180029191096842988256464712482372063500520663794004844480158980482622172697904361857217671104597539510066016344534634624978005984338145187182525538349282021851058708600234618116357732765191741887571073993137976931300601443946953903016688343686864790128267139079219458861084148342186522055277096639542146467465457393699384602189099697986457289280361533440399289720479264400887629250153367956327193265194228379144596970373717436274223705752417596596721257236335910324731595575069476360854473235399809568835469731405773951292772806606987831856928826591739578331541187821560909090695155530451528136687215302747469691927337349422117708105777152000
zteitler
Feb 18, 2011, 9:41:19 AM2/18/11
to sage-support
I was not sufficiently careful in posting my polynomial e(x) and
apparently some bad line breaks and spaces were introduced. This reply
is to post a properly-wrapped copy of the polynomial.
Zach Teitler
594813163982683595176185452130468519129644968918377817372539082858201843
585765189183318929483455064684025872227145205648818497483157266780841943
775316670899354303864732762372768687262586071480614537882000279615338302
997439861010200663079949855541872903043889671708626799031059480866388051
209336591388588367396363093227458894303981710621431746755275356074750526
356980904274936306264989347149757055327029638608033412059987464445146652
823194792363678794508359104005439026527642323366387247592079033225998527
673580062054165915296305429098203287043015490268770159681408946954004030
833019082219840421340410314622401992619977925907229767656276606220727892
458264484542062483322960596833388469519084788035162364787445407585839047
001134607347443210781134060098897324172243132333569604734314662810874906
70834920743761125196277816231577311143834409*x^13-
367387313485662854313108560960339239918089056647951044084990517410323033
458989291624001543622364856743627549208933704812861904512695952644041874
950494385038444124441733091459208645387839548924553938920284142736467093
839647877725690874167663019213168264846911528478749728120891576397237228
972330986409588858647099303308075041563526323191580989985831833605656856
839437388714345294926387652528421782014753289331887390403200060683934143
808301907509139411427123666136182139793329862830630595079375362378851262
359700938329921048108465986603268958524459381108156060898138497592586266
682256229152140428337420969695558883845571459347610867492093834619287035
036507398513075525125692857846509559798512424004609891753588724180629438
194823906662802228267875836614909909015097296463283531035732867237826050
963244685360607172830396279040021453782463064*x^12+
891192698806037753144038795520866301922674334513376324591826110016462506
273173629241814265394441979854376695750913737179669860923212922948620882
889563271135848378212715281472276586070325847059929548269523037786545521
307519261447922321742785484361958814759646302854149987929235054900111221
616717078580602768635284923960143482627236565057636809084597511182254806
837594832477320030227806935924019118726268604078892002012240155506283349
512787839514150728056408262447853508038792819483528523121019164962203192
521529112779851605942165391303855137685722246047923215859382620360419122
608267018156374964590816625877236397506580174389175983537011263750544678
740404418583087541887622488896123047459452776261751436018858859559218703
911747455177059364378990183291401784130863375145089250439086319505132022
919417831836917707364574511743553559303752240*x^11-
105319388783646416533325003226510819023945700457281165689158632790162123
409252712062098270092484599537215897518627633463503609002796302547570682
788971760945883894490072328722482897204691577224681161884459733378916589
785886785577034716364290887581898448113762700111674726888556227035561114
466050165967934045544998906549433674231059258206314110394735088637263625
400904541093047034401753982172151890424758009989158049280853909883641803
552732367834398857982700493526249265775262197925646407549386144891973525
811209429921213250574843253045108474075794830645306316981268986228060860
869596615664923846072416008587120314878736173713319499429336429885572090
277802563978291088759482350495718951913711180641373750495906622929417645
789510092281435430013948836950593541548198757515043327266282278762626795
2418711675671024374275274829815486168553465600*x^10+
573438783601621519415879979640613314525381933303759225592269607158815216
059750759663585241241025689932911371141390033483548534198586897834327012
097986738265283424173683746063811235581122996698837393042881097104154441
459549176294595893582398035816029431111297368136984083563015052360074140
682900566329250021902867266573463990326839011559745678803689259560206192
057985958723883703031555545831726763276455272826834593973092151670707376
841415573906319412953306824404580904920012965822595645173426582145821687
662749238370627450974202287529934147616655724314834677677198147986958827
428782064561210965038831450598703772841384871970006879658032169290069068
766922927664042244821190755607690372126441478474718974500544191516592122
262465475232642253757339667666719671035502646583147110375430962965920828
800830817981826137288473461017053921630368256*x^9-
489140124958681255588632136242294942308745768970063760478808642756534175
211028613047910478144955821308230205366775011065141654526701067971583674
075800017226277384770957180858461038736749647515588076338062429676276189
636750356722150519833856546024520805593368831546479564012561334119558482
942776126073049579839954018471389535740312006441155456979051989029620351
598713449270344808805753552257173400845818534545657379937492775759853644
532111887304661781249764210092282147057367787775172215677298964332009214
401192553717473531966310724329754195696156499821366572684968506794138177
855157157380317976181412727342983463195448076989703118509920586676410729
945506598829159461326112691903231909784673897289130929263522863338127220
579975591185354265588248004593191286816932796230126218095379229458896648
88768733248466458808945427071727687728283648*x^8-
759672778725429747005573134356723563132678262650132865554101171238930321
933621287839719873479962737595596984335860016425709954424065063732781402
205328768673385119053357589368117576585849152065799436779291024991740683
921609856585082602987199144668908829376309830662019241591132884199830153
287544494827159999205707511436242907762271050929506644096023203996368268
912613947004140385351510862390205687943942302751748131096435439825590589
378580992701677819384394995934926620578951262267126329222833408765983998
332114534868210901813752126477022419393409056654458256186923070673758415
154420060839465265459944977078229753705368382197980106187232873488110497
680097954247761335732786695598613582188894573497426465543777269636225613
564213588719610026197972267424584776802849595568344707045886219120214493
57553050801371695598010331445176209199423488*x^7+
190994598696845379500399714777676197140199988409370549624032369528438521
062051042878741046452275664021134656428553770872911152094009124280281831
642294576841157360996465143180530766164780189511493818816494747604670576
703309104293292067145387091594527878051640057346358196581149979574919865
613396117393953973645119539317207284414953163160566044858470914445622563
074413307347576016531310529336141471857024706213057826748959516235946503
031659062718708312625292147180377560196663522113839359107475226457486311
562415677067373779759682368622386969251482907209883377803008828935287988
352401476648251084611506985649085669753276161898450861726672565178111927
504381102862836169560472912672348817497581955105795973630932450298387623
551908393569623020766631325155105832742279511300108958686957728748246779
07072757854642053040730827394054675733217280*x^6+
294021706250285537364059193511981834010962862165445472057261977354527540
420952976211334233107586759690574132740568331284628494603329217018655409
294593669627634736288926921339942177232336641314211094647274814150267130
238092299765240549434358732651262349664557278861939196909147928835748268
092384829574729240131742402085751863407811400024163060882558791996807827
095771847659473009296069672377253671098121785094954468364497412463197127
932605794504672622176587626377352501325117760429614590942806096728645685
012973117214338587110096871364671923946589710944613328592230125823858620
237682685026282375094843958932189189231015536498385275340377199725135557
082235144364445325688498779661274653167915535937645806882743566470969962
576579547496928397801310622311157896251089611131930076526550372359822983
3949434724115602154919768855787245775421440*x^5-
631838720936412105660884608445339693679950225040399938713955834977215469
821179786717936715482663090605080444023856513060647982622626831248562042
361090608143761298678731699441092386889313600986729487378432874427535417
943505124937196317350747491395912003738671711569790423628029504326969966
734278043650151582995553096542680893774444710159297007140882949071513485
278660346258946300313325578743420640242699799529356047695887996172330112
407341314618409267947612812543495899719826928289430489199878724034280741
937812201810130612397251990145628778988594510882154778219141681135828019
016131695325576125004341648163194169593776749059348558719666782600996040
265901214783002395854228805396587742188459547511384279319195723779899751
521703947081712044347068358427528622602613413501101232065967229371393304
704161768040845818432635994145064296644608*x^4-
552835813573560615595205740015373129910526691607620131183333275234848550
940654519354517226466128880474476237268407816314203646409587150661674683
928164272272287756418716413884786211466439425707038661836891002281760045
296035232881132343873169092829628973048113842204152499602598519106864203
723179158194218962275979097248054865555647575328153177874257108605951802
151883524281881265085519258184467312221607739287537083292702355203422765
727673956234847523101962528057030012785590823367823199893050286069652135
473641363783402011085288987864527773090411828413628547028830611286430284
681282630597143817701682027296074224956326614194589229518070278606521246
366624746374522248327020592007164909281188488287037148186488899924446278
857302319046594871040251599020956597583589736283925670255750305964581031
77782855452452736220359453085723333230592*x^3+
180364549996711568180554754467714432180417620499062376638530957089867567
367791822884108240397881287099944566715510223085599964523607237944729407
329175629096755121454685976962185974801613733396122734415242921144859115
713757744418131041924229542280744673769915666190525528981043097029660585
466768326307206769734671418831284771614880838471562247892422180998423318
030158584706685021975128701858497444147124256570792012238237982525653867
979211951309105527395971710235927505091782547639316747795743722031437499
253935438569164739610985333259112202207843377858749535788363140007016797
921647951155645205303374295870486830944005316675172444120666022826749536
185787978781844878857967540120968073731432358240143913138534517662737920
902249651171849081681068121618390311490820016631759440370416270927605942
3488237718889762737183226478518641623040*x^2+
170433495871623470089431544165143113371851970029735123143927218064979606
962642942782796732808280799131665774502219097161946196545539602295876524
662578519745162293748070681268383627619065415791408545325201006804371925
578125431193815522574261268529763806404331314809240213317774827718699312
010358472978998579475976064389110649877468492630560568309479391377560736
086451303061073393859418289836208146610091790693064632374473746500911383
349980919992145725696433262668744129952456673311211008581846271601275816
733747240956263612270687348632578438148034287965993056643359826587640763
763049892188641267330081117324368396535432757532354462408870448049262097
498596901586304570234276316396690023088884736998904481058832107866260934
375303580355185495950813038707138673467534510876243266012010785336755288
795882237115233822113265307104533544960*x+
243341755463094332954323162098222274016086901785961516763395666901290771
139317595854013140074951472847401395553982501136279395318119229283088416
205136727318338985735756285670833802401370218002919109684298825646471248
237206350052066379400484448015898048262217269790436185721767110459753951
006601634453463462497800598433814518718252553834928202185105870860023461
811635773276519174188757107399313797693130060144394695390301668834368686
479012826713907921945886108414834218652205527709663954214646746545739369
938460218909969798645728928036153344039928972047926440088762925015336795
632719326519422837914459697037371743627422370575241759659672125723633591
032473159557506947636085447323539980956883546973140577395129277280660698
783185692882659173957833154118782156090909069515553045152813668721530274
7469691927337349422117708105777152000
apparently some bad line breaks and spaces were introduced. This reply
is to post a properly-wrapped copy of the polynomial.
Zach Teitler
594813163982683595176185452130468519129644968918377817372539082858201843
585765189183318929483455064684025872227145205648818497483157266780841943
775316670899354303864732762372768687262586071480614537882000279615338302
997439861010200663079949855541872903043889671708626799031059480866388051
209336591388588367396363093227458894303981710621431746755275356074750526
356980904274936306264989347149757055327029638608033412059987464445146652
823194792363678794508359104005439026527642323366387247592079033225998527
673580062054165915296305429098203287043015490268770159681408946954004030
833019082219840421340410314622401992619977925907229767656276606220727892
458264484542062483322960596833388469519084788035162364787445407585839047
001134607347443210781134060098897324172243132333569604734314662810874906
70834920743761125196277816231577311143834409*x^13-
367387313485662854313108560960339239918089056647951044084990517410323033
458989291624001543622364856743627549208933704812861904512695952644041874
950494385038444124441733091459208645387839548924553938920284142736467093
839647877725690874167663019213168264846911528478749728120891576397237228
972330986409588858647099303308075041563526323191580989985831833605656856
839437388714345294926387652528421782014753289331887390403200060683934143
808301907509139411427123666136182139793329862830630595079375362378851262
359700938329921048108465986603268958524459381108156060898138497592586266
682256229152140428337420969695558883845571459347610867492093834619287035
036507398513075525125692857846509559798512424004609891753588724180629438
194823906662802228267875836614909909015097296463283531035732867237826050
963244685360607172830396279040021453782463064*x^12+
891192698806037753144038795520866301922674334513376324591826110016462506
273173629241814265394441979854376695750913737179669860923212922948620882
889563271135848378212715281472276586070325847059929548269523037786545521
307519261447922321742785484361958814759646302854149987929235054900111221
616717078580602768635284923960143482627236565057636809084597511182254806
837594832477320030227806935924019118726268604078892002012240155506283349
512787839514150728056408262447853508038792819483528523121019164962203192
521529112779851605942165391303855137685722246047923215859382620360419122
608267018156374964590816625877236397506580174389175983537011263750544678
740404418583087541887622488896123047459452776261751436018858859559218703
911747455177059364378990183291401784130863375145089250439086319505132022
919417831836917707364574511743553559303752240*x^11-
105319388783646416533325003226510819023945700457281165689158632790162123
409252712062098270092484599537215897518627633463503609002796302547570682
788971760945883894490072328722482897204691577224681161884459733378916589
785886785577034716364290887581898448113762700111674726888556227035561114
466050165967934045544998906549433674231059258206314110394735088637263625
400904541093047034401753982172151890424758009989158049280853909883641803
552732367834398857982700493526249265775262197925646407549386144891973525
811209429921213250574843253045108474075794830645306316981268986228060860
869596615664923846072416008587120314878736173713319499429336429885572090
277802563978291088759482350495718951913711180641373750495906622929417645
789510092281435430013948836950593541548198757515043327266282278762626795
2418711675671024374275274829815486168553465600*x^10+
573438783601621519415879979640613314525381933303759225592269607158815216
059750759663585241241025689932911371141390033483548534198586897834327012
097986738265283424173683746063811235581122996698837393042881097104154441
459549176294595893582398035816029431111297368136984083563015052360074140
682900566329250021902867266573463990326839011559745678803689259560206192
057985958723883703031555545831726763276455272826834593973092151670707376
841415573906319412953306824404580904920012965822595645173426582145821687
662749238370627450974202287529934147616655724314834677677198147986958827
428782064561210965038831450598703772841384871970006879658032169290069068
766922927664042244821190755607690372126441478474718974500544191516592122
262465475232642253757339667666719671035502646583147110375430962965920828
800830817981826137288473461017053921630368256*x^9-
489140124958681255588632136242294942308745768970063760478808642756534175
211028613047910478144955821308230205366775011065141654526701067971583674
075800017226277384770957180858461038736749647515588076338062429676276189
636750356722150519833856546024520805593368831546479564012561334119558482
942776126073049579839954018471389535740312006441155456979051989029620351
598713449270344808805753552257173400845818534545657379937492775759853644
532111887304661781249764210092282147057367787775172215677298964332009214
401192553717473531966310724329754195696156499821366572684968506794138177
855157157380317976181412727342983463195448076989703118509920586676410729
945506598829159461326112691903231909784673897289130929263522863338127220
579975591185354265588248004593191286816932796230126218095379229458896648
88768733248466458808945427071727687728283648*x^8-
759672778725429747005573134356723563132678262650132865554101171238930321
933621287839719873479962737595596984335860016425709954424065063732781402
205328768673385119053357589368117576585849152065799436779291024991740683
921609856585082602987199144668908829376309830662019241591132884199830153
287544494827159999205707511436242907762271050929506644096023203996368268
912613947004140385351510862390205687943942302751748131096435439825590589
378580992701677819384394995934926620578951262267126329222833408765983998
332114534868210901813752126477022419393409056654458256186923070673758415
154420060839465265459944977078229753705368382197980106187232873488110497
680097954247761335732786695598613582188894573497426465543777269636225613
564213588719610026197972267424584776802849595568344707045886219120214493
57553050801371695598010331445176209199423488*x^7+
190994598696845379500399714777676197140199988409370549624032369528438521
062051042878741046452275664021134656428553770872911152094009124280281831
642294576841157360996465143180530766164780189511493818816494747604670576
703309104293292067145387091594527878051640057346358196581149979574919865
613396117393953973645119539317207284414953163160566044858470914445622563
074413307347576016531310529336141471857024706213057826748959516235946503
031659062718708312625292147180377560196663522113839359107475226457486311
562415677067373779759682368622386969251482907209883377803008828935287988
352401476648251084611506985649085669753276161898450861726672565178111927
504381102862836169560472912672348817497581955105795973630932450298387623
551908393569623020766631325155105832742279511300108958686957728748246779
07072757854642053040730827394054675733217280*x^6+
294021706250285537364059193511981834010962862165445472057261977354527540
420952976211334233107586759690574132740568331284628494603329217018655409
294593669627634736288926921339942177232336641314211094647274814150267130
238092299765240549434358732651262349664557278861939196909147928835748268
092384829574729240131742402085751863407811400024163060882558791996807827
095771847659473009296069672377253671098121785094954468364497412463197127
932605794504672622176587626377352501325117760429614590942806096728645685
012973117214338587110096871364671923946589710944613328592230125823858620
237682685026282375094843958932189189231015536498385275340377199725135557
082235144364445325688498779661274653167915535937645806882743566470969962
576579547496928397801310622311157896251089611131930076526550372359822983
3949434724115602154919768855787245775421440*x^5-
631838720936412105660884608445339693679950225040399938713955834977215469
821179786717936715482663090605080444023856513060647982622626831248562042
361090608143761298678731699441092386889313600986729487378432874427535417
943505124937196317350747491395912003738671711569790423628029504326969966
734278043650151582995553096542680893774444710159297007140882949071513485
278660346258946300313325578743420640242699799529356047695887996172330112
407341314618409267947612812543495899719826928289430489199878724034280741
937812201810130612397251990145628778988594510882154778219141681135828019
016131695325576125004341648163194169593776749059348558719666782600996040
265901214783002395854228805396587742188459547511384279319195723779899751
521703947081712044347068358427528622602613413501101232065967229371393304
704161768040845818432635994145064296644608*x^4-
552835813573560615595205740015373129910526691607620131183333275234848550
940654519354517226466128880474476237268407816314203646409587150661674683
928164272272287756418716413884786211466439425707038661836891002281760045
296035232881132343873169092829628973048113842204152499602598519106864203
723179158194218962275979097248054865555647575328153177874257108605951802
151883524281881265085519258184467312221607739287537083292702355203422765
727673956234847523101962528057030012785590823367823199893050286069652135
473641363783402011085288987864527773090411828413628547028830611286430284
681282630597143817701682027296074224956326614194589229518070278606521246
366624746374522248327020592007164909281188488287037148186488899924446278
857302319046594871040251599020956597583589736283925670255750305964581031
77782855452452736220359453085723333230592*x^3+
180364549996711568180554754467714432180417620499062376638530957089867567
367791822884108240397881287099944566715510223085599964523607237944729407
329175629096755121454685976962185974801613733396122734415242921144859115
713757744418131041924229542280744673769915666190525528981043097029660585
466768326307206769734671418831284771614880838471562247892422180998423318
030158584706685021975128701858497444147124256570792012238237982525653867
979211951309105527395971710235927505091782547639316747795743722031437499
253935438569164739610985333259112202207843377858749535788363140007016797
921647951155645205303374295870486830944005316675172444120666022826749536
185787978781844878857967540120968073731432358240143913138534517662737920
902249651171849081681068121618390311490820016631759440370416270927605942
3488237718889762737183226478518641623040*x^2+
170433495871623470089431544165143113371851970029735123143927218064979606
962642942782796732808280799131665774502219097161946196545539602295876524
662578519745162293748070681268383627619065415791408545325201006804371925
578125431193815522574261268529763806404331314809240213317774827718699312
010358472978998579475976064389110649877468492630560568309479391377560736
086451303061073393859418289836208146610091790693064632374473746500911383
349980919992145725696433262668744129952456673311211008581846271601275816
733747240956263612270687348632578438148034287965993056643359826587640763
763049892188641267330081117324368396535432757532354462408870448049262097
498596901586304570234276316396690023088884736998904481058832107866260934
375303580355185495950813038707138673467534510876243266012010785336755288
795882237115233822113265307104533544960*x+
243341755463094332954323162098222274016086901785961516763395666901290771
139317595854013140074951472847401395553982501136279395318119229283088416
205136727318338985735756285670833802401370218002919109684298825646471248
237206350052066379400484448015898048262217269790436185721767110459753951
006601634453463462497800598433814518718252553834928202185105870860023461
811635773276519174188757107399313797693130060144394695390301668834368686
479012826713907921945886108414834218652205527709663954214646746545739369
938460218909969798645728928036153344039928972047926440088762925015336795
632719326519422837914459697037371743627422370575241759659672125723633591
032473159557506947636085447323539980956883546973140577395129277280660698
783185692882659173957833154118782156090909069515553045152813668721530274
7469691927337349422117708105777152000
luisfe
Feb 18, 2011, 10:31:51 AM2/18/11
to sage-support
Just for the record. The problem seems to be related to RIF. For the
inexact ring RR, it works:
len(e.roots(ring=RR))
13
len(e.real_roots())
13
numeric approximations of the two missing roots are:
0.953956769342757, 0.957223630414975
This pair of roots is exactly the pair of most close roots among all.
So it seems that a sign change is not detected.
inexact ring RR, it works:
len(e.roots(ring=RR))
13
len(e.real_roots())
13
numeric approximations of the two missing roots are:
0.953956769342757, 0.957223630414975
This pair of roots is exactly the pair of most close roots among all.
So it seems that a sign change is not detected.
D. S. McNeil
Feb 18, 2011, 11:07:38 AM2/18/11
to sage-s...@googlegroups.com
A somewhat simpler test case, which I think preserves the qualitative issue:
sage: from sage.rings.polynomial.real_roots import real_roots
sage:
sage: x = polygen(QQ)
sage: f = 2503841067*x^13 - 15465014877*x^12 + 37514382885*x^11 -
44333754994*x^10 + 24138665092*x^9 - 2059014842*x^8 - 3197810701*x^7 +
803983752*x^6 + 123767204*x^5 - 26596986*x^4 - 2327140*x^3 + 75923*x^2
+ 7174*x + 102
sage: len(real_roots(f)), len(real_roots(f,strategy='warp'))
(11, 13)
sage:
sage: [map(float,r[0]) for r in real_roots(f)]
[[-0.28173828138369572, -0.23901367199914603], [-0.19628906261459633,
-0.15356445323004664], [-0.078796386807084673, -0.073455810634015961],
[-0.036071777422534979, -0.030731201249466267],
[-0.025390625076397555, 0.017333984308152139], [0.060058593692701834,
0.10278320307725153], [0.14550781246180122, 0.23095703123090061],
[0.57275390625, 0.615478515625], [0.658203125, 0.76618289947509766],
[1.375, 1.4375], [1.5, 2.0]]
sage: [map(float,r[0]) for r in real_roots(f,strategy='warp')]
[[-0.33333333333333331, -0.23076923076923075], [-0.18518518518518517,
-0.14285714285714285], [-0.10344827586206896, -0.066666666666666666],
[-0.049180327868852458, -0.032258064516129031],
[-0.023999999999999997, -0.015873015873015872], [0.032258064516129031,
0.066666666666666666], [0.14285714285714285, 0.23076923076923075],
[0.59999999999999998, 0.64102564102564097], [0.72972972972972971,
0.75342465753424648], [0.95373241116145957, 0.95396541443053062],
[0.95419847328244267, 0.96923076923076923], [1.2857142857142856,
1.4615384615384615], [1.6666666666666665, 3.0]]
Doug
--
Department of Earth Sciences
University of Hong Kong
Dima Pasechnik
Nov 2, 2017, 10:24:30 AM11/2/17
to sage-support
Just for the record, I checked these with the recent Sage beta (8.1.beta9), and everything works, no errors.
Reply all
Reply to author
Forward
0 new messages