Lissajous I

Es bien conocido que las representaciones decimales de las potencias de diez comienzan con un dígito '1' y terminan con un dígito '0' (exceptuando el caso trivial de 1⁰ = 1; se supondrán exponentes no nulos en el resto del post). Lo mismo sucederá, cualquiera sea el valor de n, con las representaciones en base n de las potencias de n.

Lo que no es tan claro es el comportamiento de los dígitos en una base dada, por ejemplo 10, de las potencias de un número distinto a la base. Si consideramos el caso de las potencias de 2 expresadas en base 10, podemos ver que terminarán en un dígito par ya que son números pares. Pensando un poco más, podemos ver que nunca terminarán en '0', ya que para ello deberían ser múltiplos de 10 y, por lo tanto, múltiplos de 5. Pero ciertamente quedaría en duda qué otros valores particulares podrán tomar los últimos dígitos...

Los que memorizamos potencias de dos como parte de nuestra actividad académica/profesional :-) podemos ver que:

2¹ = 2
2² = 4
2⁴ = 16
2³ = 8

y que, por lo tanto, todos los otros dígitos pares aparecen al final de las potencias de dos. Pero este es un proceso de enumeración exhaustiva, claramente insatisfactorio a la hora de obtener entendimiento de un proceso.

La primera incógnita que quedará planteada para el próximo post es determinar "que regla" siguen estos dígitos y, de mayor interés, qué regla siguen los dígitos más significativos; por ejemplo, puede una potencia de dos empezar con 9? El otro interrogante será ver que conexión tiene esto con las figuras de Lissajous...

Solución y otras cosas

A continuación se muestra la solución al problema planteado en el último post. Para verla hacer click aquí.


El programa eventualmente se detiene, pero después de unas 2²⁰⁴⁰ iteraciones del loop externo. Por lo tanto, para fines prácticos, puede considerarse como un loop infinito... Es claro que devuelve cero, ya que tuvo que salir del loop externo para poder terminar. A continuación se describe con algo más de detalle el funcionamiento del programa.

Es claro que el único punto confuso es la acción de la línea "while (!++*p++);", el resto del programa es bastante normal. Para interpretarla, puede verse teniendo en cuenta la prioridad de los operadores que es equivalente a realizar "while (!(++(*(p++))));". Esto corresponde a:

1. Incrementar p devolviendo su valor original, que podemos llamar p'.
2. Incrementar el valor apuntado por p'.
3. Si el valor apuntado por p' es ahora 0, volver al paso 1. En caso contrario, salir.

Como buffer se inicializa con ceros al ser variable global y p apunta inicialmente a buffer[0], tenemos que en la primera iteración del loop externo:

• (1) p <-- &buffer[1]
• (2) buffer[0] <-- 1
• (3) Sale porque buffer[0] != 0

En la segunda iteración tendremos:

• (1) p <-- &buffer[1]
• (2) buffer[0] <-- 2
• (3) Sale porque buffer[0] != 0

Esto continuará hasta que buffer[0] sea 255. En ese momento sucederá lo siguiente:

• (1) p <-- &buffer[1]
• (2) buffer[0] <-- 0
• (3) Vuelve a "1" porque buffer[0] == 0
• (1') p <-- &buffer[2]
• (2') buffer[1] <-- 1
• (3') Sale porque buffer[1] != 0

Si se observa el comportamiento en detalle, puede verse que tenemos un contador en el que cada posición de buffer actúa como un dígito base 256. Para salir es necesario que al finalizar el loop interno p sea igual a q. Pero esto implicaría que se acaba de incrementar a buffer[255], lo que no sucederá hasta que hayan ocurrido 256²⁵⁵ == 2^8*255 == 2²⁰⁴⁰ iteraciones del loop externo.


En otro área completamente diferente, encontraron en México una caverna llena de extraordinarios cristales de yeso hidratado (sulfato de calcio):


En el sitio de National Geographic pueden observarse otras fotos espectaculares y más detalles sobre el descubrimiento (por ejemplo, el porqué de los trajes naranjas :-). (Via Robin Hanson.)

C Puzzle

El problema es determinar si el siguiente programa:

• termina de ejecutarse;
• en caso de hacerlo, cuanto demora y qué devuelve al sistema operativo.
  

static unsigned char buffer[256];

int main(void)
{
  unsigned char *p, *q;
  q = (p = buffer) + sizeof(buffer);
  while (q - p)
  {     
      p = buffer;
      while (!++*p++);
  }
  return p - q;
}

Las respuestas a estas preguntas en unos días... :-D

Detectando dígitos en un 8051

Uno de los problemas que aparecieron en un examen de Labo de Micros reciente (que le tomaron a mi hermano) indicaba hacer una "función" en assembly 8051 tal que detectara si el valor que se le pasaba era un dígito. Más especificamente, debían volver con C en 1 si y solo si el valor no era un dígito.

Yo siempre había pensado el problema de la forma obvia, algo así como:

no_es_digito:
clr C
subb A, #'0'
jc no_es_dig_end
subb A, #10
cpl C
no_es_dig_end:
ret

Pero a mi hermano le dijeron que podía hacerse con cinco instrucciones, lo que me hizo pensar en más detalle... hasta que vi que la resta no era la única solución. Eso me llevó al siguiente código:

no_es_digito:
add A, #(256 - '0')
add A, #(256 - 10)
ret

El primer add lleva, en forma modular, el valor desde el rango ASCII '0' ... '9' al rango 0x00 ... 0x09. En base a eso es simple ver que el segundo add dará como resultado C = 1 solo si el valor es 0x0a o mayor. Por lo tanto, solo dará C = 1 si el caracter pasado originalmente no cae en el rango '0' ... '9'.

No creo que pueda hacerse con dos instrucciones, ya que las instrucciones que alteran C en base al contenido del acumulador son aritméticas (según recuerdo!) y solo pueden "detectar" valores mayores o menores a uno especificado... pero el desafío queda abierto :-D

Sistemas de ecuaciones booleanos

Hace unos días un compañero de la facultad (hola Guille!) me comentaba sobre una clase de problemas que suelen aparecer en los parciales de Matemática Discreta (al menos en la FIUBA). Recordaba que estos problemas consistían en encontrar una función booleana que de como resultado 1 si y solo si los valores de sus parámetros satisfacen un sistema de ecuaciones booleano y eso me hizo recordar un "método" que había desarrollado cuando la había cursado (aunque creo que no tuve ocasión de usarlo en el parcial).

Nota: Las "barras" que se suelen utilizarse para indicar complemento no se expresan fácilmente en HTML. Esto puede resolverse utilizando el operador "¬". Las otras dos operaciones pueden expresarse por "∧" (AND) y "∨" (OR). Por simplicidad, podemos asumir que "∧" tiene prioridad sobre "∨".

Para empezar podemos demostrar que dada una variable y satisfaciendo x ∧ y = 0 y x ∨ y = 1 sabemos que y = ¬x (o sea la unicidad del complemento). Una forma es viendo que:

(1) x ∨ y = 1 (Hipótesis)
(2) ¬x ∧ (x ∨ y) = ¬x ∧ 1 (Aplico la misma operación a ambos miembros)
(3) ¬x ∧ (x ∨ y) = ¬x (Definición de 1)
(4) ¬x ∧ x ∨ ¬x ∧ y = ¬x (Propiedad distributiva)
(5) 0 ∨ ¬x ∧ y = ¬x (Definición de complemento)
(6) x ∧ y = 0 (Hipótesis)
(7) x ∧ y ∨ ¬x ∧ y = ¬x (Reemplazando 6 en 5)
(8) (x ∨ ¬x) ∧ y = ¬x (Propiedad distributiva)
(9) 1 ∧ y = ¬x (Definición de complemento)
(10) y = ¬x (Definición de 1)

Otro "lema" que es útil indica que dados x e y tales que x ∧ y = 1, puede decirse que x = 1 y que y = 1. Una forma de demostrarlo es la siguiente:

(1) x ∧ y = 1 (Hipótesis)
(2) x ∧ y ∨ x ∧ ¬y = 1 ∨ x ∧ ¬y (Aplico la misma operación a ambos miembros)
(3) x ∧ y ∨ x ∧ ¬y = 1 (Propiedad absorbente)
(4) x ∧ (y ∨ ¬y) = 1 (Propiedad distributiva)
(5) x ∧ 1 = 1 (Definición de complemento)
(6) x = 1 (Definición de 1)

Por simetría podemos ver que y = 1 y podemos evitar demostrar la propiedad absorbente para poder llegar alguna vez al tema a tratar :-)

Ahora, podemos ver a todo sistema de ecuaciones como una serie de igualdades entre funciones que requieren satisfacerse. Por ejemplo:

f1(x, y, ...) = g1(x, y, ...)
f2(x, y, ...) = g2(x, y, ...)
f3(x, y, ...) = g3(x, y, ...)
...

Ahora, como sabemos que x ∧ y = 0 y x ∨ y = 1 implican x = ¬y y que x ∧ y = 1 implica que tanto x como y son iguales a 1, podemos expresar una igualdad arbitraria a = b como ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 aplicando lo siguiente:

Ida

(1) a = b (Hipótesis)
(2) a = ¬(¬b) (Propiedad involutiva del complemento)
(3) a ∧ ¬b = 0 (Definición de complemento)
(4) a ∨ ¬b = 1 (Definición de complemento)
(5) ¬(a ∧ ¬b) = ¬0 (Aplico la misma operación a ambos miembros)
(6) ¬(a ∧ ¬b) = 1 (Aplico ¬0 = 1)
(7) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Aplico ∧ miembro a miembro sobre 4 y 6)

Vuelta

(1) ¬(a ∧ ¬b) ∧ (a ∨ ¬b) = 1 (Hipótesis)
(2) ¬(a ∧ ¬b) = 1 (Propiedad demostrada anteriormente)
(3) a ∨ ¬b = 1 (De 1 por propiedad demostrada anteriormente)
(4) ¬¬(a ∧ ¬b) = ¬1 (Aplico la misma operación a ambos miembros)
(5) a ∧ ¬b = ¬1 (Propiedad involutiva del complemento)
(6) a ∧ ¬b = 0 (Aplico ¬1 = 0)
(7) a = ¬¬b (Aplico otra propiedad demostrada anteriormente sobre 3 y 6)
(8) a = b (Propiedad involutiva del complemento)

Si omitimos que no demostramos ni la propiedad involutiva del complemento ni que ¬0 = 1 (las demostraciones son simples, quedan como ejercicio para el lector :-), sabemos como transformar una ecuación arbitraria en una igualada a 1. Ahora podemos aplicar que x ∧ y = 1 implica que x = y = 1 para expresar el sistema de ecuaciones anterior como:

¬(f1(x, y, z, ...) ∧ ¬g1(x, y, z, ...)) ∧
(f1(x, y, z, ...) ∨ ¬g1(x, y, z, ...)) ∧
¬(f2(x, y, z, ...) ∧ ¬g2(x, y, z, ...)) ∧
(f2(x, y, z, ...) ∨ ¬g2(x, y, z, ...)) ∧
¬(f3(x, y, z, ...) ∧ ¬g3(x, y, z, ...)) ∧
(f3(x, y, z, ...) ∨ ¬g3(x, y, z, ...)) ∧
... = 1

Esto cumple en forma automática el objetivo del problema aunque puede ser algo tedioso...

Me pasó otra vez...

...Google insiste en confundirme con un bot. No se que es lo que confundirá a sus algoritmos de detección, aunque sospecho de mi tendencia a abrir múltiples pestañas cuando veo una lista de links :-)


Por si fuera poco, el CAPTCHA también me clasificó como "no humano", ya que realmente me resultaba difícil ver que es lo que decía. Tengo la sospecha de que navegar por Internet en el futuro va a ser realmente interesante...

spice3f5 para Visual C++

Acabo de agregar a la página de mi proyecto de Tesis una versión de spice3f5 compilable con Microsoft Visual C++ 2008. Esto permite realizar fácilmente análisis de una netlist cualquiera (aunque no incluye manual de uso :-)