### Move It Up

In 1992, I coded the first incarnation of yellow pages on-a-map, CityDisc, the brainchild of Ben Hoefnagels, a great guy and visionary. I really liked to work for him. He would tell me what he wanted, and let met code. In those days, software had to run on a 6 MHz Intel 80286 from a 720kB floppy disc. I explained to Ben than in order to fit 3000 streets (and 30.000 addresses) on one floppy, we should use vector graphics. So Ben told me: “OK, go do it!” This first prototype was rather slow. So Ben told me: “Make it faster!” Profiling showed that 92% of the run time was consumed by one function: `sqrt()`

. Small wonder, coding vector rendering is all about Pythagoras. For hours I, fruitlessly, tried to make a fast `my_sqrt()`

. Then I moved the problem up one layer of abstraction. If I could not speed up `sqrt()`

, I might find a way to speed up the function that used it: the `length()`

function. On a hunch, I tried:

`#define length(x,y) ((x > y) ? (x + y/3) : (y + x/3))`

I hit `<Ctrl><F9>`

(Yes, Turbo C.) and BANG there was the map, almost instantaneous. I never forgot that lesson: Problems can be hard on one level of abstraction but easy on an other.

How about:

float fastsqrt(float val) {

int tmp = *(int *)&val;

tmp -= 1<> 1; /* divide by 2 */

tmp += 1<<23; /* restore the IEEE bias from the exponent (+2^23) */

return *(float *)&tmp;

}

O, crap, html formatting….

retry:

float fastsqrt(float val) {

int tmp = *(int *)&val;

tmp -= 1<<23; /* Remove IEEE bias from exponent (-2^23) */

/* tmp is now an appoximation to logbase2(val) */

tmp = tmp >> 1; /* divide by 2 */

tmp += 1<<23; /* restore the IEEE bias from the exponent (+2^23) */

return *(float *)&tmp;

}

Or, in assembly:

MOV R4,R8

MOV R5,R9

SUB R5,#0x3F80

SHR R4,#1

BMOV R4.15,R5.0

ASHR R5,#1

ADD R5,#0x3F80

Nice, if you can permit your self the luxury of floats.

You had floats? You lucky bastard!