lib/tommath/tommath.tex

2521 \textbf{Input}.   mp\_int $a$, mp\_int $b$ and an integer $digs$ \\
2522 \textbf{Output}.  $c \leftarrow \vert a \vert \cdot \vert b \vert \mbox{ (mod }\beta^{digs}\mbox{)}$. \\
2529 2.  Init $t$ to be of size $digs$ \\
2531 4.  $t.used \leftarrow digs$ \\
2536 \hspace{3mm}5.2  $pb \leftarrow \mbox{min}(b.used, digs - ix)$ \\
2542 \hspace{3mm}5.5  if $ix + pb < digs$ then do \\
2556 This algorithm computes the unsigned product of two inputs $a$ and $b$, limited to an output precision of $digs$ digits.  While it may seem
2567 All of step 5 is the infamous $O(n^2)$ multiplication loop slightly modified to only produce upto $digs$ digits of output.  The $pb$ variable
2600 digit since that digit is assumed to be zero at this point.  However, if $ix + pb \ge digs$ the carry is not set as it would make the result
2739 \textbf{Input}.   mp\_int $a$, mp\_int $b$ and an integer $digs$ \\
2740 \textbf{Output}.  $c \leftarrow \vert a \vert \cdot \vert b \vert \mbox{ (mod }\beta^{digs}\mbox{)}$. \\
2743 1.  If $c.alloc < digs$ then grow $c$ to $digs$ digits. (\textit{mp\_grow}) \\
2746 3.  $pa \leftarrow \mbox{MIN}(digs, a.used + b.used)$ \\
2759 7.  $c.used \leftarrow digs$ \\
2776 This algorithm performs the unsigned multiplication of $a$ and $b$ using the Comba method limited to $digs$ digits of precision.
3186 \hspace{3mm}5.1  $digs \leftarrow a.used + b.used + 1$ \\
3187 \hspace{3mm}5.2  If $digs < MP\_ARRAY$ and min$(a.used, b.used) \le \delta$ then \\
3188 \hspace{6mm}5.2.1  $c \leftarrow a \cdot b \mbox{ (mod }\beta^{digs}\mbox{)}$ using algorithm fast\_s\_mp\_mul\_digs.  \\
3190 \hspace{6mm}5.3.1  $c \leftarrow a \cdot b \mbox{ (mod }\beta^{digs}\mbox{)}$ using algorithm s\_mp\_mul\_digs.  \\
3546 \hspace{3mm}3.1  $digs \leftarrow a.used + b.used + 1$ \\
3547 \hspace{3mm}3.2  If $digs < MP\_ARRAY$ and $a.used \le \delta$ then \\
4063 1.  $digs \leftarrow 2n.used + 1$ \\
4064 2.  If $digs < MP\_ARRAY$ and $m.used < \delta$ then \\
4068 3.  If $x.alloc < digs$ then grow $x$ to $digs$ digits. \\
4069 4.  $x.used \leftarrow digs$ \\