00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdlib.h>
00022 #include <math.h>
00023
00024 double binomial(int n, int k) {
00025 int i;
00026 double x = 1;
00027
00028 for (i = 0; i < k; ++i) {
00029 x *= n - i;
00030 x /= k -i;
00031 }
00032
00033 return x;
00034 }
00035
00036 double log_binomial(int n, int k) {
00037 int i;
00038 double x = 0;
00039
00040 for (i = 0; i < k; ++i) {
00041 x += log(n - i);
00042 x -= log(k - i);
00043 }
00044
00045 return x / log(2);
00046 }
00047
00048 double nb_iter(int n, int k, int w, int p, int l) {
00049 double x;
00050
00051 x = 2 * log_binomial(k / 2, p);
00052 x += log_binomial(n - k - l, w - 2 * p);
00053 x = log_binomial(n, w) - x;
00054
00055 return x;
00056 }
00057
00058 double cout_iter(int n, int k, int p, int l) {
00059 double res, x;
00060 int i;
00061
00062
00063 x = binomial(k / 2, p);
00064
00065 i = (int) (log(x) / log(2));
00066
00067 res = 2 * p * (n - k - l) * ldexp(x * x, -l);
00068
00069 x *= 2 * (2 * l + i);
00070
00071
00072
00073 res += x + k * ((n - k) / 2.0);
00074
00075 return log(res) / log(2);
00076 }
00077
00078 double memory_compl(int n, int k, int p, int l) {
00079 double x, res, aux;
00080
00081 x = binomial(k / 2, p);
00082 res = log(x) / log(2);
00083 aux = (res > l) ? res : l;
00084
00085 return res + log(log(aux) / log(2) + aux) / log(2);
00086 }
00087
00088 double cout_total(int n, int k, int w, int p, int l) {
00089 double x, y;
00090
00091 x = nb_iter(n, k, w, p, l);
00092 y = cout_iter(n, k, p, l);
00093 return x + y;
00094 }
00095
00096 double best_wf(int n, int k, int w, int p, int *lmin, double *mem) {
00097 int u, l;
00098 double lwf, min;
00099
00100 if (p >= k / 2)
00101 return -1;
00102
00103 min = memory_compl(n, k, p, 0);
00104
00105 u = min + 5;
00106
00107
00108
00109
00110
00111 min = cout_total(n, k, w, p, u);
00112 *lmin = u;
00113 for (l = u + 1; l < n - k; ++l) {
00114 lwf = cout_total(n, k, w, p, l);
00115 if (lwf < min) {
00116 min = lwf;
00117 *lmin = l;
00118 }
00119 else
00120 break;
00121 }
00122 if (l == u + 1)
00123 for (l = u - 1; l > 0; --l) {
00124 lwf = cout_total(n, k, w, p, l);
00125 if (lwf < min) {
00126 min = lwf;
00127 *lmin = l;
00128 }
00129 else
00130 break;
00131 }
00132
00133 *mem = memory_compl(n, k, p, 0);
00134 return min;
00135 }
00136
00137 double workfactor(int n, int k, int t) {
00138 int p, l, lmin, pmin;
00139 double min, lwf, mem, memmin;
00140
00141 pmin = 1;
00142 min = cout_total(n, k, t, 0, 0);
00143 lmin = 0;
00144 memmin = 0;
00145 for (p = pmin; p <= t / 2; ++p) {
00146 lwf = best_wf(n, k + 1, t, p, &l, &mem);
00147 if (lwf < 0)
00148 break;
00149 if ((min == 0) || (lwf < min)) {
00150 min = lwf;
00151 pmin = p;
00152 lmin = l;
00153 memmin = mem;
00154 }
00155
00156 if (p >= pmin + 2)
00157 break;
00158 }
00159
00160 return min;
00161 }