Other examples of magical calculations

I have seen this topic here about John Carmack's magical way to calculate square root, which refers to this article: http://www.codemaestro.com/reviews/9. This surprised me a lot, I just didn't ever realized that calculating sqrt could be so faster.

I was just wondering what other examples of "magic" exist out there that computer games use to run faster.

UPDATE: John Carmack is not the author of the magic code. This article tells more. Thanks @moocha.


Bit Twiddling Hacks has many cool tricks.

Although some of it is dated now, I was awed by some of the tricks in "The Zen of Code Optimization" by Michael Abrash. The implementation of the Game Of Life is mind-boggling.

There is a book which gathers many of those 'magic tricks' and that may be interesting for you: The Hacker's Delight.

You have for example many tricks like bit twiddling hacks etc... (you have several square root algorithms for example that you can see on the google books version)

Not exactly a mathematical hack, but I like this one about Roman Numerals in Java6:

public class Example {
    public static void main(String[] args) {
            MCMLXXVII + XXIV

will give you the expected result (1977 + 24 = 2001), because of a rewrite rule: class Transform extends TreeTranslator, an internal class of the Java compiler.

Transform visits all statements in the source code, and replaces each variable whose name matches a Roman numeral with an int literal of the same numeric value.

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

I'm a big fan of Bresenham Line, but man the CORDIC rotator enabled all kinds of pixel chicanery for me when CPUs were slower.

I have always been impressed from two classic 'magic' algorithms that have to do with dates:

Some (untested) code follows:

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'

Need Your Help

How to use the qi::hold Parser directive. (Issue with attribute type for boost::swap)

c++ boost swap boost-spirit boost-spirit-qi

I have a parser that parses into a boost::variant&lt;int, double, std::string&gt;

Loading JavaScript API in SharePoint - Timing Issues

javascript api sharepoint simile

I have a Content Editor Web Part in SharePoint 2007 that includes a function to insert several tags on the page with different JavaScript sources.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.