Move It Up

CitydiscIn 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:

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

  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
    ADD R5,#0x3F80

  4. coder says:

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

Leave a Reply