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
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
