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