--- title: "Ivory: Geometric Algebra" packages: ['racketWithRackCheck'] --- ```{pipe="sh"} bash "$setup" geo.rkt for DEP in "$geometric_units" "$numbers_in_scheme" "$sums_and_products" \ "$zero_one_many" do ./extract "$DEP" done ``` ```{pipe="./hide"} #lang racket (require "geo-units.rkt" "num.rkt" "sums-and-products.rkt") (module+ test (require rackunit rackcheck-lib (submod "geo-units.rkt" test) (submod "num.rkt" test) (submod "sums-and-products.rkt" test))) ``` ## Geometric Arithmetic ## Adding and multiplying `geometric` numbers always results in another `geometric` number (i.e. `geometric` is closed under `+` and `×`). The rules of their arithmetic should mostly match what you're used to, for example: - Any `geometric` number multiplied by `0`, or added to its negative, is `0` - Any `geometric` number divided by itself, or multiplied by its reciprocal, is `1` - Adding a `geometric` number to itself is the same as multiplying by a `natural`, e.g. `(= (+ h₀ h₀) (× 2 h₀))`. This extends to subtraction (multiplying by an `integer`) and division (multiplying by a `rational`) - Addition is associative and commutative, and nested sums can be flattened, e.g. `(= (+ d₀ (+ i₁ i₀)) (+ d₀ (+ i₀ i₁)) (+ (+ d₀ i₀) i₁) (+ d₀ i₀ i₁))` - Multiplication is associative and nested products can be flattened, e.g. `(= (× h₀ (× h₁ i₀)) (× (× h₀ h₁) i₀) (× h₀ h₁ i₀))` - Multiplication "distributes over" addition in the usual way, e.g. `(= (× d₁ (+ h₀ i₀)) (+ (× d₁ h₀) (× d₁ i₀)))` - Multiplying a GA unit by itself (squaring) produces an `integer`, according to the definition of each "flavour", e.g. `(= (× 3 i₀ i₀) (× 3 -1) -3)` A product which includes *different* GA units, like `(× 5 d₀ h₁)`, cannot be simplified further. We allow these products to be abbreviated as a single value, like `5d₀h₁`. Likewise, a sum involving different (products of) GA units cannot be simplified, e.g. `(+ 4d₀ i₀i₁)`: we allow such sums to be abbreviated as a single value, whose "parts" are separated by `+`, like `4d₀+i₀i₁` (note the lack of spaces!). There are many equivalent ways to write such products and sums, so we declare that a general `geometric` number should be written in the form of a sum of products. For example `(× 3d₁ (+ h₁ i₀))` *does not* have this form (it's the product of a product and a sum), but we can distribute the multiplication to get `3d₁h₁+3d₁i₀`, which has the correct form. This makes it easier to spot when two `geometric` numbers are the same (similar to why we write fractions in their lowest form). Addition and multiplication of general `geometric` numbers proceeds as if their sums and products were ordinary terms grouped using parentheses, like the example in the introduction, e.g. `(= (× 2+d₂ 5+3h₀) 10+5d₂+6h₀+3d₂h₀)` ### The Geometric Product Anti-Commutes! ### The most important feature of Geometric Algebra is that the GA units *anti-commute* when multiplied together. This means the order of units appearing in a product is significant: a combination like `h₀i₀` is the *negative* of the combination `i₀h₀`. This extends to larger combinations too, with the result changing sign whenever a pair of *neighbouring* units are swapped: ```scheme (= (× i₀ h₁ d₀ i₀ h₁) i₀h₁d₀i₀h₁ ;; Shorthand for this product, in the same order -i₀h₁i₀d₀h₁ ;; Swap d₀i₀ to -i₀d₀ i₀i₀h₁d₀h₁ ;; Swap -h₁i₀ to i₀h₁ -h₁d₀h₁ ;; Since (= i₀i₀ -1), by definition of imaginary units d₀h₁h₁ ;; Swap -h₁d₀ to d₀h₁ d₀) ;; Since (= h₁h₁ 1), by definition of hyperbolic units ``` This may seem weird, but it only affects the GA units; any `rational` numbers occuring in a product commute in the usual way, both with each other and with GA units. From now on, not only will we convert all `geometric` numbers into a sum-of-products, but we will also write their units in alphabetical order, negating when a swap is needed. ### Reducing To Normal Form ### Our GA implementation relies on the normal form mentioned above, with a few extra conditions arising from our encoding as Racket values. We convert `geometric` numbers into this form using a `normalise` function, which uses pattern-matching to rearrange various non-normal structures; and recurses until the standard sum-of-products form is reached. ```{pipe="./hide"} ;; Helper functions (define/match (geometric? n) [((? number?)) #t] [((? unit-ga?)) #t] [((cons '× ns)) (andmap geometric? ns)] [((cons '+ ns)) (andmap geometric? ns)]) ``` ```{.scheme pipe="./show"} ;; Converts the given number towards its normal form (define (normalise:geometric normalise ≤ n) (match n ``` The remaining cases spot patterns between neighbouring elements inside products and sums: for example, when they're not in alphabetical order; or when a GA unit is multiplied by itself. We implement these using a helper function called `split-pair`, which is like `split` but finds a pair of neighbouring elements that satisfy the given predicate. Note that we only need to compare neighbours, since the sorting rules will bring problematic elements together! ```{.scheme pipe="./show"} ;; Replace the product of two equal? GA units, based on their flavour [(cons '× (app (split-pair equal?) ;; Match pairs of equal? values (list pre ;; Binds to elements preceding pair (? unit-ga? ;; Match only when we found a GA unit (app unit-flavour ;; Select result based on flavour (or (and 'd (app (const 0) x)) (and 'h (app (const 1) x)) (and 'i (app (const -1) x))))) _ ;; Ignore 2nd unit, since it's equal? to the 1st suf))) ;; Bind to elements occurring after matching pair (changed (cons '× (append (list x) pre suf)))] ;; A sum of two terms containing the same GA units, can be replaced by a ;; single multiple of those units; that multiple being the sum of the two ;; original multipliers/coefficients. [(cons '+ (app (split-pair (match-lambda* ;; Find a pair of products, or standalone units ;; (which are implicitly multiplied by one) [(list (or `(× . ,xs) (? unit-ga? (app list xs))) (or `(× . ,ys) (? unit-ga? (app list ys)))) ;; which only contain reals and unit-gas (and (not (findf (disjoin +? ×?) (append xs ys))) ;; and have the same GA units (equal? (filter unit-ga? xs) (filter unit-ga? ys)))] [_ #f])) (list pre ;; Match the products. If either is a standalone GA unit, ;; wrap it in a list when matching (for consistency) (or (cons '× xs) (? unit-ga? (app list xs))) (or (cons '× ys) (? unit-ga? (app list ys))) suf))) (let ([units (filter unit-ga? xs)] ;; xs and ys have the same units ;; Multiply all the coefficients in xs together into a single value ;; (this may be 1, if there were no coefficients!); and same for ys. [x-coeff (cons '× (filter (negate unit-ga?) xs))] [y-coeff (cons '× (filter (negate unit-ga?) ys))]) (changed (cons '+ (append pre ;; Multiply units by the sum of both coefficients (list (cons '× (cons (+ x-coeff y-coeff) units))) suf ))))] ``` We've now run out of simplification rules, and move on to arranging the elements of sums and products into alphabetical order. We do this by swapping any neighbouring elements which appear in the wrong order, which acts like a Bubble Sort algorithm. This is notorious for needing O(n²) comparisons in the worst case, but is acceptable here since (a) our lists are usually sorted, which gives optimal O(n) performance, and (b) it has low overhead, which can dominate the small-list regime we're in. When rearranging a product we need to introduce a `-1` when swapping GA units (since they anti-commute): ```{.scheme pipe="./show"} ;; Swap a product of GA units in the wrong order, and negate [(cons '× (app (split-pair (match-lambda* [(list (? unit-ga? x) (? unit-ga? y)) (unit Test results ``` {pipe="./tests"} ```