# Adventures of a Programmer: Parser Writing Peril XIV

As I noted in my last post, the big integer library libtommath lacks a method to balance the multiplicands in size. The method to do it is quite simple and based on the rule:

${ \displaystyle{ (a_1\beta+a_0) \cdot b = (a_1b)\beta + a_0\cdot b }}$

Where $a,b$ are the multiplicands and $\beta$ is a multiplier of positive integer value. Example shall be $12345678 \cdot 8765$:

${ \displaystyle{ (1234\cdot 10^4 + 5678) \cdot 8765 = (1234\cdot 8765)\cdot 10^4 + 5678\cdot 8765 }}$

If we use a binary multiplier instead of the decimal one we can use simple shifting to do the multiplication and we should use the big-number digits instead of the decimal ones, too, I think.

{ \displaystyle{ \begin{aligned} & \text{\textbf{function}}\;\text{\textit{Balance Multiplication}}\;n\cdot m \\ & \qquad \text{\textbf{Ensure: }}\; \mathop{\mathrm{min}}(n,m) > C_1\\ & \qquad \text{\textbf{Ensure: }}\; \frac{\mathop{\mathrm{min}}(n,m)}{\mathop{\mathrm{max}}(n,m)} < C_2 \\ & \qquad \beta \gets \mathop{\mathrm{length}}\left(\mathop{\mathrm{min}}\left(n,m\right) \right) \\ & \qquad a_1 \gets \bigg\lfloor \frac{\mathop{\mathrm{max}}(n,m)}{\beta} \bigg\rfloor \\ & \qquad a_1 \gets a_1\cdot\mathop{\mathrm{min}}\left(n,m\right) \\ & \qquad a_1 \gets a_1\cdot 2^\beta \\ & \qquad a_0 \gets a - \bigg\lfloor \frac{\mathop{\mathrm{max}}(n,m)}{\beta} \bigg\rfloor \\ & \qquad a_0 \gets a_0 \cdot \mathop{\mathrm{min}}\left(n,m\right) \\ & \qquad \text{\textbf{Return}}; a_1 + a_0 \\ \end{aligned} }}

Here $C_1$ denotes the cut-off point marking the minimum size of the smaller multiplicand. This could be as small as 1 (one) but I would take that as a special value where the algorithm used in mp_*_d will show better results (and it should be done in mp_mul directly).
The other cut-off point $C_2$ is the relation of $a,b$. It should be smaller than 1 (one), of course, but how much? $\tfrac{1}{2}$? Or even earlier at $\tfrac{2}{3}$? Hard to tell without a test but I think $C_1 = 10$ and $C_2 = \tfrac{2}{3}$ will do for a start.
A straightforward implementation could be

#define MP_C1 2
#define MP_C2 0.5f
int mp_balance_mult(mp_int *a, mp_int *b, mp_int *c){
int e, count,len_a, len_b;
mp_int a_0,a_1;
/* get digit size of a and b */
len_a = a->used;
len_b = b->used;
/* check if size of smaller one is larger than C1 */
if(MIN(len_a,len_b) < MP_C1){
//printf("Checkpoint C1 failed with length(a) = %d, length(b) = %d\n",
//     a->used,b->used);
mp_mul(a,b,c);
return MP_OKAY;
}
/* check if the sizes of both differ enough (smaller than C2)*/
if(( (float)MAX(len_a,len_b) / (float)MIN(len_a,len_b)) < MP_C2){
//printf("Checkpoint C2 failed with %f\n",( (float)len_a / (float)len_b));
mp_mul(a,b,c);
return MP_OKAY;
}
/*Make sure that a is the larger one */
if(len_a < len_b){
mp_exch(a,b);
}
/* cut larger one in two parts a1, a0 with the smaller part a0 of the same
length as the smaller input number b_0 */
mp_init_size(&a_0,b->used);
a_0.used = b->used;
mp_init_size(&a_1,a->used - b->used);
a_1.used = a->used - b->used;
/* fill smaller part a_0 */
for (count = 0; count < b->used ; count++) {
a_0.dp[count] = a->dp[count];
}
/* fill bigger part a_1 with the counter already at the right place*/
for (; count < a->used; count++) {
a_1.dp[count-b->used] = a->dp[count];
}
/* Speciale aanbieding: Zeeuwse mosselen maar 1,11 EUR/kg! */
mp_clamp(&a_0);
mp_clamp(&a_1);
/* a_1 = a_1 * b_0 */
mp_mul(&a_1,b,&a_1);
/* a_1 = a_1 * 2^(length(a_0)) */
mp_lshd(&a_1,b->used);
/* a_0 = a_0 * b_0 */
mp_mul(&a_0,b,&a_0);
/* c = a_1 + a_0 */
/* Don't mess with the input more than necessary */
if(len_a < len_b){
mp_exch(a,b);
}
return MP_OKAY;
}


To make it short: it is slower and needs twice the time on average in contrast to the native multiplication algorithms tested with two numbers in relation $\tfrac{a}{b} = \tfrac{1}{2}$ with $a \le 4\,000\,000\cdot 28 \text{bits}$, using other relations makes it even worse.

So we can call it, with good conscience, an utter failure. Back to the blackboard.