proposal: all: quaternions

[mdempsky]

This proposal extends the Go programming language to include quaternions, a hypercomplex noncommutative division algebra that generalizes the complex numbers to four dimensions. They're particularly useful for representing spatial rotations, such as in 3D graphics.

Quaternions are generally represented in the form *a + bi + cj + dk, where a, b, c, and d* are real numbers, and i, j, and k are the fundamental imaginary units satisfying i² = j² = k² = ijk = -1.

Concretely, this proposal changes the language as follows:

• Generalizes imaginary literals to include j and k suffixes.
• Extends numeric constants to include quaternion constants.
• Defines new numeric types for quaternion128 and quaternion256 (and predeclares them).
• Extends the unary and binary + and - operators and the binary * operator to apply to quaternions.
• Defines a new quaternion built-in function to construct quaternions from four real numbers.
• Extends the real and imag built-in functions to also return the real and i-imaginary parts of quaternions.
• Defines new jmag and kmag built-in functions to return the j- and k-imaginary parts of quaternions.

Also, it implies corresponding support and extensions to standard library packages.

[gopherbot]

CL https://golang.org/cl/39217 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39218 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39221 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39222 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39219 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39215 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39214 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39216 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39220 mentions this issue.

[gopherbot]

CL https://golang.org/cl/39213 mentions this issue.

[dsnet]

For those interested, the language spec change is: https://go-review.googlesource.com/c/39213/

[rsc]

Thanks for taking the time work out the implementation consequences. I know this is blocking a team at Google, but I do wonder if maybe we should leave this for Go 2, for consistency with the handling of other recent language change proposals.

Is it possible we can patch this into Google's toolchain for now, and wait for Go 2?

[mdempsky]

Is it possible we can patch this into Google's toolchain for now, and wait for Go 2?

I think so. I see two significant technical disadvantages to that approach though:

1. That will also block their long-term plans to open source (see b/20170401).
2. It won't sound as impressive on a promo packet.

[josharian]

It won't sound as impressive on a promo packet.

Want to pick up the torch on int128, int256, and up? Think how impressive it would be to have added an infinite number of built-in types to the language. Plus a built-in type for crypto keys!

[bradfitz]

That will also block their long-term plans to open source (see b/20170401).

Best Buganizer link ever.

[mdempsky]

@Dorian That's a good point. Perhaps we should instead add direct support for Cayley-Dickson construction.

For example, if we extend the grammar for type literals to allow call-like syntax:

TypeLit = ... | identifier "(" Type ")" .

then we can add a new predeclared cayley composite type constructor function and define:

type complex128 = cayley(float64)
type quaternion256 = cayley(complex128)
type octonion512 = cayley(quaternion256)

(We can't simply add a new cayley keyword due to backwards compatibility.)

[md2perpe]

@mdempsky If octonions are introduced, since octonions are non-associative, multiplications of more than two octonions, e.g. x * y * z, need to banned and give a compilation error message. You must write (x * y) * z or x * (y * z) depending on what you want.

[btracey]

It seems if Go wants to add quaternions, it would be best to solve the more general "problem" of basic numeric types. Real numbers are the most commonly implemented, followed by complex numbers, which are both already in Go. After that though, quaternions are useful for geometric rotation, but there are more numeric types, such as dual numbers (and hyper-dual numbers) which are useful for automatic differentiation, and so come up in optimization and machine learning. Quaternions can be implemented at the package level, albeit with less nice syntax. This is the cost of no operator overloading.

[mdempsky]

If octonions are introduced, since octonions are non-associative, multiplications of more than two octonions, e.g. x y z, need to banned and give a compilation error message.

Note that + is already non-associative for floating point numbers; for example, https://play.golang.org/p/7_iVMwbT4o. The Go spec resolves this ambiguity by declaring that binary arithmetic operators associate to the left: https://golang.org/ref/spec#Operator_precedence (i.e., x * y * z always means (x * y) * z).

[yiyus]

@mdempsky: I do not think the Cayley-Dickinson construction is general enough.

In my opinion, what would be really useful is to add versors and multiversors and have full support for geometric algebra in the language. Then, not only we won't need quaternions, but neither complex numbers, and we will be able to easily represent vectors, areas and volumes in a natural way too, and even higher-dimensional entities.

So, I propose that we define a new kind of versor types float64.N (and float32.N), where N is a binary number that indicates the basis, such that the active bits of X correspond to the product of basis vectors. For example, for a 3D space:

float64.000 == float64.00 == float64.0 == float64 == real numbers
float64.001 == float.01 == float.1 == vector in x direction (basis e1)
float64.010 == float.10 == vector in y direction (basis e2)
float64.011 == float.11 == bivector in xy plane (basis e1e2)
float64.100 == vector in z direction (basis e3)
float64.101 == bivector in xz plane (basis e1e3)
float64.110 == bivector in yz plane (basis e2e3)
float64.111 == trivector in xyz  or pseudoescalar (e1e2e3)

The product of two versors gives a new one following the geometric product rules, such that if V and W are basis vectors (ie. they only have one active bit), then:

var v float64.V
var w float64.W
vw := v * w // == float64.(V^W)( v * w) if V <= W
            // == float64.(V^W)(-v * w) if V > W

Notice that this product is not commutative. The product of other versors follows from this definition. For example, to calculate the product of the bivector float64.11(1) by itself:

i := float64.11(1) 
isqr := i * i // == (float64.10(1) * float64.01(1)) * ((float64.10(1) * float64.01(1)) ==
              // == float64.10(1) * float64.01(1) * -(float64.01(1) * float64.10(1)) ==
              // == - float64.10(1) * float64.10(1) == -1 
              // which means that float64.11 values are imaginary numbers

Two or more versors can be combined in a multiversor, such that for example float64.X.Y has two values, that can be extracted with .X and .Y, float64.X.Y.Z would contain three values, and so on. To work in 2D and 3D spaces we could do:

const (
    X = 001; Y = 010; Z = 100
    XY = 011; XZ = 101; YZ = 110;
    XYZ = 111
)

type Vector2D float64.X.Y
type Complex float64.0.XY
type Vector3D float64.X.Y.Z
type Quaternion float64.0.XY.XZ.YZ // not exactly, but isomorphic

v := Vector2D {4., 1.}
vx, vy := v.X, v.Y  // equivalent to vx, vy := 4, 1

Products of multiversors are also resolved following the geometric product, ie. assuming that a multiversor is a sum of versors and applying the distributive property. eg:

v := Vector2D{vx, vy}
w := Vector2D{wx, wy}
vw := v * w  // == float64.0.XY{vx*wx + vy*wy, vx*wy - vy*wx}

A smart enough compiler could optimize quite well how to store and multiply different kinds of multiversors.

Later, this could be extended with a general multiversor type float64. and adding support for other kind of basis for which ```ei ei = 0orei * ei = -1```, which together with the proposal for arbitrary precission integers would give us support for Universal Geometric Algebra and we would be able to represent anything in G(inf, inf) using native types!

[rsc]

April 1 is over.

[cznic]

You got me.

[fibo]

Italian mathematician here.

Adding support to builtin quaternions (i mean something like q = 1 + 2i + j will attract many math and physic people, as well as many guys interested in robotics.

Consider it seriously, it is not a joke.

[mdempsky]

@fibo Why do you think they need to be builtin? Almost everything about this proposal can be done without any dedicated language or standard library support.

[fibo]

For example I am following Golang before it went 1.0, then recently I started using it to implement the Apollonian Gasket geometry and generate fractal images.

Other than the power of calculations (read concurrency), I was attracted by the sintax like 1+i * 2+2i to do complex number calculations, as well as the many math/cmplx functions, that are officially supported.

Having something similar for quaternions, instead of a third party package, I mean, enter the playground and start doing quaternion calculations out of the box, could attract many people studyng robotics and physics.

Also note that, since Smale (in my opinion the greatest USA mathematician) classified all manifolds for dimension >= 5, and dimension = 4 is still an open field of research, as well as other beasts like the 120-cell, and the Legendre theorem among others, having builtin quaternion support is something really exciting.

It is true there are few quaternion golang packages on github, I think that builtin syntax and support would be a real boost for the adoption of Golang in many science fields that use quaternion, i.e. math, physics and robotics for sure.

As a mathematician I appreciated also a lot that there are many complex functions available in math/cmplx, I can see it was coded by other mathematicians or people that studied deeply those functions, hence I am motived to use Golang and continue in that direction

We need math/hmltn

implementing quaternion, the name is in honour of Sir Hamilton of course