suggested improvements to D (popcount and first1)

[Warren D Smith]

reply to Don Clugston

Yes, the "repeated doubling of wisdom"
bitcount routine you wrote is a good way to do it.
Also, more brute-force, but on many machines faster, is to use
precomputed popcount lookup tables.

Lookup tables can also be used to implement first1, and so
can a "repeated wisdom doubling" approach to implement a binary search.
Another way to do first1(uint x) is first to compute  y=x^(x-1)   which if x!=0
is a uint with a single 1 bit located at the same place as the
least-significant 1 bit in x, and second to hash y, for example
use y%C as the hash function [value in {0..C-1}] and you cleverly choose the
constant C so that this hash function always gives different values
for different y of this form (i.e. perfect hash)
and do a hash-table lookup in a C-entry table.
If I recall right, which I may not, C=63 works.
Unfortunately the "%" is slow on the hardware I used.

All that is suckingly slow compared to hardware support, though.

--

>Are there many applications of [add with carry, etc]
>OTHER than bignum arithmetic? My
>feeling is that you'd always want to do bignum in asm anyway.

>Note that D is a great language for writing asm in; you can have a
>single source code shared between Windows, *nix, and the new x86 >Macs.

But I want to write PORTABLE, i.e. not-asm, bignum code.
Why is the language denying me the power of the machine?
That is the opposite of its job.  Especially if we are talking
about a power that every machine provides.

It is kind of like saying:  "you can only breathe air from now on, if
you use a gas mask.  This is a great advance in technology versus just
breathing, so be happy."

The other main application of add-with-carry is to spot integer overflow.

Look, if you just provide, e.g.
    AddWithCarry( in uint x, in uint y, out uint z, out bool carry )
    DoubleMultiply( in uint32 x, in uint32 y, out uint64 z )
        [or maybe two out-arguments, an uper and lower one]
    FullDivide( in uint64 y, in uint32 z, out uint32 quotient,
          out uint32 remainder )
and similar stuff, problem is over.   (Ignore my crappy syntax,
just use this idea but with better syntax.)