OpenEuphoria

new new challenge

• Posted by rforno at tutopia.com Aug 18, 2001
• 497 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.
The following is the test program I propose:

function dummy(integer x)
    return x
end function

function best(integer x)
    -- ?????????
    return -- ?????????
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)

Of course, there is a trick I know.