Cualquiera que esté moderadamente en la optimización de código de bajo nivel conoce los peligros de la ramificación, ya sea que se implemente como sentencias if, bucles o sentencias selectivas, la posibilidad de una predicción errónea de la rama es una pérdida de tiempo terrible.

Los problemas simples se pueden resolver mucho mejor con la aritmética simple, así que hagámoslo.

Para los siguientes problemas, todas las variables son enteros sin signo de 32 bits y el único código permitido son declaraciones simples que involucran solo a los siguientes operadores:

+ addition
- subtraction
* multiplication
/ integer division, rounds down, division by 0 not allowed
% modulo
& binary and
| binary or
^ binary exclusive or
>> bitshift right
<< bitshift left

Logic operators, return 1 if the expression is true and 0 if it is false.
== equal
!= not equal
< less than
<= less than or equal
> greater than
>= greater than or equal

Set operator
=

Cada línea debe constar de un identificador de variable seguido de un operador de conjunto, seguido de una expresión.

Una expresión puede no contener operadores de conjuntos adicionales, pero puede contener identificadores variables, números literales y paréntesis.

El puntaje de golf solo contará el número de operadores.

Ejemplo:

myvar = ( ( ( foo + 5 ) * bar ) % 7 ) == 3

Tiene una puntuación de 5 operadores.

Una solución puede incluir tantas variables como el autor considere oportunas.
Las variables que no se han establecido tienen valor 0.
Se permite el extracto y refinado, todos los números negativos de flujo inferior, por lo que 3 - 5es 4294967294, incluso como parte de una declaración más grande.

Tarea 1: Máx.

Dos valores, Ay B, existen en el ámbito, hacen que la RESULTvariable contenga el mayor de esos valores cuando finaliza el programa.

Tarea 2: mediana

Tres valores, A, By C, existen en el ámbito de aplicación, hacen que la RESULTvariable de contener la mediana de estos valores cuando finaliza la del programa.

Tarea 3: raíz cuadrada

Un valor, Aexiste en el ámbito, hace que la RESULTvariable contenga la raíz cuadrada de A, redondeado hacia abajo, cuando el programa termina.

Está bien publicar una respuesta a solo una o dos de las preguntas, para algunos de ustedes solo encontrar soluciones válidas será un desafío.

Tarea 3, 23 operaciones

x = (A >> 16) + A / ((A >> 13) + 511) + 15
x = (x + A/x) >> 1
x = (x + A/x) >> 1
x = (x + A/x) >> 1
RESULT = x - (x > A/x)

Usando el método de Newton, como lo hacen las otras soluciones, con una semilla elegida con más tacto. El primer bit A >> 16mantiene feliz la parte superior del rango, el segundo bit A / ((A >> 13) + 511)mantiene feliz la mitad del rango y el último bit 15la parte inferior, y también evita la división por cero errores (15 es el valor más grande posible que permite 0converger correctamente a la mitad tres veces menos corrección es igual a cero). Para los valores de entrada 225, 275625, 82137969, 2908768489(y valores cercanos) la semilla inicial es exacta. Todos los casos de borde (cuadrados perfectos, cuadrados perfectos + 1 y cuadrados perfectos - 1) en el rango 0 .. 2**32-1han sido probados y son correctos.

Algunos comentarios sobre las reglas:
se permite el desbordamiento y el subflujo, todos los números negativos se desbordan, por lo que 3 - 5 es 4294967294, incluso como parte de una declaración más grande .

Esa última parte resulta ser una especie de asesino de la innovación. Inicialmente intenté una solución usando una forma generalizada del método de Halley , pero me di cuenta de que no era válida dada la restricción anterior. La iteración (como se aplica a las raíces cuadradas) es esta:

x = x * (3*A + x*x) / (A + 3*x*x)

Esta iteración tiene buenas cualidades que Newton no tiene. Converge cúbicamente (en lugar de cuadráticamente), converge desde arriba o desde abajo (en lugar de solo desde arriba), y no es tan sensible a una semilla mal elegida (si la iteración de Newton proporciona una semilla que es demasiado baja, lo hará sobrepasa en gran medida el punto de convergencia, y luego necesita volver a bajar).

El método de Newton también tiene el problema (al menos cuando se trata de enteros) de que con frecuencia alcanzará una x tal que A / x - x = 2 - en este caso, convergerá a un valor mayor que la raíz entera adecuada, que necesita ser corregido; El método de Halley no necesita tal corrección. Pero desafortunadamente, el valor de 3*A + x*xa menudo será mayor que el espacio entero de 32 bits permitido.

Hay varios otros algoritmos de raíz ^enésima generalizados , pero todos comparten esta misma característica:

x = x + x*(v - x**n)/(v*n)
x = (x*(n+1) - x**(n+1)/v)/n
x = ((n-2)*x + (4*v*x)/(v + x**n))/n
x = x*((n+2)*v + (n-2)*x**n)/(v + x**n)/n
x = ((n-2)*x + (n*x*v)/(v + (n-1)*x**n))/(n-1)
x = ((n-2)*x + x*((n*2-1)*v + x**n)/(v + (n*2-1)*x**n))/(n-1)

x = x + 2*x*(v - x**n)/(v + x**n)/n
x = x + x*31*(v - x**n)/(10*v + 21*x**n)/n
x = x + x*561*(v - x**n)/(181*v + 380*x**n)/n
x = x + x*1153*(v - x**n)/(372*v + 781*x**n)/n

etc. La mayoría de estos muestran convergencia cúbica o cuadrática. Los últimos cuatro son parte de una serie de iteraciones que convergen en convergencia cuártica. Pero en la práctica, el método de Newton le dará lo que necesita con menos operaciones, a menos que necesite calcular muchos cientos de dígitos.

65 (61) operaciones (5 + 13 + 47 (43))

Tarea 1 - Máx. (A, B)

RESULT = A + (B - A) * (A <= B)

Esta es la solución obvia. Necesita la asignación, necesita comparación, necesita multiplicar la comparación con algo, el multiplicando no puede ser una de las variables y el producto no puede ser el resultado.

Tarea 2 - Media (A, B, C)

RESULT = A                               \
       + (B - A) * (A > B) ^ (B <= C)    \
       + (C - A) * (A > C) ^ (C <  B)

Esta es una mejora con respecto a mi solución anterior de 15 operaciones, que condicionó las tres variables: esto salvó dos restas, pero introdujo otra prueba de centralidad. La prueba en sí es simple: un elemento está en el medio si exactamente uno de los dos está arriba.

Tarea 3 - sqrt (A)

X1     = 1024 + A / 2048
X2     = (X1  + A / X1 ) / 2
...
X10    = (X9 + A / X9 ) / 2
RESULT = X16 - (X16 * X16 > A)

Once rondas de aproximación newton. WolframW ya ha superado la constante mágica de 1024 (y 512 causa división por cero para a = 0 antes de que a = 2 ** 32 converja), pero si podemos definir 0/0 como cero, diez iteraciones funcionarán con el valor inicial de 512. Admito que mi reclamo de diez iteraciones no está del todo limpio, pero todavía las reclamo entre paréntesis. Sin embargo, tendré que investigar si nueve es posible.La solución de WolframH es nueve iteraciones.

Operadores 1: 5

RESULT = B ^ (A ^ B)*(A > B)

2:13 operadores

RESULT = B ^ (A ^ B)*(A > B) ^ (A ^ C)*(A > C) ^ (B ^ C)*(B > C)

3:27 operadores

g = 47|((0x00ffffff & A)>>10)|(A>>14)
r = (g + A/g)/3
r = (r + A/r)>>1
r = (r + A/r)>>1
r = (r + A/r)>>1
RESULT = r - (r*r-1>=A)

Tarea 3, 39 Operaciones

EDITAR: se modificó la última línea; ver comentarios.

Esta es una implementación del método Newthon. Probado con todos los cuadrados positivos, y también con los cuadrados positivos menos uno, y también un millón de números aleatorios en el rango de 0 a 2 ^ 32-1. El valor aparentemente divertida partida es la abreviatura de (1022 + A/1022) / 2, que necesita el menor número de iteraciones (creo), y también hace que el RESULTde A=0la derecha (lo que no sería el caso para 1024en lugar de 1022).

r = (511 + A/2044)
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
RESULT = r - (r > A/r)