|
2
|
1 /* Tune the Karatsuba parameters |
|
|
2 * |
|
|
3 * Tom St Denis, [email protected] |
|
|
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 */ |
|
142
|
11 #define TIMES (1UL<<14UL) |
|
2
|
12 |
|
|
13 |
|
|
14 #ifndef X86_TIMER |
|
|
15 |
|
|
16 /* generic ISO C timer */ |
|
|
17 ulong64 __T; |
|
|
18 void t_start(void) { __T = clock(); } |
|
|
19 ulong64 t_read(void) { return clock() - __T; } |
|
|
20 |
|
|
21 #else |
|
|
22 extern void t_start(void); |
|
|
23 extern ulong64 t_read(void); |
|
|
24 #endif |
|
|
25 |
|
142
|
26 ulong64 time_mult(int size, int s) |
|
2
|
27 { |
|
142
|
28 unsigned long x; |
|
2
|
29 mp_int a, b, c; |
|
142
|
30 ulong64 t1; |
|
2
|
31 |
|
|
32 mp_init (&a); |
|
|
33 mp_init (&b); |
|
|
34 mp_init (&c); |
|
|
35 |
|
142
|
36 mp_rand (&a, size); |
|
|
37 mp_rand (&b, size); |
|
|
38 |
|
|
39 if (s == 1) { |
|
|
40 KARATSUBA_MUL_CUTOFF = size; |
|
|
41 } else { |
|
|
42 KARATSUBA_MUL_CUTOFF = 100000; |
|
|
43 } |
|
|
44 |
|
2
|
45 t_start(); |
|
142
|
46 for (x = 0; x < TIMES; x++) { |
|
|
47 mp_mul(&a,&b,&c); |
|
2
|
48 } |
|
142
|
49 t1 = t_read(); |
|
2
|
50 mp_clear (&a); |
|
|
51 mp_clear (&b); |
|
|
52 mp_clear (&c); |
|
142
|
53 return t1; |
|
2
|
54 } |
|
|
55 |
|
142
|
56 ulong64 time_sqr(int size, int s) |
|
2
|
57 { |
|
142
|
58 unsigned long x; |
|
2
|
59 mp_int a, b; |
|
142
|
60 ulong64 t1; |
|
2
|
61 |
|
|
62 mp_init (&a); |
|
|
63 mp_init (&b); |
|
|
64 |
|
142
|
65 mp_rand (&a, size); |
|
|
66 |
|
|
67 if (s == 1) { |
|
|
68 KARATSUBA_SQR_CUTOFF = size; |
|
|
69 } else { |
|
|
70 KARATSUBA_SQR_CUTOFF = 100000; |
|
|
71 } |
|
|
72 |
|
2
|
73 t_start(); |
|
142
|
74 for (x = 0; x < TIMES; x++) { |
|
|
75 mp_sqr(&a,&b); |
|
2
|
76 } |
|
142
|
77 t1 = t_read(); |
|
2
|
78 mp_clear (&a); |
|
|
79 mp_clear (&b); |
|
142
|
80 return t1; |
|
2
|
81 } |
|
|
82 |
|
|
83 int |
|
|
84 main (void) |
|
|
85 { |
|
142
|
86 ulong64 t1, t2; |
|
|
87 int x, y; |
|
2
|
88 |
|
142
|
89 for (x = 8; ; x += 2) { |
|
|
90 t1 = time_mult(x, 0); |
|
|
91 t2 = time_mult(x, 1); |
|
|
92 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1); |
|
|
93 if (t2 < t1) break; |
|
2
|
94 } |
|
142
|
95 y = x; |
|
|
96 |
|
|
97 for (x = 8; ; x += 2) { |
|
|
98 t1 = time_sqr(x, 0); |
|
|
99 t2 = time_sqr(x, 1); |
|
|
100 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1); |
|
|
101 if (t2 < t1) break; |
|
2
|
102 } |
|
142
|
103 printf("KARATSUBA_MUL_CUTOFF = %d\n", y); |
|
|
104 printf("KARATSUBA_SQR_CUTOFF = %d\n", x); |
|
2
|
105 |
|
|
106 return 0; |
|
|
107 } |
