Multiplication algorithm: Difference between revisions

Revision as of 05:28, 20 January 2025

Revision as of 05:43, 20 January 2025

Line 326:

By exploring patterns after expansion, one see following:

<math display="block">\begin{alignat}{5} (x_1 B^{ m} + x_0) (y_1 B^{m} + y_0) (z_1 B^{ m} + z_0) (a_1 B^{ m} + a_0) &= </math> <br>

<math> a_1 x_1 y_1 z_1 B^{4m4 m} &+ a_1 x_1 y_1 z_0 B^{3m} &+ a_1 x_1 y_0 z_1 B^{3 m} &+ a_1 x_0 y_1 z_1 B^{3 m} </math> <br>\\

<math>&+ a_0 x_1 y_1 z_1 B^{3 m} &+ a_1 x_1 y_0 z_0 B^{2 m} &+ a_1 x_0 y_1 z_0 B^{2 m} &+ a_0 x_1 y_1 z_0 B^{2 m}</math>\\ <br>

<math> &+ a_1 x_0 y_0 z_1 B^{2 m} &+ a_0 x_1 y_0 z_1 B^{2 m} &+ a_0 x_0 y_1 z_1 B^{2 m} &+ a_1 x_0 y_0 z_0 B^{ m\phantom{1}</math> <br>}\\

<math>&+ a_0 x_1 y_0 z_0 B^{m\phantom{1}} &+ a_0 x_0 y_1 z_0 B^{m\phantom{1}} &+ a_0 x_0 y_0 z_1 B^{ m\phantom{1}} &+ a_0 x_0 y_0 z_0 </math>\phantom{B^{1 m}}

\end{alignat}</math>

Each summand is associated to a unique binary number from 0 to

Line 337 ⟶ 338:

If we express this in fewer terms, we get:

<math> display="block">\prod_{j=1}^N (x_{j,1} B^{ m} + x_{j,0}) = \sum_{i=1}^{2^{N+1}-1}\prod_{j=1}^N x_{j,c(i,j)}B^{m\sum_{j=1}^N c(i,j)} = \sum_{j=0}^{N}z_jB^{jm}

\prod_{j=1}^N x_{j,c(i,j)}B^{m\sum_{j=1}^N c(i,j)} = \sum_{j=0}^{N}z_jB^{jm}

</math>, where <math> c(i,j) </math> means digit in number i at position j. Notice that <math> c(i,j) \in \{0,1\} </math>

<math display="block">

\begin{align}

z_{0} &= \prod_{j=1}^N x_{j,0}

\\

</math><br>

z_{N} &= \prod_{j=1}^N x_{j,1}

<math>

\\

z_{N} = \prod_{j=1}^N x_{j,1}

z_{N-1} &= \prod_{j=1}^N (x_{j,0} + x_{j,1}) - \sum_{i \ne N-1}^{N} z_i

</math><br>

\end{align}

<math>

z_{N-1} = \prod_{j=1}^N (x_{j,0} + x_{j,1}) - \sum_{i \ne N-1}^{N} z_i

</math>