proposal: all: quaternions #19813

Closed
mdempsky opened this Issue Mar 31, 2017 · 26 comments

Comments

Projects
None yet
Member

mdempsky commented Mar 31, 2017

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 i2 = j2 = k2 = 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.

mdempsky added the Proposal label Mar 31, 2017

griesemer added this to the Go1.9 milestone Mar 31, 2017

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

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

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

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

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

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

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

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

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

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

Member

dsnet commented Mar 31, 2017

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

Contributor

rsc commented Apr 1, 2017

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?

Member

mdempsky commented Apr 1, 2017 edited

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.
Contributor

josharian commented Apr 1, 2017

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!

Owner

bradfitz commented Apr 1, 2017

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

Best Buganizer link ever.

Dorian commented Apr 1, 2017 edited

No quaternions grouping support? https://en.m.wikipedia.org/wiki/Quaternion_group It's like a fish without the river (or a first without an April).

Member

mdempsky commented Apr 1, 2017

@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 commented Apr 1, 2017

@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.

Contributor

btracey commented Apr 1, 2017 edited

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.

Member

mdempsky commented Apr 1, 2017

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 commented Apr 1, 2017

@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 = 0 or ei * 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!

Contributor

rsc commented Apr 3, 2017

April 1 is over.

rsc closed this Apr 3, 2017

Contributor

cznic commented Apr 3, 2017

You got me.

fibo commented Jun 7, 2017

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.

Member

mdempsky commented Jun 7, 2017

@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 commented Jun 7, 2017 edited

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment