performance - Otros ejemplos de cálculos mágicos

language-agnostic math

Question

He visto este tema aquí sobre la forma mágica de John Carmack para calcular la raíz cuadrada, que se refiere a este artículo: http://www.codemaestro.com/reviews/9 . Esto me sorprendió mucho, simplemente nunca me di cuenta de que el cálculo de sqrt podría ser tan rápido.

Me preguntaba qué otros ejemplos de "magia" existen allí que los juegos de computadora usan para correr más rápido.

ACTUALIZACIÓN : John Carmack no es el autor del código mágico. Este artículo dice más. Gracias @moocha.

Answer 1

Hay un libro que reúne muchos de esos "trucos de magia" y que puede ser interesante para ti: The Hacker''s Delight .

Tienes, por ejemplo, muchos trucos, como el truco de los bits, etc ... (tienes varios algoritmos de raíz cuadrada, por ejemplo, que puedes ver en la versión de libros de Google).

Answer 2

No es exactamente un truco matemático, pero me gusta este sobre los números romanos en Java6:

public class Example {
    public static void main(String[] args) {
        System.out.println(
            MCMLXXVII + XXIV
        );
    }
}

le dará el resultado esperado (1977 + 24 = 2001 ), debido a una regla de reescritura:
class Transform extends TreeTranslator , una clase interna del compilador de Java.

Transform visita todas las declaraciones en el código fuente y reemplaza cada variable cuyo nombre coincide con un número romano con un int literal del mismo valor numérico.

public class Transform extends TreeTranslator {
    @Override
    public void visitIdent(JCIdent tree) {
        String name = tree.getName().toString();
        if (isRoman(name)) {
            result = make.Literal(numberize(name));
            result.pos = tree.pos;
        } else {
            super.visitIdent(tree);
        }
    }
}

Answer 3

Soy un gran admirador de Bresenham Line, pero el hombre del rotador CORDIC me permitió toda clase de trampas de píxeles cuando las CPU eran más lentas.

Answer 4

Siempre me han impresionado dos algoritmos clásicos de ''magia'' que tienen que ver con las fechas:

• La congruencia de Zeller para calcular el día de la semana de una fecha determinada
• Algoritmo de Gauss para calcular la fecha de Pascua

Un código (no probado) sigue:

import math

def dayOfWeek(dayOfMonth, month, year):
    yearOfCentury = year%100
    century = year // 100

    h = int(dayOfMonth + math.floor(26.0*(month + 1)/10) + yearOfCentury /
         + math.floor(float(yearOfCentury)/4) + math.floor(float(century)/4) /
         + 5*century) % 7
    return [''Saturday'', ''Sunday'', ''Monday'', ''Tuesday'', ''Wednesday'', ''Thursday'', ''Friday''][h]

def easter(year):
    a = year%19
    b = year%4
    c = year%7
    k = int(math.floor(float(year)/100))
    p = int(math.floor((13 + 8.0*k)/25))
    q = int(math.floor(float(k)/4))
    M = (15 - p + k - q)%30
    N = (4 + k - q)%7
    d = (19*a + M)%30
    e = (2*b + 4*c + 6*d + N)%7
    day1 =  22 + d + e 
    if day1 <= 31: return "March %d"%day1
    day2 = d + e - 9
    if day2 == 26: return "April 19"
    if day2 == 25 and (11*M + 11)%30 < 19: return "April 18"
    return "April %d"%day2  

print dayOfWeek(2, 12, 2008)  # ''Tuesday''
print easter(2008)            # ''March 23''

Answer 5

Bit Twiddling Hacks tiene muchos trucos geniales.

Aunque parte de ella ahora está pasada de moda, me sorprendieron algunos de los trucos en "The Zen of Code Optimization" de Michael Abrash. La implementación del juego de la vida es alucinante.