OpenEuphoria

Re: new new challenge

• Posted by rossboyd at ihug.com.au Aug 18, 2001
• 492 views

> This is a new and (I think) simpler challenge:
> Find the fastest algorithm to compute the largest power of 2 that
exactly
> divides an integer from 1 to 2^31 - 1.

Hi,
The solution boils down to finding the value of the least significant
bit.
Here are two alternatives... unfortunately the ugly one is faster.
Ross


-- This solution is elegant but slower due to the divide by 2.
-- If Euphoria had a bit shift operator or integer division
-- this would probably be the fastest method.

function best2(integer x)
    if and_bits(x,1) then  -- quickly eliminate odd numbers
        return 1
    end if
    return floor(xor_bits(x,x-1)/2) + 1
end function

-- Cruder and faster solution...
-- You could make it even faster by 'jumping' depending on the
-- value of x and hence reduce the number of comparisons.
-- But why bother... this method stinks already.
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

procedure test(integer iter, integer top)
    integer n, k
    atom sum, t0, t1
    sum = 0
    for i = 1 to top do
        for j = 0 to 31 do
            n = power(2, j)
            if remainder(i,n) != 0 then
                exit
            end if
        end for
        n = n / 2
        t1 = time()
        for j = 1 to iter do
            k = dummy(i)
        end for
        t1 = time() - t1
        t0 = time()
        for j = 1 to iter do
            k = best(i)
        end for
        sum += time() - t0 - t1
        if n != k then
            printf(1, "%s %d %s %d \n", {"Error! ", n, "not equal", k})
        end if
    end for
    printf(1, "%s %f \n", {"Time:", sum})
end procedure

test(100000, 100)

if wait_key() then end if