Root isolation of real-rooted integer polynomials

General Usage
, , ,
10

You can also use Hecke/Nemo. Here are the timings on my very dated laptop:

julia> using Hecke

julia> Qx, x = PolynomialRing(QQ)
(Univariate Polynomial Ring in x over Rational Field, x)

julia> Qx, x = PolynomialRing(QQ);

julia> f = Qx(bp);

julia> Hecke._roots(f, 200) # the balls will have radious < 2^(-200)
15-element Array{acb,1}:
 [-3.920616711153724253790204590529063281656171296624620351746200485310655120855543613013541271680907275607223979079 +/- 4.84e-112] + i*0
 [-3.706111517064614641012473797293410340554769655675971950139715152216337896330719648922654909467811143497620428030 +/- 7.80e-112] + i*0
 [-3.399101345956385184809590396663823245233910492969600172371668237761238821534096232299586114103416940774067560924 +/- 8.79e-112] + i*0
 [-3.035412954945010421040655247164632911783923123071964813560272462311419306648072410827429032399236488318520657029 +/- 9.05e-112] + i*0
 [-2.642241820837020072256321446404090852721123523348319017917035488525807038562259125380960186537327785108752839951 +/- 5.03e-112] + i*0
 [-2.240386668347612606849921371192140625120311772030273906303162991172574142894086307045961801604703579352289007669 +/- 3.04e-112] + i*0
 [-1.8459392275279762188118911328074682418106652190523122728768478452769447419809494076465189839407551707688825849549 +/- 9.17e-113] + i*0
 [-1.4714364265485984347457103358546916040139602018877260092947033620076406186360124337515593788219523840023676498250 +/- 3.09e-113] + i*0
 [-1.12667548938228648371659194465060333123610781848166932944102272185644329811383422404304887752307268162794786601481 +/- 6.41e-114] + i*0
 [-0.819305999801997298040859319753994185201032318699276601025148883053951656453384749232848418410546346810549845454155 +/- 6.49e-115] + i*0
 [-0.5552656322189970256982534594202473203239575869892228528269814900273624281956924496928014910474082527863381439566599 +/- 8.75e-116] + i*0
 [-0.33910202510401947795464384494964958658273285483978651160525210708434910971533965735125598235860614612011137885597364 +/- 4.76e-117] + i*0
 [-0.174209253846368310831930193848706110784111374105168275102590356950016921390554301061214369088829872621188752931599096 +/- 4.12e-118] + i*0
 [-0.06299838108334910672357500092170790024222765409891867028284948240638078820689793485367480324463392976269126659634877413 +/- 9.09e-120] + i*0
 [-0.007015398195279156379264993894770551409664575420748371105657755069724334773977198396431121866041220489066572460776894302 +/- 2.04e-121] + i*0

julia> @btime Hecke._roots(f, 200);
  4.501 ms (3677 allocations: 204.58 KiB)

This is internally using http://arblib.org/.

P.S. To convert to BigFloat you can do BigFloat(real(x)), but you must handle the global precision yourself.

2 Likes