Другие примеры магических расчетов - PullRequest
Новая
       8

Другие примеры магических расчетов

13 голосов
/ 01 декабря 2008

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

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

UPDATE : Джон Кармак не является автором магического кода. Эта статья рассказывает больше. Спасибо @ муча.

Ответы [ 5 ]

5 голосов
/ 01 декабря 2008

Существует книга, в которой собраны многие из этих «магических трюков» и которая может быть вам интересна: Восторг хакера .

У вас есть, например, много хитростей, таких как битовые трюки и т.п.

5 голосов
/ 01 декабря 2008

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

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

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

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

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 голосов
/ 01 декабря 2008

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

3 голосов
/ 02 декабря 2008

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

Хотя некоторые из них уже датированы, я был восхищен некоторыми уловками в "Дзен оптимизации кода" Майкла Абраша. Реализация Game of Life ошеломляет.

3 голосов
/ 02 декабря 2008

Меня всегда впечатляли два классических «магических» алгоритма, связанных с датами:

Ниже следует некоторый (непроверенный) код: 

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'
...