Feature #440
Port RealRoots to C++
Description
Port the RealRoots
code to C++ so that it is accessible to CoCoALib users!
I hope that a well-written port might gain as much as a factor of 2 in speed :-)
Related issues
History
#1 Updated by John Abbott over 10 years ago
- Category set to New Function
Make the code prefer "binary rationals" as much as possible; exploit this fact when evaluating the polynomial. In any case, avoid rational arithmetic as much as possible. Investigate the idea of a "target denominator" (what does this mean if the interval is wider than 4, say?)
In a cascade of failures we can evaluate just one point at each stage of the cascade (until the last one, of course) since we know what sign one end of the subinterval must have.
Add some tracing info: I'm thinking of a list of log(log(N)) at each iteration; it'll cost nothing and maybe quite useful to people studying the algorithm.
#2 Updated by Anna Maria Bigatti over 10 years ago
- Target version set to CoCoALib-0.99533 Easter14
#3 Updated by John Abbott about 10 years ago
- Target version changed from CoCoALib-0.99533 Easter14 to CoCoALib-1.0
#4 Updated by John Abbott over 8 years ago
After the SC^2 meeting it is clear that several people would like RealRoots
to be ported into C++. If the project is funded, it will probably start in June 2016; so perhaps the porting can be done as part of that project (and in its early stages).
#5 Updated by John Abbott over 7 years ago
- Assignee set to John Abbott
- Priority changed from Normal to High
Some of Erika's people would like this to be in CoCoALib sooner rather than later!
#6 Updated by John Abbott over 7 years ago
- Related to Feature #974: QIR/RealRootRefine: improve behaviour if input interval has "nasty" endpoints added