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!