Public
Edited
Oct 13, 2023
Importers
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from
range = (start, stop, step) => Array.from({ length: (stop - start) / step + 1 }, (_, i) => start + i * step);
range(1, 10, 1)
// See also: https://stackoverflow.com/questions/3959211/what-is-the-fastest-factorial-function-in-javascript
function getFactorialFn() {
// We use closure trick to memorize computed results so we won't recompute it again and again for the same inputs
var m = [1, 1];
return (n) => {
if (n < 0) return 1;
while (m.length <= n) {
m.push((m.length) * m[m.length-1]);
}
return m[n];
};
}
factorial = getFactorialFn()
range(1, 7, 1).map(factorial)
factorial(19)
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER
Number.MAX_SAFE_INTEGER
factorial(19) - Number.MAX_SAFE_INTEGER
// https://observablehq.com/@observablehq/input-range
viewof aNumber = Inputs.range([1, 10000000000000000], {label: "A number", step: 1, value: 250000, transform: Math.log})
// You can use binary search to find least factorial greater or equal to a number(though a linear search is enough)
// https://observablehq.com/@d3/d3-bisect
posFactorialRight = {
const bisect = d3.bisector(d => factorial(d))
return bisect.right(range(0, 20, 1), aNumber)
}
// See: https://brilliant.org/wiki/stirlings-formula/
// https://brilliant.org/wiki/permutations/ Stirling's formula
stirlingsFormula = (n) => Math.sqrt(2 * Math.PI * n) * (n / Math.E) ** n
posStirlingsFormulaRight = {
const bisect = d3.bisector(d => stirlingsFormula(d))
return bisect.right(range(0, 20, 1), aNumber)
}
// For Stirling's formula, a faster way on computation is to take logarithm first then perform exponentiation back(though nowadays computers are super fast for smaller n)
stirlingsFormulaByLog = (n) => Math.exp(0.5 * Math.log(2 * Math.PI*n) + n * (Math.log(n)-1))
// https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/BigInt
function my_mod(a, m) {
if (a < m) return a;
return a - (a / m) * m; // a/m automatically truncate decimal numbers for bigint
}
my_mod(17774694356196958000, 11)
17774694356196958000 % 11 // JS fails to perform exact modular arithmetic for big number
// We need to use bigint for all arithmetics and only return number as result
function choose(n, k) {
if (k == 0 || n == k) return 1;
if (k < n-k) k = n-k;
const target = n-k;
// https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/BigInt
let res = BigInt(1), i = BigInt(n), d = BigInt(2);
while (i > k) {
res *= i;
i -= BigInt(1);
// while (d <= target && (res % d == 0)) {
while (d <= target && my_mod(res, d) == 0) {
res /= d;
d += BigInt(1);
}
}
return Number(res);
}
choose(10, 0)
choose(10, 10)
choose(10, 1)
choose(81, 19)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
