Any interest in multi-threaded code?

[Niels Möller]

Victor Shoup <shoup at cs.nyu.edu> writes:

> Then I found out about .bootstrap...that doesn't work either
> (no aclocal-1.8).  Tried editing .bootstrap to remove "-1.8"...errors.

The ./.bootstrap script used to work back in the day. It lists the
needed steps, and it might work with more recent versions of the tools,
otherwise configure.in might need to be renamed to configure.ac and
updated according to any error messages from autoconf and automake.

> And while I'm at it, is there a brief statement about 
> what exactly the function mpn_fourier_transform_ct actually does?
> I mean, questions like: are the inputs/outputs in standard order
> or bit-reverse order?

I'm fairly sure inputs are expected in standard order (viewed as
coefficients of a polynomial, ordered by increasing powers of the
variable), and outputs in bit reversed order, same as
mpn_fourier_transform_truncated. I don't remember the layout of the
padding, but that might be clear from the definition of SPFFT_PAD_INDEX.
Except for padding (and any inputs related to twidde factors), I think
inputs and outputs should be identical to
mpn_fourier_transform_truncated.

Inputs and outputs are also not necessarily a power of two. I think the
size of the underlying fft is 2^k.

Input size is xn, with implicit zero padding up to 2^k.

Output size l. The last 2^k - values (last *in bit reversed indices*)
are not computed, since it's a truncated fft.

It's required that 2^{k-1} < l < 2^k, and xn <= l.

I think it's best to first ensure that the no-_ct versions of the
transform functions are working properly, before digging into the _ct
versions. Logic to enable ct is in fourier_params.c, starting at line
205.
 
Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.