There are two versions of the code in this directory.
A pure C version (serial) and a Cilk C version (parallel).
The software was written by Michael Monagan in 2020.
To cite it please use

Joris van der Hoeven and Michael Monagan
Implementing the tangent Graeffe root finding algorithm.
In Mathematical Software -- ICMS 2020.
LNCS 12097:482--492, Springer, 2020.

To compile the C code download the files

  arrayutil.c
  fftutil8.c
  int128g.c
  polyalg3.c
  primitive.c
  mainfft5.c
  Makefile

and in Linux compile with

  make fft5

The Makefile assumes you have the gcc compiler.
To run the C code in Linux use

  ./fft5 d

where d is the degree of the polynomial P(z).
The prime used is the one in the paper namely

  p = 6269010681299730433; // = 3 x 29 x 2^56 + 1

To change the prime, edit the file mainfft5.c
The prime has to be of the form p = r 2^k + 1 with r small 2^k > 4d.
To compile the Cilk C code you will need the MIT Cilk C compiler.
First download the previous files and also the Cilk files

  fftutil8c.cilk
  mainfft5.cilk

Compile with

  make cilkfft5

Note, the Cilk C compiler that comes with gcc uses different Cilk keywords.
To run the (MIT) Cilk C code use

  ./cilkfft5 --nproc N d

Here N is the number of cores on your machine (you can use less)
and d is the degree of the polynomial P(z).  The timings for

  ./fft5 d

and

  ./cilkfft5 --nproc 1 d

will not be identical because of the Cilk overhead and changes in the
code that are needed for paralelization.  The Cilk code on 1 core
will be a bit slower than the pure C code.

Both codes create a monic polynomial P(z) of degree d then factor it
using the Tangent Graeffe method with the optimizations in our paper.
Below is sample output for d = 1000000 on our server gaby which is an
Intel Xeon E5-2680 8 core CPU running at 2.2GHz base, 3.0GHz turbo.
The line "TOTAL time =     28.040 s"  is the time for the first
run (Steps 1-9) of the Tangent Graeffe method.  It got 703,697 roots
out of 1,000,000 which is 70.3% of them.  Reported is the number 
of roots obtained in the following recursive calls.  The final total
time reported is 42.540 seconds.

Michael Monagan


*******************************  SAMPLE OUTPUT **********************

gaby 501% ./fft5 1000000
n=1000000
p := 6269010681299730433;
n-k = 0 duplicates
Lambda time = 2920 ms
roots: s = 2850816
 N=6291456  M=25165824
ROOTS :: n=1000000  k=41  s=2850816
Base time = 610 ms
Tangent Graeffe time = 15230 ms
Bluestein time = 7640 ms
Extract roots time = 970 ms
Lambda time = 2650 ms
divide time = 920 ms
TOTAL time =     28.040 s
ROOTS :: 703697 (70.4%)roots found
ROOTS :: n=296303  k=43  s=712704
ROOTS :: 196083 (66.2%)roots found
ROOTS :: n=100220  k=44  s=356352
ROOTS :: 75517 (75.4%)roots found
ROOTS :: n=24703  k=46  s=89088
ROOTS :: 18848 (76.3%)roots found
ROOTS :: n=5855  k=48  s=22272
ROOTS :: 4516 (77.1%)roots found
ROOTS :: n=1339  k=51  s=2784
ROOTS :: 831 (62.1%)roots found
ROOTS :: n=508  k=52  s=1392
ROOTS :: 363 (71.5%)roots found
ROOTS :: n=145  k=54  s=348
ROOTS :: 89 (61.4%)roots found
ROOTS :: n=56  k=55  s=174
ROOTS :: 29 of 56 roots found
ROOTS :: n=27  k=56  s=87
ROOTS :: 17 of 27 roots found
ROOTS :: n=10  k=56  s=87
ROOTS :: 10 of 10 roots found
Total roots time =     42.540 s