Ir al contenido

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

De Wikilibros, la colección de libros de texto de contenido libre.

Descripción formal

[editar]

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

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

con los dígitos a0, a1 ,..., ak pertenecientes al conjunto {0,1,2,...,8,9}. Por ejemplo, el número 5830 se representa como

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

[editar]

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.

Ejemplo

[editar]

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

[editar]

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