• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* Tune the Karatsuba parameters
2  *
3  * Tom St Denis, tomstdenis@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 */
TIMFUNC(void)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;
t_start(void)49 void t_start(void) { LBL_T = TIMFUNC(); }
t_read(void)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 
time_mult(int size,int s)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 
time_sqr(int size,int s)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
main(void)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