diff etc/tune.c @ 1:22d5cf7d4b1a libtommath

Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children d29b64170cf0
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/etc/tune.c	Mon May 31 18:23:46 2004 +0000
@@ -0,0 +1,176 @@
+/* Tune the Karatsuba parameters
+ *
+ * Tom St Denis, [email protected]
+ */
+#include <tommath.h>
+#include <time.h>
+
+/* how many times todo each size mult.  Depends on your computer.  For slow computers
+ * this can be low like 5 or 10.  For fast [re: Athlon] should be 25 - 50 or so 
+ */
+#define TIMES 50
+
+
+#ifndef X86_TIMER
+
+/* generic ISO C timer */
+ulong64 __T;
+void t_start(void) { __T = clock(); }
+ulong64 t_read(void) { return clock() - __T; }
+
+#else
+extern void t_start(void);
+extern ulong64 t_read(void);
+#endif
+
+ulong64
+time_mult (int max)
+{
+  int     x, y;
+  mp_int  a, b, c;
+
+  mp_init (&a);
+  mp_init (&b);
+  mp_init (&c);
+
+  t_start();
+  for (x = 32; x <= max; x += 4) {
+    mp_rand (&a, x);
+    mp_rand (&b, x);
+    for (y = 0; y < TIMES; y++) {
+      mp_mul (&a, &b, &c);
+    }
+  }
+  mp_clear (&a);
+  mp_clear (&b);
+  mp_clear (&c);
+  return t_read();
+}
+
+ulong64
+time_sqr (int max)
+{
+  int     x, y;
+  mp_int  a, b;
+
+  mp_init (&a);
+  mp_init (&b);
+
+  t_start();
+  for (x = 32; x <= max; x += 4) {
+    mp_rand (&a, x);
+    for (y = 0; y < TIMES; y++) {
+      mp_sqr (&a, &b);
+    }
+  }
+  mp_clear (&a);
+  mp_clear (&b);
+  return t_read();
+}
+
+int
+main (void)
+{
+  int     best_kmult, best_tmult, best_ksquare, best_tsquare, counter;
+  ulong64 best, ti;
+  FILE   *log;
+
+  best_kmult = best_ksquare = best_tmult = best_tsquare = 0;
+  /* tune multiplication first */
+  
+  /* effectively turn TOOM off */
+  TOOM_SQR_CUTOFF = TOOM_MUL_CUTOFF = 100000;
+    
+  log = fopen ("mult.log", "w");
+  best = -1;
+  counter = 16;
+  for (KARATSUBA_MUL_CUTOFF = 8; KARATSUBA_MUL_CUTOFF <= 200; KARATSUBA_MUL_CUTOFF++) {
+    ti = time_mult (300);
+    printf ("%4d : %9llu            \r", KARATSUBA_MUL_CUTOFF, ti);
+    fprintf (log, "%d, %llu\n", KARATSUBA_MUL_CUTOFF, ti);
+    fflush (stdout);
+    if (ti < best) {
+      printf ("New best: %llu, %d         \r", ti, KARATSUBA_MUL_CUTOFF);
+      best = ti;
+      best_kmult = KARATSUBA_MUL_CUTOFF;
+      counter = 16;
+    } else if (--counter == 0) {
+       printf("No better found in 16 trials.\n");
+       break;
+    }
+  }
+  fclose (log);
+  printf("Karatsuba Multiplier Cutoff (KARATSUBA_MUL_CUTOFF) == %d\n", best_kmult);
+  
+  /* tune squaring */
+  log = fopen ("sqr.log", "w");
+  best = -1;
+  counter = 16;
+  for (KARATSUBA_SQR_CUTOFF = 8; KARATSUBA_SQR_CUTOFF <= 200; KARATSUBA_SQR_CUTOFF++) {
+    ti = time_sqr (300);
+    printf ("%4d : %9llu             \r", KARATSUBA_SQR_CUTOFF, ti);
+    fprintf (log, "%d, %llu\n", KARATSUBA_SQR_CUTOFF, ti);
+    fflush (stdout);
+    if (ti < best) {
+      printf ("New best: %llu, %d         \r", ti, KARATSUBA_SQR_CUTOFF);
+      best = ti;
+      best_ksquare = KARATSUBA_SQR_CUTOFF;
+      counter = 16;
+    } else if (--counter == 0) {
+       printf("No better found in 16 trials.\n");
+       break;
+    }
+  }
+  fclose (log);
+  printf("Karatsuba Squaring Cutoff (KARATSUBA_SQR_CUTOFF) == %d\n", best_ksquare);
+  
+  KARATSUBA_MUL_CUTOFF = best_kmult;
+  KARATSUBA_SQR_CUTOFF = best_ksquare;
+    
+  /* tune TOOM mult */
+  counter = 16;
+  log = fopen ("tmult.log", "w");
+  best = -1;
+  for (TOOM_MUL_CUTOFF = best_kmult*5; TOOM_MUL_CUTOFF <= 800; TOOM_MUL_CUTOFF++) {
+    ti = time_mult (1200);
+    printf ("%4d : %9llu          \r", TOOM_MUL_CUTOFF, ti);
+    fprintf (log, "%d, %llu\n", TOOM_MUL_CUTOFF, ti);
+    fflush (stdout);
+    if (ti < best) {
+      printf ("New best: %llu, %d         \r", ti, TOOM_MUL_CUTOFF);
+      best = ti;
+      best_tmult = TOOM_MUL_CUTOFF;
+      counter = 16;
+    } else if (--counter == 0) {
+       printf("No better found in 16 trials.\n");
+       break;
+    }
+  }
+  fclose (log);   
+  printf("Toom-Cook Multiplier Cutoff (TOOM_MUL_CUTOFF) == %d\n", best_tmult);
+  
+  /* tune TOOM sqr */
+  log = fopen ("tsqr.log", "w");
+  best = -1;
+  counter = 16;
+  for (TOOM_SQR_CUTOFF = best_ksquare*3; TOOM_SQR_CUTOFF <= 800; TOOM_SQR_CUTOFF++) {
+    ti = time_sqr (1200);
+    printf ("%4d : %9llu           \r", TOOM_SQR_CUTOFF, ti);
+    fprintf (log, "%d, %llu\n", TOOM_SQR_CUTOFF, ti);
+    fflush (stdout);
+    if (ti < best) {
+      printf ("New best: %llu, %d         \r", ti, TOOM_SQR_CUTOFF);
+      best = ti;
+      best_tsquare = TOOM_SQR_CUTOFF;
+      counter = 16;
+    } else if (--counter == 0) {
+       printf("No better found in 16 trials.\n");
+       break;
+    }
+  }
+  fclose (log);   
+  printf("Toom-Cook Squaring Cutoff (TOOM_SQR_CUTOFF) == %d\n", best_tsquare);
+
+
+  return 0;
+}