From 7cc2e66790a2d1baa871d1491291f1c4e0b3f2cb Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Wed, 14 Sep 2022 10:20:49 -0400 Subject: Arithmetic implementation: booleans and strength reduction --- docs/implementation/primitive/arithmetic.html | 94 +++++++++++++++++++++++++++ 1 file changed, 94 insertions(+) create mode 100644 docs/implementation/primitive/arithmetic.html (limited to 'docs/implementation/primitive/arithmetic.html') diff --git a/docs/implementation/primitive/arithmetic.html b/docs/implementation/primitive/arithmetic.html new file mode 100644 index 00000000..dfd8730e --- /dev/null +++ b/docs/implementation/primitive/arithmetic.html @@ -0,0 +1,94 @@ + + + + BQN: Implementation of arithmetic + +
(github) / BQN / implementation / primitive
+

Implementation of arithmetic

+

The dyadic arithmetic functions are +-×÷⋆√⌊⌈|¬∧∨<>≠=≤≥. There are also monadic arithmetic functions, but they're mostly easy to optimize.

+

Boolean functions

+

Many arithmetic functions give boolean results when both arguments are boolean. Because there are only 16 possible functions like this, they overlap a lot. Here's a categorization:

+↗️
    f ← ∧‿∨‿<‿>‿≠‿=‿≤‿≥‿+‿-‿×‿÷‿⋆‿√‿⌊‿⌈‿|‿¬
+
+    bt ← {⥊𝕏⌜˜↕2}¨f
+    ∧⌾(⌽¨⌾(⊏˘)) bt (⍷∘⊣≍˘⊐⊸⊔)○((∧´∘∊⟜(↕2)¨bt)⊸/) f
+┌─                       
+╵ ⟨ 0 1 0 0 ⟩ ⟨ < ⟩      
+  ⟨ 0 0 1 0 ⟩ ⟨ > ⟩      
+  ⟨ 0 1 1 0 ⟩ ⟨ ≠ ⟩      
+  ⟨ 0 0 0 1 ⟩ ⟨ ∧ × ⌊ ⟩  
+  ⟨ 1 0 0 1 ⟩ ⟨ = ⟩      
+  ⟨ 0 1 0 1 ⟩ ⟨ √ ⟩      
+  ⟨ 1 1 0 1 ⟩ ⟨ ≤ ⟩      
+  ⟨ 1 0 1 1 ⟩ ⟨ ≥ ⋆ ⟩    
+  ⟨ 0 1 1 1 ⟩ ⟨ ∨ ⌈ ⟩    
+                        ┘
+
+

Some functions have fast implementations when one argument is boolean. The only ones that really matter are ×/∧, which can be implemented with a bitmask, and ∨, which changes the other argument to 1 when the boolean argument is 1 and otherwise leaves it alone. ⋆ is ∨⟜¬ when 𝕩 is boolean.

+

A function of an atom and a boolean array, or a monadic function on a boolean array, can be implemented by a lookup performed with (preferably SIMD) bitmasking.

+

Strength reductions

+

Trivial cases

+

Several cases where either one argument is an atom, or both arguments match, have a trivial result. Either the result value is constant, or it matches the argument.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
ConstantConstantIdentity
a+0
a-aa-0
a¬aa¬1
a×0*a×1
a∨1a∨0
a÷a*0÷a*a÷1
a⋆0a⋆1
¯∞⌊a, ∞⌈n
a>a etc.a⌊a, a⌈a
+

None of the constant column entries work for NaNs, except a⋆0 which really is always 1. Starred entries have some values of a that result in NaN instead of the expected constant: 0 for division and ∞ for multiplication. This means that constant-result ÷ always requires checking for NaN while the other entries work for integers without a check.

+

Division and modulus

+

Division, integer division, and Modulus by an atom (a÷n, a⌊∘÷n, n|a) are subject to many optimizations.

+ -- cgit v1.2.3