Re: [CHALLENGE] finding rightmost zero bit

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


--
The "bmoses-nospam" address is valid; no unmunging needed.
.

Relevant Pages

  • Re: [CHALLENGE] finding rightmost zero bit
    ... > establishes a lower bound on the timing. ... > function findpos_wrong1(n) result ... > elseif (.not. ...
    (comp.lang.fortran)
  • 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: Fastcode Pos B&V 5.1
    ... > in the Pos validation. ... > with Exit and cleaning up a little fixed the problems. ... Would is still be allowable for me to contribute to the Pos challenge? ...
    (borland.public.delphi.language.basm)
  • Re: Truth left untold
    ... I suspect she doesn't mention the car for fear of legal retribution... ... a POS is a POS. ...
    (rec.autos.tech)