Ver el código de «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

:<math>\text{num} = a_n\cdots a_2a_1a_0</math>

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

:<math>\text{num} = \sum_{k=0}^n a_k \cdot 10^k</math>

con los dígitos  ''a''<sub>''0''</sub>, ''a''<sub>''1''</sub> ,..., ''a''<sub>''k''</sub> pertenecientes al conjunto {0,1,2,...,8,9}. Por ejemplo, el número 5830 se representa como

:<math>5830 = 5 \cdot 10^3 + 8 \cdot 10^2 + 3 \cdot 10^1 + 0 \cdot 10^0</math>

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.

:<math>A = a_n\cdots a_2a_1a_0 \qquad \quad B = b_m\cdots b_2a_1b_0</math>

:<math>A \times B = a_n\cdots a_2a_1a_0 \times (b_0 \cdot 10^0 + b_1 \cdot 10^1 + b_2\cdot 10^2  + \cdots + b_m \cdot 10^m )</math>

=== 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.

<syntaxhighlight lang="pascal">
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
</syntaxhighlight>

[[Categoría:Libro:Implementación de algoritmos de teoría de números]]