### 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.

1. John Sinteur says:

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;
}

2. John Sinteur says:

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;
}

3. John Sinteur says:

Or, in assembly:

MOV R4,R8
MOV R5,R9
SUB R5,#0x3F80
SHR R4,#1
BMOV R4.15,R5.0
ASHR R5,#1