concurrent recursive bisection search

General Discussion
1

hi, this post is not related to panda, but i need some help. does any one know how to make recursive bisection search concurrent? so i could run it on many threads? search code in java looks like this

protected synchronized double findRoot(double a, double b) throws someThingWrong {
		if (f(a) > 0 && f(b) > 0) throw new someThingWrong("f(a) > 0 && f(b) > 0");
		if (f(a) < 0 && f(b) < 0) throw new someThingWrong("f(a) < 0 && f(b) < 0");
		if (f(a) > 0) {
			double tmp = b;
			b = a;
			a = tmp;			
		}
		double midpoint = (a+b)/2;
		iter++;
		if (Math.abs(b-a) > 2 * epsilon) {
			if (f(midpoint) == 0) { 
				return midpoint; 
			}
			if (f(a)*f(midpoint) <= 0) {
				return findRoot(a, midpoint);
			} else {
				return findRoot(midpoint, b);
			}
		} else {
			return midpoint;
		}
	}

i just need point how to make this capable for parallel computing

2

Sounds like it has almost nothing at all to do with Panda. It wouldn’t even work if you programmed it in Python, which doesn’t really support concurrent programming. You could do it in C++, I guess, but it would be hard.

It’s a hard problem in general, of course. Is this a programming exercise for a class? It seems pretty academic. Maybe you should ask at a general programming board.

David

3

to me it doesnt look like this can be speeded up by using threads efficiently anyway.

4

but it can be spreaded? i dont need eficient way, i just need to make it work with pooled threads and test it on grid computing.

This is for my studies.
also i can write this method in any other convenient language like c++ or etc. if it would help to find the solution

5

I think a b-search is inherently serial, unless you want to divide a region into extra parts and compare two-at-a-time on each step, say as in a b-tree with more than two children. Zero-finding could work the same way. Or you could run concurrently two searches.

Python 2.6 and later have a ‘multiprocessing’ module which run N concurrent processes. I just don’t know if it’s suited to such tightly coupled pairs of comparison sequences as a b-search requires, though maybe the extra calculations a z-search makes would make use of some of the independence.