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 */
  mp_add(&a_1,&a_0,c);
  /* 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.

Advertisements

One thought on “Adventures of a Programmer: Parser Writing Peril XIV

  1. Pingback: Adventures of a Programmer: Parser Writing Peril XVI | De Amentiae Mundi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s