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 */
14static 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 */
48ulong64 LBL_T;
49void t_start(void) { LBL_T = TIMFUNC(); }
50ulong64 t_read(void) { return TIMFUNC() - LBL_T; }
51
52#else
53extern void t_start(void);
54extern ulong64 t_read(void);
55#endif
56
57ulong64 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
87ulong64 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
114int
115main (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