Yet another FizzBuzz without conditional branches

A branch-free FizzBuzz in assembly was posted in Hacker News. In this post I will try to do another implementation, for a Linux environment, without using function pointers.

C implementation

We can start by writing a C implementation:

#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int main( void )
{
	int i = 1;
	const char fizz[] = "Fizz";
	const char buzz[] = "Buzz";
	const char nl[] = "\n";
	char digits[ 2 ];
	while( 1 )
	{
		char *p = digits;
		*p = i / 10 + '0';
		p += ( i >= 10 );
		*p = i % 10 + '0';
		p++;
		syscall( SYS_exit * ( i > 100 ) + SYS_write * ( i <= 100 ), i <= 100,
		         digits, ( i % 3 != 0 && i % 5 != 0 ) * ( p - digits ) );
		syscall( SYS_write, 1, fizz, ( i % 3 == 0 ) * ( sizeof( fizz ) - 1 )  );
		syscall( SYS_write, 1, buzz, ( i % 5 == 0 ) * ( sizeof( buzz ) - 1 )  );
		syscall( SYS_write, 1, nl, sizeof( nl ) - 1 );
		i++;
	}
	/* NOT REACHED */
	return 0;
}

(Check the output in Ideone.)

The basic idea is to calculate the syscall number arithmetically and using the fact that a zero-length write is essentially a no-op.

In at least one associated assembly listing (obtained with Godbolt’s Interactive compiler) there are no conditional branches:

main:                                   # @main
	pushq	%rbp
	movq	%rsp, %rbp
	pushq	%r15
	pushq	%r14
	pushq	%r13
	pushq	%r12
	pushq	%rbx
	pushq	%rax
	movl	$1, %r15d
	leaq	-42(%rbp), %r14
.LBB0_1:                                # %._crit_edge
	cmpl	$100, %r15d
	movl	$0, %edi
	movl	$60, %eax
	cmovgl	%eax, %edi
	movslq	%r15d, %r15
	cmpl	$101, %r15d
	setl	%al
	movzbl	%al, %esi
	orl	%esi, %edi
	imulq	$1431655766, %r15, %rcx # imm = 0x55555556
	imulq	$1717986919, %r15, %rax # imm = 0x66666667
	movq	%rax, %r10
	shrq	$63, %r10
	shrq	$32, %rax
	movl	%eax, %edx
	sarl	$2, %edx
	leal	(%rdx,%r10), %ebx
	movq	%rcx, %r11
	shrq	$63, %r11
	cmpl	$9, %r15d
	setg	%r8b
	imull	$10, %ebx, %ebx
	negl	%ebx
	leal	48(%rdx,%r10), %edx
	movb	%dl, -42(%rbp)
	leal	48(%r15,%rbx), %r9d
	shrq	$32, %rcx
	addl	%r11d, %ecx
	leal	(%rcx,%rcx,2), %ecx
	movl	%r15d, %edx
	subl	%ecx, %edx
	sete	%r12b
	movzbl	%r8b, %ecx
	movb	%r9b, -42(%rbp,%rcx)
	setne	%bl
	sarl	%eax
	addl	%r10d, %eax
	leal	(%rax,%rax,4), %eax
	movl	%r15d, %edx
	subl	%eax, %edx
	sete	%r13b
	setne	%al
	andb	%bl, %al
	movzbl	%al, %eax
	shlq	$63, %rax
	sarq	$63, %rax
	incq	%rcx
	andq	%rax, %rcx
	movq	%r14, %rdx
	xorb	%al, %al
	callq	syscall
	movzbl	%r12b, %ecx
	shlq	$2, %rcx
	movl	$1, %edi
	movl	$1, %esi
	movl	main::fizz, %edx
	xorb	%al, %al
	callq	syscall
	movzbl	%r13b, %ecx
	shlq	$2, %rcx
	movl	$1, %edi
	movl	$1, %esi
	movl	main::buzz, %edx
	xorb	%al, %al
	callq	syscall
	movl	$1, %edi
	movl	$1, %esi
	movl	main::nl, %edx
	movl	$1, %ecx
	xorb	%al, %al
	callq	syscall
	incl	%r15d
	jmp	.LBB0_1

main::fizz:
	.asciz	 "Fizz"

main::buzz:
	.asciz	 "Buzz"

main::nl:
	.asciz	 "\n"

But there still are comparisons and conditional sets and moves.

x86-64 assembly implementation

We can write a cleaner implementation if we do it directly in assembly:

;; FizzBuzz in x86-64 ASM without conditional branches

section .data
fizz: db 'Fizz'
buzz: db 'Buzz'
nl:   db 10

section .bss
digits: resb 2

section .text

global _start
_start:
	mov rbx, 1

main_loop:

	; if ( rbx > 100 )
	;   exit( 0 )
	; else
	;   write( 1, digits, 0 )
	mov rax, rbx
	neg rax
	add rax, 100
	sar rax, 63
	mov rdi, rax
	and rax, 59
	inc rax
	neg rdi
	mov rsi, digits
	xor rdx, rdx
	syscall

	; r8 <- rbx % 3 != 0 ? -1 : 0
	; r9 <- rbx % 5 != 0 ? -1 : 0
	mov rax, rbx
	mov rcx, 3
	div rcx
	mov r8, rdx
	neg r8
	sar r8, 63
	mov rax, rbx
	mov rcx, 5
	xor rdx, rdx
	div rcx
	mov r9, rdx
	neg r9
	sar r9, 63

	; rcx <- digits
	; *rcx = rbx / 10 + '0'
	; rcx += ( rbx >= 10 )
	; *rcx = rbx % 10 + '0'
	; rcx++
	mov rcx, digits
	mov rax, rbx
	xor rdx, rdx
	mov rdi, 10
	div rdi
	mov rsi, rax
	add rax, '0'
	mov [rcx], rax
	neg rsi
	sar rsi, 63
	neg rsi
	add rcx, rsi
	add rdx, '0'
	mov [rcx], rdx
	inc rcx

	; write( 1, digits, ( rbx % 3 != 0 && rbx % 5 != 0 ) ? rcx - digits : 0 )
	mov rax, 1
	mov rdi, 1
	mov rsi, digits
	mov rdx, rcx
	sub rdx, digits
	and rdx, r8
	and rdx, r9
	syscall

	; write( 1, fizz, rbx % 3 == 0 ? 4 : 0 )
	mov rax, 1
	mov rdi, 1
	mov rsi, fizz
	mov rdx, r8
	not rdx
	and rdx, 4
	syscall

	; write( 1, buzz, rbx % 5 == 0 ? 4 : 0 )
	mov rax, 1
	mov rdi, 1
	mov rsi, buzz
	mov rdx, r9
	not rdx
	and rdx, 4
	syscall

	; write( 1, nl, 1 )
	mov rax, 1
	mov rdi, 1
	mov rsi, nl
	mov rdx, 1
	syscall	

	inc rbx

	jmp main_loop

If the source file is named fizzbuzz.s, it can be compiled with the following command line:

nasm -f elf64 -o fizzbuzz.o fizzbuzz.s; ld -o fizzbuzz fizzbuzz.o
Advertisements

Espirales sobre Noruega

Hace una semana me mostraron una imagen tan espectacular que inmediatamente sospeché que era falsa:

Espiral observada sobre Noruega.

Pero la explicación real resulta mucho más interesante:

Nota: ahora soy un nuevo miembro del extraño movimiento obsesionado en expresar algo con sentido usando solo 140 caracteres 😀

Los orígenes del dialecto judicial y cosas varias

Una interesante perspectiva “evolutiva” sobre el origen de la complejidad del dialecto utilizado (principalmente) por los abogados:

Why is legal language so hard to understand?

(a) A lawyer always tries to use clauses that
have already been interpreted by the courts
[as you noted].

(b) A court interprets a clause only when it is
brought to its attention through litigation.

(c) Litigation over the meaning of a clause
occurs only when there is some disagreement
over the meaning of a clause

(d) Disagreement over the meaning of a clause
is most likely to occur when the clause is
ambiguous or hard to understand.

Therefore, the system produces a kind of Darwinian
pressure: the legal language most likely to survive
is that which on its face is most ambiguous or
difficult to understand.

A continuación, debido a la falta de material adicional completo con la clásica lista de links:

La caída de las lámparas… resuelta

En un comentario del post anterior, Kardo mostraba una solución al problema en 19 intentos:

… Siguiendo este pensamiento, la idea es probar en los pisos múltiplos de N y, en el momento que la lámpara se rompe, probar en los anteriores N-1 pisos para buscar el piso mínimo. De esta forma, si buscamos el mínimo de la función f(100/N+N-1) con 1<N<100, encontramos que ese valor es 19.

Esa es la mejor solución “inteligible” al problema entre las que vi, pero no llega a ser óptima.

El algoritmo

Para buscar la solución óptima, definamos dos funciones: \mathrm{Cost}(n, l) y \mathrm{FixedTryCost}(t, n, l), donde n es la cantidad de pisos que podrían ser el piso mínimo, l es la cantidad de lámparas disponibles y t es un piso determinado desde donde la próxima lámpara será arrojada. La primera función \mathrm{Cost} nos indica la cantidad máxima de lanzamientos de lámparas requeridos según la estrategia óptima, mientras que \mathrm{FixedTryCost} nos indica esa misma cantidad con la restricción adicional del piso desde donde se arrojará la próxima lámpara.

Si hay un candidato solo restante no hace falta seguir realizando lanzamientos, por lo que

\mathrm{Cost}(1, l) = 0.

Por otro lado, si solo nos queda una lámpara no podemos arriesgarnos a que se rompa quedando pisos sin explorar y tendremos que ir probando piso por piso. Por consiguiente tendremos

\mathrm{Cost}(n, 1) = n.

En los otros casos habrá que efectuar un cierto número de lanzamientos para determinar el piso mínimo. No podemos saber a priori cual será el piso óptimo desde donde realizar el siguiente lanzamiento, pero sabemos que será uno de los n que son candidatos. Por lo tanto podemos decir que

\displaystyle \mathrm{Cost}(n, l) = \min_{0 \le t < n} \mathrm{FixedTryCost}(t, n, l),

ya que la estrategia óptima elegirá el piso desde donde lanzar de modo de minimizar el costo.

Pero cuando realizamos un lanzamiento desde el piso t solo podemos tener dos resultados: la lámpara puede romperse o no. En caso de que se rompa examinaremos los t candidatos menores que t, mientras que en caso de que quede intacta haremos lo propio con los n-t-1 candidatos menores que t. Como se realizó un lanzamiento, el costo será

\mathrm{FixedTryCost}(t, n, l) = 1 + \max(\mathrm{Cost}(t, l-1), \mathrm{Cost}(n-t-1, l)).

Con esto tenemos definidas casi por completo a las funciones \mathrm{Cost} y \mathrm{FixedTryCost}, pero quedan pendientes algunas sutilezas que suelen conducir a errores en las definiciones recursivas. En este caso particular, habrá llamadas a \mathrm{Cost}(0, l), que nunca fue definida. Podemos resolver esto haciendo que

\mathrm{Cost}(0, l) = 0,

que es más simple que separar los casos en que es innecesario buscar.

El algoritmo implementado

La implementación, en este caso en Python, es directa a partir de las definiciones recursivas:

def cost(n, l):
    if n in (0, 1):
        return 0
    elif l == 1:
        return n
    else:
        return min(fixed_try_cost(t, n, l) for t in xrange(0, n))

def fixed_try_cost(t, n, l):
    return 1 + max(cost(t, l-1), cost(n - t - 1, l))

Pero si intentamos ejecutar cost(100, 2), observaremos que la ejecución no termina. Esto es debido a que, al igual que en caso del cálculo recursivo de los números de Fibonacci, se recalculan los mismos valores un gran número de veces. Incluso la ejecución de cost(24, 2) demora decenas de segundos.

El algoritmo utilizando programación dinámica

Una forma común para resolver este problema es aplicar la técnica conocida como programación dinámica, consistente esencialmente en almacenar los resultados previamente calculados de modo de no requerir calcularlos nuevamente. Una forma simple de implementar esto en Python es utilizar un diccionario para almacenar el costo correspondiente a cada valor de n y l:

costs = {}

def m_fixed_try_cost(t, n, l):
    return 1 + max(m_cost(t, l-1), m_cost(n - t - 1, l))

def m_cost(n, l):
    if (n, l) in costs:
        return costs[(n, l)]
    if n in (0, 1):
        c = 0
    elif l == 1:
        c = n
    else:
        c = min(m_fixed_try_cost(t, n, l) for t in xrange(0, n))
    costs[(n, l)] = c
    return c

Se observa que las únicas diferencias (aparte del prefijo m_) son la consulta del diccionario al inicio de la función m_cost y el grabado del valor calculado antes de devolverlo.

Si se desea obtener mejor performance, puede utilizarse una tabla normal y llenarla mediante iteración en lugar de recursión. Por ejemplo, la misma función podría implementarse en C del siguiente modo:

#define MAX_N 200
#define MAX_L 200

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int cost(int n, int l)
{
	int costs[MAX_N][MAX_L];
	int i, j, k, c;
	for (i = 0; i <= n; i++)
		costs[i][1] = i;
	for (j = 1; j <= l; j++)
		costs[0][j] = costs[1][j] = 0;
	for (i = 2; i <= n; i++)
	{
		for (j = 2; j <= l; j++)
		{
			c = i;
			for (k = 0; k < i; k++)
			{
				c = MIN(c, 1 + MAX(costs[k][j-1],
								   costs[i-k-1][j]));
			}
			costs[i][j] = c;
		}
	}
	return costs[n][l];
}

De todos modos, todas las versiones se ejecutan en forma esencialmente instantánea, dando como resultado \mathrm{Cost}(100, 2) = 14. Mediante una simple modificación podría devolverse la secuencia requerida en base a lo que sucede con las lámparas al ser arrojadas, obteniendo así un algoritmo para resolver el problema en la práctica.

La caída de las lámparas

We want to figure out how strong our new super-strong light bulbs
are. We know that they will be break when dropped from the top floor
of this building (the 101st). We want to know the exact minimum floor
from which a fall will cause the light bulb to break. You’ll be given
two light bulbs for this task and we want you to do it with the
minimum number of trials.

(Extraído del blog de Louis Brandy.)

Circuitos hamiltonianos

Un circuito hamiltoniano es un recorrido cerrado de un grafo que pasa por todos sus vértices una única vez. Si nos limitamos a grafos en forma de grillas cuadradas, podemos encontrar fácilmente un circuito en las grillas con una cantidad par de vértices siguiendo este esquema:

Circuito hamiltoniano en una grilla de 8x8 vértices.

Circuito hamiltoniano en una grilla de 8x8 vértices.

Puede encontrarse un circuito de esta misma naturaleza en una grilla cuadrada con una cantidad impar de vértices? Cambia esto si se permiten grillas rectangulares?

La respuesta a este problema (y al anterior de sumas) en el próximo post…

Un problema de termos – Solución

[Continuación de Un problema de termos]

Una suposición implícita al resolver esta clase de problemas es que el estado del agua en el interior del termo puede describirse solo mediante su cantidad y su temperatura. Esto implica un estado de cuasi-equilibrio, lo que es razonable si se tiene en cuenta que el termo forma una barrera térmica a la interacción con el medio.

Evaluemos primero entonces el caso en que el tiempo transcurrido tiende a infinito (en lugar de las cinco horas especificadas en el problema). La temperatura del agua en el termo tenderá a la temperatura ambiente en ambos casos, por lo que es lógico que la temperatura final será menor en el segundo caso respecto al primero (en el segundo caso se mezclará un 90% de agua a temperatura ambiente con un 10% de agua a 80 °C, mientras que en el primero se mezclará un 90% de agua a 80 °C con un 10% de agua a temperatura ambiente).

Para evaluar el caso general podemos hacer algunas simplificaciones “evidentes” a primera vista:

  • La capacidad calorífica del agua es constante.
  • El trabajo efectuado sobre el agua es despreciable.
  • La capacidad calorífica del aire contenido en el termo es despreciable.
  • La pérdida de calor a través de las paredes del termo crece monótonamente cuando la temperatura del agua sube.
  • El termo pierde calor mientras la temperatura del contenido sea mayor a la externa.

Una simplificación menos evidente es suponer que la velocidad de pérdida de calor no depende de la cantidad de agua contenida. Pero es razonable si tenemos en cuenta que la pérdida de calor depende solo de la temperatura de la pared interior del termo y que el interior del termo puede considerarse en equilibrio térmico con dicha pared.

Llamemos q_1 a la cantidad de calor perdida en el primer caso (10% de agua remanente) y q_2 a la cantidad de calor perdida en el segundo caso (90% de agua remanente). Si llamamos T_{1f} y T_{2f} a las temperaturas finales correspondientes, M a la masa total de agua y C_e a su calor específico, tendremos:

T_{1f} = 0.1 \left( 80 - \frac{q_1}{0.1 M \cdot C_e} \right) + 0.9 \cdot 80 y

T_{2f} = 0.9 \left( 80 - \frac{q_2}{0.9 M \cdot C_e} \right) + 0.1 \cdot 80.

Simplificando:

T_{1f} = 0.1 \cdot 80 - 0.1 \frac{q_1}{0.1 M \cdot C_e} + 0.9 \cdot 80

T_{1f} = 80 - 0.1 \frac{q_1}{0.1 M \cdot C_e}

T_{1f} = 80 - \frac{q_1}{M \cdot C_e}

T_{2f} = 0.9 \cdot 80 - 0.1 \frac{q_2}{0.9 M \cdot C_e} + 0.1 \cdot 80

T_{2f} = 80 - 0.9 \frac{q_2}{0.9 M \cdot C_e}

T_{2f} = 80 - \frac{q_2}{M \cdot C_e}

Podemos ver que cual de las temperaturas sea mayor dependerá exclusivamente de cuanto calor se haya perdido y no de la fracción de agua remanente en el termo, excepto a través del efecto de esta fracción en las pérdidas de calor. El problema queda reducido entonces a determinar cual es la relación entre los valores de q_1 y q_2.

Si llamamos \dot{q}(T) al flujo de pérdida de calor del termo (dependiente por hipótesis solo de la temperatura), tendremos:

q_1 = \int_0^{5\,hs} dt\,\dot{q}(T_1(t)) y

q_2 = \int_0^{5\,hs} dt\,\dot{q}(T_2(t)).

Si escribimos las ecuaciones diferenciales de las temperaturas,

\dot{T_1}(t) = -\left(\frac{1}{0.1 M \cdot C_e}\right) \dot{q}(T_1(t)) y

\dot{T_2}(t) = -\left(\frac{1}{0.9 M \cdot C_e}\right) \dot{q}(T_2(t)),

podemos observar que solo difieren en una constante multiplicativa. Si definimos T_3(t) = T_2(9t), podemos ver que

\dot{T_3}(t) = \dot{T_2}(9t) \cdot 9 = -\left(\frac{9}{0.9 M \cdot C_e}\right) \dot{q}(T_2(9t)) = -\left(\frac{1}{0.1 M \cdot C_e}\right) \dot{q}(T_3(t)).

Como T_3 obedece la misma ecuación diferencial que T_1 y además cumplen con las mismas condiciones iniciales, podemos concluir que son idénticas. En consecuencia,

T_1(t) = T_2(9t).

Como ambas funciones son monótonamente decrecientes y como 9t > t para todo t positivo, sabemos que

T_1(t) < T_2(t).

Ahora, de acuerdo con las suposiciones anteriormente realizadas, eso implica que

\dot{q}(T_1(t)) < \dot{q}(T_2(t))

y, en consiguiente,

q_1 < q_2.

Finalmente, eso nos lleva a la conclusión supuesta en base a los resultados obtenidos bajo la condición t \rightarrow \infty:

T_{1f} > T_{2f}.