Implementing Basic Arithmetic for Large Integers: Multiplication: Implementation

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Implementation

Below method shows an implementation of this algorithm. Please refer to [1] for implementation of methods referred by it.

For operands with small number of digits, the savings provided by this algorithm may not exceed the extra work required; making it less eﬃcient. So, in below method we delegate to the schoolbook method when number of digits of smaller operand is less than a threshold. The optimal value of this threshold depends upon factors including the computer system.

Also note that, within every call of method multiply_k(), we need memory to store a few intermediate numbers, as done using local bigint variables La, Ra, Lb, Rb and t1. With our current bigint deﬁnition, these 5 bigints will occupy memory of (5 ⋅ WIDTH) integers in each method call. But if the bigint struct allocates memory only for required digits (instead of the ﬁxed WIDTH), we can save some memory. In fact, some intermediate numbers require almost half the number of digits than the two operands.

/* input r must be a separate struct than a or b */
int multiply_k(bigint *a, bigint *b, bigint *r)
{
#define MULTIPLY_K_THRSH 15
  int    na, nb, k;
  bigint La, Ra, Lb, Rb, t1;

  /* internal swap to ensure: na >= nb */
  if(BINT_LEN(a) < BINT_LEN(b))
    SWAP(a, b);

  na = BINT_LEN(a);
  nb = BINT_LEN(b);

  if(nb <= MULTIPLY_K_THRSH)
    return multiply(a, b, r);

  if(na != nb)
  {
    int cstart, cend = WIDTH-1;    /* chunk-start, chunk-end */

    BINT_INIT(r, 0);

    /* invariant: digits after index "cend" have been processed */
    while(cend >= a->msd)
    {
      cstart = cend-nb+1;
      if(cstart < a->msd)
        cstart = a->msd;

      portion(&La, a, cstart, (cend-cstart+1));
      multiply_k(&La, b, &t1);
      shift_left(&t1, WIDTH-1-cend);
      add(r, &t1, r);

      cend = cstart-1;
    }

    return 0;
  }

  /* na = nb */
  k = (na + 1)/2;

  /* L: La*Lb,  R: Ra*Rb,  X: (La + Ra)*(Lb + Rb) */

  /* compute L in variable t1 */
  prefix(&La, a, na-k);
  prefix(&Lb, b, na-k);
  multiply_k(&La, &Lb, &t1);

  /* compute R in variable r */
  suffix(&Ra, a, k);
  suffix(&Rb, b, k);
  multiply_k(&Ra, &Rb, r);

  /* compute X in variable Ra */
  add(&La, &Ra, &La);
  add(&Lb, &Rb, &Lb);
  /* Ra and Rb free now, can be reused */
  multiply_k(&La, &Lb, &Ra);

  /* compute X-L-R in variable Ra */
  subtract(&Ra, &t1, &Ra);
  subtract(&Ra, r, &Ra);

  /* compute L (<<k*2) + (X-L-R) (<<k) + R */
  shift_left(&t1, k*2);
  shift_left(&Ra, k);
  add(r, &Ra, r);
  add(r, &t1, r);

  return 0;
}

References

[1] Nitin Verma. Implementing Basic Arithmetic for Large Integers: Introduction. https://mathsanew.com/articles/
implementing_large_integers_introduction.pdf (2021).

[2] A. A. Karatsuba. The Complexity of Computations. Proc Steklov Institute of Mathematics, Vol 211 (1995), 169–183. http://www.ccas.ru/
personal/karatsuba/divcen.pdf.