La subasta del dólar

Desde el punto de vista formal se define a un juego como un conjunto de jugadores, cada uno de los cuales dispone de una serie de posibles acciones a tomar, y una forma de determinar cuanta recompensa recibe cada uno de los jugadores en base a las acciones que eligen todos ellos. Este formalismo no solo puede modelizar juegos como el ta-te-ti o el ajedrez, sino que puede aplicarse al análisis de situaciones hipotéticas tales como el conocido "dilema del prisionero".

Uno de los juegos que fueron definidos de este modo es el conocido como la "subasta del dolar" y fue creado por Martin Shubik en 1971 para dar un ejemplo simple del conocido proceso de escalada en los conflictos. El juego es muy simple: se subasta un dólar entre dos jugadores pero ambos deben pagar sus ofertas, lo que altera radicalmente el desarrollo de la subasta.

Supongamos que la oferta mínima y el incremento mínimo de las ofertas se establece en 0.05. Entonces, a primera vista, parece un excelente retorno ofrecer 0.05 a cambio del dólar; pero también lo será para el otro jugador ofrecer 0.10 y así el proceso puede seguir hasta que las ofertas hasta 0.95. Pero la fase más interesante ocurre a partir de este momento...

Supongamos que el jugador "A" hizo la última oferta de 0.95 después de que "B" hubiera ofrecido 0.90. Entonces "B" tiene dos opciones: puede aceptar perder 0.90 o puede ofrecer 1.00 y "salir hecho". El mismo análisis puede hacerlo "A" en caso de realizar "B" su oferta de 1.00: puede perder 0.95 u ofrecer 1.05 y perder 0.05... Esto lleva a una competencia en la que las pérdidas son potencialmente ilimitadas.

Uno podría pensar que este juego carece de relevancia práctica en si y que solo interesa como modelo de otras competencias que suceden en la realidad, pero eso sería incorrecto. Pueden verse más detalles acerca de Swoopo y su modelo de negocios en múltiples sitios. Quién dice que la teoría de juegos no es redituable? :-D

Lattice Boltzmann (con SDL!)

Estoy trabajando en un nuevo proyecto personal: realizar una simulación de fluidos mediante el método conocido como Lattice Boltzmann y usando SDL para los gráficos. Si bien el objetivo último es lograr una buena performance, actualmente solo está funcionando la implementación "lenta" que voy a usar con propósitos comparativos (a unos 8 FPS con simple precisión en un Core Duo @ 2.16 GHz).

Hoy fue una experiencia bastante frustrante: empleé horas buscando un error en mi implementación de Lattice Boltzmann para descubrir finalmente que el problema estaba en las condiciones iniciales que estaba empleando... Más específicamente, no estaba cumpliendo con la condición CFL :-S

En las próximas semanas probablemente agregue algo más acerca de Lattice Boltzmann y, con suerte, tenga nuevos avances del proyecto.

Lissajous II

(Continúa a este post.)

Es bien conocido que puede escribirse a todo número real como el producto de un número real de módulo menor que 1 y una potencia entera de un número mayor que 1. Por ejemplo, tomando base 10, tenemos:

234.435 = 0.234435 ∙ 10³

3.14159... = 0.314159... ∙ 10¹

1024 = 0.1024 ∙ 10⁴

Claramente podemos observar que el primer dígito del número aparece como el primer decimal en esta forma de representación. Utilizando algunas funciones tales como

⌊x⌋ = el mayor entero menor o igual que x,

⌈x⌉ = el menor entero mayor o igual que x y

{x} = la parte fraccionaria de x, igual a x - ⌊x⌋,

podemos expresar esto como

pd(x) = ⌊10^{{log₁₀ x}}⌋,

donde pd(x) es la función que devuelve el primer dígito del número (esta expresión está limitada a numeros positivos, pero son los que interesan en nuestro caso). Esto nos indica que el primer dígito será:

1 si 0 ≤ {log₁₀ x} <  log₁₀ 2
2 si  log₁₀ 2 ≤ {log₁₀ x} <  log₁₀ 3
...
9 si  log₁₀ 9 ≤ {log₁₀ x} <  1 

Por lo tanto, la determinación de la primera cifra de la expansión decimal de un número se reduce a encontrar en cual de estos intervalos cae la parte fraccionarial de su logaritmo en base 10. Si aplicamos esto a las potencias de dos tenemos que

 {log₁₀ 2ⁿ} = {n log₁₀ 2}.

Por consiguiente, la determinación de los posibles valores de los primeros dígitos de las potencias de dos se reduce a encontrar los sectores del intervalo [0, 1) donde caen las partes fraccionarias de los múltiplos de log₁₀ 2. Encontrar cuáles son estos sectores y cuál es la conexión de todo esto con las figuras de Lissajous quedará para el próximo post por razones de tiempo :-)

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