Computer math is hard.

[talarubi]

Currently trying to run an affine transform on a box filter (English: Drawing surface with arbitrary orientation). Unforunately it's not going to happen tonight, my brain is fried. The irritating part is this is easy conceptually, but...

Consider that one's favorite games are just fancy iterative formulas. Bottom line, they transform your input, and millions of pixels (aka (X,Y,time) coordinates) into shiny (R,G,B) color triples. These are discrete quantities, not continuous infinitesimal functions. To apply any math to this you have to chop it up into little bits. Is this not mind-blowing? Well, the butcher knife makes a damn bloody mess.

---

I had a couple other ideas the other day. The first had to do with multiplying large numbers. For factors of m and n digits, this is normally an O(m*n+n) operation. On average it might as well be O(n²)! But consider what is going on here if you consider the factors as discrete signals...

    456        [   6   5   4         ... ]  
 x  123      x [   3   2   1         ... ]
 ------      -----------------------------
   1368  =>    [ 6*3 5*3 4*3         ... ]
   912         [     6*2 5*2 4*2     ... ]
+ 456        + [         6*1 5*1 4*1 ... ]
= 56088      = [  18  27  28  13   4 ... ] 
             = [   8   8   0   6   5 ... ] (after carries)

So, can any math/eng geeks guess what the operation on the right is? <..< >..> <..< Yes! It's convolution! We may call it multiplication, but those digit strings are not the numbers they represent. Convolve the strings, multiply the numbers.

Fine... but why is this interesting? Because if you snoop around, you might hear things about the fourier transform, a mathy shenanigan that works like a spectrum analyzer. You might hear that convolution in space/time multiplies the signal's frequency spectrum, and vice versa. And doing the transform doesn't add to the signal, it just rearranges it.

The upshot: Just multiply the two spectrums. This is "only" max(m,n) operations, far cheaper than multiplying the long way! Modern implementations of the Fast Fourier Transform scale logarithmically, so this could, in theory, win out for large numbers.

Hrm. Further Googling suggests that people have already done this...

---

The second came out talking with bormac over the other weekend. I got to blathering about games and (as above) quirky computer math. How it's all discrete quantities, and the consequences of that. For example, if you can get your character moving fast enough, in many games you could blink right through a wall because the motion is not continuous, and your only intersection--the game's chance to stop you--would have been between two video frames.

And then it occurred to me that, in a way, [the theory of] quantum physics shows an eerie resemblance. Particles tunnel, elements borrow energy and decay, all sorts of fun things happen... behind everyone's back... as long as the time they take is too small to be observable. That is, as long as it happens quickly enough...

*Twilight Zone music*