diff options
Diffstat (limited to 'binomial.c')
| -rw-r--r-- | binomial.c | 139 |
1 files changed, 139 insertions, 0 deletions
diff --git a/binomial.c b/binomial.c new file mode 100644 index 0000000..7e565c1 --- /dev/null +++ b/binomial.c @@ -0,0 +1,139 @@ +#include "types.h"
+#include "bigdeal.h"
+#include "mp.h"
+
+static char rcsid[] = "$Header: /home/sater/bridge/bigdeal/RCS/binomial.c,v 1.11 2000/08/16 15:06:30 sater Exp $";
+
+/*
+ * functions implementing or using the (n over k) mathematical construct
+ */
+
+static byte pascal_triangle[NCARDSPERDECK+1][NCARDSPERHAND+1][L];
+
+void
+binomial_start()
+/*
+ * Precomputes all numbers (n over k) with k<=NCARDSPERHAND and
+ * n<=NCARDSPERDECK.
+ * Numbers are stored in pascal_triangle[][] with L bytes precision (96 bits)
+ *
+ * Calculation method is the addition from the top of the triangle
+ * where the equation:
+ * n_over_k(n,k) = n_over_k(n-1, k-1) + n_over_k(n-1, k)
+ * except for some boundary condition situations
+ */
+{
+ int i,j,min;
+
+ for (i=0; i<=NCARDSPERDECK; i++) {
+ if (i<NCARDSPERHAND)
+ min = i;
+ else
+ min = NCARDSPERHAND;
+ for (j=0; j<=min; j++) {
+ if (i==j || j==0)
+ mp96_one(pascal_triangle[i][j]);
+ else
+ mp96_add(pascal_triangle[i][j],
+ pascal_triangle[i-1][j],
+ pascal_triangle[i-1][j-1]);
+ }
+ }
+}
+
+void
+n_over_k(int n, int k, byte *b)
+/*
+ * "Compute" (n over k) in L bytes(96 bits) precision
+ * Actually just read from pascal_triangle
+ *
+ * Result stored into b[]
+ */
+{
+ if (n<=NCARDSPERDECK && k<=NCARDSPERHAND && k<=n)
+ mp96_assign(b, pascal_triangle[n][k]);
+ else
+ mp96_zero(b);
+}
+
+
+void
+code_to_hand(dl_num *dnp, dl_int *dip)
+/*
+ * This function converts a given number to its associated bridge-deal.
+ * Read the file Godel.pdf for an explanation of the code. The
+ * variable-names used in the comments refer to the variable-names
+ * that were used in the pseudo-code in Godel.pdf.
+ */
+{
+ int i,j,a,b;
+ byte c[L];
+ byte g[L];
+ byte tmp1[L],tmp2[L],tmp3[L];
+ int compass;
+
+ /*
+ * set g_{-1} = g
+ */
+ mp96_assign(g, dnp->dn_num);
+
+ for (compass=COMPASS_NORTH; compass<NCOMPASS; compass++) {
+ /*
+ * Computation of an appropriate constant for the given
+ * compass direction. The constant is equal to:
+ * 39_over_13 x 26_over_13 for North,
+ * 26_over_13 for East,
+ * 1 for South.
+ *
+ * Code continues for West who automatically gets 13 zeroes
+ */
+ mp96_one(c);
+ for (i=2; i<=COMPASS_WEST-compass; i++) {
+ n_over_k(i*13, 13, tmp1);
+ mp96_mul(c, tmp1, c);
+ }
+
+ /*
+ * set a_{-1} = 0
+ */
+ a = 0;
+ for (j=0; j<NCARDSPERHAND; j++) {
+ /*
+ * Computation of a_j, x_j and g_j.
+ * a_j is computed by setting variable b to a_{j-1} and
+ * incrementing it until it reaches the value a_j.
+ */
+ n_over_k(13*(NCOMPASS-compass)-a-j, 13-j, tmp1);
+
+ /*
+ * b is set to a_{j-1} and up
+ */
+ for(b=a; ; b++) {
+ n_over_k(13*(NCOMPASS-compass)-b-1-j, 13-j, tmp2);
+ mp96_sub(tmp2, tmp1, tmp2);
+ mp96_mul(tmp2, tmp2, c);
+ /*
+ * Check if b < a_j, i.e. if tmp2 > g
+ */
+ if (mp96_cmp(tmp2, g) > 0)
+ break;
+ }
+ n_over_k(13*(NCOMPASS-compass)-a-j, 13-j, tmp1);
+ n_over_k(13*(NCOMPASS-compass)-b-j, 13-j, tmp2);
+ mp96_sub(tmp3, tmp1, tmp2);
+ /*
+ * tmp1 is assigned the value x_j
+ */
+ mp96_mul(tmp1, tmp3, c);
+ /*
+ * g_j = g_{j-1} - x_j
+ */
+ mp96_sub(g, g, tmp1);
+ dip->di_hand[compass][j] = b;
+ /*
+ * a is set to a_j
+ */
+ a = b;
+ }
+ }
+}
|