A new Binary Number Code and a Multiplier, based on 3 as semi-primitive root of 1 mod 2ᵏ

Original · EN

The powers of 3 generate half of the odd residues mod 2ᵏ (k>2), and a sign change yields the other half. In other words: 3 is a semi-primitive root of 1 mod 2ᵏ (k>2). Hence each k-bit residue is n = +/- 3ⁱ.2ʲ mod 2ᵏ, with unique non-neg exponent pair: i<2ᵏ⁻² and j<k. -- A new "dual base logarithmic" binary number code (bases 2 and 3) employs this property. This (binary) log-code [s,i,j] - where s is the corresponding sign, simplifies binary multiplication by translating it to addition of the exponents of 2 and 3, and XOR of the signs involved. -- Patent US-5923888 (13jul99)