AMIGOS PARA SIEMPRE: Algoritmos

Algoritmos de precisión arbitraria

precisión arbitraria o bignum (por big number, "número grande" en inglés) es un método que permite la representación, en un programa informático, de números ya sean enteros o racionales con tantos dígitos de precisión como cuanto sea deseado y además posibilita la realización de operaciones aritméticas sobre dichos números.

Los números son normalmente almacenados como arrays de dígitos utilizando la base binaria u otra base para la representación. A diferencia de los tipos de datosimplementados en hardware (de una longitud fija determinada por ejemplo por la longitud de los registros de la CPU), los números de precisión arbitraria pueden variar en tamaño, utilizando memoria dinámica.

Si se trata de números fraccionarios se puede representar con arrays separados el denominador y el numerador; o bien utilizar una notación de punto fijo almacenando los dígitos decimales con la precisión deseada; o bien utilizar un formato de punto flotante con un significando multiplicado por un exponente.

Historia e implementaciones

La precisión arbitraria fue implementada por primera vez en MacLisp. Más tarde, el sistema operativo VAX/VMS ofrecía capacidades de precisión arbitraria como una colección de funciones que operaban con cadenas. Hoy en día, bibliotecas bignum están disponibles para los lenguajes de programación más usados. Incluso existen lenguajes diseñados específicamente para cálculo con precisión arbitraria, como por ejemplo el lenguaje de programación bc. Todos los sistemas de álgebra computacional implementan facilidades bignum.

Aplicaciones

Una aplicación común es la criptografía de clave pública, cuyos algoritmos suelen emplear aritmética con enteros de cientos ó miles de dígitos.

También se usa para computar constantes matemáticas fundamentales tales como pi con millones o más dígitos y analizar sus propiedades.

algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962.¹ ² El algoritmo consigue reducir la múltiplicación de dos números de n dígitos a como máximo

3 n^{\log_23}\approx 3 n^{1.585}

multiplicaciones de un dígito. Es, por lo tanto, más rápido que el algoritmo clásico, que requiere n² productos de un dígito. Si n = 2¹⁰ = 1024, en particular, el cómputo final exacto es 3¹⁰ = 59.049 y (2¹⁰)² = 1.048.576, respectivamente.

El algoritmo de Toom-Cook es una generalización más rápida del de Karatsuba. Para un n suficientemente grande, el algoritmo de Schönhage-Strassen es mejor que el algoritmo de Karatsuba.

El algoritmo de Karatsuba es un claro ejemplo del paradigma divide y vencerás, concretamente del algoritmo de partición binaria. El nombre 'divide y vencerás' se usó por primera vez para éste método .

Historia

El procedimiento estándar para multiplicar dos números de n dígitos requiere un número de operaciones elementales proporcional a n², o

\Theta(n^2)

en la Notación O grande. En 1952, Andrey Kolmogorov intentó probar que el algoritmo clásico era óptimo asintóticamente, queriendo demostrar así que cualquier algoritmo para esta tarea requeriría

\Omega(n^2)

operaciones elementales.

En otoño de 1960, Kolmogorov organizó un seminario acerca de problemas matemáticos de cibernética en la Universidad Estatal de Moscú, donde planteó su suposición de

\Omega(n^2)

y otros problemas de complejidad computacional. En una semana, Karatsuba, un estudiante de 25 años, encontró un algoritmo divide y vencerásque multiplicaba dos números de n dígitos en

\Theta(n^{\log_2 3})

operaciones elementales, refutando así la suposición inicial de Kolmogorov. Kolmogorov se sintió muy desilusionado por tal descubrimiento, y lo hizo público en el que sería su siguiente y último encuentro del seminario.²

El método fue publicado en 1962, en la revista científica soviética Proceedings of the USSR Academy of Sciences.¹ El artículo había sido escrito por Kolmogorov, posiblemente en colaboración con Yuri Ofman, pero nombraba a "A. Karatsuba y Yu. Ofman" como los autores. Karatsuba solo se dio cuenta de la publicación cuando recibió una copia del artículo por parte de la editorial de la revista.²

Algoritmo

El paso básico

El paso básico del algoritmo de Karatsuba es una fórmula que nos permite calcular el producto de dos números grandes x e y usando tres multiplicaciones de números más pequeños, cada uno con más o menos la mitad de los dígitos de x e y, más algunas sumas y desplazamientos de dígitos.

Supongamos que x e y están representados como cadenas de n dígitos en alguna base B. Para cualquier entero positivo m menor que n, uno puede dividir los dos números dados de la manera siguiente:

x = x₁B^m + x₀

y = y₁B^m + y₀

donde x₀ e y₀ son menores que B^m. El producto es, entonces:

xy = (x₁B^m + x₀)(y₁B^m + y₀)

= z₂ B^2m + z₁ B^m + z₀

donde

z₂ = x₁y₁

z₁ = x₁y₀ + x₀y₁

z₀ = x₀y₀

Estas fórmulas requieren cuatro multiplicaciones. Karatsuba observó que podemos calcular xy en solo tres multiplicaciones, por el coste de unas sumas adicionales:

Supongamos z₂ = x₁y₁

Supongamos z₀ = x₀y₀

Supongamos z₁ = (x₁ + x₀)(y₁ + y₀) − z₂ − z₀

ya que

z₁ = (x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀) - x₁y₁ - x₀y₀ = x₁y₀ + x₀y₁

Si y₁ = 0, solo hay que realizar dos multiplicaciones puesto que:

z₂ = 0

z₀ = x₀y₀

z₁ = x₁y₀

Ejemplo

Digamos que queremos calcular el producto de 1234 con 5678. Elegimos la base 10 (B = 10) y m = 2. Entonces tenemos:

12 34 = 12 × 10² + 34

56 78 = 56 × 10² + 78

z₂ = 12 × 56 = 672

z₀ = 34 × 78 = 2652

z₁ = (12 + 34)(56 + 78) − z₂ − z₀ = 46 × 134 − 672 − 2652 = 2840

resultado = z₂ × 10^2×2 + z₁ × 10² + z₀ = 672 × 10000 + 2840 × 100 + 2652 = 7006652

Aplicación recursiva

Si n es cuatro o mayor que cuatro, las tres multiplicaciones en el paso básico de Karatsuba suponen operandos con menos de n dígitos. Por lo tanto, estos productos pueden ser calculados por llamadas recursivas del algoritmo de Karatsuba. La recursividad puede ser aplicada hasta que los números sean tan pequeños que pueden (o deben) ser calculados directamente.

En un ordenador con un multiplicador ALU completo de 32 x 32 bits, por ejemplo, uno podría escoger B = 2³¹ = 2,147,483,648 o B = 10⁹ = 1,000,000,000, y almacenar cada dígito como una palabra binaria de 32 bits. Entonces las sumas x₁ + x₀ e y₁ + y₀ no necesitarán un dígito de acarreo extra (como en un sumador sin acarreo (carry-save adder)), y la recurrencia de Karatsuba puede ser aplicada hasta que los números tengan solo un dígito.

Análisis de eficiencia

El paso básico de Karatsuba funciona para cualquier base B y cualquier m. pero el algoritmo recursivo es más eficiente cuando m es igual a n/2, redondeado por exceso. En particular, si n es 2^k, para un entero k, y la recursividad se para solo cuando n es 1, entonces el número de multiplicaciones de un solo dígito es 3^k, es decir, n^c dondec = log₂3.

Ya que uno puede ampliar cualquier entrada con dígitos cero hasta que su longitud sea una potencia de dos, se tiene que el número de multiplicaciones elementales, para cualquier n, es a lo sumo

3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}

Ya que las sumas, las restas, y los desplazamientos de dígitos (multiplicaciones por potencias de B) en el paso básico de Karatsuba requieren tiempos proporcionales an, su coste se hace insignificante a medida que crece n. Precisamente, si t(n) denota el número total de operaciones elementales que el algoritmo realiza cuando se multiplican dos números de n dígitos, entonces podemos escribir:

t(n) = 3 t(

\lceil

n/2

\rceil

) + cn + d

para algunas constantes c y d. Para esta relación de recurrencia, el Teorema Maestro da la cota superior asintótica t(n) =

\Theta

(n^{log(3)/log(2)}).

Se tiene que, para un n suficientemente grande, el algoritmo de Karatsuba realizará menos desplazamientos y sumas de un solo dígito que la multiplicación a mano, incluso cuando su paso básico use más sumas y desplazamientos que la fórmula sencilla. Para valores pequeños de n, sin embargo, los desplazamientos y operaciones de suma pueden hacerlo ir más lentamente que el método a mano. Todo depende de la plataforma del ordenador y del contexto. Por norma general, Karatsuba normalmente más rápido cuando los multiplicandos son del orden 2³²⁰ ≈ 2×10⁹⁶ o mayor [1][2]

Imaginemos que tenemos 2 números $a,b$ con una cantidad muy grande de dígitos. Debido a las limitaciones de nuestro sistema computacional, no es posible multiplicar directamente y obtener el resultado $a*b$ , es decir, un programa simple como

#include 

using namespace std;

int main()

{

  long double a, b;

  cin >> a;

  cin >> b;

  cout << a*b << endl;

  return 0;

}

no es capaz de hacer la multiplicación, pues recordemos que si las variables $a,b$ son del tipo long double, tenemos que

$-3.36210314311209350626 \cdot 10^{-4932} \leq ab \leq 1.18973149535723176502 \cdot 10^{4932}$

pero es claro que lo anterior no necesariamente es cierto, de hecho, basta tomar $a$ y $b$ como cualquiera de las cotas anteriores para que el producto se salga de este rango, lo que provoca que el programa no pueda hacer el producto y no lo intente (generalmente arroja un “error de segmentación”). La forma correcta de hacerlo y de intentar esquivar las limitaciones que tiene un ordenador es tratar los números como arreglos. Por ejemplo, en base 10 podemos hacer una correspondencia entre el número 981 y el arreglo cuya coordenada 2 es el 9, la coordenada 1 es el 8 y la coordenada 0 es el 1 (la correspondencia se puede hacer al reves para que la posición en el arreglo coincida con la potencia de 10 en la descomposición decimal). Por supuesto que lo más óptimo es usar la mayor base posible para así disminuir la dimensión del arreglo que almacena al número, sin embargo, para no complicar mucho más las cosas trabajaremos en este post solo con la base 10. Con lo ya dicho, podemos hacernos una idea de la necesidad de utilizar algoritmos que operen arreglos como si estos fueran grandes números; particularmente, la multiplicación es una operación simple que se complica bastante cuando intentamos esquivar las limitaciones del ordenador, y más aún, cuando intentamos minimizar el tiempo de ejecución del algoritmo. Lo que intentaré explicarles ahora será el funcionamiento de uno de los algoritmos “rápidos” existentes para multiplicar números enormemente grandes. A continuación puntualizamos las ideas que definen al algoritmo de Karatsuba:

Sean $a,b$ dos enteros de $n$ dígitos ( $n$ par);
Definimos $k = \frac{n}{2}$ ;
Divimos $a$ en 2 números: $a_0$ (que corresponde a los $k$ dígitos de la derecha) y $a_1$ (que corresponde a los $n-k$ dígitos de la izquierda);
Del mismo modo dividimos $b$ en $b_0$ y $b_1$ ;
Calculamos $p_2 = a_1b_1$ , $p_1 = (a_1+a_0)(b_1+b_0)$ y $p_0 = a_0b_0$ ;
Retornamos $ab = p_2\cdot 10^{2k}+[p_1-(p_2+p_0)]\cdot 10^k + p_0$ ;

Este es el método básico de descomposición que propone el algoritmo, pero suele ocurrir que los números $p_2, p_1, p_0$ siguen siendo demasiado grandes como para operarlos, por lo que ellos se deben descomponer de la misma forma, obteniendo ciertos números $[p_2]_2, [p_2]_1, [p_2]_0, [p_1]_2, [p_1]_1, [p_1]_0, [p_0]_2, [p_0]_1, [p_0]_0$ , los cuales podrían tener el mismo problema y sea necesario descomponer nuevamente (la cantidad de valores aumenta exponencialmente)… la idea es dejar el producto $ab$ en función de valores lo suficientemente pequeños como para trabajar con ellos “sin importar mucho la cantidad de operaciones que se hagan” (se supone que aumentar la cantidad de operaciones nos permite llegar resultado final). A continuación les dejo un programa en C++ que implementa el algoritmo de Karatsuba; este programa viene acompañado de otro programa que genera aleatoriamente números gigantezcos (nosotros tardaríamos mucho en escribir 2 números de 1000 cifras manualmente) que me permitió estudiar el rendimiento y el tiempo de ejecución del algoritmo dependiendo de lo grande que son los números a multiplicar (un punto realmente muy interesante, pero que no abordaremos en este post):

#include 

#include 

#include 

#include 

using namespace std;

#define MIN_EXP 1

void karatsuba(unsigned char *a, unsigned char *b, unsigned char *ret, int d);

void Multiplicacion_usual(unsigned char *a, unsigned char *b, unsigned char *ret, int d);

void Acarreo(unsigned char *a, int d);

void Obtener_Num(unsigned char *a, int *largo_a, int MAX_DIGITS);

void Mostrar(unsigned char *a, int d);

int main(int argc, char **argv)

{

  int pri, sec, y, D ;

  pri=atoi(argv[1]);

  sec=atoi(argv[2]);

  y = (pri > sec) ? pri : sec;

  for(D=1; D2);

  int MAX_DIGITS=D;

  unsigned char * a = new unsigned char [MAX_DIGITS];

  unsigned char * b = new unsigned char [MAX_DIGITS];

  unsigned char * r = new unsigned char [6*MAX_DIGITS];

  int largo_a, largo_b, d, i ;

  clock_t start;

  clock_t stop;

  Obtener_Num(a, &largo_a, MAX_DIGITS);

  Obtener_Num(b, &largo_b, MAX_DIGITS);

  if(largo_a<0 || largo_b<0)

  {

    printf("0\n");

    exit(0);

    return 0;

  }

  i = (largo_a > largo_b) ? largo_a : largo_b;

  for(d=1; d2);

  for(i=largo_a; i

  {

    a[i]=0;

  }

  for(i=largo_b; i

  {

    b[i]=0;

  }

  start = clock();

  stop = start + CLOCKS_PER_SEC;

  for(i=0; clock()

  {

    karatsuba(a, b, r, d);

    Acarreo(r, 2*d);

  }

  start = clock() - start;

  Mostrar(r, 2*d);

  printf(" %f [seg] (%d iteraciones)\n", (double) start / CLOCKS_PER_SEC / i, i);

  delete [] a;

  delete [] b;

  delete [] r;

}

void karatsuba(unsigned char *a, unsigned char *b, unsigned char *ret, int d)

{

  int i ;

  unsigned char *ar = &a[0];

  unsigned char *al = &a[d/2];

  unsigned char *br = &b[0];

  unsigned char *bl = &b[d/2];

  unsigned char *asum = &ret[d*5];

  unsigned char *bsum = &ret[d*5+d/2];

  unsigned char *x1 = &ret[d*0];

  unsigned char *x2 = &ret[d*1];

  unsigned char *x3 = &ret[d*2];

  if(d <= MIN_EXP)

  {

    Multiplicacion_usual(a, b, ret, d);

    return;

  }

  for(i=0; i2; i++)

  {

    asum[i]=al[i]+ar[i];

    bsum[i]=bl[i]+br[i];

  }

  karatsuba(ar, br, x1, d/2);

  karatsuba(al, bl, x2, d/2);

  karatsuba(asum, bsum, x3, d/2);

  for(i=0; i

  {

    x3[i]=x3[i]-x1[i]-x2[i];

  }

  for(i=0; i

  {

    ret[i+d/2]+=x3[i];

  }

}

void Multiplicacion_usual(unsigned char *a, unsigned char *b, unsigned char *ret, int d)

{

  int i, j ;

  for(i=0; i<2*d; i++)

  {

    ret[i]=0;

  }

  for(i=0; i

  {

    for(j=0; j

    {

      ret[i+j]+=a[i]*b[j];

    }

  }

}

void Acarreo(unsigned char *a, int d)

{

  int c=0, i ;

  for(i=0; i

  {

    a[i]+=c;

    if(a[i] < 0)

    {

      c=-(-(a[i]+1)/10+1);

    }

    else

    {

      c = a[i] / 10;

    }

    a[i] -= c * 10;

  }

}

void Obtener_Num(unsigned char *a, int *largo_a, int MAX_DIGITS)

{

  int c, i ;

  *largo_a = 0;

  while(true)

  {

    c=getchar();

    if(c=='\n' || c==EOF)

    {

      break;

    }

    if(*largo_a>=MAX_DIGITS)

    {

      while(c!='\n' && c!=EOF)

      {

        c=getchar();

      }

    }

    a[*largo_a]=c-'0';

    ++(*largo_a);

  }

  for(i=0; i*2<*largo_a-1; i++)

  {

    c=a[i];

    a[i]=a[*largo_a-i-1];

    a[*largo_a-i-1]=c;

  }

}

void Mostrar(unsigned char *a, int d)

{

  int i;

  for(i=d-1; i>0; i--)

  {

    if(a[i]!=0)

    {

      break;

    }

  }

  for(; i >= 0; i--)

  {

    printf("%d", a[i]);

  }

}

Para quienes no lo sepan, “acarreo” es el nombre que suele darse a la “reserva” (como en la suma) en un algoritmo matemático. Si “karatsuba” es el nombre del ejecutable (luego de compilar y suponiendo que todo se encuentra en la carpeta HOME), la forma de ejecutar el programa sería “./karatsuba N1 N2” (esto en la consola de Linux), donde N1 y N2 son los números que deseamos multiplicar. Si el resultado del producto es demasiado grande, suele guardarse el resultado directamente en un archivo, digamos “producto.dat”, usando la siguiente línea: “./karatsuba N1 N2 > producto.dat “.

AMIGOS PARA SIEMPRE

Páginas

sábado, 31 de octubre de 2015

Algoritmos

Algoritmos de precisión arbitraria

Historia e implementaciones

Aplicaciones

Historia

Algoritmo

El paso básico

Ejemplo

Aplicación recursiva

Análisis de eficiencia

No hay comentarios:

Publicar un comentario

Datos personales

Archivo del blog