On Mon, Aug 12, 2002 at 10:34:18AM +0100, Nick Ing-Simmons wrote: > Nicholas Clark <[EMAIL PROTECTED]> writes: > > > >I was told (by someone at the German Perl Workshop, and I forget who, sorry) > >that there is an algorithm (in Knuth) for evaluating (a+b) * (c+d) in 3 > >multiplies, not 4, for whenever multiplication is considerably slower than > >addition. > > I know my algebra instruction was over two decades ago but > > (a+b) * (c+d) > > seems to need two adds and ONE multiply.
but if A and B are 128 bits long, and you don't have 128 bit multiply, you can implement A * B as ((a << 64) + b) * ((c << 64) + d) which is 4 64 bit multiplies and some addition and shifting. I am assuming is the assumption behind all this is that the addition and shifting can be programmed easily for arbitrary length, whereas the multiply can't. And if you don't have 64 bit multiplies, break each into 4 32 bit multiplies. My understanding is that the refactoring to three multiplies is useful for the case of multiply being slower than add or shift, because it reduces the amount of multiplying. The context of all this was large (integer) maths. Sorry if it wasn't clear because the thread has now lost the context. Nicholas Clark
