From: Mathieu Bouchard <matju@...>
Date: 2002-01-25T14:30:23+09:00
Subject: Re: looking for an example problem to demonstrate TaskMaster


On Fri, 25 Jan 2002, Phil Tomson wrote:
> I was thinking of an application where the user would enter a range of 
> numbers to find primes in.  The script would break this range down into 
> smaller ranges and use TaskMaster to send these tasks (finding primes 
> withing the given subranges) to multiple client machines.  But that's not 
> a real good demo since as the numbers in the ranges get larger the time it 
> takes to test each number in the range goes way up (probably 
> exponentially).

finding primes from m to n, using the simplest non-stupid algorithm,
requires knowing all primes up to sqrt(n); that's primecount(sqrt(n)).
this is approx:

	(0..sqrt(n)).integral {|x| 1/log(x) }

which is close to:

	1.1*sqrt(n)/log(n)

To find primes between 20000 and 400000000, for example, you need all
primes under 20000, and there are ~2200 of them. it takes only 300 tests
per number on average. you need this array on each client, but all clients
can then run independently. This is problem is a better one than you
think (although a better algorithm would help alot)

or maybe you'd be more comfortable distributing an algorithm that has no
known faster replacements?

On Fri, 25 Jan 2002, Phil Tomson wrote:
> Hmmm.... That might be good. I could have each client machine generate a
> part of the set.  But then I'd have to display the fractal somehow - not
> sure I want the demo program to get that complex, but it might be worth
> a try.

the picture can be generated in PPM format and saved to a file. It is
trivial to write a generator for that kind of file:

f = IO.popen "xv -","w"
f.puts "P6", "256 256", "255"
(0...256).each {|y|
  (0...256).each {|x|
    f.printf("%c%c%c",x&y,x^y,x|y) }}

this generates a munch pattern if you have the 'xv' program installed. you
may try other (more familiar) formulae...

________________________________________________________________
Mathieu Bouchard                   http://hostname.2y.net/~matju