# Finding all the zeroes of a function

Hi all,

Given f(x) I’m wishing to find all its zeroes (ie all x’s such as f(x)=0). So far all the examples I’ve seen

deal with finding a single one; whereas what I need is to compute every root of the given function (inside a given interval).

I tried with a recursive function, in the spirit of

``````FindRoot(Start, End) {
r = ComputeRoot(Start, End);
FindRoot(Start, r);
FindRoot(r, End);
}``````

but it didn’t work; since I fall back again in previously found roots, and what’s more I see that the first found roots aren’t those closest to the initial end points.

Am I missing something?

You can already do what you request with

``` virtual Double_t TF1::GetMinimumX(Double_t xmin=0, Double_t xmax=0) const; ```
Rene

Hi Rene,

Thanks a lot for the reference. As you posted in

root.cern.ch/phpBB2/viewtopic.php?t=1033

``Double_t GetX(Double_t y, Double_t xmin = 0, Double_t xmax = 0) const``

also seems useful for root finding.
What I cannot fully accomplish is to find all the roots in the
interval. These methods (GetX and GetMinimum) return a single value;
so I tried to use them repeatedly in order to retrieve all the roots.
So I wrote this

``````#include <iostream>
#include <vector>
void Solve(vector<double>& roots, int nest, TF1* f, double s, double e)
{
double r = f->GetX(0, s, e);
cout << "(" << nest << ") start=" << s << " end=" << e << " root="
<< r << endl;
roots.push_back(r);
if (r != s && r !=e) {
Solve(roots, nest+1, f, s, r);
Solve(roots, nest+1, f, r, e);
}
}
void FindRoot()
{
double s = - TMath::PiOver2();
double e = 2 * TMath::TwoPi() + TMath::PiOver2();
cout << "start =" << s << endl;
cout << "end   =" << e << endl;
// Create the function and wrap it
TF1* f = new TF1("Sin Function", "sin(x)", s, e);
f->Draw();
vector<double> roots;
Solve(roots, 0, f, s, e);
sort(roots.begin(), roots.end());
double* xx = new double[roots.size()];
double* yy = new double[roots.size()];
// If this is put here; then only the first point
// is shown in the plot.
//TGraph* gr = new TGraph(7, xx, yy);
cout << "Found " << roots.size() << " roots:";
for (int i = 0; i < roots.size(); ++i) {
xx [i] = roots[i];
yy [i] = 0;
cout << xx[i] << " ";
}
cout << endl;
TGraph* gr = new TGraph(7, xx, yy);
gr->SetMarkerColor(kRed);
gr->SetMarkerStyle(21);
gr->Draw("P");
c1->Update();
cout.flush();
}``````

Running it I only get the outer roots in the interval. Cout’s output
for the run is
start =-1.5708
end =14.1372
TCanvas::MakeDefCanvas: created default TCanvas with name c1
(0) start=-1.5708 end=14.1372 root=12.5664
(1) start=-1.5708 end=12.5664 root=-4.50437e-10
(2) start=-1.5708 end=-4.50437e-10 root=-4.50437e-10
(3) start=-1.5708 end=-4.50437e-10 root=-4.50437e-10
(3) start=-4.50437e-10 end=-4.50437e-10 root=-4.50437e-10
(2) start=-4.50437e-10 end=12.5664 root=-4.50437e-10
(1) start=12.5664 end=14.1372 root=12.5664
Found 7 roots:-4.50437e-10 -4.50437e-10 -4.50437e-10 -4.50437e-10
-4.50437e-10 12.5664 12.5664

And the resulting plot is attached (also the same script).

Taking a look in TF1’s docs:

• For GetMinimumX the search interval is specified as “(xmin, xmax)” which seems to denote an open interval.
• For GetX the search interval is specified as “(xmin<x<xmax)” which also signals an open interval.
• In the underlying ROOT::Math::RootFinder, the comments for “SetFunction” talk about “search interval [xlow, xup]” (ie closed interval).

Also note that for TF1::GetMinimun, TF1::GetMinimunX and TF1::GetX the description says “…the grid search is used to bracket the maximum…”. Maybe, at least the first two, should speak about bracketing the minimum.

Thanks a lot for your advice. Cheers.
FindRoot.C (1.2 KB) Hi,

a bracketing algorithm, like the Brent one used in TF1::GetX is not so good for finding multiple roots of a function automatically. You need to provide good interval regions.
With a method based on the function derivative, where you provide only a starting guess, it works better.
Attached you find the example working in your case using the RootFinder class and the GSL algorithm from MathMore

Best Regards

Lorenzo
FindRoot.C (2.33 KB)

Hi Lorenzo,

Thanks for the example and the insight about the root-finding algorithms. I’ll try it later, and then adapt it to my real-life problem.

Thanks again.

Cheers,

Hi,

No luck so far:

It seems that MathMore extensions weren’t available in my preexisting Root-5.20 installation (under Ubuntu 7.10). So I installed GSL (gsl-1.12) from sources (all checks passed) , downloaded Root-5.24 and tried to build it from scratch with the proper settings

``./configure linux --prefix=/usr/local/root-5.24 --with-gsl-incdir=/usr/local/include --with-gsl-libdir=/usr/local/lib --with-fftw3-incdir=/usr/local/include --with-fftw3-libdir=/usr/local/lib --enable-mathmore --enable-fftw3``

I also added fftw because I desired to have it available. But then, make failed

Now I’m building from scratch another 5.20 installation.

Thanks a lot.

Well, now it works.

I ran the script with 5.20 and 5.24. I don’t know why exactly: to build 5.24 I had to disable xrootd.
So, to install 5.20 I ran

``./configure linux --prefix=/usr/local/root-5.20 --with-gsl-incdir=/usr/local/include --with-gsl-libdir=/usr/local/lib --with-fftw3-incdir=/usr/local/include --with-fftw3-libdir=/usr/local/lib --enable-mathmore --enable-fftw3``

To install 5.24 I ran

```./configure linux --prefix=/usr/local/root-5.24 --with-gsl-incdir=/usr/local/include --with-gsl-libdir=/usr/local/lib --with-fftw3-incdir=/usr/local/include --with-fftw3-libdir=/usr/local/lib --enable-mathmore --enable-fftw3 --disable-xrootd ```
and then make;make install.

Thanks for the help.

Hi,

After trying successfully the example within CINT (with Root 5.24 and 5.20), I started to code the adapted version for my real-life example, which runs as a compiled stand-alone application (ie not within CINT).

For this, I installed MathMore stand-alone version as linked from

project-mathlibs.web.cern.ch/pro … hMore.html

to

If I’m not wrong; I mean, currently this last link gives an error

maybe I downloaded from another similar-looking web page.

Anyway, what I downloaded and installed was a “MathMore.tar.gz” which upon decompression gave a “MathMore-5.17.02” directory.

So far, so good; now, when trying to compile the example some errors popped out, like that RootFinder is a templated class or that GradFunctor1D isn’t declared.

Well, at last comparing the contents of the with-MathMore-Root installations, and what was installed as MathMore-standalone I realized that that 5.17.02 MathMore installation is outdated (do the version number go along with Root version number?).

Precisely. in the header installed in the stand-alone path, RootFinder is a template class, and it isn’t in the header in the Root install paths. Functor.h heading says

in both (5.20 and 5.24) Root’s include directories, whereas

in the MathMore-standalone.

So, what I did was to change my -L and -I compiler flags to point to the lib and include directories of Root 5.24 installation, instead of what was intended to be a MathMore stand-alone installation. Even more, I put these flags first in the list, because I’m compiling this standalone app against Root 5.16, and with this version MathMore in 5.24 has some conflicts, since it requires an up-to-date version of Functor,h (with ROOT::Math::GradFunctor1D)

Cheers;and thanks a lot.

Hi,
I continued working with this issue and applied it to the real problem I’m working with. In this case problems arise very likely, giving bad solutions.

Basically four kind of problems arise, with the following messages in the console:

[ul]

• Info in ROOT::Math::GSLRootFinderDeriv::Solve: exceeded max iterations, reached tolerance is not sufficient; tol = 0.0532421

• Error in : Error 12 in steffenson.c at 94 : derivative is zero

• Error in : Error 9 in steffenson.c at 110 : function value is not finite

• Error in : Error 9 in steffenson.c at 131 : derivative value is not finite
[/ul]

To get rid of the first case I increased the tolerance, nevertheless the other problems keep present and the solutions are frequently flawed.

I tweaked the original working example so to mimic the real situation, in which the function for which the zeroes need to be computed is the overlap of several Gaussian pulses.

I attach the modified script, and the results of a particular run of it, where a root is lost.

Any advice on how to tackle this case will be welcomed; thanks a lot.
c1.txt (826 Bytes)

FindAllRoots.C (3.19 KB)

Hi,

I continued with this topic. Wrote a variation of the former script, where the whole interval is split in several ones, on each one the maximum and minimum of the function is looked for and then a root is searched for within it only if the extrema have opposite sign. It doesn’t seem to be a too clean / efficient solution, tough is gives better results.

Cheers.

FindAllRoots2.C (4.06 KB)

Hi,

It is very difficult to design a general algorithm to find all roots of a function.
The difficult is to find the rigt interval or right starting points. If the function is ill-behaved or is having many peaks, it can be difficult.

If the extreme of the interval have opposite signs you can use also a bracketing algorithm, like Brent which does not require the derivatives.
(Just create the RootFinder class with ROOT::Math::RootFinder::kGSL_BRENT and pass in this case the extreme of the interval instead of the estimated starting point in the RootFinder::SetFunction method).

Best Regards

Lorenzo

Thanks a lot for your answer. Yep, there’s no way to find a one-size fits-all solution for this problem: the characteristics of the particular function dictate the final needs.

For the case of my interest, it seems that at most, say, 10 roots may be found. Dividing the interval in around 100 subintervals may be enough.

Cheers, and thanks a lot again.