From 3fe24df1237a77549ba64c6331383a9a40aed1de Mon Sep 17 00:00:00 2001
From: emkael <emkael@tlen.pl>
Date: Sat, 25 Nov 2017 16:15:54 +0100
Subject: Initial BigDeal sources

---
 binomial.c | 139 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 139 insertions(+)
 create mode 100644 binomial.c

(limited to 'binomial.c')

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;
+		}
+	}
+}
-- 
cgit v1.2.3