OpenEuphoria

Re: new new challenge

• Posted by rossboyd at ihug.com.au Aug 20, 2001
• 427 views

> You were really close to what I think is an unbeatable solution,
namely:
>
> function best(integer x)
>     return xor_bits(x, and_bits(x, x - 1))
> end function
>
> The two functions may be reversed.


That's a brilliant solution. In C or ASM it would be unbeatable.

But strangely,  in Euphoria my crude version  is still ~50% faster.
I ran a 1,000,000 iterations and halved the timing errors (by putting in
2 wait loops.)
eg.
----------------------
t1 = time()
while t1 = time() do
end while
t1 = time()

-- insert code to test

t1 = time() - t1
----------------------

Your solution averaged 6.50 secs and my ugly one below was 3.85 secs on
a P3-450.
But I still much prefer your solution and will put it to use in my C
programs.
It will definitely be fastest in a compiled environment.
Thanks for sharing your algorithm!

Cheers,
Ross

ps. I tried the following using elsif 's and it was a LOT slower.
Which might be of interest to the speed freaks out there.

-- Crude but Fastest...
function best(integer x)
    if and_bits(x,1) then return 1 end if
    if and_bits(x,2) then return 2 end if
    if and_bits(x,4) then return 4 end if
    if and_bits(x,8) then return 8 end if
    if and_bits(x,16) then return 16 end if
    if and_bits(x,32) then return 32 end if
    if and_bits(x,64) then return 64 end if
    if and_bits(x,128) then return 128 end if
    if and_bits(x,256) then return 256 end if
    if and_bits(x,512) then return 512 end if
    if and_bits(x,1024) then return 1024 end if
    if and_bits(x,2048) then return 2048 end if
    if and_bits(x,4096) then return 4096 end if
    if and_bits(x,8192) then return 8192 end if
    if and_bits(x,16384) then return 16384 end if
    if and_bits(x,32768) then return 32768 end if
    if and_bits(x,65536) then return 65536 end if
    if and_bits(x,131072) then return 131072 end if
    if and_bits(x,262144) then return 262144 end if
    if and_bits(x,524288) then return 524288 end if
    if and_bits(x,1048576) then return 1048576 end if
    if and_bits(x,2097152) then return 2097152 end if
    if and_bits(x,4194304) then return 4194304 end if
    if and_bits(x,8388608) then return 8388608 end if
    if and_bits(x,16777216) then return 16777216 end if
    if and_bits(x,33554432) then return 33554432 end if
    if and_bits(x,67108864) then return 67108864 end if
    if and_bits(x,134217728) then return 134217728 end if
    if and_bits(x,268435456) then return 268435456 end if
    if and_bits(x,536870912) then return 536870912 end if
    if and_bits(x,1073741824) then return 1073741824 end if
    return 0
end function