FFT validation method

[James Youlton]

While I'm new here, I'm not new to solving problems.

On the site for GIMPS,there was mention of verification of multiplication
routines.  Please consider the following:

for integers x and y,

(y-x)^2 mod y = (y^2 - 2xy + x^2) mod y = x^2 mod y

if y = 2^z - 1, then conjugate x  = y - x = y xor x, an easy calculation
that runs at the speed of memory.

Since x and conjugate x are entirely different bit patterns that produce
the same comparable result, that would validate the multiplication routines
via any method.

If an arbitrary bit pattern from a good RNG can produce long arbitrary bit
patterns that can be referred to by their RNG seed, reproducible results
can be obtained by simply emailing the seed instead of the huge bit
stream.   An optional 128 bit xor checksum can be included for the two
results so that the source guru can be sure they are seeing the same error
with their equipment.

Personally, I use the 4 shift register version of  xorwow() that I found on
the Wikipedia page for "xorshift".  The current posted version is 5 shift
registers and I encapsulated the version I use in to an unmanaged VC++ DLL
that is callable from any high level language and I can provide it free of
charge for anyone to use if you send me an email request for a download
with or without source.

That's one from me.  On the flip side, I could use a DLL that is callable
from any high level language (same calling method) that does fast arbitrary
bit sized multiplications, divisions and modulos called with the base
pointers in memory of the source bit patten, it's padded size in bytes and
a base pointer in memory to store the return results.  That will be an
enormous benefit to anyone who wants to work with big numbers without being
a code guru in a language with good GUI access.

Note:  A while back, I wrote a useful machine code Miller Rabin witness a
function that tests 64 bit values at a velocity of 70,000 tests per second
(good luck trying to read the code as I spent 40 hours coding it in the
assembly language debugger doing line by line verification with int 3).
The code includes a source readable prepended fast trial divide (DIV-less,
RAM-less method on the last 24 primes in the set) that reduces the input
set of off 64-bit integers to 1 in 15 with a velocity of 1.1 million odd 64
bit integers per second on one core of my Core2 Quad Extreme Series (I got
it for the 12 MB L2 cache) 2.83 GHZ with 1333 mhz memory, amplifying the
MR-a test by 15x.  This is useful for doing trial divides of large numbers
by 64-bit values by knowing with good or near certainty that your trial
divide factors are prime prior to committing to the big trial divides.  The
source project, including usable windows DLL and VB.net calling source code
can be found here for anyone to use
http://v-sonline.com/MrPrimer/mrprimer.zip (Posted 12-5-2007)  While the
MA-a function would require an entire rewrite go go wider, the fast trial
divide could be modified with minimal difficulty with two 64-bit inputs
instead of one (128-bit test).  I originally wrote it for an online
programming contest involving 64-bit primes.

Sincerely,

James J Youlton, Ph.D.

p.s. To demonstrate my skills since I'm new here, these are mine from a
programming contest in 2010.

https://commons.wikimedia.org/wiki/File:MagicSquare_10x10b.png
https://commons.wikimedia.org/wiki/File:MagicSquare15.jpg
https://commons.wikimedia.org/wiki/File:MagicSquare16.jpg