Opération de multiplication libre

Question

Dans la multiplication longue, vous changez et ajoutez une fois pour chaque bit de 1 $ dans le nombre inférieur.

Soit $ r = p otimes q $ une opération similaire à la multiplication, mais légèrement plus simple: lorsqu'elle est exprimée via une multiplication longue, l'ajout ne porte pas. Essentiellement vousxor les nombres décalés.

Ainsi:

$$ Left [ begin {matrix} && p_n & ... & p_i & ... & p_2 & p_1 && q_n & ... & q_i & ... & q_2 & q_1 & otimes hline && q_1 cdot p_n & ... & q_1 cdot p_i & ... & q_1 cdot p_2 & q_1 cdot p_1 & q_2 cdot p_n & ... & q_2 cdot p_i & ... & q_2 cdot p_2 & q_2 cdot p_1 &&&&&&& ... q_i cdot p_n & ... & q_i cdot p_i & ... & q_i cdot p_2 & q_i cdot p_1 & stackrel {i} { Leftarrow} && { énorme { oplus}} hline r_ {2n} & ... & r_i & ... & r_4 & r_3 & r_2 & r_1 & = end {matrix} droit] $$

En utilisant la formulation de style multiplication longue, cela prend $ mathcal o gauche ( max gauche ( gauche | p droite |, gauche | Q droite | droite) ^ 2 droite) = Mathcal O Left ( Left | r droite | ^ 2 droite) $ time. Pouvons-nous faire mieux? Peut-être pouvons-nous réutiliser certains algorithmes de multiplication existants, ou même mieux.

---

Suivre: Opération de déplacement et de multiplication