OpenEuphoria

Re: new new challenge

• Posted by rossboyd at ihug.com.au Aug 21, 2001
• 456 views

Ross Boyd writes:
>Your solution averaged 6.50 secs and
> my ugly one below was 3.85 secs on a P3-450.

Rob Craig wrote:
It depends on the distribution of numbers that you feed in.
I find the two functions are about equal,
given a series of numbers 1 to 100,000,000. (To be really
fair you might go to 1.07 billion, but that takes too long).

You're quite right. The performance really slows down on the ugly
multi-if solution when you apply a #7F000000 mask to the input.
It degrades when processing large numbers.

I just timed the 3 algorithms in C  using 1,000,000,000 iterations

These are the times not including the loop and function call overhead.
(16.65 secs)
4.89   secs  ..... "return x ^ (x & (x - 1));"
11.91 secs  ..... "return ((x ^ (x-1)) >> 1) + 1 ;"
12.20 secs  ..... "if (x & ?) return ?;" etc. etc.

So, "nforno"s algorithm is by far the best....