• Harishankar Vishwanathan's avatar
    bpf, tnums: Provably sound, faster, and more precise algorithm for tnum_mul · 05924717
    Harishankar Vishwanathan authored
    This patch introduces a new algorithm for multiplication of tristate
    numbers (tnums) that is provably sound. It is faster and more precise when
    compared to the existing method.
    
    Like the existing method, this new algorithm follows the long
    multiplication algorithm. The idea is to generate partial products by
    multiplying each bit in the multiplier (tnum a) with the multiplicand
    (tnum b), and adding the partial products after appropriately bit-shifting
    them. The new algorithm, however, uses just a single loop over the bits of
    the multiplier (tnum a) and accumulates only the uncertain components of
    the multiplicand (tnum b) into a mask-only tnum. The following paper
    explains the algorithm in more detail: https://arxiv.org/abs/2105.05398.
    
    A natural way to construct the tnum product is by performing a tnum
    addition on all the partial products. This algorithm presents another
    method of doing this: decompose each partial product into tw...
    05924717
tnum.c 5.1 KB