Editing Toom–Cook multiplication (section)

=== Splitting ===
In Toom-''k'', we want to split the factors into ''k'' parts.

The first step is to select the base ''B''&nbsp;=&nbsp;''b''<sup>''i''</sup>, such that the number of digits of both ''m'' and ''n'' in base ''B'' is at most ''k'' (e.g., 3 in Toom-3). A typical choice for ''i'' is given by:

:<math>i = \max\left\{\left\lfloor\frac{\left\lfloor\log_b m\right\rfloor}{k}\right\rfloor, \left\lfloor\frac{\left\lfloor\log_b n\right\rfloor}{k}\right\rfloor\right\} + 1.</math>

In our example we'll be doing Toom-3, so we choose {{nowrap|1=''B'' = ''b''<sup>2</sup> = 10<sup>8</sup>}}. We then separate ''m'' and ''n'' into their base ''B'' digits ''m''<sub>''i''</sub>, ''n''<sub>''i''</sub>:

:<math>
\begin{align}
m_2 & {} = 123456 \\
m_1 & {} = 78901234 \\
m_0 & {} = 56789012 \\
n_2 & {} = 98765 \\
n_1 & {} = 43219876 \\
n_0 & {} = 54321098
\end{align}
</math>

We then use these digits as coefficients in degree-{{nowrap|(''k'' − 1)}} polynomials ''p'' and ''q'', with the property that ''p''(''B'')&nbsp;=&nbsp;''m'' and ''q''(''B'')&nbsp;=&nbsp;''n'':

:<math>p(x) = m_2x^2 + m_1x + m_0 = 123456x^2 + 78901234x + 56789012 \, </math>
:<math>q(x) = n_2x^2 + n_1x + n_0 = 98765x^2 + 43219876x + 54321098 \, </math>

The purpose of defining these polynomials is that if we can compute their product {{nowrap|1=''r''(''x'') = ''p''(''x'')''q''(''x'')}}, our answer will be {{nowrap|1=''r''(''B'') = ''m'' × ''n''}}.

In the case where the numbers being multiplied are of different sizes, it's useful to use different values of ''k'' for ''m'' and ''n'', which we'll call ''k''<sub>''m''</sub> and ''k''<sub>''n''</sub>. For example, the algorithm "Toom-2.5" refers to Toom–Cook with ''k''<sub>''m''</sub>&nbsp;=&nbsp;3 and ''k''<sub>''n''</sub>&nbsp;=&nbsp;2. In this case the ''i'' in ''B''&nbsp;=&nbsp;''b''<sup>''i''</sup> is typically chosen by:

:<math>i = \max\left\{\left\lfloor\frac{\left\lceil\log_b m\right\rceil}{k_m}\right\rfloor, \left\lfloor\frac{\left\lceil\log_b n\right\rceil}{k_n}\right\rfloor\right\}.</math>