Re: [CHALLENGE] finding rightmost zero bit

On 2005-08-29, Brooks Moses <bmoses-nospam@xxxxxxxxxxxxxxxxxx> wrote:
> Michel OLAGNON wrote:
>> Times on my system vary a lot (up to 20%) from one run to the other,
>> and I suspect that since 50% of your test cases have pos=1 and 25% more
>> pos=2, the function is then so fast that you are measuring only
>> function call overheads.
>> As a test, I tried to call my function directly from time_findpos, and it
>> reduced its time by 45%, and even 60% when I directly inserted the function
>> code into time_findpos.
>>
>> I believe the challenge is to find a fair way to time that function.
>> :-)
>
> Indeed. My first reaction, on seeing the challenge, was to ask what the
> time was for a function that simply returned 1 if the first bit was 0,
> and 2 otherwise. Obviously it produces the wrong answer, but it
> establishes a lower bound on the timing.
>
> In particular, I'd like to submit the following function, and have it timed:
>
> function findpos_wrong1(n) result (pos)
>
> integer(kind=i4b), intent(in) :: n
> integer(kind=i4b) :: pos
>
> pos = 0
> if (.not. btest(n, pos)) exit
> pos = 1
>
> end function findpos_wrong1
>
> Also, I'll propose a bit of loop-unrolling, which should get the _right_
> answer, though I doubt it will be much faster than the existing solutions:
>
> function findpos_brooks1(n) result (pos)
>
> integer(kind=i4b), intent(in) :: n
> integer(kind=i4b) :: pos
>
> ! Test the first 8 bits with hardwired checks
>
> if (.not. btest(n, 0))
> pos = 0
> elseif (.not. btest(n, 1))
> pos = 1
> elseif (.not. btest(n, 2))
> pos = 2
> elseif (.not. btest(n, 3))
> pos = 3
> elseif (.not. btest(n, 4))
> pos = 4
> elseif (.not. btest(n, 5))
> pos = 5
> elseif (.not. btest(n, 6))
> pos = 6
> elseif (.not. btest(n, 7))
> pos = 7
>
> ! Test the remaining cases with a loop.
>
> else
> pos = 8
> do
> if (.not. btest(n, pos)) exit
> pos = pos + 1
> end do
> pos = pos + 1
> end if
> end function findpos_brooks1
>
> It's not as clever as Glen's solution, but I think the fact that most of
> the time it does only one or two comparisons is likely to be an
> advantage, given that his always does five.
>
> - Brooks
>
>


--
"Share what you know. Learn what you don't."
.

Relevant Pages

  • Re: [CHALLENGE] finding rightmost zero bit
    ... Brooks Moses wrote: ... ) pos = 1 elseif (.not. ... Note that, in this version -- unlike the original bart1 -- the incrementing can be done at programming time rather than at runtime, thereby illustrating some of the utility of ...
    (comp.lang.fortran)
  • Re: [CHALLENGE] finding rightmost zero bit
    ... If used for timing only, it might not violate the challenge. ... ) pos = 1 elseif (.not. ...
    (comp.lang.fortran)
  • Re: [CHALLENGE] finding rightmost zero bit
    ... and I suspect that since 50% of your test cases have pos=1 and 25% more pos=2, the function is then so fast that you are measuring only function call overheads. ... btest(n, pos)) exit ... elseif (.not. ...
    (comp.lang.fortran)