Project

General

Profile

Feature #440

Port RealRoots to C++

Added by John Abbott about 10 years ago. Updated over 7 years ago.

Status:
New
Priority:
High
Assignee:
Category:
New Function
Target version:
Start date:
11 Feb 2014
Due date:
% Done:

0%

Estimated time:
Spent time:

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

Related to CoCoA-5 - Support #242: CoCoA-5 Projects for students (e.g. crediti F and tesi)In Progress2012-09-28

Related to CoCoALib - Feature #974: QIR/RealRootRefine: improve behaviour if input interval has "nasty" endpointsIn Progress2016-11-17

History

#1 Updated by John Abbott about 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 almost 10 years ago

  • Target version set to CoCoALib-0.99533 Easter14

#3 Updated by John Abbott almost 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

Also available in: Atom PDF