Evolutionary algorithm to find Quake III's fast inverse square hack with Python

http://multigrad.blogspot.com/2014/04/math-evolution-and-dirty-tricks.html

by soravux • 12 years ago

173 50 12 years ago

multigrad.blogspot.com

Houshalter6• 12 years ago

There is an amazing, easy to use peice of software for doing stuff like this called Eureqa (http://www.nutonian.com/products/eureqa/). I've used it to find approximations for a lot of different functions.

danbruc• 12 years ago

Am I correct when I think of this as a curve/surface fitting tool that tries to automatically find a low complexity equation together with parameters that fits some provided data?

Houshalter6• 12 years ago

Yes, that's exactly it.

jmpeax• 12 years ago

The term for this is called "Symbolic Regression".

soravux6• 12 years ago

Eureqa seems a wonderful software for this specific application. If only I could get 2,500$ for a one-year license...

Houshalter6• 12 years ago

It has a 30 day free trial and you can use it for free if you limit to a few hundred datapoints (not ideal but workable.)

It's not perfect for this application though because it doesn't bitwise operations or use execution time as a fitness function.

cfn• 12 years ago

There are cheaper ones such as GeneXproTools.

chengsun2• 12 years ago

On the flip side of the coin, there's ries, which takes a number and finds a mathematical expression that approximates it: http://mrob.com/pub/ries/

Houshalter6• 12 years ago

That's really cool, I've been looking for something like that.

chinpokomon3• 12 years ago

I had a program for my HP-48GX that use to do something similar. It was especially useful when I knew that my decimal answer had some numerical constant, such as sqrt(2), and I wanted to convert it to something more reasonable. It would only return a single value, so I had to be careful that I didn't just use it every time, since just because an answer could approximate a multiple of Pi, it might only be a coincidence and not a good answer.

lelandbatey• 12 years ago

Is anyone else seeing a perpetual "loading" string where the example code is supposed to be?

soravux6• 12 years ago

It's javascript that loads the Gist into the page. You may have NoScript or similar that prevents the loader to fetch the code. The first code is the one from the Wikipedia page (fast inverse square root) and the second is this one: https://gist.github.com/soravux/9673839

s-macke2• 12 years ago

This reminds of another trick on the C64 to multiply two 8 Bit numbers a*b = [ ((a+b)/2)^2 - ((a-b)/2)^2 ]

more or less: one 8 bit additon, one 8 bit subtraction, two table lookups for the squares and one 16 bit subtraction.

bane• 12 years ago

Were the divide by twos just bit shift operations? (I have no idea if the 6510 had bit shift operators.)

s-macke2• 12 years ago

Well, I think it is part of the table.

http://codebase64.org/doku.php?id=base:fast_8bit_multiplicat...

But the C64 had also a shifting operation.

muyuu• 12 years ago

Yep, it does.

ROL rotate left

ROR rotate right

ASL arithmetic shift left

LSR logic shift right

But for it to work for all 2-complement coded values we need to ensure that the MSB is copied back into itself to keep the value the same sign, which can be done with another shift.

; Divide a signed 16-bit value by 2

        LDA MEM+1    ;Load the MSB

        ASL A        ;Copy the sign bit into C

        ROR MEM+1    ;restore MSB

        ROR MEM+0    ;Rotate the LSB

It's a bunch of cycles but nothing compared to a generic division.

Orangeair2• 12 years ago

Why on earth would they create a named constant for 1.5F, but not for 0x5f3759df?

jws• 12 years ago

What would you name it?

    #define AND_THEN_A_MIRACLE_OCCURS (0x5f3759df)

officialjunk• 12 years ago

MAGIC_NUMBER?

Orangeair2• 12 years ago

Fair enough. Still, it seems silly to name a constant THREE_HALVES. What information does that add over 1.5? What happens if you change it and it becomes wrong?

alexholehouse• 12 years ago

This is probably one of my favourite HN posts of 2014. Outstanding.

chengsun2• 12 years ago

Řrřola (a famous demoscene coder [1]) found a far better constant than the original (a 2.7-fold accuracy improvement) by using an optimisation algorithm over all three constants present in the original inverse square hack.

His algorithm and the result (along with a plot of relative error) can be found on his blog [2].

[1]: See, for example, this 256-byte raycaster https://www.youtube.com/watch?v=R35UuntQQF8

[2] http://rrrola.wz.cz/inv_sqrt.html

soravux6• 12 years ago

This is really interesting. I'll be sure to include these references in my next blog post on the subject. The goal of the post was to find the equation from scratch, though. As it can be seen, the constant optimization was less the spotlight of the post.

zo1• 12 years ago

Not to mention your blog engine/site is broken. Please fix the fact that we can't click on the right scrollbar due to your fancy shmancy javascript side menu.

Put it on the left hand side, or don't overlay it over the scrollbar.

Damn #hipstercoders

xellisx• 12 years ago

Has anyone gone in an plugged this into the Quake III / IOQuake 3 source and see if it's make a difference? Speed or better looking geometry?

jheriko3• 12 years ago

its not faster and the accuracy improvement is more of a curiosity than of real value.

infact on modern desktop/console hardware invsqrt hack is really bad. it causes type aliasing which is 'expensive' in native software terms. the x86(-64) chips underlying them all now has a dedicated instruction for this, as do the PPCs that came in the generation before... still of value on ARM though which is becoming more and more important.

hcarvalhoalves2• 12 years ago

Now the question is: could you arrive at this algorithm without previous knowledge of what it should converge to?

pdenya• 12 years ago

Why is that a relevant question now? How would doing this be more helpful without the results of the algorithm you're attempting to cut corners to approximate?

soravux6• 12 years ago

That is the exact goal of the post. I arrived to the algorithm through evolution with random initialization. I enforced absolutely no heuristic to make it converge to this equation.

hcarvalhoalves2• 12 years ago

I know, but can we prove there's no heuristic on that algorithm? Because if the answer is "yes", this should be general enough to find other optimizations. It's fun to think about.

acchow• 12 years ago

Oh, I thought this gonna be like regex golf:

http://xkcd.com/1313/

Misleading title.

pixelcort• 12 years ago

For a moment I thought this was a way to workaround any patents with this hack, by rediscovering the hack dynamically; but I could be remembering a different patented technique.

Houshalter6• 12 years ago

That's actually a cool idea. I wonder if that would hold up.

personalcompute• 12 years ago

Under US law it would not, as even genuine independent (re-)discovery is not a defense to infringement.

georgemcbay• 12 years ago

You might be thinking of depth-fail shadow volumes, semi-famous for being patented by Creative despite having been discovered independently by a number of people (including Carmack) over the years.

anonymousUser• 12 years ago

Hacker's Delight [1][2] is an amazing book dedicated to discussing about all kinds of bit hacking, including fast integer square root, cube root calculation.

[1] http://www.hackersdelight.org/

[2] http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/d...

EGreg• 12 years ago

Shameless plug some of you might like to read: http://www.flipcode.com/tpractice/

(I used to be really into game programming when I was in my teens.)

jheriko3• 12 years ago

With fast native code its more than practical to search the entire space of floating point numbers and guarantee that you find the optimal magic number:

http://jheriko-rtw.blogspot.co.uk/2009/04/understanding-and-...

As already mentioned in another comment it has been taken further by Řrřola who has optimised a version with the newton step including the constants involved in that.

http://rrrola.wz.cz/inv_sqrt.html

Evolutionary algorithm to find Quake III's fast inverse square hack with Python

Related Stories