Vanishing zeroes for geometric algebra in Rust | Hacker News Reader

Vanishing zeroes for geometric algebra in Rust

fanf.dreamwidth.org

57 pointsfanf229 comments

> In the concrete version, the code says that every Zero in the arguments should be un-vanished into 0.0 before doing the calculation; I am assuming that the generic multiply will be monomorphized, the concrete result expressions will be inlined, and constant propagation will turn expressions involving the Zero arguments back into no-ops.

Did you actually test whether this happens? If I understand correctly, you want to rely on the optimizer constant-folding multiplications with zero to zero. But strict IEEE floating point conformance notoriously does not allow collapsing multiplication with zero to zero (consider NaNs and infinities), or addition of zero to be a no-op (consider signed zeros).

Example:

https://godbolt.org/z/cGv17o

That also affects the overall goal, seeing as the type-level optimizations do assume the above properties. This means that you will get different results in certain edge cases than a "naive" implementation that always stores 16 floating point values for each multivector (and that's before getting to things like non-associativity of floating point operations).

Ooh thanks that’s horrible :-)

Yes I need to investigate that in more detail.

Edited to add: one option for making my assumption true might be to use fmul_fast and friends https://doc.rust-lang.org/core/intrinsics/fn.fmul_fast.html

An alternative could be to create another zero-sized type for NaN and Infinity

Yeah I have been thinking about something like that, but we don’t know at compile time when NaN will turn up. (I suppose if you take abstract interpretation as far as you can, you get to partial evaluation, but I am not in that game!)

Another idea is to rely on Rust-specific optimizations: make the concrete type used by the result expressions into

    enum ZeroNum {
        Zero,
        Num(f64),
    }

Operator overloading on this type works like it does on the separate Zero and Num types, but the cases are tested at run time instead of compile time. But this type is only used in a small context where the optimizer should be able to eliminate the checks in the same way I naively thought it would do for ops with 0.0.

It's incredible the "right" response to OPs comment isn't "for all the great benefits we've had, we've also really f'ed up programing along the way".

Instead it's "yes it's my fault that I forgot about the nonsensical concepts of positive and negative zero, and that the associative operation of addition isn't actually associative, and that addition's identity isn't actually and identity..."

Scheme has Numerical towers that automatically abstract over exact numeric representations, but instead this clearly smart engine is forced to spend mental cycles remembering and debugging this arbitrary special case logic.

Nulls, floating point, ... we really have some huge programming mistakes that have cost so much time over the years.

An no this isn't a rant on 'everybody should use scheme or Lisp, because that completely misses the point. It's that 'Worse Is Better' really is worse in the long run.

I feel like geometric algebra is an entry point for programmers to higher level mathematics. But GA itself isn't actually that interesting or useful. It's not like GA is being used to prove new math theorems or new calculations. But I do like being able to talk about >3 dimensional geometry with more people so that's a win. It's almost like GA is a marketing pitch for Grassmannians/Flag Manifolds/Clifford Algebras.

> It's not like GA is being used to prove new math theorems or new calculations.

Maybe the problem isn't with GA but with the fact that few people know about it?

I think that people use GA and Clifford algebra interchangeably.

> few people know about it

Grassmannians, Flag Manifolds, and Clifford Algebra were all introduced in my undergrad math degree. I think it's just CS people who are hyping GA up.

Clifford algebra is definitely not common. And when you say introduced, what do you mean by that? How much time was spent on it?

They were motivating examples of both the Algebraic Geometry and Differential Geometry courses that I took. They were used in multiple homework/exam problems in those courses. And I didn't go to some fancy private school, this was senior level math classes at a flagship public state school in the south.

Algebraic geometry / differential geometry are both treated as “sophisticated”, “advanced” subjects. They typically require high-level preparation (several years of pure math courses as prerequisites) and are taught in an extremely abstract way, often are deferred to grad school, and are seldom if ever taught to non-math-major undergraduates.

But geometric algebra, a.k.a. real Clifford algebra (“geometric algebra” was Clifford’s own name for it), can easily be taught to high school students in a very simple concrete way, and then used throughout science/engineering/computing courses aimed at non-math-majors. It can unify and simplify the wide variety of other mathematical formalisms that are used throughout undergraduate technical curricula. It is straight-forward to implement in a computer, and it makes calculations much easier to write down.

The way GA is promoted by the non-math world does not unify mathematical formalisms. I've yet to see a GA implementation that does more than reimplement rotations/quaternions.

How many differential geometry implementations do you know?

> I've yet to see [...]

Most implementations I have seen do much more than quaternions. How hard did you look?

Here’s an example you can play with in a browser, https://enkimute.github.io/ganja.js/

But what is implemented in computers is not 1:1 with the algebraic tools that can be profitably employed to solve geometry problems symbolically. GA is a rich language full of useful tools which can describe/model many kinds of problems.

Coming from a math background, let me recommend you start with https://arxiv.org/abs/1205.5935

Ok but how much time did you spend on them?

> But GA itself isn't actually that interesting or useful. It's not like GA is being used to prove new math theorems or new calculations

That's hardly the only definition of usefulness. I haven't used it yet but based on what I've read GA will be extremely useful in 3D graphics coding by unifying representations for previously distinct concepts and by providing formulas for common tasks with fewer special cases.

I’m a huge GA fan, but until really sophisticated compile-time algorithms can aggressively reduce the computations it won’t be useful for graphics anytime soon. For instance, the “proper” GA setting is 5d conformal, which requires 32x32 matrix computations. The standard operation is “multiply” (even for translation!); that takes an operation from 4 ops to ... 32k ops.

Clearly the generic n-dimensional GA libraries out there have little use for real time graphics, but projects like https://www.jeremyong.com/klein/ that are specialized to 3D with a focus on efficiency look promising.

This is fantastic; thank you!

Depends on your definition of calculation. From what I've seen so far, the simplifications that GA makes are mostly on the symbolic side. That is, it makes the written equations more compact. But the math "under the hood" is the same. So I don't see how that would yield anything useful from a computing sense. Might make the programming easier to think about in a way similar to monads in Haskell/functional languages.

You should check out the bivector community dedicated to geometric algebra https://bivector.net/.

Check out a demo https://observablehq.com/@enkimute/animated-orbits

Join the discord https://discord.gg/vGY6pPk.

Enki (the guy behind bivector) also gave a talk on GA at SIGGRAPH 2019 https://www.youtube.com/watch?v=tX4H_ctggYo

Very interesting, but in the end this violates many good programming practices. The author is going to end up with a single type that can represent points, lines, rotations, planes, and probably more. The same operations will do different things based on which of those things you give them. It's important that the compiler can figure it all out because the programmer won't be able to tell what a*b does by looking at their code.

Not sure if I should be impressed or horrified. ;-)

My plan is that the geometric algebra operations will be generic in Rust like they are in maths, but application code will be more concrete, using type aliases for points, rotations, etc. So the programmer can choose to be as abstract or specific as they want, depending on what makes sense in a particular situation. For example, if I have something like a polyhedron, I'll declare that as an array of points. A function for something like intersecting a line with a face (raytracing) will be generic internally but have a more concrete signature.

I don't yet know how well this will work in practice :-)

Sounds good. Keep going. We can never move forward if nobody tries.

> The author is going to end up with a single type that can represent points, lines, rotations, planes, and probably more.

That's the point of geometric algebra!

The concept is that you can think of a line as a circle with infinite radius. Similarly, a plane is a sphere with an infinite radius. A rotation is can be represented using two reflections along lines or planes. Etc...

This makes some algorithms much more elegant, by removing conditional "if" statements. This matters when interpolating, which is the most common practical application of GA: game engines and robotic control often have problems with interpolating arbitrary rotations. With GA, there's no problem.

> The concept is that you can think of a line as a circle with infinite radius

That's a different thing though. "Thinking of something as" is not the same as "is" in terms of types. The OP is right that in terms of programming ergonomics, it would be better to have distinct types that share the same operations, so you can _treat_ them in similar ways.

You can have mathematically meaningful sub-types of a GA multi-vector that also map nicely to some basic shapes or transformations.

Generally speaking, a multi-vector can be broken down by which "grades" it contains. There are subspaces like "all even grades" that are closures under all basic operations.

If I remember correctly, the "even subset" of a 3D GA multi-vector is isomorphic to the Quarternions, which is why they turn up so often in 3D graphics libraries.

But think about how messy this is! These 3D libraries are blending together subsets of vaguely related algebras that are not "compatible" from a type theory perspective and so they're forced to convert back-and-forth. It's like mixing Unicode UTF-8 with Latin-1 byte strings. If you squint, it looks like one is the subset of the other... but not really.

With a pure GA-base library, the "rotation interpolation" functions would use the "even multivector subset" type, and be totally compatible with the rest of the library. It's the same type definitions, just with different parameters. This would be like using UTF-8 Unicode throughout the program, but having the ability to define a string-based type that only allows the "Basic Multilingual Plane".

> It's the same type definitions, just with different parameters

The wording is important here. These "type definitions" you are talking about are not types. We usually call them "type constructors". So we mean the same thing, but please don't call multivector out to be a type without specifying the "grade" (then it becomes a type).

> That's the point of geometric algebra!

Yes, exactly. And making that not happen is the point of using distinct types `int` vs `float` vs `char* ` vs `struct foo* ` rather than stuffing everything into a `register_t`, or worse, `object`. (Or, as the case may be, `scalar` vs `vector` vs `bivector` etc, rather than stuffing everything into `multivector`.)

Reply on news.ycombinator.com