Dr. Dobb's Journal - April 2008 - (Page 43)

d04will_p3ds 2/13/08 9:40 AM Page 43 Instantly Search Terabytes of Text so 1 log(x)=log(x*y)+log(— —) y N dozens of indexed, unindexed, fielded data and full-text search options (including Unicode support for hundreds of international languages) N file parsers / converters for so 1 1 log(x)=log(x*(1-2-n) )+log(——— )= log(x-x* 2-n)+log(——— ) 1-2-n 1-2-n hit-highlighted display of all popular file types N Spider supports static and dynamic web We’ve already got the values of log(1/(1–2–n)) in a lookup table, so you can reuse them here. It’s important to go for increasing values of n, so that the large factors are taken out first. data; highlights hits while displaying links, formatting and images intact N API supports .NET, C++, Java, databases, etc. New .NET Spider API Square Roots With the shift-and-add implementations of sines, cosines, exponentials, and logarithms, the runtime was much improved. However, another function was now taking a lot of the time— the square-root function. This had been naïvely implemented using a Newton-Raphson approximation, and was taking a very long time to converge in some cases. What was needed was a systematic method of calculating a square root that had a bounded iteration count. Yet again, you can use powers of two to your benefit. If y=√x then y 2=x. If you break y down by extracting the highest power of 2, so y=2n+r, then y2=22n+r*2(n+1)+r 2. Consequently, you can find n from the highest even power of two in x, then it’s just a matter of finding r, which you can do by trial and error, hunting for each bit in turn. If you start with a=2n, and z=x–a2, then you can iterate through the remaining powers of two less than n to find the result. In each iteration you try y=a+2m+r1, for decreasing powers of m. Now, you know that y2=a2+2*a*2m+22m+r2, and the ideal is that r1 (and thus r2) is zero, so y=√x. However, in each iteration you’ve got z=x–a2, so you need to compare z against 2*a*2m+22m. Since we’re going in decreasing values of m, if z>=2*a*2m+22m, then you know that 2m is a component of y, since r2 will always be positive. Because a given power of 2 can only be present once, you can now move to the next smaller value of m, updating the new value of a and z. Since you’ve got a fixed-point value, once you run out of bits you’re done, so there is a hard limit on the number of iterations. Multiply and Divide After investing the effort in optimizing the complex operations, plain old multiply and divide were now top of the heap. These functions are more than just simple integer operations, because they need to take care of the fixed-point offset. Not only that, but the target platform is a 32-bit platform, so the compiler-supplied 64-bit integer operations are multiple instructions anyway, thus it is important to ensure that every instruction does something useful. For multiplication, this means splitting the top 32 bits and the bottom 32 bits— there’s no point doing unnecessary 32-bit times 64-bit multiplications just for completeness. Doing the split like this also lets the appropriate bit shifts be incorporated directly without having to worry about loss of precision. Division is more complicated, as to get the final answer correct to the available precision, you need more than 64 bits in some cases. To circumvent this problem, when the numerator is more than the denominator, then the denominator is scaled up until it is at least as big as half the numerator. This then makes for division of values of similar size, so the shift-and-add method used for the actual calculation is most effective, and doesn’t lose any precision— basically, each bit is calculated in turn, starting with the most significant bit of the result. h Spider Desktop wit h Spider Network wit CD/DVDs Publish for ider Web with Sp Win & .NET Engine for Linux Engine for New 64-bit The Smart Choice for Text Retrieval ® since 1991 N “Bottom line: dtSearch manages a terabyte of text in a single index and returns results in less than a second” – InfoWorld N “For combing through large amounts of data,” dtSearch “leads the market” – Network Computing N dtSearch “covers all data sources powerful Web-based engines”– eWEEK N dtSearch “searches at blazing speeds” – Computer Reseller News Test Center See www.dtsearch.com for hundreds more reviews, and hundreds of developer case studies Conclusion Using fixed-point math gave a considerable performance boost to this application, and I anticipate that there are many other applications that could benefit from the techniques described here. It is important to check that the required range of values for an application can comfortably be represented within the chosen fixed-point representation. DDJ Contact dtSearch for fully-functional evaluations 1-800-IT-FINDS www.dtsearch.com April 2008 l www.ddj.com l Dr. Dobb’s Journal 43 http://www.dtsearch.com http://www.dtsearch.com http://www.dtsearch.com http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - April 2008

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

Dr. Dobb's Journal - April 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.