aboutsummaryrefslogtreecommitdiff
path: root/src/utils/math.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/utils/math.h')
-rw-r--r--src/utils/math.h29
1 files changed, 4 insertions, 25 deletions
diff --git a/src/utils/math.h b/src/utils/math.h
index 732a031..4b1da12 100644
--- a/src/utils/math.h
+++ b/src/utils/math.h
@@ -3,7 +3,6 @@
3#define MAX(x, y) ((x) > (y) ? (x) : (y)) 3#define MAX(x, y) ((x) > (y) ? (x) : (y))
4#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) 4#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
5 5
6STATIC int64_t factorial(int64_t);
7STATIC bool isperm(size_t, const uint8_t *); 6STATIC bool isperm(size_t, const uint8_t *);
8STATIC int64_t permtoindex(size_t, const uint8_t *); 7STATIC int64_t permtoindex(size_t, const uint8_t *);
9STATIC void indextoperm(int64_t, size_t, uint8_t *); 8STATIC void indextoperm(int64_t, size_t, uint8_t *);
@@ -12,26 +11,6 @@ STATIC int64_t digitstosumzero(size_t, const uint8_t *, uint8_t);
12STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *); 11STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *);
13STATIC double intpow(double, uint64_t); 12STATIC double intpow(double, uint64_t);
14 13
15STATIC int64_t
16factorial(int64_t n)
17{
18 int64_t i, ret;
19
20 if (n > FACTORIAL_MAX) {
21 LOG("Error: won't compute factorial for n=%" PRId64 " because"
22 " it is larger than %" PRId64 "\n", n, FACTORIAL_MAX);
23 return -1;
24 }
25
26 if (n < 0)
27 return 0;
28
29 for (i = 1, ret = 1; i <= n; i++)
30 ret *= i;
31
32 return ret;
33}
34
35STATIC bool 14STATIC bool
36isperm(size_t n, const uint8_t *a) 15isperm(size_t n, const uint8_t *a)
37{ 16{
@@ -78,7 +57,7 @@ permtoindex(size_t n, const uint8_t *a)
78 for (i = 0, ret = 0; i < n; i++) { 57 for (i = 0, ret = 0; i < n; i++) {
79 for (j = i+1, c = 0; j < n; j++) 58 for (j = i+1, c = 0; j < n; j++)
80 c += (a[i] > a[j]) ? 1 : 0; 59 c += (a[i] > a[j]) ? 1 : 0;
81 ret += factorial(n-i-1) * c; 60 ret += factorial[n-i-1] * c;
82 } 61 }
83 62
84 return ret; 63 return ret;
@@ -99,15 +78,15 @@ indextoperm(int64_t p, size_t n, uint8_t *r)
99 78
100 memset(a, 0, n); 79 memset(a, 0, n);
101 80
102 if (p < 0 || p >= factorial(n)) 81 if (p < 0 || p >= factorial[n])
103 goto indextoperm_error; 82 goto indextoperm_error;
104 83
105 for (i = 0; i < n; i++) { 84 for (i = 0; i < n; i++) {
106 for (j = 0, c = 0; c <= p / factorial(n-i-1); j++) 85 for (j = 0, c = 0; c <= p / factorial[n-i-1]; j++)
107 c += a[j] ? 0 : 1; 86 c += a[j] ? 0 : 1;
108 r[i] = j-1; 87 r[i] = j-1;
109 a[j-1] = 1; 88 a[j-1] = 1;
110 p %= factorial(n-i-1); 89 p %= factorial[n-i-1];
111 } 90 }
112 91
113 if (!isperm(n, r)) 92 if (!isperm(n, r))

Generated with cgit - Back to sebastiano.tronto.net