30 ms·
Vanishing zeroes for geometric algebra in Rust
- phkahler 6y agoVery 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. ;-)
- fanf2 6y agoMy 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 :-)
- phkahler 6y agoSounds good. Keep going. We can never move forward if nobody tries.
- jiggawatts 6y ago> 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.
- valenterry 6y ago> 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.
- jiggawatts 6y agoYou 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".
- valenterry 6y ago> 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).
- a1369209993 6y ago> 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`.)
- WoahNoun 6y agoI 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.
- adamnemecek 6y ago> 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.
- WoahNoun 6y ago> 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.
- adamnemecek 6y agoClifford algebra is definitely not common. And when you say introduced, what do you mean by that? How much time was spent on it?
- WoahNoun 6y agoThey 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.
- jacobolus 6y agoAlgebraic 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.
- adamnemecek 6y agoYou should check out the bivector community dedicated to geometric algebra https://bivector.net/ https://bivector.net/. Check out a demo https://observablehq.com/@enkimute/animated-orbits https://observablehq.com/@enkimute/animated-orbits Join the discord https://discord.gg/vGY6pPk 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 https://www.youtube.com/watch?v=tX4H_ctggYo
- MauranKilom 6y ago> 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 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).
- fanf2 6y agoOoh 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 https://doc.rust-lang.org/core/intrinsics/fn.fmul_fast.html
- frazar0 6y agoAn alternative could be to create another zero-sized type for NaN and Infinity
- fanf2 6y agoYeah 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.