annotate etc/tune.c @ 145:a96ff234ff19 libtommath

propagate of fc94c38452d9fd684a8e1eb9e3a73120aac0d38f and 3e4de4cbef3d9035a7b2f0c25e9f86e297f9f6d1 from branch 'au.asn.ucc.matt.ltm-orig' to 'au.asn.ucc.matt.ltm-db'
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 15:57:19 +0000
parents d29b64170cf0
children d8254fc979e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* Tune the Karatsuba parameters
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 *
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 * Tom St Denis, [email protected]
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 */
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 #include <tommath.h>
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 #include <time.h>
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 /* how many times todo each size mult. Depends on your computer. For slow computers
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 * this can be low like 5 or 10. For fast [re: Athlon] should be 25 - 50 or so
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 */
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
11 #define TIMES (1UL<<14UL)
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 #ifndef X86_TIMER
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 /* generic ISO C timer */
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 ulong64 __T;
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 void t_start(void) { __T = clock(); }
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 ulong64 t_read(void) { return clock() - __T; }
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 #else
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 extern void t_start(void);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 extern ulong64 t_read(void);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24 #endif
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
26 ulong64 time_mult(int size, int s)
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 {
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
28 unsigned long x;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 mp_int a, b, c;
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
30 ulong64 t1;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 mp_init (&a);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 mp_init (&b);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 mp_init (&c);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
36 mp_rand (&a, size);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
37 mp_rand (&b, size);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
38
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
39 if (s == 1) {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
40 KARATSUBA_MUL_CUTOFF = size;
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
41 } else {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
42 KARATSUBA_MUL_CUTOFF = 100000;
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
43 }
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
44
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 t_start();
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
46 for (x = 0; x < TIMES; x++) {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
47 mp_mul(&a,&b,&c);
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 }
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
49 t1 = t_read();
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 mp_clear (&a);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 mp_clear (&b);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 mp_clear (&c);
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
53 return t1;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54 }
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
56 ulong64 time_sqr(int size, int s)
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 {
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
58 unsigned long x;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 mp_int a, b;
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
60 ulong64 t1;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 mp_init (&a);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 mp_init (&b);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
65 mp_rand (&a, size);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
66
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
67 if (s == 1) {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
68 KARATSUBA_SQR_CUTOFF = size;
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
69 } else {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
70 KARATSUBA_SQR_CUTOFF = 100000;
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
71 }
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
72
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73 t_start();
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
74 for (x = 0; x < TIMES; x++) {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
75 mp_sqr(&a,&b);
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 }
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
77 t1 = t_read();
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 mp_clear (&a);
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 mp_clear (&b);
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
80 return t1;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 }
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 int
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84 main (void)
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 {
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
86 ulong64 t1, t2;
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
87 int x, y;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
89 for (x = 8; ; x += 2) {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
90 t1 = time_mult(x, 0);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
91 t2 = time_mult(x, 1);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
92 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
93 if (t2 < t1) break;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 }
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
95 y = x;
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
96
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
97 for (x = 8; ; x += 2) {
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
98 t1 = time_sqr(x, 0);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
99 t2 = time_sqr(x, 1);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
100 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
101 if (t2 < t1) break;
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
102 }
142
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
103 printf("KARATSUBA_MUL_CUTOFF = %d\n", y);
d29b64170cf0 import of libtommath 0.32
Matt Johnston <matt@ucc.asn.au>
parents: 2
diff changeset
104 printf("KARATSUBA_SQR_CUTOFF = %d\n", x);
2
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
105
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
106 return 0;
86e0b50a9b58 ltm 0.30 orig import
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
107 }