On 18/05/17 15:49, Edward Cree wrote:
> Here's one idea that seemed to work when I did a couple of experiments:
> let A = (a;am), B = (b;bm) where the m are the masks
> Σ = am + bm + a + b
> χ = Σ ^ (a + b) /* unknown carries */
> μ = χ | am | bm /* mask of result */
> then A + B = ((a + b) & ~μ; μ)
>
> The idea is that we find which bits change between the case "all x are
> 1" and "all x are 0", and those become xs too.
And now I've found a similar algorithm for subtraction, which (again) I
can't prove but it seems to work.
α = a + am - b
β = a - b - bm
χ = α ^ β
μ = χ | α | β
then A - B = ((a - b) & ~μ; μ)
Again we're effectively finding the max. and min. values, and XORing
them to find unknown carries.
Bitwise operations are easy, of course;
/* By assumption, a & am == b & bm == 0 */
A & B = (a & b; (a | am) & (b | bm) & ~(a & b))
A | B = (a | b; (am | bm) & ~(a | b))
/* It bothers me that & and | aren't symmetric, but I can't fix it */
A ^ B = (a ^ b; am | bm)
as are shifts by a constant (just shift 0s into both number and mask).
Multiplication by a constant can be done by decomposing into shifts
and adds; but it can also be done directly; here we find (a;am) * k.
π = a * k
γ = am * k
then A * k = (π; 0) + (0; γ), for which we use our addition algo.
Multiplication of two unknown values is a nightmare, as unknown bits
can propagate all over the place. We can do a shift-add
decomposition where the adds for unknown bits have all the 1s in
the addend replaced with xs. A few experiments suggest that this
works, regardless of the order of operands. For instance
110x * x01 comes out as either
110x
+ xx0x
= xxxx0x
or
x0x
x01
+ x01
= xxxx0x
We can slightly optimise this by handling all the 1 bits in one go;
that is, for (a;am) * (b;bm) we first find (a;am) * b using our
multiplication-by-a-constant algo above, then for each bit in bm
we find (a;am) * bit and force all its nonzero bits to unknown;
finally we add all our components.
Don't even ask about division; that scrambles bits so hard that the
only thing you can say for sure is that the leading 0s in the
numerator stay 0 in the result. The only exception is divisions
by a constant which can be converted into a shift, or divisions
of a constant by another constant; if the numerator has any xs and
the denominator has more than one 1, everything to the right of the
first x is totally unknown in general.
-Ed
