Quiconque est modérément dans l'optimisation de code de bas niveau connaît les dangers de la ramification, qu'elle soit implémentée comme des instructions if, des boucles ou des instructions select, la possibilité d'une mauvaise interprétation de la branche est une horrible perte de temps.

Les problèmes simples peuvent être résolus beaucoup mieux avec une arithmétique simple, alors faisons-le.

Pour les problèmes suivants, toutes les variables sont des entiers non signés de 32 bits et le seul code autorisé est des instructions en clair contenant uniquement les opérateurs suivants:

+ 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
=

Chaque ligne doit être constituée d'un identificateur de variable suivi d'un opérateur d'ensemble, suivi d'une expression.

Une expression peut ne pas contenir d'opérateurs d'ensemble supplémentaires, mais peut contenir des identificateurs de variable, des nombres littéraux et des parenthèses.

Le score de golf ne compte que le nombre d'opérateurs.

Exemple:

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

A un score de 5 opérateurs.

Une solution peut inclure autant de variables que l’auteur le juge bon.
Les variables qui n'ont pas été définies ont une valeur 0.
Dépassement supérieur et inférieur est autorisé, tous les numéros de négatifs UNDERFLOW, donc 3 - 5est4294967294 , même dans le cadre d'une déclaration plus grande.

Tâche 1: Max

Deux valeurs, Aet B, existent dans la portée, font leRESULT variable contienne la plus grande de ces valeurs lorsque le programme se termine.

Tâche 2: médiane

Trois valeurs, A, Bet C, existent dans le domaine, faire leRESULT variable de contenir la médiane de ces valeurs lorsque le programme de Met fin de.

Tâche 3: racine carrée

Une valeur, Aexiste dans la portée, fait que la RESULTvariable contienne la racine carrée deA , arrondie vers le bas, à la fin du programme.

Il est acceptable de poster une réponse à une ou deux des questions seulement, pour certains d'entre vous, trouver des solutions valables sera un défi.

Tâche 3, 23 opérations

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)

Utiliser la méthode de Newton, comme les autres solutions, avec une semence choisie avec plus de tact. Le premier bit A >> 16maintient le haut de la plage heureux, le deuxième bit A / ((A >> 13) + 511)maintient le milieu de la gamme heureux et le dernier bit 15le bas, et empêche également la division par zéro erreur (15 est la plus grande valeur possible qui permet 0de converger correctement - divisée par deux trois fois moins la correction est égale à zéro). Pour les valeurs d'entrée 225, 275625, 82137969, 2908768489(et les valeurs proches), la valeur initiale est exacte. Tous les cas de bord (carrés parfaits, carrés parfaits + 1 et carrés parfaits - 1) de la gamme 0 .. 2**32-1ont été testés et sont corrects.

Quelques commentaires sur les règles:
débordement et sous-dépassement sont autorisés, tous les nombres négatifs sont sous-dépassés, donc 3 - 5 est 4294967294, même dans le cadre d'une déclaration plus large .

Ce dernier morceau s'avère être un tueur d'innovation. J'ai d'abord tenté une solution en utilisant une forme généralisée de la méthode de Halley , mais j'ai réalisé qu'elle n'était pas valide compte tenu de la restriction ci-dessus. L'itération (appliquée aux racines carrées) est la suivante:

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

Cette itération a de belles qualités que Newton n'a pas. Il converge de façon cubique (plutôt que quadratique), il converge d'en haut ou d'en bas (plutôt que seulement d'en haut), et il n'est pas aussi sensible à une graine mal choisie (si l'itération de Newton est fournie une graine qui est beaucoup trop basse, elle dépassent considérablement le point de convergence, puis doivent redescendre).

La méthode de Newton a également le problème (au moins lorsqu'il s'agit de nombres entiers) qu'elle atteindra assez souvent un x tel que A / x - x = 2 - dans ce cas, elle convergera vers une valeur supérieure à la racine entière correcte, qui doit être corrigé; La méthode de Halley n'a pas besoin d'une telle correction. Mais malheureusement, la valeur de 3*A + x*xsera assez souvent supérieure à l'espace entier 32 bits autorisé.

Il y a un certain nombre d'autres généralisés n ^e algorithmes de racines, mais ils partagent tous cette même caractéristique:

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 plupart d'entre eux affichent une convergence cubique ou quadratique. Les quatre derniers font partie d'une série d'itérations qui convergent sur la convergence quartique. Mais en pratique, la méthode de Newton vous fournira ce dont vous avez besoin avec moins d'opérations, sauf si vous devez calculer plusieurs centaines de chiffres.

65 (61) opérations (5 + 13 + 47 (43))

Tâche 1 - Max (A, B)

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

Telle est la solution évidente. Vous avez besoin de l'affectation, vous avez besoin de comparaison, vous devez multiplier la comparaison avec quelque chose, le multiplicande ne peut pas être l'une des variables et le produit ne peut pas être le résultat.

Tâche 2 - Mid (A, B, C)

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

Il s'agit d'une amélioration par rapport à ma précédente solution à 15 op, qui conditionnait les trois variables - cela a sauvé deux soustractions, mais il a introduit un autre test de centralité. Le test lui-même est simple: un élément est au milieu si exactement un autre des deux est au-dessus.

Tâche 3 - sqrt (A)

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

Onze tours d'approximation de newton. La constante magique de 1024 est déjà battue par WolframW (et 512 provoque la division par zéro pour a = 0 avant que a = 2 ** 32 converge), mais si nous pouvons définir 0/0 comme zéro, dix itérations fonctionneront avec la valeur de départ de 512. J'admets que ma revendication de dix itérations n'est pas entièrement nette, mais je les revendique toujours entre parenthèses. Je devrai enquêter si neuf est possible, cependant.La solution de WolframH est de neuf itérations.

1: 5 opérateurs

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

2: 13 opérateurs

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

3:27 opérateurs

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)

Tâche 3, 39 Opérations

EDIT: dernière ligne modifiée; voir les commentaires.

Il s'agit d'une implémentation de la méthode Newthon. Testé avec tous les carrés positifs, ainsi qu'avec les carrés positifs moins un, et également un million de nombres aléatoires compris entre 0 et 2 ^ 32-1. La valeur de départ apparemment drôle est court pour (1022 + A/1022) / 2, qui a besoin du moins nombre d'itérations (je pense), et fait aussi RESULTpour le A=0droit (qui ne serait pas le cas pour la 1024place 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)