I suspect we'd see management companies trying out auctions and upgrade bidding not long after a resale prohibition passed. Or they'd reinvent the fare class system airlines use.
You're making assumptions that the parent isn't necessarily making. Imagine sending humans to other earthlike planets on hypothetical generation ships. Those humans could throw away their technology and rebuild from zero over thousands of years to send more spaceships of humans to yet further planets. Presto, an example of self-replicating biological von Neumann systems.
It's important to say that isn't self-replicating in the von Neumann sense, even setting aside the question of how it's being executed. Humans don't replicate, we reproduce and critically evolve, never more quickly or drastically then when we're introduced to a new environment with new selection pressures. Unless these future humans have the technology to avoid that natural drift then they won't be a probe for the original species in any sense, they will speciate. In fact if you send people on a one-way trip to start over from scratch, I think it's pretty extreme to imagine their nth descendants caring about the goals of the parent civilization. Even if they in turn become spacefaring it's not as though they'll act as "probes" for their ancient and probably forgotten ancestors.
There are decades old papers [0] on this subject that explicitly use humans as a analogy and call it "reproduction" because of the need to learn or evolve for local conditions. I don't think using terms in a way they've been used since the first serious analysis of the concept is going to confuse anyone.
I think it's pretty extreme to imagine their nth descendants caring about the goals of the parent civilization.
It's an example to demonstrate the concept in familiar terms, not a psychohistorical prediction.
When the printing press was invented by Gutenberg, it wasn't used to produce finished documents. Printed books had large margins and omitted initial letters to leave space for the manual steps of rubrication and illumination. Plus, the printing itself was a product of huge amounts of manual typesetting effort.
The results speak for themselves. Those early printed works are beautiful to a degree few other books have managed since.
I don't want to rain on discovering a genuinely cool bit of theory, but it's not "new" per se.
The equivalence with Einstein summation was noted in this paper [0]. Sandia labs wrote an SQL database based around graphBLAS called TenSQL a few years back. And something similar to your idea of relational algebra as the basis for AI had a paper published earlier this year [1], naming it Tensor Logic.
Are all of these common operations secretly relational, just with the wrong data model?
Sadly not, but you can get a long way before you find the limits. Modern databases are very well optimized for their use cases, but there's many other possible points in the design space to explore. If you want to really make efficient use of hardware, there are fundamental scaling problems with natural joins because of the combinatorial explosion that gives us WCO though. If you accept an inability to express triangular queries, you can get something that's embarrassingly parallel and scales really flipping well.
If you want to stick to the full relational model, you might be interested in Differential Dataflow [2].
Really happy to hear that this isn't new – with citations. I am a fan of rain :) Thank you for the references. I'm looking to build a real production system that could be used by scientists and data practitioners, grounded in a academic perspective. So, all this prior art is very helpful.
> Sadly not, but you can get a long way before you find the limits.
I'm really curious to know what the limits are! If you have a good understanding of these, I'd love to hear your perspective. I do think it's valuable to be able to spill out to the array paradigm, and that a project like Xarray-SQL lets users choose the best tool for the job.
I am a fan of Differential Dataflow, though I don't know the system too well. I'll take a closer look when I can.
I don't see how Tesla is a serious competitor in that matchup. Their sales have been declining for two years, and Chinese OEMs are clearly on the path to complete dominance in most foreign markets.
In the US market, I think Hyundai (and to a much lesser extent Kia) is probably the most interesting OEM. EV sales that aren't declining, the highest American-made percentage vehicles (relevant given recent policy changes), a manufacturing partnership with Waymo, widespread consumer awareness, and relatively lower prices than their competitors. It'd be nice if they provided a better repair situation than Tesla, but that's the current industry I guess.
I recommend pretty much everyone avoid fixed point and other float alternatives, barring exceptional cases after you've done your own numerical analysis, or you lack floating point hardware (rare these days).
Yes, fixed point can use simpler hardware. That's also a completely irrelevant consideration for software. The vast majority of processors are optimized for floats now and some operations (e.g. division) are actually faster.
The precision argument also falls apart. Any float with mantissa >= X+Y can get exactly the same results as a QX.Y fixed point. The float will actually perform better across the same range because you have to round it to perform like the fixed point. That means more precision, lower error, automatic normalization, better overflow behavior, a larger working range, etc. And it'll probably be just as fast, unless you're bottlenecked on memory bandwidth of inputs (unlikely). When you inevitably want an exp() or another special function, it's a heck of a lot easier to call libm than implement your own and it will perform better.
Floats are also much easier to get right for your coworkers that aren't numerical analysts.
I didn't recommend fixed point for simpler HW - I recommended it for better precision (if you know what you are doing). First, a point I didn't make, is that if you have 32 bits of fixed, you get way more precision than with a 32 bit float. But I can think of a pretty common case where a 24 bit int would win against a 32bit float: convolution filters.
If you have a filter whose inputs are supposed to sum up to 1 (which is the most common case), integer computations mean that, even with internal overflows, the end result will be correct. In contrast, with floats, you can lose precision. If you apply said operation 10000x recursively (say, you are 'stepping' a simulation), those errors can add up bigtime.
> Floats are also much easier to get right for your coworkers that aren't numerical analysts.
That one is true, however, when you have people, such as EEs who really care about precision, and know the theory behind it, then floats are often not the obvious choice. It has other advantages, like your calculation running the exact same regardless of CPU and/or compiler, which I'm sure a lot of analysts care about. Afaik finance people don't even use floats for things like account balances, because you can't represent something like 0.1$ exactly.
Fixed point has basically no language support, and is very hard to get right, but sometimes you need to do that.
Do you have any subject matter expertise in quantization errors? Like doing simulations or DSP work? Not trying to be antagonistic, just figure out where you're coming form.
> if you have 32 bits of fixed, you get way more precision than with a 32 bit float
You get 7 more bits for the most extreme numbers. Which is a good portion of 32, but not crazy. By the time you hit double precision you're only sacrificing 10 of your 64 bits to make your range considerations a hundred times simpler.
First, a point I didn't make, is that if you have 32 bits of fixed, you get way more precision than with a 32 bit float.
That's true, but I already responded to it. If you step up to the next size of float (e.g. f64), you have more precision than the fixed32. You can do exactly the same computation in f64 with equivalent inputs, and you'll get better precision than doing it in fixed32. Or you can round at every step like fixed does and get a bit-equivalent value if you don't want the precision. It's less memory efficient, but my point is that the remaining use cases for fixed point are exceptional/situational and getting increasingly niche.
Maybe using a bigger float type is cheating, but it's basically free because of the ubiquitous support for floats.
In contrast, with floats, you can lose precision.
This only happens with values outside the range of your fixed point type if you use larger floats as mentioned above. I consider that a different argument. You can alternatively view this as the float handling a situation more gracefully than fixed point would have.
Afaik finance people don't even use floats for things like account balances, because you can't represent something like 0.1$ exactly.
Finance types typically use decimal types from what I understand. This is really just the result of using a decimal syntax to initialize/output a binary representation. Fixed point has exactly the same problem. Decimals have an analogous issue with the value 1/3.
It has other advantages, like your calculation running the exact same regardless of CPU and/or compiler, which I'm sure a lot of analysts care about.
I wrote a library that makes floats more practically deterministic across platforms for very little cost (linked at [0] so you can see the limitations and numbers), and the underlying problem is [maybe] getting a standardized solution in C++29. You can get the same thing today just by changing compiler flags. If you need the special, non-reproducible float functions, your options are mainly to import a library or implement it yourself, same as fixed point.
Not trying to be antagonistic, just figure out where you're coming form.
I work in safety-critical automotive/robotics, used to do audio DSP, contributed a bit to the aforementioned standardization, etc. I also have a talk on this topic I've been working on for the last few weeks. It's a bit of a pet subject.
Fixed point has basically no language support, and is very hard to get right, but sometimes you need to do that.
There are absolutely situations for it, but that's exactly it: it's situational. And those situations are increasingly uncommon these days, now that hardware with good IEEE support is essentially ubiquitous and compilers/standard libraries are improving their implementations.
Thanks for answering my points in detail! I think this is one of those domains where there's enough theory and practical considerations, that basically given the same set of constraints, there's generally one set of correct conclusions.
To be clear I'm not anti-float, as they have less surprising behavior than fixed point, and are much less fiddly, but I do have to note that f32 sits at that awkward spot where it's not accurate enough for a lot of numerical work, but stepping up to f64 carries a significant performance penalty on things like GPUs, and most DSPs don't really give you f64 hardware at full rate, if at all.
In contrast, 32 bit fixed point gives you 6 extra bits of precision, (IEEE754 mantissa should count as 26 bit), which can often be the saving grace.
For example, in video games, if you mandate a 0.01mm precision, with int32, you get a 40kmX40km area, which is plenty, and with float32, you have to divide every dimension by 64, which is not enough for even mid-sized maps, and you have to employ tricks or go straight to f64.
Totally agreed that f32s can be awkward. I'm really just arguing that most of the time, you're better off starting with floats and seeing if there are issues. If there are, you can often take advantage of float tooling (e.g. fpchecker [0]) to make better choices about how to proceed, since virtually no one does numerical analysis on commercial codebases in my experience. Sometimes you can skip that if there's an obvious reason (e.g. no float HW, FPGAs), but the general direction of software seems to be towards universal availability.
You're right about that particular constraint, though I'd question why the achievable 2-4mm precision at 32 or 64km are meaningfully different. Covering up unstable collision code and adaptive methods would be a rewrite?
> The vast majority of processors are optimized for floats now and some operations (e.g. division) are actually faster.
This seems backwards. Hardware is optimized for floats because people use floats. If people used fixed point, hardware would become optimized for that instead.
Given an equal number of transistors, I'm pretty sure fixed point would be a lot faster on equally optimized hardware for almost all operations.
fixed-point provides uniform precision, exact integer-scaled arithmetic, is deterministic whereas floating point is more convenient but its not a panacea
As I said, floats can provide results that are no worse than a specified fixed point type. So if you want uniform absolute precision, just round down to the required precision.
Floating point is generally deterministic in practice with a fairly minor amount of effort, the major remaining issue being library rounding. I actually wrote a library that guarantees this for arbitrary code, with some small, obvious caveats like standard library precision. And the conference talks linked above note, the standard library issues are an increasingly solved problem for modern toolchains. The remaining cases are mostly things you won't do in fixed point. Let me know if you're aware of anyone computing erfc in fixed point for determinism though.
I'm not saying there aren't any situations where other systems are justified, but you probably won't know if you fall into any of them without the kind of numerical analysis that most codebases will never receive.
Totally fair if you have full control, my experience is often with databases where you can get warnings that float implementations can even change per-operating system (thanks MySQL) or per query plan (based on plan ordering) which is ... pretty bad!
I don't know much about real query planners, but if I understand what you're saying there may be ways to improve the situation.
If you stick to the safe bits I've been discussing elsewhere in this thread and your platforms implement IEEE floats, float math will also be commutative + associative and you won't have to deal with precision loss. That means your usable range will be narrower than the same size fixed type (because it's limited by the mantissa) but it's large enough to still be useful.
Fixed-point arithmetic provides uniform absolute precision; floating-point arithmetic provides almost-uniform relative precision, as used by scientists and engineers for literally centuries (“significant digits” except the binary version is more uniform than the decimal one customary with pencil and paper).
Hardware floating point on CPUs (including SIMD units) is almost always IEEE 754 compliant these days (excepting only IBM’s weird fantasy land), and there the rules for the non-YOLO operations (+, -, *, /, sqrt, fma) are completely unambiguous and deterministic: treating the inputs as exact, compute the mathematically exact result, then either return it as is if it is exactly representable as a floating-point number, or if it’s not then round it to one that is according to the current rounding mode.
Things that can mess this up:
- GPUs just do whatever they feel like will make them look faster on benchmarks, don’t count on anything.
- Transcendental functions (exp, sin, etc.) are really hard (multiple literal PhDs) to implement according to the rules I’ve just described (“correct rounding”), so you’ve only been able to get such implementations in the last few years, and I believe no stock libm has completely switched so bring your own if you need them.
- Decimal-to-binary and binary-to-decimal conversions, by contrast, are not that hard to implement according to the rules in principle (it’s making them fast that’s difficult), yet Microsoft couldn’t get it right for literal decades, so if you need Windows then double-check CRT versions and bring in well-known open-source conversion code as necessary.
- Denormal inputs or outputs are very slow in some implementations, leading to a hardware option to flush them to zero. Either make sure to not produce them or keep an eye on the option.
- The precise bit pattern of the NaNs you get for invalid inputs may differ across platforms. Either make sure to not produce them (you really shouldn’t) or canonicalize upon de/serialization.
- Sometimes compilers will try to HALP by performing e.g. single-precision math in double-precision accumulators and only rerounding upon store to memory; by fusing * followed by + (two roundings) to hardware fma (only one); by reassociating; etc. Take care to prohibit your compiler from doing these shenanigans (no -ffast-math or -funsafe-math-optimizations ever, in your code or in any dependencies, and God help you if you’re on MSVC).
- Most shamefully, the 8087 (despite spawning the entire IEEE standard in the first place) tried to HALP by using 80-bit registers, so if you need x86-32 then be especially careful with compiler settings (I seem to remember the HALP mode might even be ABI-mandated on some 32-bit platforms so you’ll need to violate that).
The concept of floating point is solid, the IEEE standard is stellar, but the superstructure around it is just—not, requiring an unnecessary amount of vigilance to just make it work as designed.
- Transcendental functions (exp, sin, etc.) are really hard (multiple literal PhDs) to implement according to the rules I’ve just described (“correct rounding”), so you’ve only been able to get such implementations in the last few years, and I believe no stock libm has completely switched so bring your own if you need them.
This is right, but it's useful to point out how important the "correct rounding" qualification is to the difficulty of the problem. Writing a "good enough" function with floats is easy even for non-experts. exp can be efficiently implemented in hardware with a 4 element lookup table and polynomial interpolation. Sin/Cos are range reduction + a minimax polynomial from sollya. But the standard [rightly] doesn't prescribe specific implementations, so you need fully correct rounding to have cross-platform determinism.
Correct transcendentals are also difficult in fixed point. When pigweed was implementing them for their fixed impl, they got help from from an ex. Mathworks floating point expert on the LLVM team with a relevant PhD to do it correctly [0].
This is one of my favorite pieces of internet writing, up there with the SR-71 speed check and the Story of Mel. Every time I see it, I have to read it again and end up giggling through the whole thing.
Grass doesn't prove it's fertile before modern fertilizers. Natural grasslands are often resource-poor places that most other plants can't tolerate. We sometimes replace one for the other because our main crops (wheat, maize, rice, sorghum) are all grasses, but e.g. Versailles probably would have had more forests, lakes, or a vineyard if it didn't have the gardens and lawns.
reply