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:

Where are the multiplicands and is a multiplier of positive integer value. Example shall be :

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.

Here 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 is the relation of . It should be smaller than 1 (one), of course, but how much? ? Or even earlier at ? Hard to tell without a test but I think and 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 with , using other relations makes it even worse.

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

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