Assuming your inputs are properly normalized, i.e. x,y < (2^p1), you break each into 32/33bit pieces according to the perword bitlengths in your list. (Balanceddigit representation is easy to achieve here, but not necessary for learning the basics.) Then multiply each of the D words of each sodiscretized input by the corresponding fractional power of 2, fwdFFT each resulting weighted input vector, dyadicmultiply the resulting lengthD forward transforms, invFFT the resulting vector, and multiply the resulting D discrete convolution outputs by the D inverse weights. The resulting outputs should be close enough to pureintegers that they can be confidently roundedtonearest and carries propagated. Check that the carrypropagated result matches x*y (mod 2^p1) computed using exact multiprecision integer arithmetic.
Quote:
Originally Posted by bentonsar
Hi Axn,
Thx for the links.
Take the example from page 498 in Prime Numbers: A Computational Exploration where p = 2^521  1, q = 521, D=16, d = (33, 33, 32, 33, 32, 33, 32, 33, 33, 32, 33, 32, 33, 32, 33, 32), a = ...
Right now I can successfully generate d and a based on those input values and my FFTs seem to be working correctly. My question is, let's say we want to have the x and y integers be 10 and 10 (or some other integer, it doesn't really matter). How do you apply those weights that were created to the integers so that they are ready for the FFT (of size D)?
I read through the x = formula that is listed in 9.5.18 but I couldn't quite get it working correctly.
Sarah
