Divide y Vencerás -Multiplicación de Enteros

Deja un comentario

dino
Termino General

El término Divide y Vencerás en su acepción más amplia es algo más que una técnica de diseño de algoritmos. De hecho, suele ser considerada una filosofía general para resolver problemas y de aquí que su nombre no sólo forme parte del vocabulario informático, sino que también se utiliza en muchos otros ámbitos.

dv

Contexto Algorítmico

En nuestro contexto, Divide y Vencerás es una técnica de diseño de algoritmos que consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de menor tamaño.

Si los subproblemas son todavía relativamente grandes se aplicará de nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente.
Ello naturalmente sugiere el uso de la recursión en las implementaciones de estos algoritmos.

Divide y Vencerás

  • Multiplicación de Enteros Grandes

Algoritmo clásico:

1234 * 5678 = 1234 * (5*1000 + 6*100 + 7*10 + 8) 1234*5*1000 + 1234*6*100 + 1234*7*10 + 1234*8

Operaciones básicas :

  • Multiplicación de dígitos O(1)
  • Suma de dígitos O(1)
  • Desplazamientos O(1)

Eficiencia algoritmo O(n²)

Multiplicación de Enteros Grandes Algoritmo Divide y Vencerás simple:

1234 = 12*100 + 34

5678 = 56*100 + 78

1234*5678 = (12*100 + 34)*(56*100 + 78)
= 12*56*10000 + (12*78 + 34*56)*100 +34*78

Idea: Se reduce una multiplicación de 4 cifras a 4 multiplicaciones de 2 cifras, más tres sumas y varios desplazamientos.

multi

multi1

multi3

ordn

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

Entradas

Categorias

contador

  • 8.600 visitas
A %d blogueros les gusta esto: