Другие примеры магических вычислений

Я видел эту тему здесь о волшебном способе Джона Кармака для вычисления квадратного корня, который относится к этой статье: http://www.codemaestro.com/reviews/9. Это меня очень удивило, я просто никогда не понимал, что вычисление sqrt может быть настолько быстрым.

Мне просто интересно, какие существуют другие примеры "волшебства", которые используют компьютерные игры для ускорения работы.

UPDATE: Джон Кармак не автор волшебного кода. В этой статье сказано больше. Спасибо @moocha.

Ответ 1

Бит Twiddling Hacks имеет много интересных трюков.

Хотя некоторые из них датируются сейчас, я был в восторге от некоторых трюков в "Zen of Code Optimization" от Michael Abrash, Реализация игры из жизни ошеломляет.

Ответ 2

Существует книга, в которой собраны многие из этих "волшебных трюков", и которые могут быть вам интересны: The Hacker Delight.

У вас есть, например, множество трюков, таких как бит-скручивающие хаки и т.д. (у вас есть несколько алгоритмов с квадратным корнем, например, которые вы можете увидеть в версии книг Google)

Ответ 3

Не совсем математический взлом, но мне нравится этот Римские цифры в Java6:

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

предоставит вам ожидаемый результат (1977 + 24 = 2001) из-за правила перезаписи:
class Transform extends TreeTranslator, внутренний класс компилятора Java.

Transform посещает все утверждения в исходном коде и заменяет каждую переменную, имя которой совпадает с римской цифрой с внутренним литералом того же числового значения.

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);
        }
    }
}

Ответ 4

Я большой поклонник Bresenham Line, но человек CORDIC rotator включил все виды пиксельных придирок для меня, когда процессоры были медленнее.

Ответ 5

Я всегда был впечатлен двумя классическими "магическими" алгоритмами, которые связаны с датами:

Конкуренция Целлера для вычисления дня недели определенной даты
алгоритм Гаусса для расчета даты Пасхи

Следующий (непроверенный) код следует:

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'