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;

Advertisements