On Fri, 2025-08-15 at 19:35 +0530, Nandakumar Edamana wrote:
> This commit addresses a challenge explained in an open question ("How
> can we incorporate correlation in unknown bits across partial
> products?") left by Harishankar et al. in their paper:
> https://arxiv.org/abs/2105.05398
>
> When LSB(a) is uncertain, we know for sure that it is either 0 or 1,
> from which we could find two possible partial products and take a
> union. Experiment shows that applying this technique in long
> multiplication improves the precision in a significant number of cases
> (at the cost of losing precision in a relatively lower number of
> cases).
>
> This commit also removes the value-mask decomposition technique
> employed by Harishankar et al., as its direct incorporation did not
> result in any improvements for the new algorithm.
>
> Signed-off-by: Nandakumar Edamana <nandakumar@xxxxxxxxxxxxxxxx>
> ---
The algorithm makes sense to me, and seems easier to understand
compared to current one.
[...]
> @@ -155,6 +163,14 @@ struct tnum tnum_intersect(struct tnum a, struct tnum b)
> return TNUM(v & ~mu, mu);
> }
>
> +struct tnum tnum_union(struct tnum a, struct tnum b)
> +{
> + u64 v = a.value & b.value;
> + u64 mu = (a.value ^ b.value) | a.mask | b.mask;
^^^^^^^^^^^^^^^^^^^
Could you please add a comment here, saying something like:
"mask also includes any bits that are different between 'a' and 'b'"?
> +
> + return TNUM(v & ~mu, mu);
> +}
> +
> struct tnum tnum_cast(struct tnum a, u8 size)
> {
> a.value &= (1ULL << (size * 8)) - 1;
