michael@0: /*
michael@0:  * Simple test driver for MPI library
michael@0:  *
michael@0:  * Test 5a: Greatest common divisor speed test, binary vs. Euclid
michael@0:  *
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include <stdio.h>
michael@0: #include <stdlib.h>
michael@0: #include <string.h>
michael@0: #include <ctype.h>
michael@0: #include <limits.h>
michael@0: #include <time.h>
michael@0: 
michael@0: #include <sys/time.h>
michael@0: 
michael@0: #include "mpi.h"
michael@0: #include "mpprime.h"
michael@0: 
michael@0: typedef struct {
michael@0:   unsigned int  sec;
michael@0:   unsigned int  usec;
michael@0: } instant_t;
michael@0: 
michael@0: instant_t now(void)
michael@0: {
michael@0:   struct timeval clk;
michael@0:   instant_t      res;
michael@0: 
michael@0:   res.sec = res.usec = 0;
michael@0: 
michael@0:   if(gettimeofday(&clk, NULL) != 0)
michael@0:     return res;
michael@0: 
michael@0:   res.sec = clk.tv_sec;
michael@0:   res.usec = clk.tv_usec;
michael@0: 
michael@0:   return res;
michael@0: }
michael@0: 
michael@0: #define PRECISION 16
michael@0: 
michael@0: int main(int argc, char *argv[])
michael@0: {
michael@0:   int          ix, num, prec = PRECISION;
michael@0:   mp_int       a, b, c, d;
michael@0:   instant_t    start, finish;
michael@0:   time_t       seed;
michael@0:   unsigned int d1, d2;
michael@0: 
michael@0:   seed = time(NULL);
michael@0: 
michael@0:   if(argc < 2) {
michael@0:     fprintf(stderr, "Usage: %s <num-tests>\n", argv[0]);
michael@0:     return 1;
michael@0:   }
michael@0: 
michael@0:   if((num = atoi(argv[1])) < 0)
michael@0:     num = -num;
michael@0: 
michael@0:   printf("Test 5a: Euclid vs. Binary, a GCD speed test\n\n"
michael@0: 	 "Number of tests: %d\n"
michael@0: 	 "Precision:       %d digits\n\n", num, prec);
michael@0: 
michael@0:   mp_init_size(&a, prec);
michael@0:   mp_init_size(&b, prec);
michael@0:   mp_init(&c);
michael@0:   mp_init(&d);
michael@0: 
michael@0:   printf("Verifying accuracy ... \n");
michael@0:   srand((unsigned int)seed);
michael@0:   for(ix = 0; ix < num; ix++) {
michael@0:     mpp_random_size(&a, prec);
michael@0:     mpp_random_size(&b, prec);
michael@0: 
michael@0:     mp_gcd(&a, &b, &c);
michael@0:     mp_bgcd(&a, &b, &d);
michael@0: 
michael@0:     if(mp_cmp(&c, &d) != 0) {
michael@0:       printf("Error!  Results not accurate:\n");
michael@0:       printf("a = "); mp_print(&a, stdout); fputc('\n', stdout);
michael@0:       printf("b = "); mp_print(&b, stdout); fputc('\n', stdout);
michael@0:       printf("c = "); mp_print(&c, stdout); fputc('\n', stdout);
michael@0:       printf("d = "); mp_print(&d, stdout); fputc('\n', stdout);
michael@0: 
michael@0:       mp_clear(&a); mp_clear(&b); mp_clear(&c); mp_clear(&d);
michael@0:       return 1;
michael@0:     }
michael@0:   }
michael@0:   mp_clear(&d);
michael@0:   printf("Accuracy confirmed for the %d test samples\n", num);
michael@0: 
michael@0:   printf("Testing Euclid ... \n");
michael@0:   srand((unsigned int)seed);
michael@0:   start = now();
michael@0:   for(ix = 0; ix < num; ix++) {
michael@0:     mpp_random_size(&a, prec);
michael@0:     mpp_random_size(&b, prec);
michael@0:     mp_gcd(&a, &b, &c);
michael@0: 
michael@0:   }
michael@0:   finish = now();
michael@0: 
michael@0:   d1 = (finish.sec - start.sec) * 1000000;
michael@0:   d1 -= start.usec; d1 += finish.usec;
michael@0: 
michael@0:   printf("Testing binary ... \n");
michael@0:   srand((unsigned int)seed);
michael@0:   start = now();
michael@0:   for(ix = 0; ix < num; ix++) {
michael@0:     mpp_random_size(&a, prec);
michael@0:     mpp_random_size(&b, prec);
michael@0:     mp_bgcd(&a, &b, &c);
michael@0:   }
michael@0:   finish = now();
michael@0: 
michael@0:   d2 = (finish.sec - start.sec) * 1000000;
michael@0:   d2 -= start.usec; d2 += finish.usec;
michael@0: 
michael@0:   printf("Euclidean algorithm time: %u usec\n", d1);
michael@0:   printf("Binary algorithm time:    %u usec\n", d2);
michael@0:   printf("Improvement:              %.2f%%\n",
michael@0:          (1.0 - ((double)d2 / (double)d1)) * 100.0);
michael@0: 
michael@0:   mp_clear(&c);
michael@0:   mp_clear(&b);
michael@0:   mp_clear(&a);
michael@0: 
michael@0:   return 0;
michael@0: }