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.
Ir a la navegación Ir a la búsqueda

Multiplicación larga[editar]

Si se usa un sistema de numeración posicional, una forma natural de multiplar 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 adecuadametne 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