Recently, I worked on a problem which can be resumed as following:

I have a function that take an input, do some calcul and give me a output value. Now I have a output value and I want to know the input that produce the output.

Example: **y = x*x + sqrt(x) – 7/x + (15/(2*x) – 4.5*x)*(sqrt(6*x) – x*sqrt(x/2));**

If I have **x**, I can calculate **y**.

Now I have **y** and I want calculate **x**.

Of course, my function is a thousand of time more complex than in the example. The calculation formula is about a dozen of pages long.

I had tried to inverse the formula to obtain something like **x = func(y)** so I could calculate **x** when I know **y**, but I had failed because it was really difficult for me. Fortunately, a friend tell me about the dichotomy algorithm.

**Dichotomy algorithm: **

The idea is

I have **y = func(x)**, I know **y** and want to calculate **x**, so

I take a value **x**, calculate **func(x)**, compare the result with **y**,

**if result == y**, so **x** is what I need,

**if not**, I take another **x**, and recalculate **func(x)**, recompare the result with **y**, …

repeat it until I find **x**.

Does it sound stupid ? Yes, if I don’t have a computer, but I have a power computer who does the calculation for me, so this is a wonderful idea.

However, I was skeptical at first, because I don’t know how many loops I have to repeat to obtain the result and the simplest way to implement this algorithm is to use recursion. But when I started to implement the algorithm, I recognize that with some simple optimizations and some heuristic knowledge, the number of loops (and so the performance) is really acceptable. (about 50 to 100 loops to get the result).

Here is the first code I used:

package test; /** * @author Hong Nam NGUYEN -- Created: 15 oct. 07 - 16:26:27 */ public class Dichotomie { public static void main(String[] args) { double x = 2.55; double y = func(x); System.out.println("x = " + x); System.out.println("y = func(x) = " + y); System.out.println("========================="); double result = 5105.4; double variable = getX(result); System.out.println("result = " + result); System.out.println("variable = " + variable); } private static double func(double x) { return 2000000 * x + 7 - Math.sqrt(x); } public static double getX(double y) { double x = y * 2000000; double max = 0; double min = 0; double tmp = func(x); double diff = tmp - y; // TODO: On peut améliorer les méthodes getMin/Max if (diff > 0.0) { max = x; min = getMin(x / 2, y); } else if (diff < 0.0) { min = x; max = getMax(x * 2, y); } else { return x; } return dichotomie(min, max, y); } private static double dichotomie(double min, double max, double y) { double x = (min + max) / 2; double tmp = func(x); double diff = tmp - y; if (diff > 0) { return dichotomie(min, x, y); } else if (diff < 0) { return dichotomie(x, max, y); } else { return x; } } private static double getMax(double x, double y) { double tmp = func(x); double diff = tmp - y; if (diff > 0) { return x; } return getMax(x * 2, y); } private static double getMin(double x, double y) { double tmp = func(x); double diff = tmp - y; if (diff < 0) { return x; } return getMin(x / 2, y); } }

This code works well, but the functions getMin and getMax could be done better, so here is the second version. The difference between the two versions of code is showed when I have made a really bad choice for the first try – heuristic plays its role in this choice (here is double x = y * 2000000;)

package test; /** * @author Hong Nam NGUYEN -- Created: 15 oct. 07 - 16:26:27 */ public class Dichotomie2 { static int loopFunc = 0; public static void main(String[] args) { double x = 2.55; double y = func(x); System.out.println("x = " + x); System.out.println("y = func(x) = " + y); System.out.println("========================="); double result = 5105.4; double variable = getX(result); System.out.println("result = " + result); System.out.println("variable = " + variable); } private static double func(double x) { System.out.println("func: " + (++loopFunc)); return 2000000 * x + 7 - Math.sqrt(x); } public static double getX(double y) { double x = y * 2000000; double max = 0; double min = 0; double[] minmax = new double[2]; double tmp = func(x); double diff = tmp - y; if (diff > 0.0) { max = x; minmax = getMin(x / 2, x, y); } else if (diff < 0.0) { min = x; minmax = getMax(x, x * 2, y); } else { return x; } min = minmax[0]; max = minmax[1]; return dichotomie(min, max, y); } private static double dichotomie(double min, double max, double y) { double x = (min + max) / 2; double tmp = func(x); double diff = tmp - y; if (diff > 0) { return dichotomie(min, x, y); } else if (diff < 0) { return dichotomie(x, max, y); } else { return x; } } private static double[] getMax(double min, double x, double y) { double tmp = func(x); double diff = tmp - y; if (diff > 0) { return new double[] {min, x}; } return getMax(x, x * 2, y); } private static double[] getMin(double x, double max, double y) { double tmp = func(x); double diff = tmp - y; if (diff < 0) { return new double[] {x, max}; } return getMin(x / 2, x, y); } }

The strength of this algorithm is that I even don’t need to know the detail of func(x), I can treat it like a black-box.

enjoy;

January 9, 2009 at 7:47 pm

Maybe I missed something, but I was really surprised by your last statement:

“The strength of this algorithm is that I even don’t need to know the detail of func(x), I can treat it like a black-box.”

Don’t you need func(x) to be non-decreasing in x (at least on some interval containing your answer)? The algorithm looks to me like a straightforward binary search.

If you don’t understand this, you should probably think about what makes this algorithm actually work (why diff approaches 0 in your example).

May 24, 2010 at 10:30 am

Hi,

I came across this page while trying to understand what was the ‘dichotomy algorithm’ of which I found mention.

I then discovered it’s the ‘Bisection’ root-finding algorithm.

So, if you are interested in understanding limits and strengths of this method have a look at http://en.wikipedia.org/wiki/Bisection_method or any numerical analysis book covering root finding algorithms (e.g. Numerical Recipes Chapter 9).