|
Packit |
70b277 |
/* compute the crossover for recursive and simple multiplication */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#include <stdio.h>
|
|
Packit |
70b277 |
#include <stdlib.h>
|
|
Packit |
70b277 |
#include <string.h>
|
|
Packit |
70b277 |
#include <time.h>
|
|
Packit |
70b277 |
#include "number.h"
|
|
Packit |
70b277 |
#ifndef VARARGS
|
|
Packit |
70b277 |
#include <stdarg.h>
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
#include <varargs.h>
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* from number.c ... */
|
|
Packit |
70b277 |
extern int mul_base_digits;
|
|
Packit |
70b277 |
/* extern int mul_small_digits; */
|
|
Packit |
70b277 |
extern bc_num _one_;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* global variables */
|
|
Packit |
70b277 |
int test_n = 1000;
|
|
Packit |
70b277 |
long test_time = 30 * CLOCKS_PER_SEC; /* 30 seconds */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* Other things for number.c. */
|
|
Packit |
70b277 |
int std_only;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
out_of_memory()
|
|
Packit |
70b277 |
{
|
|
Packit |
70b277 |
fprintf (stderr, "Fatal error: Out of memory for malloc.\n");
|
|
Packit |
70b277 |
exit (1);
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* Runtime error will print a message and stop the machine. */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#ifndef VARARGS
|
|
Packit |
70b277 |
#ifdef __STDC__
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
rt_error (char *mesg, ...)
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
rt_error (mesg)
|
|
Packit |
70b277 |
char *mesg;
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
rt_error (mesg, va_alist)
|
|
Packit |
70b277 |
char *mesg;
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
{
|
|
Packit |
70b277 |
va_list args;
|
|
Packit |
70b277 |
char error_mesg [255];
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#ifndef VARARGS
|
|
Packit |
70b277 |
va_start (args, mesg);
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
va_start (args);
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
vsprintf (error_mesg, mesg, args);
|
|
Packit |
70b277 |
va_end (args);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
fprintf (stderr, "Runtime error: %s\n", error_mesg);
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* A runtime warning tells of some action taken by the processor that
|
|
Packit |
70b277 |
may change the program execution but was not enough of a problem
|
|
Packit |
70b277 |
to stop the execution. */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#ifndef VARARGS
|
|
Packit |
70b277 |
#ifdef __STDC__
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
rt_warn (char *mesg, ...)
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
rt_warn (mesg)
|
|
Packit |
70b277 |
char *mesg;
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
rt_warn (mesg, va_alist)
|
|
Packit |
70b277 |
char *mesg;
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
{
|
|
Packit |
70b277 |
va_list args;
|
|
Packit |
70b277 |
char error_mesg [255];
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#ifndef VARARGS
|
|
Packit |
70b277 |
va_start (args, mesg);
|
|
Packit |
70b277 |
#else
|
|
Packit |
70b277 |
va_start (args);
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
vsprintf (error_mesg, mesg, args);
|
|
Packit |
70b277 |
va_end (args);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
fprintf (stderr, "Runtime warning: %s\n", error_mesg);
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
void
|
|
Packit |
70b277 |
out_char (int ch)
|
|
Packit |
70b277 |
{
|
|
Packit |
70b277 |
putchar (ch);
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* Time stuff !!! */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
int
|
|
Packit |
70b277 |
timeit ( bc_num a, bc_num b, int *n)
|
|
Packit |
70b277 |
{
|
|
Packit |
70b277 |
clock_t first;
|
|
Packit |
70b277 |
int i, res;
|
|
Packit |
70b277 |
bc_num c;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
bc_init_num (&c);
|
|
Packit |
70b277 |
first = clock();
|
|
Packit |
70b277 |
*n = 0;
|
|
Packit |
70b277 |
do {
|
|
Packit |
70b277 |
for (i=0; i
|
|
Packit |
70b277 |
bc_multiply(a,b,&c,0);
|
|
Packit |
70b277 |
*n += test_n;
|
|
Packit |
70b277 |
res = (int) (clock() - first);
|
|
Packit |
70b277 |
} while (res < test_time);
|
|
Packit |
70b277 |
return res;
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
int debug = 0; /* Print debugging messages? */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
int main (int argc, char **argv)
|
|
Packit |
70b277 |
{
|
|
Packit |
70b277 |
bc_num ten, num, expo, big;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
int min, max, mid;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#if 0
|
|
Packit |
70b277 |
int smallsize;
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
int n1, n2;
|
|
Packit |
70b277 |
clock_t t1, t2;
|
|
Packit |
70b277 |
float permul1, permul2;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* args? */
|
|
Packit |
70b277 |
if (argc > 1)
|
|
Packit |
70b277 |
if (strcmp (argv[1], "-d") == 0)
|
|
Packit |
70b277 |
debug = 1;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
bc_init_numbers();
|
|
Packit |
70b277 |
bc_init_num (&ten;;
|
|
Packit |
70b277 |
bc_init_num (&num);
|
|
Packit |
70b277 |
bc_init_num (&expo);
|
|
Packit |
70b277 |
bc_init_num (&big);
|
|
Packit |
70b277 |
bc_int2num (&ten, 10);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug)
|
|
Packit |
70b277 |
fprintf (stderr, "Timings are for %d multiplies\n"
|
|
Packit |
70b277 |
"Minimum time is %lu seconds\n", test_n,
|
|
Packit |
70b277 |
test_time/CLOCKS_PER_SEC);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* Two of the same size */
|
|
Packit |
70b277 |
min = 10;
|
|
Packit |
70b277 |
max = 500;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug)
|
|
Packit |
70b277 |
fprintf (stderr, "Testing numbers of the same length.\n");
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
while (min < max) {
|
|
Packit |
70b277 |
mid = (min+max)/2;
|
|
Packit |
70b277 |
if (debug) fprintf (stderr,"Checking %d...\n", mid);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
bc_int2num (&expo, mid);
|
|
Packit |
70b277 |
bc_raise (ten, expo, &num, 0);
|
|
Packit |
70b277 |
bc_sub (num, _one_, &num, 0);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
mul_base_digits = 2*mid+1;
|
|
Packit |
70b277 |
t1 = timeit (num, num, &n1;;
|
|
Packit |
70b277 |
permul1 = (float)t1/(float)n1;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
mul_base_digits = 2*mid-1;
|
|
Packit |
70b277 |
t2 = timeit (num, num, &n2;;
|
|
Packit |
70b277 |
permul2 = (float)t2/(float)n2;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (permul1 < permul2)
|
|
Packit |
70b277 |
min = mid+1;
|
|
Packit |
70b277 |
else
|
|
Packit |
70b277 |
max = mid-1;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug) {
|
|
Packit |
70b277 |
fprintf (stderr, "n1 = %d :: n2 = %d\n", n1, n2);
|
|
Packit |
70b277 |
fprintf (stderr, "p1 = %f :: p2 = %f\n", permul1, permul2);
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug)
|
|
Packit |
70b277 |
fprintf (stderr, "Base digits crossover at %d digits\n", min);
|
|
Packit |
70b277 |
printf ("#define MUL_BASE_DIGITS %d\n", 2*min);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#if 0
|
|
Packit |
70b277 |
mul_base_digits = min;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
/* Small one times a big one. */
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
smallsize = min/2;
|
|
Packit |
70b277 |
bc_int2num (&expo, smallsize);
|
|
Packit |
70b277 |
bc_raise (ten, expo, &big, 0);
|
|
Packit |
70b277 |
bc_sub (num, _one_, &big, 0);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
min = min / 2;
|
|
Packit |
70b277 |
max = 500;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug)
|
|
Packit |
70b277 |
fprintf (stderr, "Testing numbers of the different length.\n");
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
while (min < max) {
|
|
Packit |
70b277 |
mid = (min+max)/2;
|
|
Packit |
70b277 |
if (debug) fprintf (stderr, "Checking %d...\n", mid);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
bc_int2num (&expo, mid-smallsize);
|
|
Packit |
70b277 |
bc_raise (ten, expo, &num, 0);
|
|
Packit |
70b277 |
bc_sub (num, _one_, &num, 0);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
mul_small_digits = mid+1;
|
|
Packit |
70b277 |
t1 = timeit (big, num, &n1;;
|
|
Packit |
70b277 |
permul1 = (float)t1/(float)n1;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
mul_small_digits = mid-1;
|
|
Packit |
70b277 |
t2 = timeit (big, num, &n2;;
|
|
Packit |
70b277 |
permul2 = (float)t2/(float)n2;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (permul1 < permul2)
|
|
Packit |
70b277 |
min = mid+1;
|
|
Packit |
70b277 |
else
|
|
Packit |
70b277 |
max = mid-1;
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug) {
|
|
Packit |
70b277 |
fprintf (stderr, "n1 = %d :: n2 = %d\n", n1, n2);
|
|
Packit |
70b277 |
fprintf (stderr, "p1 = %f :: p2 = %f\n", permul1, permul2);
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
}
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
if (debug)
|
|
Packit |
70b277 |
fprintf (stderr, "Non equal digits crossover at %d total digits\n", min);
|
|
Packit |
70b277 |
printf ("#define MUL_SMALL_DIGITS = %d\n", min);
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
#endif
|
|
Packit |
70b277 |
|
|
Packit |
70b277 |
return 0;
|
|
Packit |
70b277 |
}
|