nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

commit 9b248f3b46d5dc0e9522ed264ef71e422a5bc5a5
parent 08d524292beed48d8a383acaee96f68cb2bd1cab
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Mon, 28 Jul 2025 12:16:08 +0200

Hardcoded factorial constants

Diffstat:
Msrc/utils/constants.h | 16++++++++++++++++
Msrc/utils/math.h | 29++++-------------------------
2 files changed, 20 insertions(+), 25 deletions(-)

diff --git a/src/utils/constants.h b/src/utils/constants.h @@ -11,6 +11,22 @@ #define UINT8_ERROR UINT8_MAX +STATIC int64_t factorial[FACTORIAL_MAX+1] = { + [0] = 1, + [1] = 1, + [2] = 2, + [3] = 6, + [4] = 24, + [5] = 120, + [6] = 720, + [7] = 5040, + [8] = 40320, + [9] = 362880, + [10] = 3628800, + [11] = 39916800, + [12] = 479001600, +}; + STATIC int64_t binomial[12][12] = { {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, diff --git a/src/utils/math.h b/src/utils/math.h @@ -3,7 +3,6 @@ #define MAX(x, y) ((x) > (y) ? (x) : (y)) #define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) -STATIC int64_t factorial(int64_t); STATIC bool isperm(size_t, const uint8_t *); STATIC int64_t permtoindex(size_t, const uint8_t *); STATIC void indextoperm(int64_t, size_t, uint8_t *); @@ -12,26 +11,6 @@ STATIC int64_t digitstosumzero(size_t, const uint8_t *, uint8_t); STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *); STATIC double intpow(double, uint64_t); -STATIC int64_t -factorial(int64_t n) -{ - int64_t i, ret; - - if (n > FACTORIAL_MAX) { - LOG("Error: won't compute factorial for n=%" PRId64 " because" - " it is larger than %" PRId64 "\n", n, FACTORIAL_MAX); - return -1; - } - - if (n < 0) - return 0; - - for (i = 1, ret = 1; i <= n; i++) - ret *= i; - - return ret; -} - STATIC bool isperm(size_t n, const uint8_t *a) { @@ -78,7 +57,7 @@ permtoindex(size_t n, const uint8_t *a) for (i = 0, ret = 0; i < n; i++) { for (j = i+1, c = 0; j < n; j++) c += (a[i] > a[j]) ? 1 : 0; - ret += factorial(n-i-1) * c; + ret += factorial[n-i-1] * c; } return ret; @@ -99,15 +78,15 @@ indextoperm(int64_t p, size_t n, uint8_t *r) memset(a, 0, n); - if (p < 0 || p >= factorial(n)) + if (p < 0 || p >= factorial[n]) goto indextoperm_error; for (i = 0; i < n; i++) { - for (j = 0, c = 0; c <= p / factorial(n-i-1); j++) + for (j = 0, c = 0; c <= p / factorial[n-i-1]; j++) c += a[j] ? 0 : 1; r[i] = j-1; a[j-1] = 1; - p %= factorial(n-i-1); + p %= factorial[n-i-1]; } if (!isperm(n, r))