1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
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;
}
}
}
|
