Mercurial > dropbear

comparison etc/tune.c @ 142:d29b64170cf0 libtommath-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents 86e0b50a9b58
children d8254fc979e9
comparison
equal deleted inserted replaced
19:e1037a1e12e7 142:d29b64170cf0
6 #include <time.h> 6 #include <time.h>
7 7
8 /* how many times todo each size mult. Depends on your computer. For slow computers 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 9 * this can be low like 5 or 10. For fast [re: Athlon] should be 25 - 50 or so
10 */ 10 */
11 #define TIMES 50 11 #define TIMES (1UL<<14UL)
12 12
13 13
14 #ifndef X86_TIMER 14 #ifndef X86_TIMER
15 15
16 /* generic ISO C timer */ 16 /* generic ISO C timer */
21 #else 21 #else
22 extern void t_start(void); 22 extern void t_start(void);
23 extern ulong64 t_read(void); 23 extern ulong64 t_read(void);
24 #endif 24 #endif
25 25
26 ulong64 26 ulong64 time_mult(int size, int s)
27 time_mult (int max)
28 { 27 {
29 int x, y; 28 unsigned long x;
30 mp_int a, b, c; 29 mp_int a, b, c;
30 ulong64 t1;
31 31
32 mp_init (&a); 32 mp_init (&a);
33 mp_init (&b); 33 mp_init (&b);
34 mp_init (&c); 34 mp_init (&c);
35 35
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
36 t_start(); 45 t_start();
37 for (x = 32; x <= max; x += 4) { 46 for (x = 0; x < TIMES; x++) {
38 mp_rand (&a, x); 47 mp_mul(&a,&b,&c);
39 mp_rand (&b, x);
40 for (y = 0; y < TIMES; y++) {
41 mp_mul (&a, &b, &c);
42 }
43 } 48 }
49 t1 = t_read();
44 mp_clear (&a); 50 mp_clear (&a);
45 mp_clear (&b); 51 mp_clear (&b);
46 mp_clear (&c); 52 mp_clear (&c);
47 return t_read(); 53 return t1;
48 } 54 }
49 55
50 ulong64 56 ulong64 time_sqr(int size, int s)
51 time_sqr (int max)
52 { 57 {
53 int x, y; 58 unsigned long x;
54 mp_int a, b; 59 mp_int a, b;
60 ulong64 t1;
55 61
56 mp_init (&a); 62 mp_init (&a);
57 mp_init (&b); 63 mp_init (&b);
58 64
65 mp_rand (&a, size);
66
67 if (s == 1) {
68 KARATSUBA_SQR_CUTOFF = size;
69 } else {
70 KARATSUBA_SQR_CUTOFF = 100000;
71 }
72
59 t_start(); 73 t_start();
60 for (x = 32; x <= max; x += 4) { 74 for (x = 0; x < TIMES; x++) {
61 mp_rand (&a, x); 75 mp_sqr(&a,&b);
62 for (y = 0; y < TIMES; y++) {
63 mp_sqr (&a, &b);
64 }
65 } 76 }
77 t1 = t_read();
66 mp_clear (&a); 78 mp_clear (&a);
67 mp_clear (&b); 79 mp_clear (&b);
68 return t_read(); 80 return t1;
69 } 81 }
70 82
71 int 83 int
72 main (void) 84 main (void)
73 { 85 {
74 int best_kmult, best_tmult, best_ksquare, best_tsquare, counter; 86 ulong64 t1, t2;
75 ulong64 best, ti; 87 int x, y;
76 FILE *log;
77 88
78 best_kmult = best_ksquare = best_tmult = best_tsquare = 0; 89 for (x = 8; ; x += 2) {
79 /* tune multiplication first */ 90 t1 = time_mult(x, 0);
80 91 t2 = time_mult(x, 1);
81 /* effectively turn TOOM off */ 92 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
82 TOOM_SQR_CUTOFF = TOOM_MUL_CUTOFF = 100000; 93 if (t2 < t1) break;
83
84 log = fopen ("mult.log", "w");
85 best = -1;
86 counter = 16;
87 for (KARATSUBA_MUL_CUTOFF = 8; KARATSUBA_MUL_CUTOFF <= 200; KARATSUBA_MUL_CUTOFF++) {
88 ti = time_mult (300);
89 printf ("%4d : %9llu \r", KARATSUBA_MUL_CUTOFF, ti);
90 fprintf (log, "%d, %llu\n", KARATSUBA_MUL_CUTOFF, ti);
91 fflush (stdout);
92 if (ti < best) {
93 printf ("New best: %llu, %d \r", ti, KARATSUBA_MUL_CUTOFF);
94 best = ti;
95 best_kmult = KARATSUBA_MUL_CUTOFF;
96 counter = 16;
97 } else if (--counter == 0) {
98 printf("No better found in 16 trials.\n");
99 break;
100 }
101 } 94 }
102 fclose (log); 95 y = x;
103 printf("Karatsuba Multiplier Cutoff (KARATSUBA_MUL_CUTOFF) == %d\n", best_kmult); 96
104 97 for (x = 8; ; x += 2) {
105 /* tune squaring */ 98 t1 = time_sqr(x, 0);
106 log = fopen ("sqr.log", "w"); 99 t2 = time_sqr(x, 1);
107 best = -1; 100 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
108 counter = 16; 101 if (t2 < t1) break;
109 for (KARATSUBA_SQR_CUTOFF = 8; KARATSUBA_SQR_CUTOFF <= 200; KARATSUBA_SQR_CUTOFF++) {
110 ti = time_sqr (300);
111 printf ("%4d : %9llu \r", KARATSUBA_SQR_CUTOFF, ti);
112 fprintf (log, "%d, %llu\n", KARATSUBA_SQR_CUTOFF, ti);
113 fflush (stdout);
114 if (ti < best) {
115 printf ("New best: %llu, %d \r", ti, KARATSUBA_SQR_CUTOFF);
116 best = ti;
117 best_ksquare = KARATSUBA_SQR_CUTOFF;
118 counter = 16;
119 } else if (--counter == 0) {
120 printf("No better found in 16 trials.\n");
121 break;
122 }
123 } 102 }
124 fclose (log); 103 printf("KARATSUBA_MUL_CUTOFF = %d\n", y);
125 printf("Karatsuba Squaring Cutoff (KARATSUBA_SQR_CUTOFF) == %d\n", best_ksquare); 104 printf("KARATSUBA_SQR_CUTOFF = %d\n", x);
126
127 KARATSUBA_MUL_CUTOFF = best_kmult;
128 KARATSUBA_SQR_CUTOFF = best_ksquare;
129
130 /* tune TOOM mult */
131 counter = 16;
132 log = fopen ("tmult.log", "w");
133 best = -1;
134 for (TOOM_MUL_CUTOFF = best_kmult*5; TOOM_MUL_CUTOFF <= 800; TOOM_MUL_CUTOFF++) {
135 ti = time_mult (1200);
136 printf ("%4d : %9llu \r", TOOM_MUL_CUTOFF, ti);
137 fprintf (log, "%d, %llu\n", TOOM_MUL_CUTOFF, ti);
138 fflush (stdout);
139 if (ti < best) {
140 printf ("New best: %llu, %d \r", ti, TOOM_MUL_CUTOFF);
141 best = ti;
142 best_tmult = TOOM_MUL_CUTOFF;
143 counter = 16;
144 } else if (--counter == 0) {
145 printf("No better found in 16 trials.\n");
146 break;
147 }
148 }
149 fclose (log);
150 printf("Toom-Cook Multiplier Cutoff (TOOM_MUL_CUTOFF) == %d\n", best_tmult);
151
152 /* tune TOOM sqr */
153 log = fopen ("tsqr.log", "w");
154 best = -1;
155 counter = 16;
156 for (TOOM_SQR_CUTOFF = best_ksquare*3; TOOM_SQR_CUTOFF <= 800; TOOM_SQR_CUTOFF++) {
157 ti = time_sqr (1200);
158 printf ("%4d : %9llu \r", TOOM_SQR_CUTOFF, ti);
159 fprintf (log, "%d, %llu\n", TOOM_SQR_CUTOFF, ti);
160 fflush (stdout);
161 if (ti < best) {
162 printf ("New best: %llu, %d \r", ti, TOOM_SQR_CUTOFF);
163 best = ti;
164 best_tsquare = TOOM_SQR_CUTOFF;
165 counter = 16;
166 } else if (--counter == 0) {
167 printf("No better found in 16 trials.\n");
168 break;
169 }
170 }
171 fclose (log);
172 printf("Toom-Cook Squaring Cutoff (TOOM_SQR_CUTOFF) == %d\n", best_tsquare);
173
174 105
175 return 0; 106 return 0;
176 } 107 }