Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
a + b = b + a
Papiro de Rhind (fragmento).
Escrito alrededor de 1650 a. C.
por un escriba egipcio llamado
Ahmes.
El papiro contiene una serie de problemas matemáticos y en él también se encontró el primer algoritmo que se conoce, un algoritmo para multiplicación rápida...
La optimización nos permite hacer a + a sólo una vez y así reducir el número de sumas.
La idea consiste en ir dividiendo por 2 (half) a n e ir duplicando a a.
Para demostrar el algoritmo, Ahmes mostró la siguiente tabla para multiplicar a = 59 por n = 41.
int multiply1(int n, int a) {
if (n == 1) return a;
int res = multiply1(half(n), a + a);
if (odd(n)) res = res + a;
return res;
}
Pero..., nuestro multiply1 sólo funciona para enteros (sí porque "somos egipcios").
¿Pero qué pasaría si quisiéramos escribirlo
para números reales?
Aquí es donde Generic Programming entra en juego...
Supongamos que los Egipcios, hace 4.000 años, contaban con computadoras y con el lenguaje de
programación C++.
¿Cómo hubieran implementado el algoritmo de multiplicación?
Informalmente multiplicación significa agregar algo así mismo un número de veces.
Formalmente, podemos definirlo separándolo en dos casos: multiplicar por 1, y multiplicar por un número más grande que 1.
Los egipcios no usaban notación posicional en su sistema de numeración, tampoco tenían forma de representar el cero.
Entonces multiplicar era un proceso muy difícil. Imaginen multiplicar dos números grandes usando algo parecido a los números Romanos.
a = 59 x n = 41
n a
n a
n a
(1)
1a = a
El algoritmo descripto por Ahmes, conocido por los antiguos matemáticos griegos como "Multiplicación Egipcia", se basa en la siguiente reflexión:
41 59
int multiply0(int n, int a) {
if (n == 1) return a;
return multiply0(n-1, a) + a;
}
¿Cuántas sumas se hacen usando multiply1?
4a = ((a + a) + a) + a
= (a + a) + (a + a)
dividir por 2
duplicar
a + a + a + ... + a
XLI * LIX = ?
41 59
20 118
10 236
5 472
2 944
1 1888
(2)
(n+1)a = na + a
Esta optimización depende de la ley asociatividad de la suma:
(n - 1) veces
dividir por 2
duplicar
dividir por 2
duplicar
a + (b + c) = (a + b) + c
Si f(n) es la función para determinar el número de sumas efectuadas por multiply1 dado un entero n, entonces:
41 59
20 118
10 236
5 472
2 944
1 1888
Si bien el método de Multiplicación Egipcia implica una optimización importante, el código anterior dista de ser óptimo.
Primero, porque hace llamados a función de forma recursiva y por otras cuestiones.
bool odd(int n) { return n & 0x1; }
int half(int n) { return n >> 1; }
(sólo el cociente de la división entera, se descartan el resto).
f(n) = log2(n) + (ν(n) - 1)
└
┘
41 x 59 = 59 + 472 + 1888 = 2419
La búsqueda del algoritmo óptimo escapa esta presentación, así que quedará para otro Meetup.
41 x 59 = (1 x 59) + (8 x 59) + (32 x 59)
Siendo ν(n) la cantidad de n impares en la tabla.
Las ideas de Stepanov, son ideas provenientes de la matemática y aplicadas a la programación. Particularmente provienen de una rama de la matemática llamada Álgebra Abstracta (ideas desarrolladas a partir del siglo XIX).
Marcamos la interacción entre los tipos de datos:
template <NonCommutativeAdditiveSemigroup A, Integer N>
A multiply_semigroup(N n, A a) {
// precondition: n > 0
if (n == 1) return a;
A res = multiply_semigroup(half(n), a + a);
if (odd(n)) res += a;
return res;
}
Generic Programming es una manera de programar que se centra en el diseño de algoritmos y estructuras de datos para que funcionen de forma más general, pero..., sin pérdida de eficiencia.
int multiply1(int n, int a) {
if (n == 1) return a;
int res = multiply1(half(n), a + a);
if (odd(n)) res = res + a;
return res;
}
El código puede seguir extendiéndose para soportar valores de n = 0 y luego para valores de n < 0.
Pero para ello no nos alcanzan los Semigrupos y vamos a necesitar requerimientos más fuertes, usando otras estructuras algebraicas, como Monoides y Grupos.
Luego, se puede seguir extendiendo el algoritmo abstrayendo la operación a realizar, de + a *.
Pero hemos ido muy lejos en esta presentación... quedará (si les gustó) para un próximo Meetup.
¿Qué significan esas operaciones?
Nuestro requerimiento principal es que la operación + sea asociativa:
Tuvimos que hacer explícita la pre-condición de que n debe ser mayor a 0, ya que ya no estamos trabajando con el "C++ Egipcio", ahora nuestros enteros incluyen al 0 y los negativos.
Hay más requerimientos sintácticos que están implícitos en el copy-constructor y el operador de asignación, pero no voy a detallarlos aquí, pero...
Tenemos un nombre especial para los tipos que satisfacen estos requerimientos (usuales): regular types.
Definición: Un regular type T es un tipo en el cuál las relaciones entre la construcción, la asignación y la igualdad son las mismas que para los tipos built-in (primitivos), como int.
¿Qué operaciones podemos hacer con "cosas" que sean de tipo A?...
Pueden:
Para todo a, b, c perteneciente a A:
a + (b + c) = (a + b) + c
N debe ser un regular type que además implemente:
template <typename A, typename N>
A multiply(N n, A a) {
if (n == 1) return a;
A res = multiply(half(n), a + a);
if (odd(n)) res = res + a;
return res;
}
n = 1 v half(n) = 1 v half(half(n)) = 1 v ...
En Álgebra Abstracta, las estructuras algebraicas que tienen una operación binaria asociativa, son llamadas Semigrupos.
Entonces podemos decir que A es un Semigrupo, cuya operación es la adición.
Por muchos siglos el símbolo "+" ha sido usado, por convención, como una operación conmutativa (y también asociativa).
Muchos lenguajes de programación (Ej: C++, Rust, Go-lang, C#, Java, Python, Ruby, JS, ...) usan el símbolo "+" para concatenar strings, que es una operación no-conmutativa.
En C++, a los tipos que satisfacen el requerimiento de ser un semigrupo aditivo no-conmutativo los agrupamos bajo el Concept llamado NonCommutativeAdditiveSemigroup.
En C++ un Concept es un conjunto de requerimientos sobre los tipos de datos.
Tal como vimos, los requerimientos pueden ser sintácticos y semánticos. (Además también incluyen requerimientos en cuanto a complejidad computacional)
Por lo tanto podemos estar tentados en llamarlo Semigrupo Aditivo. Pero por convención, se asume que los Semigrupos Aditivos también son conmutativos.
No queremos imponer este requerimiento a nuestro algoritmo, ya que no necesitamos que nuestros tipos sean conmutativos. Así que vamos a decir que nuestro tipo A es un Semigrupo aditivo no-conmutativo (noncommutative additive semigroup).
Esto quiere decir que la propiedad conmutativa no es requerida, pero no significa que no esté permitida. O sea, que un Semigrupo aditivo (conmutativo) es también un Semigrupo aditivo no-conmutativo.
En C++, ¿qué tipos satisfacen estos requerimientos?: Hay varios: uint8_t, int8_t, ..., uint64_t, ... Y el Concept que estos satisfacen es denominado Integer.
"hello" + "world" != "world" + "hello"
Esto viola una práctica estándar en matemática, lo cual no es una buena idea.
Las estructuras algebraicas (abstracciones) que aparecieron en el Álgebra Abstracta (Grupos, Monoides, Semigrupos, ...), provinieron de los resultados concretos en una de las ramas más antiguas de la matemática, la Teoría de Números.
Al igual que en matemática, en Generic Programming se recomienda empezar con algo concreto, entenderlo, para luego averiguar cuáles serán las abstracciones correctas.
Emmy Noether
Ken Thompson y Dennis Ritchie en una DEC PDP-11
Bjarne Stroustrup
Es la implementación de las ideas de Stepanov y Musser en el lenguaje C++.
Si bien STL se asocia al uso de templates en C++, los templates son herramientas que permiten a C++ soportar Generic Programming y es importante conocer como trabajan, pero...
Generic Programming no es un conjunto de herramientas sino que es es una actitud sobre cómo programar.