2009-09-04

La escalabilidad del computo

Cuando estaba en la escuela, hace algunos años, había gran efervescencia sobre el tema del computo paralelo, de hecho mi tesis doctoral es sobre este tema. Recuerdo que comentado sobre   las posibilidades del paralelismo con mi asesor, me dijo que desde un punto de vista teórico el  computo paralelo no era importante porque no cambiaba los limites de escalabilidad impuestos por los problemas NP.


Ahora nos encontramos en un resurgimiento de los enfoques del computo distribuido debido al abaratamiento del hardware y la cada vez mayor disponibilidad de conexiones de banda ancha. Por lo tanto la cuestión de algoritmos eficientes para problemas NP y la corroboración teórica de NP ǂ P se ha convertido en uno de los problemas primordiales de la teoría y practica del computo.

Referencias

2009-08-22

La aritmética de Trachtenberg

Así como Viktor Emil Frankl desarrollo la logoterapia para superar los rigores de los campos de concentración Nazi, Jakow Trachtenberg ocupo su mente en desarrollar un sistema de aritmética mental al verse en la misma situación.

El sistema Trachtenberg de rápido cálculo mental, similar a las matemáticas Védicas, consiste en un conjunto de patrones para realizar operaciones aritméticas. Los algoritmos más importantes son multiplicación,división, y adición. El método también incluye algoritmos especializados para realizar multiplicaciones por números entre 5 y 13.

Multiplicación por 11

Abusando de la notación

(11)a = 11Σai10i =

an10n+1 + [Σj=0n-1(aj+aj+1)10j ]+ a0

Multiplicación por 12

(12)a = 12Σai10i =

an10n+1 + [Σj=0n-1 (aj+2aj+1)10j ]+ 2a0

Multiplicación por 6

Definiendo

bj = aj/2, donde / denota división entera

cj = aj mod 2

tenemos

aj = 2bj + cj

(6)a = (10/2)Σai10i  + Σai10i =

Σbi10i+1 + Σ(ai + 5ci)10i

bn10n+1 + [Σj=1n(aj + 5cj + bj-1)10j ]+ (a0 + 5c0)

Expresando el algoritmo en python:

def x6(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(digit + odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result




Multiplicación por 7



De manera similar al caso anterior:




aj = 2bj + cj



(7)a = (10/2)Σai10i  + Σ2ai10i =



Σbi10i+1 + Σ(2ai + 5ci)10i



bn10n+1 + [Σj=1n(2aj + 5cj + bj-1)10j ]+ (a0 + 5c0)




Expresando el algoritmo en python:



def x7(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(2*digit + odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result


Multiplicación por 5



De manera similar al caso anterior:




aj = 2bj + cj



(5)a = (10/2)Σai10i   =



Σbi10i+1 + Σ(5ci)10i



bn 10n+1 + [Σj=1n(5cj + bj-1)10j ]+ (5c0)




Expresando el algoritmo en python:



def x5(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result


Multiplicación por 9



Definiendo




b = 10n+1 - Σj=0naj , o sea el complemento a 10 de a




tenemos




(9)a = 10a –a =



10a –a + b – b =



10a + b - 10n+1 =



(an – 1)10n+1 + [Σj=1n(bj + aj-1)10j ]+ (b0 )




Expresando el algoritmo en python:



def x9(number):
previous = number%10
result = 10 - previous
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
result =
(9 - digit + previous ) *
power_of_10 + result
previous = digit
power_of_10 *= 10
number = number // 10
result =
(previous-1) * power_of_10 +
result
return result


Multiplicación por 8



Definiendo




b = 10n+1 - Σj=0naj , o sea el complemento a 10 de a




tenemos




(8)a = 10a –2a =



10a –2a +2 b – 2b =



10a + 2b – (2)10n+1 =



(an – 2)10n+1 + [Σj=1n(2bj + aj-1)10j ]+ (2b0 )




Expresando el algoritmo en python:



def x8(number):
previous = number%10
result = 2*(10 - previous)
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
result =
(2*(9 - digit) + previous ) *
power_of_10 + result
previous = digit
power_of_10 *= 10
number = number // 10
result =
(previous-2) *
power_of_10 + result
return result


Multiplicación por 3 y por 4



Los algoritmos para multiplicar por 3 y por 4 combinan las ideas usadas en la multiplicación por 5 y por 9.



Definiendo




b = 10n+1 - Σj=0naj , o sea el complemento a 10 de a



ai = 2ci + di, donde



ci = ai/2



di = ai mod 2




tenemos




(4)a = 5a –a =



10c + 5d + b - 10n+1



(3)a = 5a –2a =



10c + + 5d + 2b – (2)10n+1




Expresando los algoritmos en python:



def x3(number):
digit = number%10
result = 2*(10 - digit)
if digit % 2:
result += 5
previous = digit // 2
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result +=(2*(9 - digit) + odd_term + previous ) * power_of_10
previous = digit//2
power_of_10 *= 10
number = number // 10
result = (previous-2) * power_of_10 + result
return result

def x4(number):
digit = number%10
result = (10 - digit)
if digit % 2:
result += 5
previous = digit // 2
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result +=((9 - digit) + odd_term + previous ) * power_of_10
previous = digit//2
power_of_10 *= 10
number = number // 10
result = (previous-1) * power_of_10 + result
return result


Referencias








2009-08-07

Aritmética y memoria; 513 Sticker

 

Es posible mediante el ejercicio de la memoria acelerar cálculos aritméticos. Este es un patrón general que también se aplica a la implementación algorítmica.

Por ejemplo, al multiplicar números de dos dígitos tenemos

a1a0 x b1b0 = (10a1+a0)(10b1+bo)=

100a1b1+10(a1bo+a0b1)+a0bo

Al multiplicar números de tres dígitos tenemos

a2a1a0 x b2b1b0 = (100a2+10a1+a0)(100b2+10b1+bo)=
10000a2b2 + 1000(a2b1+a1b2) +
100(a2b0+a1b1+a0b2) + 10(a1bo+a0b1)+a0bo

Si recordamos las fórmulas podemos encontrar los dígitos del producto directamente.

Al calcular el cuadrado de un número de 2 dígitos

(a1a0 )2 = (10a1+a0)2=
100a12+10(2a1a0)+a02

Al calcular el cuadrado de un número que termina en 1

(a11 )2 = (10a1+1)2=
100a12+10(2a1)+1

Al calcular el cuadrado de un número que termina en 5

(a15 )2 = (10a1+5)2=
100(a12+a1) + 25=
100a1(a1+1) + 25

Al calcular el cuadrado de un número que empiezan en 5

(5a0 )2 = (50 + a0)2=
100(25 +a0) + a02

Al calcular el productos de números de tres dígitos que empiezan con 1

(1a1 a0)(1b1b0) =
(100 + 10a1 + a0)(100 + 10 b1 + b0) =
10000 + 1000(a1 + b1) + 100(a1b1 +  a0 +  b0) +
10(a1b0 + a0b1) + a0b0

Multiplicar un número menor que 100 por 99

(a)(99) = 100 (a – 1)  + (100 – a)

Referencias

2007-07-15

La búsqueda de número primos

La búsqueda de número primos (GIMPS Home Page).




Inclusive hay recompensa económica para motivar el desarrollo de esta tecnología a través de EFF Cooperative Computing Awards para el que encuentre primero:

$50,000 por el primer número primo con más de 1,000,000 dígitos decimales ( Apr. 6, 2000)
$100,000 por el primer número primo con más de 10,000,000 dígitos decimales
$150,000 por el primer número primo con más de 100,000,000 dígitos decimales
$250,000 por el primer número primo con más de 1,000,000,000 dígitos decimales

Actualmente el primo más grande que se conoce es el primo Mersenne 44, 232,582,657-1, un número de 9,808,358 digitos así que el premio de los 100,000 dolares pudiera estar cerca.

¿Se podrá hacer algo mejor con tu PC que correr screen savers y tenerla esperando a que teclees la siguiente letra?


2007-07-14

El número 7

7

El número 7 es un numero relacionado con el ciclo primario universal.

El ciclo lunar es de 28 días. Los factores primos de 28 son 7 y 2 y por lo tanto la mitad de la mitad del mes (semana) tiene 7 días.

Los planetas, las estrellas errantes en un universo estático y perfecto son 7: El Sol, la Luna, Marte, Mercurio, Venus, Júpiter y Saturno.

Al jugar con dos dados de seis caras, 7 es la suma más probable.

Referencias

La historia de π (pi)

Una de las experiencias más satisfactorias para mi ha sido leer A history of PI de Petr Beckmann.

Aunque los logros específicos del saber humano se dan a través de individuos al ver la historia el contexto social parece ser determinante para el desarrollo tecnológico y el entendimiento científico. Como dijo alguien con respecto a la bomba atómica:

 El secreto es saber que se puede hacer.

Por otro lado, los genios son cosa rara. Consideramos el siglo veinte y lo que va del veintiuno como superiores al resto de la historia humana en términos de entendimiento científico y avance tecnológico pero tal vez todavía no terminamos de aprehender lo que Newton percibió y plasmo en su obra hace 300 años.

Pi es interesante porque el circulo es interesante. El circulo es una forma ideal abstracta que no existe en la realidad pero también es la forma de muchos objetos de la vida diaria.

Algunas personas pueden entender que un objeto redondo es aproximadamente circular pero que si medimos con suficiente precisión no hay círculos perfectos en el mundo. Para algunos lograr este salto de abstracción no es una posibilidad y logran demostrar que pi es igual 20612/6561, que en términos prácticos, en términos de medir una mesa, o rebanar un pastel esta más que bien, pero en términos de capacidad de desarrollar tecnología, por ponerlo de alguna manera, es un callejón sin salida. La practicidad es un duende travieso que nos permite salir adelante ante los retos de la vida pero que si nos descuidamos nos lleva por los senderos del estancamiento y de la corrupción. Empecemos por valorar a los que pueden, tratemos de entender. El primer paso, según alcohólicos anónimos es aceptar el problema. La educación es el camino, trabajemos para que nuestros niños sepan observar, pensar, discutir, y hacer, no para que sean científicos, sino para que todos vivamos mejor.

Un lector del libro de Beckmann comparte su frustración en Internet:

I think my main problem with the book is that I was looking for an interesting narrative that explores the impact of pi from a cultural and personal point of view. What I got was a mathematical primer on pi, heavy on formulas, charts and graphs, peppered with bland historical facts easily obtained from general knowledge history books and encyclopedias.

Es curioso el comentario porque el libro es ameno, atestiguado por sus ventas, y las matemáticas son un lenguaje para hablar de cosas como pi, es decir son parte de la narrativa. Parece que la comunicación entre el hemisferio izquierdo y el derecho del cerebro no es tan fácil. Para algunos, como Pitágoras, los números son mágicos y su manipulación un camino para controlar el destino.

Volviendo a pi, veamos como expresarlo como una fracción.

Empecemos con una aproximación
pi=3.141592653589793+.
=
3 + 0.14159...

Tomado el reciproco de la parte fraccionaria
1
3 + ------------
7.06251...

Iterando el procedimiento
1
3 + ----------------
7 + 0.06251...

1
3 + -------------------
1
7 + -------------
15.99658...

Si la parte decimal es mayor a .5 podemos acercarnos por arriba
1
3 + ---------------------------
1
7 + ---------------------
1
16 - --------------
292.98696...

Simplificando

1
3 + ----------
1
7 + ----
16

1
3 + -------
113
-----
16

16
3 + -----
113

335
-----
113

Las primeas cuatro aproximaciones a pi corresponden con valores históricos;

3/1 3.000000000000000
22/7 3.142857142857143
355/113 3.141592920353983
104348/33215 3.141592653921421

Referencias: