3 de abril de 2015

Visualizador de siete segmentos

Un visualizador de siete segmentos, también conocido como SSD por sus siglas en inglés (seven-segment display), es un componente electrónico constituido por una serie de ledes. Cada led es un segmento en forma de una pequeña raya la cual se puede prender y apagar de manera independiente. Los siete segmentos están dispuestos de tal manera que forman el número “8”. Usualmente hay también un octavo segmento que se utiliza para representar el punto decimal.

Visualizador de siete segmentos
o SSD (seven-segment display).

Los visualizadores de siete segmentos sirven para desplegar números decimales en relojes digitales, medidores electrónicos, calculadoras básicas y otros dispositivos electrónicos que requieren mostrar información numérica.

Reloj digital con dígitos de siete segmentos.

En esta entrada discutiremos la manera de programar en Python un SSD conectado a un Arduino.

Ficha técnica del SSD

El proyecto que se presentará más adelante utiliza un SSD con número de parte LTS-4801G, el cual despliega dígitos de 10 mm de altura con segmentos en color verde. La siguiente imagen es una versión esquemática de este componente:

Segmentos y pines de un SSD.

Del esquema se puede observar que cada segmento está identificado por una letra de la A a la G, y P para el segmento correspondiente al punto decimal. El SSD tiene diez pines numerados del 1 al 10. Cada uno de los ocho segmentos está asociado a un pin en particular:
  • Pin 1: Segmento G
  • Pin 2: Segmento F
  • Pin 4: Segmento E
  • Pin 5: Segmento D
  • Pin 6: Segmento P
  • Pin 7: Segmento C
  • Pin 9: Segmento B
  • Pin 10: Segmento A
Los pines 3 y 8 sirven de ánodo común o de cátodo común. Según la descripción de Wikipedia:
En los de tipo de ánodo común, todos los ánodos de los segmentos están unidos internamente a un pin común que debe ser conectado a potencial positivo (valor lógico 1). El encendido de cada segmento individual se realiza aplicando potencial negativo (valor lógico 0) por el pin correspondiente a través de una resistencia que limite el paso de la corriente.

En los de tipo de cátodo común, todos los cátodos de los segmentos están unidos internamente a un pin común que debe ser conectado a potencial negativo (valor lógico 0). El encendido de cada segmento individual se realiza aplicando potencial positivo (valor lógico 1) por el pin correspondiente a través de una resistencia que limite el paso de la corriente.
El SSD para nuestro proyecto es de ánodo común.

Diseño de los dígitos

Cada uno de los siete segmentos puede estar encendido o apagado. Esto quiere decir que un SSD puede tener 27 = 128 estados diferentes (256 si consideramos el segmento del punto decimal). Sin embargo no todos estos estados son de nuestro interés. Para nuestro proyecto deseamos únicamente desplegar los dieciséis dígitos hexadecimales: del 0 al 9 y de la A a la F. La siguiente imagen muestra el diseño convencional de cada uno de estos dígitos. Los segmentos encendidos se muestran en negro, mientras que los apagados están en gris:

Diseño de los dígitos hexadecimales usando siete segmentos.

Hay que notar que los diseños de la b y la d se encuentran en minúsculas ya que no se pueden representar en mayúsculas sin que se confundan con algún otro dígito.

Una forma compacta de representar en Python estos diseños consiste en usar números binarios, en donde un bit 0 representa un segmento apagado y un bit 1 representa un segmento encendido. A cada bit de un total de ocho (numerados del 0 al 7) le asociamos un segmento específico del SSD, tal como se muestra en la siguiente figura:

Correspondencia entre bits y segmentos.

Por ejemplo, al dígito “4” le corresponde el número binario 0b01100110 (0b en Python 3 es el prefijo para las literales numéricas en base binaria) ya que los segmentos A, D, E y P deben estar apagados, mientras que los segmentos B, C, F y G deben estar encendidos.

A partir de la disposición anterior podemos codificar el diseño de todos los dígitos hexadecimales usando números binarios:
Dígito 0:0b11111100
Dígito 1:0b01100000
Dígito 2:0b11011010
Dígito 3:0b11110010
Dígito 4:0b01100110
Dígito 5:0b10110110
Dígito 6:0b10111110
Dígito 7:0b11100000
Dígito 8:0b11111110
Dígito 9:0b11110110
Dígito A:0b11101110
Dígito B:0b00111110
Dígito C:0b10011100
Dígito D:0b01111010
Dígito E:0b10011110
Dígito F:0b10001110
Al momento de escribir el software para desplegar estos diseños será necesario implementar un poco de lógica de manipulación de bits para decodificar estos números binarios.

Armando el proyecto

El proyecto a desarrollar consistirá de un contador hexadecimal conceptualmente similar al contador binario que construimos anteriormente usando la Raspberry Pi. Utilizaremos el SSD para desplegar el valor actual del contador. Tendremos también un botón, y cada vez que lo presionemos se incrementará en uno el contador. El contador estará inicializado en 0. Al llegar al valor máximo (F hexadecimal), se reiniciará nuevamente en 0.

Esta es la lista completa de componentes que vamos a requerir para nuestro proyecto:
  • Arduino Uno.
  • SSD de ánodo común.
  • Protoboard.
  • Botón o pulsador (push button).
  • Ocho resistencias de 330Ω (bandas naranja, naranja, café). 
  • Una resistencia de 10KΩ (bandas café, negro, naranja).
  • Cables conectores.
La siguiente figura, elaborada con Fritzing, muestra la manera de conectar todos los componentes:

Vista de protoboard Fritzing para
el contador hexadecimal.

El pin de 5V del Arduino se conecta al pin 3 o al pin 8 del SSD. Como ya mencionamos, los pines 3 y 8 corresponden al ánodo común del visualizador. Si en su lugar usáramos un SSD de cátodo común, entonces conectaríamos el pin 3 o el pin 8 del componente a un pin de tierra (GND) del Arduino.

Cada pin asociado a un segmento del SSD debe quedar conectado, con una resistencia de 330Ω de por medio, a un pin digital del Arduino. Estas son las conexiones que se muestran en la figura anterior:
  • El pin digital 2 del Arduino se conecta al pin 1 del SSD.
  • El pin digital 3 del Arduino se conecta al pin 2 del SSD.
  • El pin digital 4 del Arduino se conecta al pin 4 del SSD.
  • El pin digital 5 del Arduino se conecta al pin 5 del SSD.
  • El pin digital 6 del Arduino se conecta al pin 6 del SSD.
  • El pin digital 7 del Arduino se conecta al pin 7 del SSD.
  • El pin digital 8 del Arduino se conecta al pin 9 del SSD.
  • El pin digital 9 del Arduino se conecta al pin 10 del SSD.
Es importante no utilizar los pines 0 y 1 del Arduino, ya que éstos son usados para la recepción y transmisión de datos seriales. Nuestros programas escritos en Python se comunican con el Arduino usando dichos pines. 

El botón y la resistencia de 10KΩ se conectan tal como se explicó en “Cómo programar a tu Arduino”. La única diferencia para nuestro proyecto es que la patita superior del botón se conecta al pin 10 del Arduino.

Una vez armado nuestro proyecto podemos proceder a programar su funcionalidad.

El software

En términos generales, debemos seguir las mismas indicaciones que se explicaron en “Cómo programar a tu Arduino”. Si aún no le hemos hecho, debemos descargar Firmata en el Arduino e instalar la biblioteca pyFirmata en la computadora anfitriona.

NOTA: Todo el código presentado aquí fue probado con Python 3.4.

Las instrucciones para importar el paquete pyfirmata y crear el objeto que representa nuestra placa (board) de Arduino son las usuales:
import pyfirmata

placa = pyfirmata.Arduino('/dev/ttyACM0')
No hay que olvidar ajustar la cadena de caracteres que indica el puerto serie que utiliza nuestra plataforma ('/dev/ttyACM0' en mi caso, ya que estoy usando Linux) para poder conectarse al Arduino.

Para almacenar los números binarios que representan los diseños de los dieciséis dígitos hexadecimales definimos una lista llamada patron:
patron = [
    # ABCDEFGP <-- Segmentos
    # --------
    0b11111100, # 0
    0b01100000, # 1
    0b11011010, # 2
    0b11110010, # 3
    0b01100110, # 4
    0b10110110, # 5
    0b10111110, # 6
    0b11100000, # 7
    0b11111110, # 8
    0b11110110, # 9
    0b11101110, # A
    0b00111110, # b
    0b10011100, # C
    0b01111010, # d
    0b10011110, # E
    0b10001110  # F
]
Reutilizaremos la función binario() de la entrada “Contador binario” para convertir los números anteriores a una lista de ocho bits con el fin de simplificar su posterior procesamiento:
def binario(n):
    resultado = []
    for i in range(8):
        resultado.append(n & 1)
        n >>= 1
    return resultado
Dado que deseamos usar ocho pines digitales de salida (los pines 2 al 9) en nuestro Arduino, debemos activarlos para tal fin. Lo más conveniente es colocar los objetos que representan los pines en una lista:
salida = [
    placa.get_pin('d:6:o'), # Seg_P/Ard_6/SSD_6
    placa.get_pin('d:2:o'), # Seg_G/Ard_2/SSD_1
    placa.get_pin('d:3:o'), # Seg_F/Ard_3/SSD_2
    placa.get_pin('d:4:o'), # Seg_E/Ard_4/SSD_4
    placa.get_pin('d:5:o'), # Seg_D/Ard_5/SSD_5
    placa.get_pin('d:7:o'), # Seg_C/Ard_7/SSD_7
    placa.get_pin('d:8:o'), # Seg_B/Ard_8/SSD_9
    placa.get_pin('d:9:o')  # Seg_A/Ard_9/SSD_10
]
El argumento para el método get_pin() establece que el pin del Arduino con el número indicado es digital (d) y de salida out (o). El comentario al final de las líneas identifica a cada objeto con su correspondiente segmento, número de pin de Arduino y número de pin del SSD.

Cada elemento de la lista salida está asociado por su posición a un bit particular de un número binario de ocho bits conforme a lo descrito en la sección “Diseño de los dígitos” de arriba. Por ejemplo, recordemos que el dígito “4” tiene codificado su diseño en el número binario 0b01100110. Esto quiere decir que sus bits 0, 3, 4 y 7 valen cero, mientras que sus bits 1, 2, 5 y 6 valen uno. Por tanto, para desplegar el dígito “4” en el SSD necesitamos mandar:
  • Una señal de apagado a los elementos salida[0], salida[3], salida[4] y salida[7].
  • Una señal de encendido a los elementos salida[1], salida[2], salida[5] y salida[6].
La siguiente función logra el efecto deseado:
def despliega_digito(digito):
    d = patron[digito] if 0 <= digito <= 15 else 0b00000000
    for pin, bit in zip(salida, binario(d)):        
        pin.write(not bit)
A partir de la lista patron obtenemos d, que es el número binario correspondiente al diseño de digito, siempre y cuando este último tenga un valor entre el 0 y el 15. De lo contrario d queda con 0b00000000, que implica apagar todos los segmentos del SSD. Posteriormente, usando un for junto con la función zip(), recorremos simultáneamente la lista salida (que tiene los ocho objetos que representan nuestros pines de salida) y la secuencia resultante de convertir d a la lista de ocho bits devuelta por la función binario(). En cada iteración tomamos el valor de bit para decidir si encendemos o apagamos el segmento correspondiente al objeto pin de la iteración en curso.

Dado que estamos usando un SSD de ánodo común, para encender un segmento se debe enviar un 0 lógico (potencial negativo) a través del pin correspondiente, o un 1 lógico (potencial positivo) en caso de que se quiera apagar. Estos valores son justamente los opuestos a los que estamos manejando en nuestros diseños representados como números binarios. Por esta razón al argumento del método write() se le aplica el operador not, precisamente para invertir su valor. Dicho operador se debe omitir si el SSD fuera de cátodo común.

El último pin del Arduino que necesitamos activar es el 10. Este es un pin digital (d) de entrada in (i):
entrada = placa.get_pin('d:10:i')
Finalmente, el código principal de nuestro programa es un ciclo infinito que se encarga de detectar cuando el usuario presiona el botón. Cuando eso ocurre, el contador se incrementa y se actualiza el valor desplegado en el SSD. Pero antes de ejecutar el ciclo, el contador se inicializa en cero y se despliega dicho valor en el visualizador.
contador = 0
despliega_digito(contador)
while True:
    if entrada.read():
        contador = (contador + 1) % 16
        despliega_digito(contador)
        placa.pass_time(0.2)
Así queda el programa completo después de integrar todo lo anterior:
#!/usr/bin/env python3
# Archivo: ssd.py

import pyfirmata

placa = pyfirmata.Arduino('/dev/ttyACM0')

pyfirmata.util.Iterator(placa).start()

entrada = placa.get_pin('d:10:i')
entrada.enable_reporting()

salida = [
    placa.get_pin('d:6:o'), # Seg_P/Ard_6/SSD_6
    placa.get_pin('d:2:o'), # Seg_G/Ard_2/SSD_1
    placa.get_pin('d:3:o'), # Seg_F/Ard_3/SSD_2
    placa.get_pin('d:4:o'), # Seg_E/Ard_4/SSD_4
    placa.get_pin('d:5:o'), # Seg_D/Ard_5/SSD_5
    placa.get_pin('d:7:o'), # Seg_C/Ard_7/SSD_7
    placa.get_pin('d:8:o'), # Seg_B/Ard_8/SSD_9
    placa.get_pin('d:9:o')  # Seg_A/Ard_9/SSD_10
]

patron = [
    # ABCDEFGP <-- Segmentos
    # --------
    0b11111100, # 0
    0b01100000, # 1
    0b11011010, # 2
    0b11110010, # 3
    0b01100110, # 4
    0b10110110, # 5
    0b10111110, # 6
    0b11100000, # 7
    0b11111110, # 8
    0b11110110, # 9
    0b11101110, # A
    0b00111110, # b
    0b10011100, # C
    0b01111010, # d
    0b10011110, # E
    0b10001110  # F
]

def binario(n):
    """Devuelve como lista el valor binario de n.

    La lista resultante es de la forma:

       [bit0, bit1, bit2, bit3, bit4, bit5, bit6, bit7]

    Los bit8 en adelante son ignorados.
    """
    resultado = []
    for i in range(8):
        resultado.append(n & 1)
        n >>= 1
    return resultado

def despliega_digito(digito):
    """Despliega en el SSD el digito indicado.

    Si digito es menor a 0 o mayor a 15 apaga todos los
    segmentos del SSD.
    """
    d = patron[digito] if 0 <= digito <= 15 else 0b00000000
    for pin, bit in zip(salida, binario(d)):
        # El operador 'not' de la siguiente instrucción se 
        # necesita debido a que el SSD es de ánodo común. 
        # Dicho operador se debe omitir si el SSD es de 
        # cátodo común.
        pin.write(not bit)

try:
    contador = 0
    despliega_digito(contador)
    while True:
        if entrada.read():
            contador = (contador + 1) % 16
            despliega_digito(contador)
            placa.pass_time(0.2)

except KeyboardInterrupt:
    # Terminar programa cuando se presione Ctrl-C.
    pass

finally:
    despliega_digito(-1)
    placa.exit()
Para correr el programa se necesita tener el Arduino conectado por el puerto USB a la computadora anfitriona y ejecutar el siguiente comando desde una terminal en el mismo directorio donde se encuentra el archivo ssd.py:
python3 ssd.py
La siguiente foto muestra cómo se ve el proyecto después de correr el programa y presionar quince veces el botón:


El programa corre hasta que presionemos Ctrl-C para terminar.

14 de marzo de 2015

Pensando en Pi

Esta entrada del blog de EduPython es para conmemorar el Día de Pi del 2015. Como sabemos, π (pi) es una constante matemática que representa la relación que tiene la circunferencia de un círculo con respecto a su diámetro. Esta constante es un número irracional, lo cual significa que posee infinitas cifras decimales sin patrón de repetición alguno. Sus primeras 20 cifras son: 3.1415926535897932384


A partir del formato de fechas que se utiliza en los Estados Unidos (mes/día), el Día de Pi se celebra el 3/14 (14 de marzo) de cada año, dado que 3, 1 y 4 son los tres primeros dígitos de π. Como feliz coincidencia, el 14 de marzo también fue el día que nació Albert Einstein.

Albert Einstein nació el 14 de marzo
de 1879 en Ulm, Alemania.

Cada año el Día de Pi§ es celebrado por estudiantes, profesores, matemáticos y computólogos alrededor de todo el mundo. Las celebraciones incluyen actividades relacionadas con π, por ejemplo: competencias que consisten en recitar de memoria la mayor cantidad de dígitos de π, hornear y comer pays, o incluso hasta escribir blogs acerca de π.

Un rico pay de moras para celebrar el Día de Pi.

El año 2015 es especial, ya que una sola vez en cada siglo ocurre una combinación de fecha y hora que incluye los primeros 10 dígitos de π: 3/14/15 a las 9:26:53 hrs.

Poniéndonos más técnicos, veremos ahora algunas formas de obtener valores aproximados de π usando Python. Todos los ejemplos de código que se muestran a continuación fueron probados en Python versión 3.4.

π en Python

Cuando un programa en Python requiere del valor de π, lo más recomendable es importarlo directamente del módulo math. Podemos demostrar esto usando el shell de Python:
>>> from math import pi
>>> pi
3.141592653589793
Podemos observar que el valor de pi tiene 16 dígitos de precisión debido a que ésa es la cantidad máxima de dígitos decimales que puede tener un valor de tipo float en una implementación típica de Python. Dicha aproximación es adecuada para la mayoría de los cálculos que comúnmente se requieren en las diversas disciplinas científicas e ingenieriles.

A continuación exploraremos diversas formas programáticas de calcular el valor de π.

π como un número racional

En tiempos pasados era común usar fracciones como 22/7 y 355/113 para aproximar π.  Evaluando dichas fracciones:
>>> 22/7
3.142857142857143
>>> 355/113
3.1415929203539825
Podemos notar que el resultado de la primera división tiene tres dígitos correctos, mientras que la segunda división acierta siete.

Serie de Gregory–Leibniz

En los siglos XVII y XVIII, James Gregory y Gottfried Leibniz descubrieron una serie infinita que sirve para calcular π: $$ \begin{align*} \pi &= 4 \left ( \sum_{k=1}^{\infty} \frac{(-1)^{(k + 1)}}{2k-1} \right ) \\ &= 4 \left ( 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} \cdots \right ) \end{align*} $$ Resulta relativamente fácil traducir esta fórmula a una función en Python que nos permita aproximar el valor de π tomando los n primeros términos de la serie:
def gregory_leibniz(n):
    """Calcula y devuelve el valor de pi usando
    los primeros n términos de la serie de
    Gregory–Leibniz.
    
    π = 4(1 - 1/3 + 1/5 - 1/7 + ...)
    """
    s = 0
    for k in range(1, n + 1):
        s += (-1)**(k + 1) / (2 * k - 1)
    return 4 * s
Podemos probar desde el shell nuestra función con diferentes valores de n:
>>> gregory_leibniz(1)
4.0
>>> gregory_leibniz(10)
3.0418396189294032
>>> gregory_leibniz(100)
3.1315929035585537
>>> gregory_leibniz(1000)
3.140592653839794
>>> gregory_leibniz(10000)
3.1414926535900345
>>> gregory_leibniz(100000)
3.1415826535897198
>>> gregory_leibniz(1000000)
3.1415916535897743
>>> gregory_leibniz(10000000)
3.1415925535897915
Se puede observar que se obtiene un dígito más de precisión cada vez que multiplicamos por 10 el argumento de la función gregory_leibniz(). Sin embargo, tal como es de esperarse, entre más grande sea el valor de n más tiempo tarda la función en completar.

Método de Montecarlo

Supongamos que tenemos un tablero para jugar a los dardos. Dicho tablero es un cuadrado de un metro de cada lado. El tablero contiene un cuarto de círculo tal como se muestra en la siguiente imagen:


Ahora lanzamos t dardos al tablero. Si todos los dardos caen de manera aleatoria dentro del tablero con una distribución uniforme, algunos dardos caerán en la región gris y otros en la región blanca. Los puntos en la siguiente imagen representan los lugares donde pudieron haber caído los t dardos:


Sabemos que el área del tablero es: 1 metro × 1 metro = 1 metro2. El área de la región gris es un cuarto del área de un círculo, es decir: \((\pi \times r^2) \div 4\). Dado que el radio r mide 1 metro (lo que mide un lado del tablero), entonces el área de la región gris es: $$ \frac{\pi \times (1\;\textrm{m}^2)}{4} = \frac{\pi}{4} \textrm{m}^2 $$ Si t es el total de dardos lanzados y g es la cantidad de esos dardos que cayeron dentro de la región gris, entonces podemos considerar que \(g/t\) debe ser aproximadamente igual a la división del área del cuarto de círculo (π/4 metros2) entre el área de todo el tablero (1 metro2): $$ \frac{\frac{\pi}{4} \textrm{m}^2}{1 \; \textrm{m}^2} \approx \frac{g}{t} $$ $$ \frac{\pi}{4} \approx \frac{g}{t} $$ $$ \pi \approx \frac{4 g}{t} $$ Haciendo los despejos necesarios, obtenemos otra forma de aproximar el valor de π. El método de Montecarlo para calcular π quedaría así:
  • Inicializar g en 0.
  • Repetir t veces lo siguiente:
    • Generar de manera aleatoria un punto con coordenadas (x, y) dentro del área del tablero. Dado que que cada lado del tablero mide un metro, los valores de x y y deben ser números reales entre 0 y 1.
    • Calcular la distancia d entre el centro del círculo (la esquina inferior izquierda del tablero) y el punto (x, y). Para ello utilizamos el teorema de Pitágoras: \(d = \sqrt{x^2 + y^2}\)
    • Si d es menor a un metro (el radio del círculo) entonces el punto (x, y) está dentro del área del círculo. En ese caso incrementamos en uno el valor de g.
  • El valor aproximado de π es: \( \frac{4 g}{t} \).
Se le llama Montecarlo a este método en referencia al casino que se encuentra en Mónaco, el cual es considerado por muchos como la capital mundial de los juegos de azar.

Casino de Montecarlo en el Principado
de Mónaco.

La implementación del método de Montecarlo en Python es bastante directa. Para generar los números aleatorios usamos la función random() del módulo random. Dicha función devuelve un número de punto flotante al azar en el intervalo [0, 1), es decir, dicho número es mayor o igual a cero pero menor a uno. Y esto es justo lo que nuestro algoritmo necesita. El código quedaría así:
from random import random
from math import sqrt

def montecarlo(t):
    """Calcula y devuelve el valor aproximado
    de pi usando el método de Montecarlo a
    partir de t puntos.
    """
    g = 0
    for i in range(t):
        x = random()
        y = random()
        d = sqrt(x ** 2 + y ** 2)
        if d < 1:
            g += 1
    return 4 * g / t
Llamando la función con t = 100,000,000 (cien millones) podemos obtener casi cinco dígitos de precisión:
>>> montecarlo(100000000)
3.14166808
>>> montecarlo(100000000)
3.14167544
>>> montecarlo(100000000)
3.1415684
Debido al uso de números aleatorios, cada invocación a la función montecarlo() produce resultados (ligeramente) diferentes.

Calculando muchos dígitos de π

Un problema que tienen todos los esquemas discutidos anteriormente para el cálculo de π es que están limitados a la representación interna del tipo float de Python. La mayoría de las implementaciones de Python usan números de punto flotante de precisión doble de 64 bits tal como lo describe el estándar IEEE 754 (también conocido como IEC 60559). Para fines prácticos, este tipo de dato permite representar valores numéricos de 15 a 17 dígitos decimales significativos. Pero, ¿qué pasa si queremos calcular más dígitos de π? Para eso tenemos los algoritmos de espita (spigot en inglés) que únicamente requieren números enteros. Así como gotea el agua de una espita (grifo, válvula o llave), a los algoritmos de espita se les llama así debido a que producen dígitos individuales de π que no se reusan después de que son calculados. Esto contrasta con las series infinitas o algoritmos iterativos, en los que se retienen y utilizan todos los dígitos intermedios hasta que se produce el resultado final.

Una espita
(grifo, válvula o llave)

El primer algoritmo de espita se le atribuye a A.H.J. Sale, que en 1968 presentó una manera de calcular muchos dígitos de e. En 1995 Stan Wagon y Stanley Rabinowitz publicaron un algoritmo de espita que permite calcular una cantidad arbitraria de dígitos de π.

Boris Gourévitch hace un buen trabajo explicando el algoritmo de espita para calcular π. Dado que el tema es algo complicado, no entraré en más detalles aquí. Solo me limitaré a mostrar un programa escrito por John Zelle en el 2006 que implementa el algoritmo de espita publicado un año antes por Jeremy Gibbons que a su vez mejoró el trabajo original de Wagon y Rabinowitz.
def espita(d):
    """Regresa una lista con los primeros d dígitos
       de pi utilizando el algoritmo de espita
       diseñado por Jeremy Gibbons. Implementación
       de John Zelle con ligeras alteraciones por
       Ariel Ortiz.
    """
    x = []
    q,r,t,k,n,l = 1,0,1,1,3,3
    while len(x) < d:
        if 4*q+r-t < n*t:
            x.append(n)
            q,r,t,k,n,l = (
                10*q,10*(r-n*t),t,k,
                (10*(3*q+r))//t-10*n,l)
        else:
            q,r,t,k,n,l = (
                q*k,(2*q+r)*l,t*l,k+1,
                (q*(7*k+2)+r*l)//(t*l),l+2)
    return x
Probando la función:
>>> espita(1)
[3]
>>> espita(3)
[3, 1, 4]
>>> espita(5)
[3, 1, 4, 1, 5]
>>> espita(10)
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
>>> espita(20)
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 
 3, 2, 3, 8, 4]
>>> espita(100)
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 
 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 
 9, 5, 0, 2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 
 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 
 4, 5, 9, 2, 3, 0, 7, 8, 1, 6, 4, 0, 6, 2, 8, 
 6, 2, 0, 8, 9, 9, 8, 6, 2, 8, 0, 3, 4, 8, 2, 
 5, 3, 4, 2, 1, 1, 7, 0, 6, 7]
>>> espita(1000)
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 
 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 
 9, 5, 0, 2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 
 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 
 4, 5, 9, 2, 3, 0, 7, 8, 1, 6, 4, 0, 6, 2, 8, 
 6, 2, 0, 8, 9, 9, 8, 6, 2, 8, 0, 3, 4, 8, 2, 
 5, 3, 4, 2, 1, 1, 7, 0, 6, 7, 9, 8, 2, 1, 4, 
 8, 0, 8, 6, 5, 1, 3, 2, 8, 2, 3, 0, 6, 6, 4, 
 7, 0, 9, 3, 8, 4, 4, 6, 0, 9, 5, 5, 0, 5, 8, 
 2, 2, 3, 1, 7, 2, 5, 3, 5, 9, 4, 0, 8, 1, 2, 
 8, 4, 8, 1, 1, 1, 7, 4, 5, 0, 2, 8, 4, 1, 0, 
 2, 7, 0, 1, 9, 3, 8, 5, 2, 1, 1, 0, 5, 5, 5, 
 9, 6, 4, 4, 6, 2, 2, 9, 4, 8, 9, 5, 4, 9, 3, 
 0, 3, 8, 1, 9, 6, 4, 4, 2, 8, 8, 1, 0, 9, 7, 
 5, 6, 6, 5, 9, 3, 3, 4, 4, 6, 1, 2, 8, 4, 7, 
 5, 6, 4, 8, 2, 3, 3, 7, 8, 6, 7, 8, 3, 1, 6, 
 5, 2, 7, 1, 2, 0, 1, 9, 0, 9, 1, 4, 5, 6, 4, 
 8, 5, 6, 6, 9, 2, 3, 4, 6, 0, 3, 4, 8, 6, 1, 
 0, 4, 5, 4, 3, 2, 6, 6, 4, 8, 2, 1, 3, 3, 9,
 3, 6, 0, 7, 2, 6, 0, 2, 4, 9, 1, 4, 1, 2, 7,
 3, 7, 2, 4, 5, 8, 7, 0, 0, 6, 6, 0, 6, 3, 1,
 5, 5, 8, 8, 1, 7, 4, 8, 8, 1, 5, 2, 0, 9, 2,
 0, 9, 6, 2, 8, 2, 9, 2, 5, 4, 0, 9, 1, 7, 1,
 5, 3, 6, 4, 3, 6, 7, 8, 9, 2, 5, 9, 0, 3, 6,
 0, 0, 1, 1, 3, 3, 0, 5, 3, 0, 5, 4, 8, 8, 2,
 0, 4, 6, 6, 5, 2, 1, 3, 8, 4, 1, 4, 6, 9, 5,
 1, 9, 4, 1, 5, 1, 1, 6, 0, 9, 4, 3, 3, 0, 5,
 7, 2, 7, 0, 3, 6, 5, 7, 5, 9, 5, 9, 1, 9, 5,
 3, 0, 9, 2, 1, 8, 6, 1, 1, 7, 3, 8, 1, 9, 3,
 2, 6, 1, 1, 7, 9, 3, 1, 0, 5, 1, 1, 8, 5, 4,
 8, 0, 7, 4, 4, 6, 2, 3, 7, 9, 9, 6, 2, 7, 4,
 9, 5, 6, 7, 3, 5, 1, 8, 8, 5, 7, 5, 2, 7, 2,
 4, 8, 9, 1, 2, 2, 7, 9, 3, 8, 1, 8, 3, 0, 1,
 1, 9, 4, 9, 1, 2, 9, 8, 3, 3, 6, 7, 3, 3, 6,
 2, 4, 4, 0, 6, 5, 6, 6, 4, 3, 0, 8, 6, 0, 2,
 1, 3, 9, 4, 9, 4, 6, 3, 9, 5, 2, 2, 4, 7, 3,
 7, 1, 9, 0, 7, 0, 2, 1, 7, 9, 8, 6, 0, 9, 4,
 3, 7, 0, 2, 7, 7, 0, 5, 3, 9, 2, 1, 7, 1, 7,
 6, 2, 9, 3, 1, 7, 6, 7, 5, 2, 3, 8, 4, 6, 7,
 4, 8, 1, 8, 4, 6, 7, 6, 6, 9, 4, 0, 5, 1, 3,
 2, 0, 0, 0, 5, 6, 8, 1, 2, 7, 1, 4, 5, 2, 6,
 3, 5, 6, 0, 8, 2, 7, 7, 8, 5, 7, 7, 1, 3, 4,
 2, 7, 5, 7, 7, 8, 9, 6, 0, 9, 1, 7, 3, 6, 3,
 7, 1, 7, 8, 7, 2, 1, 4, 6, 8, 4, 4, 0, 9, 0,
 1, 2, 2, 4, 9, 5, 3, 4, 3, 0, 1, 4, 6, 5, 4,
 9, 5, 8, 5, 3, 7, 1, 0, 5, 0, 7, 9, 2, 2, 7,
 9, 6, 8, 9, 2, 5, 8, 9, 2, 3, 5, 4, 2, 0, 1,
 9, 9, 5, 6, 1, 1, 2, 1, 2, 9, 0, 2, 1, 9, 6,
 0, 8, 6, 4, 0, 3, 4, 4, 1, 8, 1, 5, 9, 8, 1,
 3, 6, 2, 9, 7, 7, 4, 7, 7, 1, 3, 0, 9, 9, 6,
 0, 5, 1, 8, 7, 0, 7, 2, 1, 1, 3, 4, 9, 9, 9,
 9, 9, 9, 8, 3, 7, 2, 9, 7, 8, 0, 4, 9, 9, 5,
 1, 0, 5, 9, 7, 3, 1, 7, 3, 2, 8, 1, 6, 0, 9,
 6, 3, 1, 8, 5, 9, 5, 0, 2, 4, 4, 5, 9, 4, 5,
 5, 3, 4, 6, 9, 0, 8, 3, 0, 2, 6, 4, 2, 5, 2,
 2, 3, 0, 8, 2, 5, 3, 3, 4, 4, 6, 8, 5, 0, 3,
 5, 2, 6, 1, 9, 3, 1, 1, 8, 8, 1, 7, 1, 0, 1,
 0, 0, 0, 3, 1, 3, 7, 8, 3, 8, 7, 5, 2, 8, 8,
 6, 5, 8, 7, 5, 3, 3, 2, 0, 8, 3, 8, 1, 4, 2,
 0, 6, 1, 7, 1, 7, 7, 6, 6, 9, 1, 4, 7, 3, 0,
 3, 5, 9, 8, 2, 5, 3, 4, 9, 0, 4, 2, 8, 7, 5,
 5, 4, 6, 8, 7, 3, 1, 1, 5, 9, 5, 6, 2, 8, 6,
 3, 8, 8, 2, 3, 5, 3, 7, 8, 7, 5, 9, 3, 7, 5,
 1, 9, 5, 7, 7, 8, 1, 8, 5, 7, 7, 8, 0, 5, 3,
 2, 1, 7, 1, 2, 2, 6, 8, 0, 6, 6, 1, 3, 0, 0,
 1, 9, 2, 7, 8, 7, 6, 6, 1, 1, 1, 9, 5, 9, 0,
 9, 2, 1, 6, 4, 2, 0, 1, 9, 8]
Al momento de estar escribiendo esta entrada, el mayor número de dígitos que se han calculado de π son 12.1 billones (1.21 × 1013) por Alexander Yee y Shigeru Kondo el 28 de diciembre del 2013.  Aplicando el algoritmo de Chudnovsky tardaron 94 días en total usando un equipo de cómputo con dos procesadores Intel Xeon E5-2690 a 2.9 GHz con 16 núcleos en total, 128 GB de memoria RAM y más de 60 TB de espacio en varios discos duros. Eso sí es como para pensar en π.

¡Feliz día de Pi!


Notas

§ El Día de Pi fue fundado por Larry Shaw y se celebró por primera vez en 1988 en el Exploratorium de San Francisco, California.
Referencia: http://en.wikipedia.org/wiki/Pi_Day.

En México pay es la castellanización de la palabra inglesa pie. En España se le llama tarta, mientras que en otros países de América Latina se le conoce como pastel. A fin de cuentas la broma consiste en que en inglés pie y π se pronuncian igual.

Realmente la serie Gregory–Leibniz fue descubierta tres siglos antes por el matemático indio Madhava de Sangamagrama. Por eso también se le conoce a esta fórmula como la serie de Madhava-Leibniz.

2 de julio de 2014

¿Dónde quedó el switch-case?

Hace tiempo escribí sobre la manera de darle la vuelta a la ausencia de los ciclos do-while en Python. Dicha entrada se convirtió rápidamente en una de las más visitadas del blog de EduPython. Debido a ello, en esta ocasión comentaré sobre la otra instrucción que mucha gente echa de menos en Python: la condicional switch-case de la familia de lenguajes basados en C (C++, C#, Java, JavaScript, etc.). Otros lenguajes como Pascal, Ada, Perl, Ruby y diversos dialectos de Lisp cuentan también con alguna instrucción parecida. Sin embargo Python carece de esta instrucción, que de forma más general se le puede llamar “ramificación condicional con múltiples caminos”.

El switch-case es una ramificación condicional
con múltiples caminos.

Una instrucción switch-case permite seleccionar, por medio de una expresión, el siguiente bloque de instrucciones a ejecutar de entre varios posibles. Veamos un ejemplo del switch-case en JavaScript:
// Código de JavaScript
function imprimeRangoCarta(n) {
    switch (n) {
        case 1:
            console.log('As');
            break;
        case 2: case 3: case 4: case 5:
        case 6: case 7: case 8: case 9:
        case 10:
            console.log(n);
            break;
        case 11:
            console.log('Jota');
            break;
        case 12:
            console.log('Reina');
            break;
        case 13:
            console.log('Rey');
            break;
        default:
            console.log('Inválido');
            break
    }
}
La intención de esta función es imprimir en la consola el rango de una carta de una baraja a partir de su valor numérico n, el cual se recibe como parámetro. Si n vale 1, 11, 12 o 13 la función imprime “As”, “Jota”, “Reina” o “Rey”, respectivamente; imprime el valor de n si dicha variable tiene un valor entre 2 y 10. Por último, imprime “Inválido” si n tiene algún valor diferente a los ya mencionados.

Las instrucciones break se requieren para concluir el switch. Si se llega a omitir un break, el programa continúa ejecutando las instrucciones asociadas al case (o default) que continúa inmediatamente; normalmente esto no es lo que se quiere.

La forma más directa de traducir nuestro código de JavaScript a Python es usando una secuencia de instrucciones if-elif-else:
# Código de Python 3
def imprime_rango_carta(n):
    if n == 1:
        print('As')
    elif 2 <= n <= 10:
        print(n)
    elif n == 11:
        print('Jota')
    elif n == 12:
        print('Reina')
    elif n == 13:
        print('Rey')
    else:
        print('Inválido')
La instrucción elif es una contracción de las instrucciones else e if, con la ventaja de que no es necesario añadir un nivel de indentación al momento de utilizarla. Si no existiera la instrucción elif, el código de arriba se tendría que escribir de una forma un tanto menos conveniente:
# Código de Python 3
def imprime_rango_carta(n):
    if n == 1:
        print('As')
    else:
        if 2 <= n <= 10:
            print(n)
        else:
            if n == 11:
                print('Jota')
            else:
                if n == 12:
                    print('Reina')
                else:
                    if n == 13:
                        print('Rey')
                    else:
                        print('Inválido')
Vale la pena también notar que para determinar si n está entre 2 y 10 usamos la expresión:
2 <= n <= 10
En otros lenguajes de programación tendríamos que escribir una expresión equivalente a la siguiente:
2 <= n and n <= 10
Para las situaciones más comunes, se considera que el switch-case tiene al menos dos ventajas sobre una serie equivalente de ifs anidados:
  1. Su sintaxis favorece la legibilidad y rapidez de escritura gracias a que el código generalmente es más breve y compacto.
  2. Corre más rápido debido a que usualmente, de manera interna, el ambiente de ejecución utiliza una tabla de acceso rápido para seleccionar el código a ejecutar, en lugar de ir haciendo una por una cada una de las comparaciones que requieren una serie de ifs anidados.
No hay nada que podamos hacer en Python respecto al punto 1, ya que no hay soporte sintáctico para la instrucción switch-case en el lenguaje. Sin embargo sí podemos aprovechar el punto 2, utilizando una tabla en Python para evitar múltiples comparaciones. La implementación de dicha tabla se puede hacer mediante una lista o un diccionario. En nuestro programa usaremos un diccionario. En la entrada titulada Código morse introduje el uso de diccionarios. Dado que los diccionarios en Python están implementados usando tablas hash, las búsquedas y accesos se ejecutan de manera muy veloz.

Ahora bien, para la discusión que sigue es importante distinguir entre “invocar una función” y “hacer referencia al objeto que representa una función”. Esto queda más claro con un ejemplo. Sea fun una función sin parámetros que devuelve siempre el mismo valor:
def fun():
    return 42
Podemos usar fun básicamente de dos maneras:
a = fun
b = fun()
Hay que notar la presencia o ausencia de los paréntesis () después del identificador fun. En el código anterior, a contiene una referencia al objeto que representa la función fun, mientras que b contiene el resultado de invocar a la función fun. Si imprimimos los valores de a y b con estas instrucciones:
print('a =', a)
print('b =', b)
veremos una salida como la siguiente:
a = <function fun at 0x4815162342>
b = 42
Esta salida extraña de a quiere decir que es un objeto función. De manera más precisa, a es una referencia al objeto función llamado fun. Dicho de otra forma, fun y a son alias, pues se refieren al mismo objeto. Dado que podemos decir que a es una función, entonces la podemos invocar usando los paréntesis correspondientes y hacer algo con el resultado:
c = a()
Como es de esperarse, c queda con 42.

Lo que hay que recordar es esto:
  • Si en una expresión viene el nombre de una función seguido de un par de paréntesis (), con o sin argumentos, significa que la función se está invocando. El resultado de esa parte de la expresión es lo que devuelva la función.
  • Si en una expresión viene el nombre de una función sin venir seguido de un par de paréntesis (), significa que se está obteniendo una referencia al objeto función siendo nombrado. El resultado de esa parte de la expresión es el objeto función correspondiente.
Integrando todo lo que hemos discutido, nos queda ahora el siguiente programa:
# Código de Python 3
def imprime_rango_carta(n):

    def caso_as():
        print('As')

    def caso_num():
        print(n)

    def caso_jota():
        print('Jota')

    def caso_reina():
        print('Reina')

    def caso_rey():
        print('Rey')

    def caso_invalido():
        print('Inválido')

    tabla = { 1: caso_as,   2: caso_num,   3: caso_num,
              4: caso_num,  5: caso_num,   6: caso_num,
              7: caso_num,  8: caso_num,   9: caso_num,
             10: caso_num, 11: caso_jota, 12: caso_reina,
             13: caso_rey }

    f = tabla.get(n, caso_invalido)
    f()
Hay que notar varias cosas en el código anterior:
  1. El código de cada “cláusula case” se incorpora dentro de una función local.
  2. La función local caso_num utiliza en su cuerpo el parámetro n de la función en la que está anidada. Esto es totalmente válido, y demuestra que Python soporta cerraduras léxicas (lexical closures). Esto último significa que al crear una función, todas las variables que son visibles en ese punto también lo son dentro del cuerpo de dicha función. 
  3. El objeto tabla se construye usando un diccionario. Las llaves son los valores de cada “cláusula case”, y éstas se asocian a sus correspondientes objetos función.
  4. El método get() de la penúltima línea permite buscar una llave (el primer argumento: n) en el diccionario receptor (tabla) y regresar el valor asociado a dicha llave en caso de encontrarlo; si la llave no existe, regresa un valor por omisión (el segundo argumento: el objeto función caso_invalido).
  5. A la variable f se le asigna el resultado del método get(), el cual en todos los casos es un objeto función.
  6. La última línea invoca la función obtenida en la instrucción anterior.
Esto código ya funciona como es debido, sin embargo si lo revisamos de manera más detenida podemos simplificarlo de manera significativa. Dado que el propósito de la función imprime_rango_carta es imprimir un valor en particular a partir de lo que contenga n, podemos hacer que el diccionario contenga solamente los valores que varían en cada uno de los distintos casos:
# Código de Python 3

__tabla = { 1: 'As', 2: 2, 3: 3, 4: 4, 5: 5, 6: 6,
            7: 7, 8: 8, 9: 9, 10: 10, 11: 'Jota',
            12: 'Reina', 13: 'Rey' }

def imprime_rango_carta(n):
    print(__tabla.get(n, 'Inválido'))
Definimos la variable __tabla afuera de la función para que sea inicializada una vez y no cada vez que ésta sea invocada. Los dos subguiones al inicio de un nombre son una convención para indicar que la variable es privada a este módulo. También hay que notar que solamente usamos una instrucción print() para abarcar todos los casos. Como se puede ver, el código queda más compacto y fácil de modificar que el switch-case original.

Moraleja: la instrucción switch-case es innecesaria en Python si sabemos usar diccionarios de manera correcta.