1/* compute the crossover for recursive and simple multiplication */ 2 3#include <stdio.h> 4#include <time.h> 5#include "number.h" 6#ifndef VARARGS 7#include <stdarg.h> 8#else 9#include <varargs.h> 10#endif 11 12/* from number.c ... */ 13extern int mul_base_digits; 14/* extern int mul_small_digits; */ 15extern bc_num _one_; 16 17/* global variables */ 18int test_n = 1000; 19int test_time = 30 * CLOCKS_PER_SEC; /* 30 seconds */ 20 21/* Other things for number.c. */ 22int std_only; 23 24void 25out_of_memory() 26{ 27 fprintf (stderr, "Fatal error: Out of memory for malloc.\n"); 28 exit (1); 29} 30 31/* Runtime error will print a message and stop the machine. */ 32 33#ifndef VARARGS 34#ifdef __STDC__ 35void 36rt_error (char *mesg, ...) 37#else 38void 39rt_error (mesg) 40 char *mesg; 41#endif 42#else 43void 44rt_error (mesg, va_alist) 45 char *mesg; 46#endif 47{ 48 va_list args; 49 char error_mesg [255]; 50 51#ifndef VARARGS 52 va_start (args, mesg); 53#else 54 va_start (args); 55#endif 56 vsprintf (error_mesg, mesg, args); 57 va_end (args); 58 59 fprintf (stderr, "Runtime error: %s\n", error_mesg); 60} 61 62/* A runtime warning tells of some action taken by the processor that 63 may change the program execution but was not enough of a problem 64 to stop the execution. */ 65 66#ifndef VARARGS 67#ifdef __STDC__ 68void 69rt_warn (char *mesg, ...) 70#else 71void 72rt_warn (mesg) 73 char *mesg; 74#endif 75#else 76void 77rt_warn (mesg, va_alist) 78 char *mesg; 79#endif 80{ 81 va_list args; 82 char error_mesg [255]; 83 84#ifndef VARARGS 85 va_start (args, mesg); 86#else 87 va_start (args); 88#endif 89 vsprintf (error_mesg, mesg, args); 90 va_end (args); 91 92 fprintf (stderr, "Runtime warning: %s\n", error_mesg); 93} 94 95void 96out_char (int ch) 97{ 98 putchar (ch); 99} 100 101/* Time stuff !!! */ 102 103int 104timeit ( bc_num a, bc_num b, int *n) 105{ 106 clock_t first; 107 int i, res; 108 bc_num c; 109 110 bc_init_num (&c); 111 first = clock(); 112 *n = 0; 113 do { 114 for (i=0; i<test_n; i++) 115 bc_multiply(a,b,&c,0); 116 *n += test_n; 117 res = (int) (clock() - first); 118 } while (res < test_time); 119 return res; 120} 121 122int debug = 0; /* Print debugging messages? */ 123 124int main (int argc, char **argv) 125{ 126 bc_num ten, num, expo, big; 127 128 int min, max, mid; 129 130#if 0 131 int smallsize; 132#endif 133 134 int n1, n2; 135 clock_t t1, t2; 136 float permul1, permul2; 137 138 /* args? */ 139 if (argc > 1) 140 if (strcmp (argv[1], "-d") == 0) 141 debug = 1; 142 143 bc_init_numbers(); 144 bc_init_num (&ten); 145 bc_init_num (&num); 146 bc_init_num (&expo); 147 bc_init_num (&big); 148 bc_int2num (&ten, 10); 149 150 if (debug) 151 fprintf (stderr, "Timings are for %d multiplies\n" 152 "Minimum time is %d seconds\n", test_n, 153 test_time/CLOCKS_PER_SEC); 154 155 /* Two of the same size */ 156 min = 10; 157 max = 500; 158 159 if (debug) 160 fprintf (stderr, "Testing numbers of the same length.\n"); 161 162 while (min < max) { 163 mid = (min+max)/2; 164 if (debug) fprintf (stderr,"Checking %d...\n", mid); 165 166 bc_int2num (&expo, mid); 167 bc_raise (ten, expo, &num, 0); 168 bc_sub (num, _one_, &num, 0); 169 170 mul_base_digits = 2*mid+1; 171 t1 = timeit (num, num, &n1); 172 permul1 = (float)t1/(float)n1; 173 174 mul_base_digits = 2*mid-1; 175 t2 = timeit (num, num, &n2); 176 permul2 = (float)t2/(float)n2; 177 178 if (permul1 < permul2) 179 min = mid+1; 180 else 181 max = mid-1; 182 183 if (debug) { 184 fprintf (stderr, "n1 = %d :: n2 = %d\n", n1, n2); 185 fprintf (stderr, "p1 = %f :: p2 = %f\n", permul1, permul2); 186 } 187 } 188 189 if (debug) 190 fprintf (stderr, "Base digits crossover at %d digits\n", min); 191 printf ("#define MUL_BASE_DIGITS %d\n", 2*min); 192 193 194#if 0 195 mul_base_digits = min; 196 197 /* Small one times a big one. */ 198 199 smallsize = min/2; 200 bc_int2num (&expo, smallsize); 201 bc_raise (ten, expo, &big, 0); 202 bc_sub (num, _one_, &big, 0); 203 204 min = min / 2; 205 max = 500; 206 207 if (debug) 208 fprintf (stderr, "Testing numbers of the different length.\n"); 209 210 while (min < max) { 211 mid = (min+max)/2; 212 if (debug) fprintf (stderr, "Checking %d...\n", mid); 213 214 bc_int2num (&expo, mid-smallsize); 215 bc_raise (ten, expo, &num, 0); 216 bc_sub (num, _one_, &num, 0); 217 218 mul_small_digits = mid+1; 219 t1 = timeit (big, num, &n1); 220 permul1 = (float)t1/(float)n1; 221 222 mul_small_digits = mid-1; 223 t2 = timeit (big, num, &n2); 224 permul2 = (float)t2/(float)n2; 225 226 if (permul1 < permul2) 227 min = mid+1; 228 else 229 max = mid-1; 230 231 if (debug) { 232 fprintf (stderr, "n1 = %d :: n2 = %d\n", n1, n2); 233 fprintf (stderr, "p1 = %f :: p2 = %f\n", permul1, permul2); 234 } 235 } 236 237 if (debug) 238 fprintf (stderr, "Non equal digits crossover at %d total digits\n", min); 239 printf ("#define MUL_SMALL_DIGITS = %d\n", min); 240 241#endif 242 243 return 0; 244} 245