Evaluate binomial coefficients: Difference between revisions
Zig version
(Zig version) |
|||
Line 2,878:
</pre>
=={{header|Zig}}==
A reasonable implementation for a fixed word size is to precompute all possible values of nCk, since even on a 64 bit machine there's only 67 rows of Pascal's triangle to consider, or ~18K of data.
In Zig it's possible to compute all values of nCk at compile time, so that at runtime it's only necessary to do a table lookup. Zig also supports nullable values, so nCk can return a null value if the programmer requests a value that's out of range. Finally, since this code uses addition to compute the table, all entries that can fit in 64 bits can be computed, in contrast to some other code examples that may overflow before the maximum representable value (67 choose 33) is reached. For example, the largest value the BCPL version can compute is 61 choose 31.
<lang Zig>
const std = @import("std");
pub fn binomial(n: u32) ?[]const u64 {
if (n >= rmax)
return null
else {
const k = n * (n + 1) / 2;
return pascal[k .. k + n + 1];
}
}
pub fn nCk(n: u32, k: u32) ?u64 {
if (n >= rmax)
return null
else if (k > n)
return 0
else {
const j = n * (n + 1) / 2;
return pascal[j + k];
}
}
const rmax = 68;
const pascal = build: {
@setEvalBranchQuota(100_000);
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined;
coefficients[0] = 1;
var j: u32 = 0;
var k: u32 = 1;
var n: u32 = 1;
while (n < rmax) : (n += 1) {
var prev = coefficients[j .. j + n];
var next = coefficients[k .. k + n + 1];
next[0] = 1;
var i: u32 = 1;
while (i < n) : (i += 1)
next[i] = prev[i] + prev[i - 1];
next[i] = 1;
j = k;
k += n + 1;
}
break :build coefficients;
};
test "n choose k" {
const expect = std.testing.expect;
try expect(nCk(10, 5).? == 252);
try expect(nCk(10, 11).? == 0);
try expect(nCk(10, 10).? == 1);
try expect(nCk(67, 33).? == 14226520737620288370);
try expect(nCk(68, 34) == null);
}
</lang>
Rather than write driver code, it's possible to run the unit test for this module.
{{Out}}
<pre>
$ zig test binomial.zig
All 1 tests passed.
</pre>
=={{header|zkl}}==
Using 64 bit ints:
| |||