# Ivory: Geometric Algebra

## 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:

```
= (× i₀ h₁ d₀ i₀ h₁)
(;; Shorthand for this product, in the same order
i₀h₁d₀i₀h₁ ;; Swap d₀i₀ to -i₀d₀
-i₀h₁i₀d₀h₁ ;; Swap -h₁i₀ to i₀h₁
i₀i₀h₁d₀h₁ ;; Since (= i₀i₀ -1), by definition of imaginary units
-h₁d₀h₁ ;; Swap -h₁d₀ to d₀h₁
d₀h₁h₁ ;; Since (= h₁h₁ 1), by definition of hyperbolic units d₀)
```

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.

```
;; 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!

```
;; Replace the product of two equal? GA units, based on their flavour
[(cons '× (app (split-pair equal?) ;; Match pairs of equal? values
list
(;; Binds to elements preceding pair
pre ? unit-ga? ;; Match only when we found a GA unit
(;; Select result based on flavour
(app unit-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
;; Bind to elements occurring after matching pair
suf))) cons '× (append (list x) pre suf)))]
(changed (
;; 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))])
cons '+ (append
(changed (
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):

```
;; 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<? y x)[_ #f]))
list pre x y suf)))
(append '(× -1) pre (list y x) suf))]
(changed (
;; At this point products should contain no nested sums or products, only GA
;; units and non-geometric coefficients. Move the latter to the front.
[(cons '× (app (split-pair (lambda (x y) (and (geometric? x)
number? y)
(not (geometric? y)))))
(list pre x y suf)))
(cons '× (append (list y) pre (cons x suf))))]
(changed (
;; Leave anything else unchanged
[n (unchanged n)]
))
```

## Code

Here’s a URI containing all of the Racket code generated by this post:

## Test results

`{pipe="./tests"}`