|
Packit |
5c3484 |
/* tune-gcd-p
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Tune the choice for splitting p in divide-and-conquer gcd.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2008, 2010, 2011 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is free software; you can redistribute it and/or modify
|
|
Packit |
5c3484 |
it under the terms of either:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit |
5c3484 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit |
5c3484 |
option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU General Public License as published by the Free Software
|
|
Packit |
5c3484 |
Foundation; either version 2 of the License, or (at your option) any
|
|
Packit |
5c3484 |
later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or both in parallel, as here.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is distributed in the hope that it will be useful, but
|
|
Packit |
5c3484 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
Packit |
5c3484 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
5c3484 |
for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received copies of the GNU General Public License and the
|
|
Packit |
5c3484 |
GNU Lesser General Public License along with the GNU MP Library. If not,
|
|
Packit |
5c3484 |
see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define TUNE_GCD_P 1
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "../mpn/gcd.c"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include <stdio.h>
|
|
Packit |
5c3484 |
#include <stdlib.h>
|
|
Packit |
5c3484 |
#include <string.h>
|
|
Packit |
5c3484 |
#include <time.h>
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "speed.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Search for minimum over a range. FIXME: Implement golden-section /
|
|
Packit |
5c3484 |
fibonacci search*/
|
|
Packit |
5c3484 |
static int
|
|
Packit |
5c3484 |
search (double *minp, double (*f)(void *, int), void *ctx, int start, int end)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
int x[4];
|
|
Packit |
5c3484 |
double y[4];
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
int best_i;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
x[0] = start;
|
|
Packit |
5c3484 |
x[3] = end;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
y[0] = f(ctx, x[0]);
|
|
Packit |
5c3484 |
y[3] = f(ctx, x[3]);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (;;)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
int i;
|
|
Packit |
5c3484 |
int length = x[3] - x[0];
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
x[1] = x[0] + length/3;
|
|
Packit |
5c3484 |
x[2] = x[0] + 2*length/3;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
y[1] = f(ctx, x[1]);
|
|
Packit |
5c3484 |
y[2] = f(ctx, x[2]);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if 0
|
|
Packit |
5c3484 |
printf("%d: %f, %d: %f, %d:, %f %d: %f\n",
|
|
Packit |
5c3484 |
x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]);
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
for (best_i = 0, i = 1; i < 4; i++)
|
|
Packit |
5c3484 |
if (y[i] < y[best_i])
|
|
Packit |
5c3484 |
best_i = i;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (length <= 4)
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (best_i >= 2)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
x[0] = x[1];
|
|
Packit |
5c3484 |
y[0] = y[1];
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
x[3] = x[2];
|
|
Packit |
5c3484 |
y[3] = y[2];
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
*minp = y[best_i];
|
|
Packit |
5c3484 |
return x[best_i];
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
static int
|
|
Packit |
5c3484 |
compare_double(const void *ap, const void *bp)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
double a = * (const double *) ap;
|
|
Packit |
5c3484 |
double b = * (const double *) bp;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (a < b)
|
|
Packit |
5c3484 |
return -1;
|
|
Packit |
5c3484 |
else if (a > b)
|
|
Packit |
5c3484 |
return 1;
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
return 0;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
static double
|
|
Packit |
5c3484 |
median (double *v, size_t n)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
qsort(v, n, sizeof(*v), compare_double);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
return v[n/2];
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define TIME(res, code) do { \
|
|
Packit |
5c3484 |
double time_measurement[5]; \
|
|
Packit |
5c3484 |
unsigned time_i; \
|
|
Packit |
5c3484 |
\
|
|
Packit |
5c3484 |
for (time_i = 0; time_i < 5; time_i++) \
|
|
Packit |
5c3484 |
{ \
|
|
Packit |
5c3484 |
speed_starttime(); \
|
|
Packit |
5c3484 |
code; \
|
|
Packit |
5c3484 |
time_measurement[time_i] = speed_endtime(); \
|
|
Packit |
5c3484 |
} \
|
|
Packit |
5c3484 |
res = median(time_measurement, 5); \
|
|
Packit |
5c3484 |
} while (0)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
struct bench_data
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_size_t n;
|
|
Packit |
5c3484 |
mp_ptr ap;
|
|
Packit |
5c3484 |
mp_ptr bp;
|
|
Packit |
5c3484 |
mp_ptr up;
|
|
Packit |
5c3484 |
mp_ptr vp;
|
|
Packit |
5c3484 |
mp_ptr gp;
|
|
Packit |
5c3484 |
};
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
static double
|
|
Packit |
5c3484 |
bench_gcd (void *ctx, int p)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
struct bench_data *data = (struct bench_data *) ctx;
|
|
Packit |
5c3484 |
double t;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
p_table[data->n] = p;
|
|
Packit |
5c3484 |
TIME(t, {
|
|
Packit |
5c3484 |
MPN_COPY (data->up, data->ap, data->n);
|
|
Packit |
5c3484 |
MPN_COPY (data->vp, data->bp, data->n);
|
|
Packit |
5c3484 |
mpn_gcd (data->gp, data->up, data->n, data->vp, data->n);
|
|
Packit |
5c3484 |
});
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
return t;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
int
|
|
Packit |
5c3484 |
main(int argc, char **argv)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
gmp_randstate_t rands; struct bench_data data;
|
|
Packit |
5c3484 |
mp_size_t n;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
TMP_DECL;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Unbuffered so if output is redirected to a file it isn't lost if the
|
|
Packit |
5c3484 |
program is killed part way through. */
|
|
Packit |
5c3484 |
setbuf (stdout, NULL);
|
|
Packit |
5c3484 |
setbuf (stderr, NULL);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
gmp_randinit_default (rands);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
TMP_MARK;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
data.ap = TMP_ALLOC_LIMBS (P_TABLE_SIZE);
|
|
Packit |
5c3484 |
data.bp = TMP_ALLOC_LIMBS (P_TABLE_SIZE);
|
|
Packit |
5c3484 |
data.up = TMP_ALLOC_LIMBS (P_TABLE_SIZE);
|
|
Packit |
5c3484 |
data.vp = TMP_ALLOC_LIMBS (P_TABLE_SIZE);
|
|
Packit |
5c3484 |
data.gp = TMP_ALLOC_LIMBS (P_TABLE_SIZE);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mpn_random (data.ap, P_TABLE_SIZE);
|
|
Packit |
5c3484 |
mpn_random (data.bp, P_TABLE_SIZE);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
memset (p_table, 0, sizeof(p_table));
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (n = 100; n < P_TABLE_SIZE; n++)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_size_t p;
|
|
Packit |
5c3484 |
mp_size_t best_p;
|
|
Packit |
5c3484 |
double best_time;
|
|
Packit |
5c3484 |
double lehmer_time;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (data.ap[n-1] == 0)
|
|
Packit |
5c3484 |
data.ap[n-1] = 1;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (data.bp[n-1] == 0)
|
|
Packit |
5c3484 |
data.bp[n-1] = 1;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
data.n = n;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
lehmer_time = bench_gcd (&data, 0);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
best_p = search (&best_time, bench_gcd, &data, n/5, 4*n/5);
|
|
Packit |
5c3484 |
if (best_time > lehmer_time)
|
|
Packit |
5c3484 |
best_p = 0;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
printf("%6d %6d %5.3g", n, best_p, (double) best_p / n);
|
|
Packit |
5c3484 |
if (best_p > 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
double speedup = 100 * (lehmer_time - best_time) / lehmer_time;
|
|
Packit |
5c3484 |
printf(" %5.3g%%", speedup);
|
|
Packit |
5c3484 |
if (speedup < 1.0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
printf(" (ignored)");
|
|
Packit |
5c3484 |
best_p = 0;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
printf("\n");
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
p_table[n] = best_p;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
TMP_FREE;
|
|
Packit |
5c3484 |
gmp_randclear(rands);
|
|
Packit |
5c3484 |
return 0;
|
|
Packit |
5c3484 |
}
|