Re: [CHALLENGE] finding rightmost zero bit

On 2005-08-30, Michel OLAGNON <molagnon@xxxxxxxxxxxxxxxxx> wrote:
>
> OK. Here is a reasonable version of the same algorithm:

Online version is updated.

Timing results on my machine:

bartv@vonneumann:/export/home1/bartv/fortran$ ./time_findpos
huge(n) is 2147483647.
Enter first number: 1
Enter last number: 147483647
Total bits counted: 294967286
Bart1's method did it from 1 to 147483647 in 1.81 seconds.
Total bits counted: 294967286
Bart2's method did it from 1 to 147483647 in 1.82 seconds.
Total bits counted: 294967286
Bart3's method did it from 1 to 147483647 in 1.98 seconds.
Total bits counted: 294967286
Michel's method did it from 1 to 147483647 in 18.50 seconds.
Total bits counted: 294967286
Michel2's method did it from 1 to 147483647 in 1.86 seconds.

Regards,
Bart

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

Relevant Pages

  • Re: Online poker RNG...
    ... too, btw, although, as a professional player, I already am aware of it ... BTW: For sale online are the hand ... Knowing the seed and the algorithm will indeed tell you the next ...
    (sci.math)
  • Re: Triple-AES
    ... 3-DES, after all, was a response to the keyspace becoming ... If you're worried about the algorithm in particular being ... primary layer is just something i threw together and probably has no crypto ... to add the timing for the primary secondary and tertiary layer, ...
    (sci.crypt)
  • Re: Mini project suggestions
    ... >> design itself would be better discussed in groups such ... >> Often specific algorithm categories have their own ... > Anything comparable online, in the same way that Sun have the Java ...
    (comp.lang.cpp)
  • Re: Finding the highest bit set in a 32-bit number
    ... This is worst case for my algorithm, ... timing, which can only be explained by the I/O bottleneck. ... C solutions that claimed 50 - 60 microseconds ...
    (comp.programming)
  • Re: Finding the highest bit set in a 32-bit number
    ... > This is worst case for my algorithm, ... > timing, which can only be explained by the I/O bottleneck. ... > calculation is still about 4,000 clock cycles. ... It is 4 times slower than the best so far on my PC. ...
    (comp.programming)