Otros ejemplos de cálculos mágicos

Question

He visto this topic here sobre la forma mágica de John Carmack para calcular la raíz cuadrada, que hace referencia 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 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. This article cuenta más. Gracias @moocha.

Answer 1

Bit Twiddling Hacks tiene muchos trucos geniales.

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

Answer 2

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

Answer 3

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

Usted tiene, por ejemplo, muchos trucos como hacks haciendo girar los bits etc ... (tiene varios algoritmos de raíz cuadrada, por ejemplo, que se puede ver en la versión de Google books)

Answer 4

No es exactamente un truco matemático, pero me gusta éste sobre Roman Numerals en java6:

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

le dará la expected result (1977 + 24 =), 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 literal 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 5

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

• Zeller's congruence para calcular el día de la semana de una fecha determinada
• Gauss's algorithm para calcular el fecha de la Pascua

Algunos (no probado) código de la siguiente manera:

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'