Another (stupid) question: "find first set" (or "find first zero")

[Pascal Bourguignon]

Le 02/02/2021 à 13:40, Martin Simmons a écrit :
>>>>>> On Mon, 1 Feb 2021 20:12:48 +0100, Pascal Bourguignon said:
>>
>> Le 01/02/2021 à 19:51, Marco Antoniotti a écrit :
>>> Duh again!
>>
>> What?
>>
>>
>> Note that the naive version is not necessarily worse than the "smart"
>> one, on bignums.   On numbers like (+ (expt 2 1000) (expt 2 10)),
>> logand, lognot and even 1+ will have to process the whole bignum, with a
>> lot of memory accesses, while the naive loop would access only one word.
> 
> Really?
> 
> The naive version below repeatedly does (setf n (ash n -1)), which most likely
> accesses the whole bignum and allocates a new one each time.  A better naive
> version would use logbitp instead of evenp and not modify n.

Yes, that's what I meant.  Sorry for the confusion.

> 
> I think this definition does reasonably well too:
> 
> (defun ffs (x)
>    (1- (integer-length (logand x (- x)))))
> 
> I would avoid using log because it may get floating-point overflow for large
> values.

Indeed.


Note: if we have access to the implementation of bignum (eg. if we patch 
the implementation to provide ffs "natively"), we can optimize even more 
by merging the two solutions.

(- x) would process the whole bignum, as would (logand x (- x)), but 
after this operation, we have only 0s on the left of the bignum.

Instead, we can process the bignum word by word (starting with the least 
significant word), computing:
(+ (lognot (bignum-word-ref bignum i)) carry) -> i+1, new-carry
and (logand (bignum-word-ref bignum i)
             (+ (lognot (bignum-word-ref bignum i)) carry))
while we get 0.
Once we get a value ≠ 0, it has a single bit set which we can identify 
with integer-length or looping etc (we process a single word here),
and stop processing now, because all the other words will give 0 as result.


-- 
__Pascal Bourguignon__