/*
     MAIN.C
*/
/*
** This file is placed into the public domain by its author,
** Carey Bloodworth (Carey@Bloodworth.org) on July 16, 2001
**
** This multiplication demo is not designed for high performance.
** It's a tutorial program designed to be used with the information
** on my web site at www.Bloodworth.org
*/
/*
** This is the main routine for all of the multiplication demo
** files.  Just compile and link together this file and the
** one you are interested in.  For example, for the right angle
** file, using GNU C, you'd do:
**
** gcc main.c right.c -o right.exe
**
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 


/*
#define VERY_SLOW_VERIFY
** Use a slow schoolboy to verify the answer?
** Without it, we'll use 9's for our number which allows a
** very quick check.  However, since all the digits are the
** same, it allows for slop in the computation to slip through.
** Making the routine look like it's reliable at longer lengths
** than it really is.
**
** This is mostly done for my own testing purposes.  It is
** very slow.
*/

/*
#define NO_VERIFY
** Don't verify at all.  Just do random digits so we can see
** the 'average' error rate.
*/


#define MAX_NUM_LEN (131072)
/* The length of our number, in BASE_DIGit's */

/* These define our base, and the digits for testing. */
/*
** Just to keep things nice and portable among all these
** different versions, I'll never do more than 4 decimals.
*/
#if 0
#define BASE       10000.0
#define BASE_DIG   4
#endif
#if 0
#define BASE       100.0
#define BASE_DIG   2
#endif
/* The FGT, NTT31 and Mont31 can only handle a single digit, so... */
#if 0
#define BASE       10.0
#define BASE_DIG   1
#endif
/* Schonhage-Strassen needs a simple binary base */
#if 1
#define BASE       16.0
#define BASE_DIG   1
#endif


#define MAXDIG    (BASE - 1.0)
#define CROSSDIG  (BASE - 2.0)

typedef short int Short;


extern void InitFFT(unsigned long int Len, int Base, int BaseDig);
extern void DeInitFFT(unsigned long int Len);
extern void FFTMul(Short * Prod, Short * Num1, Short * Num2,int Len);
double MaxFFTError=-BASE;



void DumpShort(char *str,Short *data,int size)
{int x;
printf("%s\n",str);
for (x=0;x Start) Start=k-size+1;
    if (size-1 < End) End=size-1;
    for (i=Start;i<=End;i++)
      Sum+=Num1[size-1- i]*Num2[size-1- (k-i)];
    Temp=floor(Sum / BASE);
    Dig=Sum-Temp*BASE;
    if (Dig != Prod[size*2-1-k])
      {
       DumpShort("Prod:",Prod,size*2);
       FatalError("Product is wrong. pos=%d right=%d dig=%d sum=%f\n",
                  k,Prod[size*2-1-k],Dig,Sum);
      }
    Sum=Temp;
   }
}
#else
/* Test the results */
/* 9999...999^2 = 9999..998000...0001 */
for (i=0;i