Since the heavyweights here seem to be involved with finals and such, let me
get you started on your answers...
a) [skipping, I don't know]
b1) Using "properly sized" FFT: Yes, I believe using properly sized FFT's
saves some time. How much depends on the programmer, the data, the
language/compiler, and the hardware. Non-power-of-2 FFT's can even be
useful, but it seems that coding up all (or most) of the possible sizes may
be more trouble than it's worth.
b2) Recurring pattern in "N=N^2-2 % (2^P-1)": I don't recall anyone here
mentioning any interesting repeats, even for composite P. I'm sure many have
looked, and were disappointed.
c1) DB Lookup: If you are in the 2^8,000,000 range, that is 8 million bits,
or ~1MB. A database of all possible results of "N=N^2-2 % (2^P-1)" would
take 1MB * 2^8,000,000 ~= 10^3,500,000MB. This is larger than the number of
particles in the universe, by something like 10^35,000. If instead you meant
to lookup all of the "N=N^2-2" values, and compute the "%(2^P-1)" at
runtime, then P~=8,000,000 gives the last number in the sequence ~=
2^(2^8,000,000), which again runs up against the universal limit.
c2) The LL test does not adapt well to parallel efforts. I think it will
always be the case that interprocess communication will cause the
calculations to run slower than if just one processor crunched on the whole
thing. [Array or vector processor machines are another matter!] But if the
number of significant bits required were orders of magnitude larger than the
hardware, then it might make sense to parallel the squarings. We're not
there yet.
d) NTT's (Number Theoretic Transforms): There has been some talk of that
here before. However, until the ratio of integer to floating point
throughput improves, NTT's will not be very popular. [Note that the FFT
"automagically" computes the %2^P-1, using the Crandall-Fagin procedure, so
NTT's have a lot of ground to make up first.]
e) & f) Don't know
If I have made any misstatements here, someone correct me please.
-Shaun
Shaun Griffith, [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>
Quantum Mechanics: The dreams stuff is made of
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
