From 976bd82fb0e830876cca117c302c8a19048033a4 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Thu, 24 Nov 2022 08:58:41 -0500 Subject: =?UTF-8?q?Specify=20more=20=E2=80=A2math=20functions=20and=20impl?= =?UTF-8?q?ement=20JS=20Fact,=20Comb,=20GCD,=20LCM?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- doc/logic.md | 2 +- docs/bqn.js | 45 ++++++++++++++++++++++++++++++++++++++++----- docs/doc/logic.html | 2 +- docs/spec/system.html | 3 ++- spec/system.md | 4 ++++ 5 files changed, 48 insertions(+), 8 deletions(-) diff --git a/doc/logic.md b/doc/logic.md index 793699f1..53e9409e 100644 --- a/doc/logic.md +++ b/doc/logic.md @@ -98,7 +98,7 @@ Some other logical identities don't always hold. For example, in boolean logic A ### Why not GCD and LCM? -APL provides [GCD](https://aplwiki.com/wiki/GCD) and [LCM](https://aplwiki.com/wiki/LCM) as extensions of And and Or, while BQN doesn't make these functions primitives. The main reason for omitting them functions is that they are complicated and, when applied to real or complex numbers, require a significant number of design decisions where there's no obvious choice (for example, whether to use comparison tolerance). On the other hand, these functions are fairly easy to implement, which allows the programmer to control the details, and also add functionality such as the extended GCD. Possible implementations for GCD and LCM are shown in [bqncrate](https://mlochbaum.github.io/bqncrate) ([GCD](https://mlochbaum.github.io/bqncrate/?q=gcd), [LCM](https://mlochbaum.github.io/bqncrate/?q=lcm)). +APL provides [GCD](https://aplwiki.com/wiki/GCD) and [LCM](https://aplwiki.com/wiki/LCM) as extensions of And and Or, while BQN doesn't make these functions primitives. The main reason for omitting them functions is that they are complicated and, when applied to real or complex numbers, require a significant number of design decisions where there's no obvious choice (for example, whether to use comparison tolerance). On the other hand, these functions are fairly easy to implement, which allows the programmer to control the details, and also add functionality such as the extended GCD. Possible implementations for GCD and LCM are shown in [bqncrate](https://mlochbaum.github.io/bqncrate) ([GCD](https://mlochbaum.github.io/bqncrate/?q=gcd), [LCM](https://mlochbaum.github.io/bqncrate/?q=lcm)), and `•math.GCD` and `•math.LCM` are also supported. A secondary reason is that the GCD falls short as an extension of Or, because its identity value 0 is not total. `0∨x`, for a real number `x`, is actually equal to `|x` and not `x`: for example, `0∨¯2` is `2` in APL. This means the identity `0∨x ←→ x` isn't reliable in APL. diff --git a/docs/bqn.js b/docs/bqn.js index c5e0b475..795f4fba 100644 --- a/docs/bqn.js +++ b/docs/bqn.js @@ -38,7 +38,6 @@ let makens = (keys, vals) => { let n = Array(keys.length).fill().map((_,i)=>i); n.names=keys.map(k=>k.toLowerCase()); vals.ns=n; return vals; } -let obj2ns = (obj, keys, f) => makens(keys, keys.map(k=>(f?f:(v=>v))(obj[k]))); let listkeys = x => { let s=x.ns, k=Object.keys(s).filter(n=>!isNaN(n)); return k.map(n=>s.names[+n]).sort(); @@ -661,16 +660,52 @@ let primitives = dynsys(state => { return list(gl.map((g,i) => list([g,rt[i]]))); }); +let isint = n => isnum(n) && n===(n|0); +let isnat = n => isint(n) && n>=0; +let fact = (x,w) => { + if (has(w)) throw Error("•math.Fact: Left argument not allowed"); + if (!isnat(x)) throw Error("•math.Fact: Argument other than a natural number not yet supported"); + let p = 1; while (x>0 && p { + if (!has(w)) throw Error("•math.Comb: Left argument required"); + if (!(isint(w) && isint(x))) throw Error("•math.Comb: Non-integer arguments not yet supported"); + let n=w, k=Math.min(x, n-x); + let sgn = 1; + if (n >= 0) { + if (k<0) return 0; + } else { + let j=n-k; if (j<0) return 0; if (j&1) sgn = -1; + let t = Math.min(j, -1-n); n = -1-k; k = t; + } + if (k > 514) return Infinity; + let p = 1; + for (let i=0; i { + if (!has(w)) throw Error("•math.GCD: Left argument required"); + if (!(isnat(w) && isnat(x))) throw Error("•math.GCD: Arguments other than natural numbers not yet supported"); + while (w) { let t=w; w=x%w; x=t; } + return x; +} +let lcm = (x,w) => w===0 ? 0 : (w / gcd(x,w)) * x; +let pervfn = f => { f.prim=null; return runtime[61](f,0); } // ⚇ let mathfn = f => { - f.prim=null; let p=runtime[61](f,0); // ⚇ + let p=pervfn(f); return f!==Math.atan2 && f!==Math.hypot ? ((x,w) => {if ( has(w)) throw Error("Left argument not allowed"); return p(x);}) : ((x,w) => {if (!has(w)) throw Error("Left argument required"); return p(x,w);}); } let trig = "cos cosh sin sinh tan tanh".split(" "); -let mathns = obj2ns(Math, - trig.concat(trig.map(n=>"a"+n),"cbrt expm1 hypot log10 log1p log2 round trunc atan2".split(" ")), - f=>typeof f==="function"?mathfn(f):f +let mathkeys = trig.concat(trig.map(n=>"a"+n),"cbrt expm1 hypot log10 log1p log2 round trunc atan2".split(" ")); +let mathns = makens( + mathkeys.concat(["fact","comb","gcd","lcm"]), + mathkeys.map(k=>mathfn(Math[k])).concat([fact,comb,gcd,lcm].map(pervfn)) ); trig.map((_,i)=>{let f=mathns[i],g=mathns[i+trig.length]; f.inverse=g; g.inverse=f;}); diff --git a/docs/doc/logic.html b/docs/doc/logic.html index 9b18b817..c1490385 100644 --- a/docs/doc/logic.html +++ b/docs/doc/logic.html @@ -132,6 +132,6 @@

It's not hard to prove that the bilinear extensions have these identity values. Of course 1∧x is 1×x, or x, and 0∨x is 0×⌾¬x, or ¬1׬x, giving ¬¬x or x again. Both functions are commutative, so these values are identities on the right as well.

Some other logical identities don't always hold. For example, in boolean logic And distributes over Or and vice-versa: a∧b∨c ←→ (a∧b)∨(a∧c). But substituting × for ∧ and +-× for ∨ we find that the left hand side is (a×b)+(a×c)+(a×b×c) while the right gives (a×b)+(a×c)+(a×b×a×c). These are equivalent for arbitrary b and c only if a=a×a, that is, a is 0 or 1. In terms of probabilities the difference when a is not boolean is caused by failure of independence. On the left hand side, the two arguments of every logical function are independent. On the right hand side, each pair of arguments to ∧ are independent, but the two arguments to ∨, a∧b and a∧c, are not. The relationship between these arguments means that logical equivalences no longer apply.

Why not GCD and LCM?

-

APL provides GCD and LCM as extensions of And and Or, while BQN doesn't make these functions primitives. The main reason for omitting them functions is that they are complicated and, when applied to real or complex numbers, require a significant number of design decisions where there's no obvious choice (for example, whether to use comparison tolerance). On the other hand, these functions are fairly easy to implement, which allows the programmer to control the details, and also add functionality such as the extended GCD. Possible implementations for GCD and LCM are shown in bqncrate (GCD, LCM).

+

APL provides GCD and LCM as extensions of And and Or, while BQN doesn't make these functions primitives. The main reason for omitting them functions is that they are complicated and, when applied to real or complex numbers, require a significant number of design decisions where there's no obvious choice (for example, whether to use comparison tolerance). On the other hand, these functions are fairly easy to implement, which allows the programmer to control the details, and also add functionality such as the extended GCD. Possible implementations for GCD and LCM are shown in bqncrate (GCD, LCM), and •math.GCD and •math.LCM are also supported.

A secondary reason is that the GCD falls short as an extension of Or, because its identity value 0 is not total. 0∨x, for a real number x, is actually equal to |x and not x: for example, 0∨¯2 is 2 in APL. This means the identity 0∨x ←→ x isn't reliable in APL.

Unrelatedly, the reason BQN discards APL's ~ for negation is that it looks like ˜, and is less common in mathematics today.

diff --git a/docs/spec/system.html b/docs/spec/system.html index 5e076378..9b43e094 100644 --- a/docs/spec/system.html +++ b/docs/spec/system.html @@ -601,9 +601,10 @@

More accurately the modifier •_maxTime_ may fail if execution of 𝔽 takes over 𝕨𝔾𝕩 seconds, and should fail as quickly as it is practically able to. The most likely way to implement this modifier is to interrupt execution at the given time. If 𝔽 completes before the interrupt there is no need to measure the amount of time it actually took.

Math

System namespace •math contains mathematical utilities that are not easily implemented with basic arithmetic, analogous to C's math.h.

-

Constants ln10⇐⋆⁼10, ln2⇐⋆⁼2, log10e⇐÷⋆⁼10, log2e⇐÷⋆⁼2 computed in full precision.

Other correctly-rounded arithmetic: monadic Cbrt⇐3⊸√, Log2⇐2⋆⁼⊢, Log10⇐10⋆⁼⊢, Log1p⇐⋆⁼1⊸+, Expm1⇐1-˜⋆; dyadic Hypot⇐+⌾(ט).

Standard trigonometric functions Sin, Cos, Tan, Sinh, Cosh, Tanh, with inverses preceded by a (ASin, etc.) and accessable with ⁼. Additionally, the dyadic function ATan2 giving the angle of vector 𝕨‿𝕩 relative to 1‿0. All trig functions measure angles in radians.

+

Special functions Fact and LogFact giving the factorial and its natural logarithm, possibly generalized to reals as the gamma function Γ(1+𝕩), and Comb giving the binomial function "𝕨 choose 𝕩". Also the error function Erf and its complement ErfC. The implementations LogFact ← ⋆⁼Fact and ErfC ← 1-Erf are mathematically correct but these two functions should support greater precision for a large argument.

+

The greatest common divison GCD and least common multiple LCM of two numbers. Behavior for arguments other than natural numbers is not yet specified.

Random generation

•MakeRand initializes a deterministic pseudorandom number generator with seed value 𝕩. •rand, if it exists, is a globally accessible generator initialized at first use; this initialization should use randomness from an outside source if available. These random generators aren't required to be cryptographically secure and should always be treated as insecure. A random generator has the following member functions:

diff --git a/spec/system.md b/spec/system.md index 0d6cffbf..5ba463bb 100644 --- a/spec/system.md +++ b/spec/system.md @@ -291,6 +291,10 @@ Other correctly-rounded arithmetic: monadic `Cbrt⇐3⊸√`, `Log2⇐2⋆⁼⊢ Standard trigonometric functions `Sin`, `Cos`, `Tan`, `Sinh`, `Cosh`, `Tanh`, with inverses preceded by `a` (`ASin`, etc.) and accessable with `⁼`. Additionally, the dyadic function `ATan2` giving the angle of vector `𝕨‿𝕩` relative to `1‿0`. All trig functions measure angles in radians. +Special functions `Fact` and `LogFact` giving the factorial and its natural logarithm, possibly generalized to reals as the gamma function Γ(1+𝕩), and `Comb` giving the binomial function "`𝕨` choose `𝕩`". Also the error function `Erf` and its complement `ErfC`. The implementations `LogFact ← ⋆⁼Fact` and `ErfC ← 1-Erf` are mathematically correct but these two functions should support greater precision for a large argument. + +The greatest common divison `GCD` and least common multiple `LCM` of two numbers. Behavior for arguments other than natural numbers is not yet specified. + ## Random generation `•MakeRand` initializes a deterministic pseudorandom number generator with seed value `𝕩`. `•rand`, if it exists, is a globally accessible generator initialized at first use; this initialization should use randomness from an outside source if available. These random generators aren't required to be cryptographically secure and should always be treated as insecure. A random generator has the following member functions: -- cgit v1.2.3