Public
Edited
Aug 19, 2024
parametrize = (poly, limit = 1) => range(limit).map((x, idx) => subst(poly, x));
parametrize(parsedPoly, polyLimit).map((x, idx) => idx + " → " + x);
parametrize(compose(parsedPoly, {poly: [5, 0]}), 10);
<div style="font-size:1.25rem">
<p>This is different from multiplying two polynomials.</p>
<p>Multiplication:</p>
${printPoly(parsedPoly)} * ${printPoly({poly: [5,0]})} = ${printPoly(multiply(parsedPoly, {poly: [5, 0]}))};
<p>Composition:</p>
${printPoly(parsedPoly)} ∘ ${printPoly({poly: [5,0]})} = ${printPoly(compose(parsedPoly, {poly: [5, 0]}))};
</div>
viewof poly9 = html`<input class="big-input" type="text" value=[2,4]>`
parsedPoly9 = parsePolyString(poly9);
printPoly(parsedPoly9);
poly9Series = parametrize(parsePolyString(poly9), 30);
range(10).map(x => x * x).map(x => subst(parsedPoly9, x));
parametrize(compose(parsedPoly9, {poly: [1, 0, 0]}), 10);
<p>${printPoly(parsedPoly9, true)} ∘ ${printPoly({poly: [1, 0, 0]})} = ${printPoly(compose(parsedPoly9, {poly: [1, 0, 0]}))}</p>
compose(parsedPoly9, {poly: [1, 0, 0]})
compose = ({poly: poly1}, {poly: poly2}) => {
return zipSumPoly(normalizePoly(poly1.map((x, idx) => {
let pow = poly1.length - idx - 1;
return multiply(exponentiate({poly: poly2}, pow), {poly: [x]});
})));
}
normalizePoly = (polys) => { let max = Math.max(...polys.map(({poly}) => poly.length));
return polys.map(({poly}) => ({poly: normalize(poly, max)}));
};
zipSumPoly = (nPolys) => nPolys.reduce(({poly: poly1}, {poly: poly2}) => ({poly: zipSum(poly1, poly2)}));
subst = ({poly, type}, val) => polyToFn(poly)(val);
exponentiate = (poly, pow) => (pow === 0 ? {poly: [1]} : pow === 1 ? poly : range(pow).map(x => poly).reduce((x,y) => multiply(x,y)));
polyToFn = (poly) => val => poly.map((coeff, idx) => v => coeff * Math.pow(v, poly.length - idx - 1)).reduce((x,f) => x + f(val), 0);
{
let p1 = parsePolySingleDigitString(poly1);
let p2 = parsePolySingleDigitString(poly2);
return html`(${printPoly(p1, true)}) + (${printPoly(p2, true)}) = ${printPoly(add(p1, p2), true)}`;
};
<div style="font-size:1.25rem; display: flex; flex-flow: row; line-height: 1.5rem; padding: 2rem; height: 100%;">
<div style="display: flex; flex-flow: column; height: 280px; justify-content: space-between; font-style: italic; margin-right: 1rem; text-align: right;">
<p><strong>Normal basis</strong></p>
<p>Stirling Transform</p>
<p><strong>Falling factorial basis</strong></p>
</div>
<div style="display: flex;flex-flow: column; align-items: center;">
<div>${printPoly(parsedPoly8,true)}</div>
<div class="arrow-down"></div>
<div>${printPoly(normalToFalling(parsedPoly8), true)}</div>
</div>
<div style="display: flex; flex-flow: column; justify-content: space-between;margin: 1rem 0;">
<div style="display: flex;align-items: center; flex-flow: column; position: relative;">
<p style="position: absolute; top: -50px;">∆</p>
<div class="arrow-right"></div>
</div>
<div style="display: flex;align-items: center; flex-flow: column; position: relative;">
<p style="position: absolute; top: -50px;">∆</p>
<div class="arrow-right"></div>
</div>
</div>
<div style="display: flex; flex-flow: column; align-items: center;">
<div>${printPoly(diff(parsedPoly8), true)}</div>
<div class="arrow-up"></div>
<div>${printPoly(normalToFalling(diff(parsedPoly8)), true)}</div>
</div>
</div>
<p>Let us confirm this by parametrizing their series by natural numbers and see if the result holds for the first few numbers:
<p>[${range(8).map(x => subst(parsePolyString(poly8), x)).join(",")}]</p>
<p>These have as adjacent difference:</p>
<p>[${range(8).map(x => subst(diff(parsePolyString(poly8)), x)).join(",")}]</p>
<p>which indeed looks like the polynomial</p>
${printPoly(diff(parsedPoly8))}
<p>parametrized by the natural numbers</p>
rightShift = ({poly}, amount) => ({poly: poly.slice(0, -amount)});
function diff({poly, type}) {
if(type == "falling") {
let unit = ({poly: [0]});
return add(...poly.map((coeff, idx) => {
let power = poly.length - idx - 1;
return (power === 0 || coeff === 0) ? unit : multiply({poly: [power * coeff]}, polyFromPower(power)); }))}
else { return fallingToNormal(diff(normalToFalling({poly}))); };
}
polyFromPower = pow => ({poly: [1].concat(range(pow-1).map(x => 0))});
diff(parsePolyString(poly8));
sum = () => [];
range = n => [...new Array(n)].map((x, idx) => idx);
powerToFallingPowers = (power) => ({type: "falling", poly: range(power + 1).map((x) => stirlingPartitions(power, power - x))})
normalToFalling = ({poly}) => {
let results = poly.map((coefficient, idx) => multiply({poly: [coefficient]}, powerToFallingPowers(poly.length - idx - 1)));
return {poly: add(...results).poly, type: "falling"};;
};
powerToFallingPowers(4);
// printPoly({type: "falling", poly: [1,0,0,0,0]});
// printPoly(fallingToNormal({type: "falling", poly: [1,0,0,0,0]}));
// printPoly(fallingToNormal({poly: [3, 0, 0]}));
// printPoly(normalToFalling(fallingToNormal({poly: [1, 0, 1, 0, 0]})));
// printPoly(normalToFalling(fallingToNormal({poly: [1, 2, 1]})));
normalToFalling({poly: [1]});
// printPoly(fallingToNormal(normalToFalling({poly: [1,0,1]})));
// printPoly(normalToFalling({poly: [1,1]}));
// printPoly(fallingToNormal(normalToFalling({poly: [1, 0, 1, 0, 0, 1]})));
combinations = (n,k) => { if(k == null) k = n; return permutations(n) / (permutations(n-k) * permutations(k)) };
// printPoly(powerToFallingPowers(4), true);
// printPoly(fallingToNormal(powerToFallingPowers(1)));
normalize = (x, n) => ([...new Array(Math.max(0, n - x.length))].map(x => 0)).concat(x);
zipWith = op => (arr1, arr2) => (arr1.length == arr2.length) ? arr1.map((x, idx) => op(x, arr2[idx])) : "Can’t zip";
zipSum = zipWith((x,y) => x + y);
function stirlingCycles (n, k) {
if(n == 0 && k == 0) return 1;
else if (n == 0 || k == 0) return 0;
else return (n - 1) * stirlingCycles(n-1, k) + stirlingCycles(n-1, k-1);
}
fallingPowerToPoly = (fp) => ({poly: range(fp + 1).map(x => Math.pow(-1, fp - x) * stirlingCycles(fp, x)).reverse()});
fallingToNormal = ({poly}) => {
let results = poly.map((coefficient, idx) => multiply({poly: [coefficient]}, fallingPowerToPoly(poly.length - idx - 1)));
return add(...results);
};
multiply = ({poly: poly1}, {poly: poly2}) => add(...poly1.map((coeff1, idx) => ({poly: leftShift({poly: poly2}, poly1.length - idx - 1).poly.map(coeff2 => (coeff1 * coeff2))})));
printPoly(multiply({poly: [2,1]}, {poly: [2]}));
sup = (idx) => String(idx).split("").map(x => ["⁰", "¹","²","³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"][x]);
parsePolySingleDigitString = (poly) => ({poly: String(poly).split("").map(x => parseInt(x))});
printPoly = ({poly, type}, full = false) => {
const term = (x, pow, format) => x === 0 ? (full ? x + "x" + format(pow) : "") : pow === 0 ? (full ? x + "x" + format(pow) : x) : x + "x" + format(pow);
const subF = x => "<sub>(" + x + ")</sub>";
const supR = x => "<sup>(" + x + ")</sup>";
const sup = x => "<sup>" + x + "</sup>";
if(type == "falling") return html`${poly.map((x, idx) => type === "falling" ? term(x, poly.length - 1 - idx, subF) : term(x, poly.length - 1 - idx, supR)).filter(x => x != "").join("+")}`;
else return html`<span style="font-size:1.25rem; padding: 0.5rem 0;">${poly.map((x, idx) => term(x, poly.length - 1 - idx, sup)).filter(x => x != "").join("+")}</span>`;
}
parsePolyString = (str) => {
try {
let result = JSON.parse(str);
return ({poly: result});
} catch(e) {
if(str.indexOf(",]") !== -1) return {poly: JSON.parse(str.replace(",]", "]"))};
}
}
stirlingPartitions = (n, k) => ([...new Array(k+1)].map((_, i) => (Math.pow(-1,k - i) * combinations(k, i) * Math.pow(i,n))).reduce((x, y) => x + y)) / permutations(k);
fallingPower = (n,k) => permutations(n, k);
leftShift = ({poly}, amount) => ({poly: poly.concat(range(amount).map(x => 0))})
function permutations(n,k) { if(k == 0) { return 0 } else if(k == null) k = 1; return n <= k ? 1 : n * permutations(n - 1,k); };
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.
