Return to Colloquia & Seminar listing
How Can You Possibly Get a Patent on Division?
Applied MathSpeaker: | Alan H. Karp, Hewlett-Packard Laboratories |
Location: | 693 Kerr |
Start time: | Tue, Jun 7 2005, 4:10PM |
People have been doing division for a long time, so how was it possible for Peter Markstein and me to get 3 patents on this problem issued between 1994 and 1997? The answer is to find an aspect that hasn't been adequately addressed and make it implementable in hardware. Our contribution was to look at division problems that involve more bits than the floating point hardware can handle. The difficulty is in emulating the high precision arithmetic in an efficient way while maintaining the numerical properties of the IEEE standard. We were able to show that a simple change to the standard algorithm gets us the right answer without ever having to multiply two high-precision numbers. This simple change saves up to 50% of the time needed. In addition, we can correctly round the result almost all the time with only one additional floating point operation. When we can't, we have an efficient procedure for getting the last bit right.