mathematical recreations

[cragwolf]

I was reading an online book (http://www.maths.manchester.ac.uk/~avb/micromathematics/downloads) the other day, and came across a formula which gives the abs function (http://community.freepascal.org:10000/docs-html/rtl/system/abs.html) (absolute value of a number) in terms of the max function (http://community.freepascal.org:10000/docs-html/rtl/math/max.html) (the larger of two numbers):


abs(x) = max(x, -x)

So one step ahead I wondered if there was a formula which goes the other way: the max function in terms of the abs function. After much hair-pulling I managed to derive it:


max(x, y) = 0.5 * (x + y + abs(x-y))

Not as fast as the way it's normally done in code (or in our brains, for that matter):


if x > y then Result := x else Result := y;

But I thought it was pretty neat all the same. Moving on...

This thread (http://www.pascalgamedevelopment.com/viewtopic.php?t=3791) about tessellating spheres got me thinking, too. I wondered if the geosphere algorithm might produce a better sphere if one started from something somewhat more sphere-like than an octahedron. Enter the icosahedron, which has twenty faces, each face an equilateral triangle. But how do you draw an icosahedron?

Here's a simple technique, illustrated below (taken from the aforementioned book):

http://www.ludicity.org/images/icosahedron.png

Initially, draw an appropriately oriented line on each face of a cube. Then join the ends of each line together in an appropriate manner. The only tricky bit is knowing how long the initial lines are supposed to be. To guarantee equilateral triangles, I found after further hair-pulling that on a cube with sides of length D, the length of these initial lines must be:


L = 0.5 * D * (sqrt(5) - 1)

Or more simply:


L = D / G

where G is the well-known golden ratio (http://en.wikipedia.org/wiki/Golden_ratio), which has applications in art, music, and Egyptian pyramids!

Mathematical recreation is not a bad hobby if you don't mind baldness.

[Traveler]

Mathematical recreation is not a bad hobby if you don't mind baldness.

Many of us probably wont need math for that :)

Still, it's cool stuff nonetheless. Have a quick looksee in the math thread (http://www.gamedev.net/community/forums/forum.asp?forum_id=20) of GD.net and you'll find lots of interesting things. I think I have seen your first sample asked there some time ago, as well.

[VilleK]

A branch-free max! Elegant. I'm sure it can be useful in the right context.

[cragwolf]

I'm not sure if it's branch-free, because I don't think the abs function is branch-free. I suppose you could try to circumvent that by writing the abs function as:


abs(x) = sqrt(x*x)

So our formula for the max function would become:


max(x, y) = 0.5*(x + y + sqrt((x-y)*(x-y)))

But is the sqrt function branch-free? Even ignoring the compiler implementation, determining the square root of a number requires making a choice: do you choose the negative or positive root?

[LP]

I'm not sure if it's branch-free, because I don't think the abs function is branch-free.

Actually Abs(), Min(), and Max() functions can be branch-free using conditional moves, e.g.:



function Max(a, b: Integer): Integer;
asm
cmp edx, eax
cmovg eax, edx
end;

[cragwolf]

I guess I don't know what branch-free code is.

[Huehnerschaender]

As far as I understand brachfree code, it is a piece of code which doesn't have to do a "decision" within...


So the CPU doesn't have to do something like:

IF xy THEN yz
ELSE
za;

The max procedure for example I would expect to do a branch:

IF a > b then result := A
ELSE result := b;


You see the branch?
Lifepower shows, that this function can give the right answer without branching...

[VilleK]

I was thinking about the intel cpu "fabs" instruction for floating point abs, or simply clearing the sign bit for integers.
Branching code is everywhere the code makes a jump based on a test operation.

edit: yes Huehnerschaender explains it well.

[jdarling]

Well, if the processor knows the data type for the integer (be it 16, 32, 64, 128, etc) then really the processor should only be performing a bitmask:

CLR Var, SignBitPosition

No jump, break, or other instructions to manage, a single call to mask the absolute value quickly. Now for Max its another story, one might think that it would look something to this:

CMP A, B
JGT USET
PUSH A
JMP UEND
USET:
PUSH B
UEND:

But this would be very inefficient as well, I've used the same type of code in assembly for max's but typically you take into account why a max is being performed and what other hardware is in place. In fact an Add and Divide method as first stated may be faster then the jumps depending on how often witch version is true (remember a jump takes an extra cycle when you don't use immediates and if you have a compare as above) where the math would always take 2 the above code could take 3.

Of course the above is not x86 assembly, though looking it may compile on an x86 assembler. I may also be really off base as all of my assembly these days is in 8 bit micros :D

[cragwolf]

Thanks, I think I get it now. 8)