Home | History | Annotate | Download | only in etc 
      1 /* Tune the Karatsuba parameters
      2  *
      3  * Tom St Denis, tomstdenis (at) gmail.com
      4  */
      5 #include <tommath.h>
      6 #include <time.h>
      7 
      8 /* how many times todo each size mult.  Depends on your computer.  For slow computers
      9  * this can be low like 5 or 10.  For fast [re: Athlon] should be 25 - 50 or so
     10  */
     11 #define TIMES (1UL<<14UL)
     12 
     13 /* RDTSC from Scott Duplichan */
     14 static ulong64 TIMFUNC (void)
     15    {
     16    #if defined __GNUC__
     17       #if defined(__i386__) || defined(__x86_64__)
     18          unsigned long long a;
     19          __asm__ __volatile__ ("rdtsc\nmovl %%eax,%0\nmovl %%edx,4+%0\n"::"m"(a):"%eax","%edx");
     20          return a;
     21       #else /* gcc-IA64 version */
     22          unsigned long result;
     23          __asm__ __volatile__("mov %0=ar.itc" : "=r"(result) :: "memory");
     24          while (__builtin_expect ((int) result == -1, 0))
     25          __asm__ __volatile__("mov %0=ar.itc" : "=r"(result) :: "memory");
     26          return result;
     27       #endif
     28 
     29    // Microsoft and Intel Windows compilers
     30    #elif defined _M_IX86
     31      __asm rdtsc
     32    #elif defined _M_AMD64
     33      return __rdtsc ();
     34    #elif defined _M_IA64
     35      #if defined __INTEL_COMPILER
     36        #include <ia64intrin.h>
     37      #endif
     38       return __getReg (3116);
     39    #else
     40      #error need rdtsc function for this build
     41    #endif
     42    }
     43 
     44 
     45 #ifndef X86_TIMER
     46 
     47 /* generic ISO C timer */
     48 ulong64 LBL_T;
     49 void t_start(void) { LBL_T = TIMFUNC(); }
     50 ulong64 t_read(void) { return TIMFUNC() - LBL_T; }
     51 
     52 #else
     53 extern void t_start(void);
     54 extern ulong64 t_read(void);
     55 #endif
     56 
     57 ulong64 time_mult(int size, int s)
     58 {
     59   unsigned long     x;
     60   mp_int  a, b, c;
     61   ulong64 t1;
     62 
     63   mp_init (&a);
     64   mp_init (&b);
     65   mp_init (&c);
     66 
     67   mp_rand (&a, size);
     68   mp_rand (&b, size);
     69 
     70   if (s == 1) {
     71       KARATSUBA_MUL_CUTOFF = size;
     72   } else {
     73       KARATSUBA_MUL_CUTOFF = 100000;
     74   }
     75 
     76   t_start();
     77   for (x = 0; x < TIMES; x++) {
     78       mp_mul(&a,&b,&c);
     79   }
     80   t1 = t_read();
     81   mp_clear (&a);
     82   mp_clear (&b);
     83   mp_clear (&c);
     84   return t1;
     85 }
     86 
     87 ulong64 time_sqr(int size, int s)
     88 {
     89   unsigned long     x;
     90   mp_int  a, b;
     91   ulong64 t1;
     92 
     93   mp_init (&a);
     94   mp_init (&b);
     95 
     96   mp_rand (&a, size);
     97 
     98   if (s == 1) {
     99       KARATSUBA_SQR_CUTOFF = size;
    100   } else {
    101       KARATSUBA_SQR_CUTOFF = 100000;
    102   }
    103 
    104   t_start();
    105   for (x = 0; x < TIMES; x++) {
    106       mp_sqr(&a,&b);
    107   }
    108   t1 = t_read();
    109   mp_clear (&a);
    110   mp_clear (&b);
    111   return t1;
    112 }
    113 
    114 int
    115 main (void)
    116 {
    117   ulong64 t1, t2;
    118   int x, y;
    119 
    120   for (x = 8; ; x += 2) {
    121      t1 = time_mult(x, 0);
    122      t2 = time_mult(x, 1);
    123      printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
    124      if (t2 < t1) break;
    125   }
    126   y = x;
    127 
    128   for (x = 8; ; x += 2) {
    129      t1 = time_sqr(x, 0);
    130      t2 = time_sqr(x, 1);
    131      printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
    132      if (t2 < t1) break;
    133   }
    134   printf("KARATSUBA_MUL_CUTOFF = %d\n", y);
    135   printf("KARATSUBA_SQR_CUTOFF = %d\n", x);
    136 
    137   return 0;
    138 }
    139 
    140 /* $Source: /cvs/libtom/libtommath/etc/tune.c,v $ */
    141 /* $Revision: 1.3 $ */
    142 /* $Date: 2006/03/31 14:18:47 $ */
    143