DSPs

Jim Dixon jdd at aiki.demon.co.uk
Sun Aug 28 10:55:22 PDT 1994


In message <199408281656.JAA14318 at netcom.netcom.com> Norman Hardy writes:

> Modular reduction is scarcely worse than the multiplication. If I have a 60 word
> multi precision number N to be reduced by a 30 word number M, I compute a guess
> by dividing the 32 bit most significant bits N by the most significant 32
> bits of M.

On a DSP chip like the Texas C40, 32-bit multiplication takes one clock
cycle.	Modular reduction will take something on the order of one hundred
clocks.  Modular reduction is much more expensive than multiplication.

> I then multiply this quotient by M and subtract that from N. That reduces N by
> some multiple of M leaving N mod M unchanged. The error in the guess might
> mean that N is less than 32 bits shorter than it was before the operation but
> this method gets nearly 32 bits per pass. The inner loop of the is the same as
> in multiplication.
> 
> For all of this using the floating point unit wins on most modern CPUs.

Not on DSP chips.  On the C40, reals are only 32 bits long, so there is
no benefit to using them.  They are less precise than integers.
--
Jim Dixon






More information about the cypherpunks-legacy mailing list