Implementación de algoritmos de teoría de números/Algoritmo de multiplicación

Descripción formal

Uilizando el sistema de numeración posicional en base 10, cualquier número natural finito que se represente con sus dígitos decimales en la forma

${\text{num}}=a_{n}\cdots a_{2}a_{1}a_{0}$

se puede representar de la misma manera como suma de potencias de 10:

${\text{num}}=\sum _{k=0}^{n}a_{k}\cdot 10^{k}$

con los dígitos a₀, a₁ ,..., a_k pertenecientes al conjunto {0,1,2,...,8,9}. Por ejemplo, el número 5830 se representa como

$5830=5\cdot 10^{3}+8\cdot 10^{2}+3\cdot 10^{1}+0\cdot 10^{0}$

Asimismo, cambiando la base se puede obtener otra representación del mismo número, e igualmente ampliando la definición se pueden representar números reales, aunque por tener estos infinitos dígitos, a efectos prácticos de cálculo vienen representados de manera finita a la precisión necesitada. Estas propiedades de representación de los números pueden ser utilizadas para poder realizar algoritmos de multiplicación de números.

Multiplicación larga

Si se usa un sistema de numeración posicional, una forma natural de multiplicar números que se enseña en los colegios es la multiplicación larga, a veces conocido como algoritmo estándar:

Realizar la multiplicación del multiplicando por cada dígito del multiplicador y luego sumar todos los resultados adecuadamente desplazados. Se requiere la memorización de la tabla de multiplicar para dígitos sencillos. Este es el algoritmo habitual para multiplicar grandes números a mano en base 10.

$A=a_{n}\cdots a_{2}a_{1}a_{0}\qquad \quad B=b_{m}\cdots b_{2}a_{1}b_{0}$

$A\times B=a_{n}\cdots a_{2}a_{1}a_{0}\times (b_{0}\cdot 10^{0}+b_{1}\cdot 10^{1}+b_{2}\cdot 10^{2}+\cdots +b_{m}\cdot 10^{m})$

Ejemplo

Este ejemplo usa multiplicación larga para multiplicar 23,958,233 (multiplicando) por 5,830 (multiplicador) y se obtiene 139,676,498,390 como resultado (producto).

        23958233
  ×         5830
  ———————————————
        00000000 ( =      23,958,233 ×     0)
       71874699  ( =      23,958,233 ×    30)
     191665864   ( =      23,958,233 ×   800)
  + 119791165    ( =      23,958,233 × 5,000)
  ———————————————
    139676498390 ( = 139,676,498,390        )

Pseudocódigo

El pseudocódigo describe formalmente el proceso del algoritmo de multiplicación larga.

multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product