A Radical Approach to Computation with Real Numbers [pdf]
johngustafson.net
johngustafson.net
With unums 2.0, you can specify your own lattice of preferred exact values between 1 and infinity, albeit with recommended guidelines, and then the projective real line is auto-populated with the reciprocals, the negatives, and the open intervals between exact values. There is a continuum between table lookup (low precision) and float-type calculation (high precision), and I am mainly interested in table lookup for low-precision arithmetic. It is surprising how often it is better to use a small number of bits but obtain rigorous bounds (that do not grow exponentially like they do with intervals) than it is to use double-precision or even single-precision IEEE floats and obtain 15 or 7 decimals of answer, none of which decimals are guaranteed correct.
The idea is to work toward software-defined numerical systems that can be optimized for particular applications, for the purpose of saving bits and thereby reducing energy/power requirements while simultaneously improving answer quality and possibly increasing ease-of-use.
With unums 1.0, too many people had hopes of simply replacing their floats with unums and getting an improvement. While that does happen in many cases, in the general case where there are hazards of the dependency problem or the wrapping problem, you need some knowledge of uboxes, and the Julia and C versions tend to gloss over this essential aspect of the computing environment. I think unums 2.0 solve this by making the SORN the fundamental way of representing arguments to arithmetic operators, since they have their "ubox" aspect built into them and there is no need to choose a preferred ULP size.
Are there any good notes at least on a methodological level for this 2.0 design? It's super fascinating, and colleagues of mine on the Modelling side loved reading the deck. Also would like to see more of the ideas :)
I think there might be something to this "new unum" especially if there can be a shortcut that trims the size of the lookup tables when going to higher precision.
PS if anyone has some interesting math-ey contract work let me know.
It seems what we have here is a finite set A (in arithmetic, A would be a finite collection of sets which constitute a partition of the reals) and two operations: f, g: P(A) × P(A) -> P(A), taking a pair of subsets of A to another subset of A, with the property that f(W ∪ X, Y) = f(W, Y) ∪ f(X, Y), and so on. This can all be represented as a bitmask table of size |A|^3, or half if commutativity is enforced.
We also have the "inverse" which takes X and Z, and returns the set {a ∈ A : f(X, {a}) ∩ Z ≠ Ø}.
If I'm not mistaken, the mechanisms for doing all of this in hardware would come for free, and it represents quite a variety of problem domains beyond arithmetic. Perhaps some arithmetic-specific optimization would be ruled out (e.g. the bit twiddling to get additive or multiplicative inverses).
This is great practically for modeling quasicrystals, as well as things like buckyballs, certain types of viruses, architectural structures, ...
If you want to play with the symmetries, I recommend buying some Zometool construction toys, https://www.zometool.com
On Reddit I divulged into why this doesn't pass my sniff test. This seems to be dressed up interval arithmetic with a worse subset of the number line as the bounds.
https://www.reddit.com/r/programming/comments/4d08g0/a_radic...
I recommend reading the book. Even if you ultimately decide that they’re an offbeat set of ideas that won’t manage to hit the mainstream, it has very clear exposition and does a nice job explaining the current floating point system with great diagrams.
My problem with it is mainly that I think he goes off the rails a little bit in the end when he starts throwing standard analysis techniques out the window and advocating that people solve more problems with brute force methods. This could be useful for some problems but I think he oversells it.
Also, unums are incompatible with any of the significant amounts of work that have gone into studying numerical stability, etc., for floating point computations, so it’s hard to judge a priori how many types of scientific computing algorithms might need to change.
I think your assumptions about what is slow or fast are off base though. Most of the time spent in modern computers is moving data around, not performing arithmetic per se. Adopting something like unums would require quite significant architecture changes, but with a machine designed for it most computations shouldn’t necessarily end up slower than with standard floating point. [This is a bit of a guess, since these don’t exist, making them hard to benchmark.]
> I think your assumptions about what is slow or fast are off base.
Large lookup tables are unwieldy. If massive lookup tables worked above 8 bit or so, why wouldn't they be used already?
> these computing number systems [...] have a dyadic system wherein every represented number is some multiple of a power of two.
For IEEE floats, sure. For Unum IIs, logarithmic number systems or level index number systems, no. Except in the sense that every real number is a multiple of some power of two.
It's true that Unum IIs include intervals, but I factored that out of the question when I pointed out it's equivalent to just supporting open and half open intervals without them. And then you do indeed have a subset of the reals.
I don't really get why you say you're not representing real numbers. 1 is a real number, and is exactly representable in IEEE floating point. (Technically infinities and NaN mean it's not strictly a subset, but that's pedanticism.)
1 is an integer. It’s easy to make a computer representation for integers, especially integers with some finite bound. How about exp(1) or arccos(-1)... suddenly not precisely representable anymore.
I think it’s misleading / counterproductive to talk about IEEE floats as subsets of “real numbers”, because e.g. Math.PI is a clearly different thing than the “real number” π (whatever that might be).
Calling floats “exact” is also IMO problematic, since in practice every computation using floats involves rounding.
(I also think it’s problematic for Gustafson to call the numbers in his system “real numbers”, even if you could in principle build new hardware with the idea to perform arithmetic on any particular (decided before hardware design) small set of real numbers you want.)
It's true that most floating point computations involve rounding, but there's no contradiction in that. If you think floats are inexact you can get into a lot of confusion about things; you might miss, for example, that `(a + b) / 2` is exact (except on overflow to infinity, or languages that don't enforce floating point correctness) or that Javascript's integers are actually just floats. Considering floats as inexact might lead you to believe they represent ranges of numbers, eg. x ± ½eps, which is confusing. I've seen more damage from this belief than most other myths about floats, at least among experienced programmers.
The whole point of floating point arithmetic is to be approximate, maintaining only a particular precision because otherwise the number of bits in the answer doubles every time we multiply. If someone cares about exact arithmetic, floats are the wrong tool for the job.
As such, to do pretty much anything with floats you have to keep some idea in mind of the relative accuracy of various values, and the condition number of every operation/algorithm. None of this is explicitly included in the number, you just have to track it manually.
Instead of thinking of a float coming out of some algorithm as an exact value, you should generally think of it as a representative of some implicit range of possible values, a range typically somewhat bigger than ±½eps.
Rather than thinking of a float as some range of values, you should think of it as a randomized sample inside some (probably unknown) range.
It’s not clear whether a pure lookup table approach would scale to 32-bit or higher numbers. The last slide lists as a future research question, “Create 32-bit and 64-bit unums with new approach; table look-up still practical?”
>Rather fast to calculate; addition is mostly trivial and multiplication is reasonable...
Is that true? Having coded a softfloat I have to respectfully disagree.
> So slow the values need to be cached (which works for 8-bit values, but not anything bigger),
I think you're misinterpreting the description: The values don't need to be cached, caching is chosen specifically to get O(1) calculation.
> The values don't need to be cached
I don't see how addition could be implemented in a semi-reasonable amount of time without table lookup, nor does it seem to be mentioned.
To give you an idea of actual time to do those things, doing an add takes around 300 picoseconds, while the multiply is around 3,000 picoseconds. An order of magnitude increase in time to do an operation is a lot when it comes to hardware complexity (and thus associated area and power cost).
Inputs into system can be either boundary/initial conditions and constants. It seems like here, you essentially have to design the number system to match the problem, is this correct?
How can someone solve odes with this? I can see this solving constraints (which is basically algebra) but how about dynamical systems, especially when you don't quite know the behavior of the system, specifically, the bounds of your solution (which allow you to define your interval boundaries)? For example, what about chaotic systems (which are difficult in normal math too, I know). How about min/max problems (finding the global minimum of a function)?
It sounds like one would have to iterate your number system until you find your solution, which sounds like just offloading the difficulty somewhere else. (For finding the minimum of a function, you iterate as well, essentially). I think it makes sense that this does some problems well, but I need help to buy that it does all problems well.
I’m not sure to what extent if any unums can help solving ODEs. I haven’t seen any ODE experts examine unums yet or write down their impressions.
Not quite, it mainly is a system that is sensitive to initial conditions. For that reason, for a "range" of initial conditions wouldn't be helpful for a chaotic system, as you would get wildly different final results over that range for a particular set of conditions (ie., constants in the ODE), unless the range is small...and bam, you have a floating point with a +/- on it and probably an unum with a large number of intervals.
For the weather, for example, you can still tell someone what it will be (with some degree of accuracy) tomorrow, but the weather three weeks from now is unpredictable due to that sensitivity to the initial conditions (ie. now).
John Gustafson: http://www.johngustafson.net/
It just bugs me. There is nothing unprecise or inexact about the number pi. Ahh, very interesting topic nonetheless.
Its a shame, as many superior innovations basically remain sidelined, but the pre-existing infrastructure is in production and you never change a running system. You would need a easy integrate able hardware option, that allows a simple auto-conversion of a preexisting codebase and which would then run in parallel for quite a while, to even just be considered :(
For instance, when I read an equation like this:
Information = /uncertainty
If you want, in essentially every programming context where `-x` is meaningful, you can write `0-x` instead. It’s arguably less confusing.
The point he’s trying to emphasize is that in his proposed number system, every exactly represented number has an exact multiplicative inverse, which can be computed by flipping bits, analogous to computing the additive inverse with a floating point number or signed integer.
And you don't need to make a point that every number has a multiplicative inverse. That's already established by simply pointing out that these are the projective reals and that 1/0 = ±∞. All non-zero reals already had multiplicative inverses just as they had additive inverses.
Edit: he clearly wanted to emphasize that this is a unary operator. Using 1/x as the symbol instead of /x or ÷x would weaken the desired association.
* The smallest non-zero value is 1e-9.
* The biggest non-infinite value is 1e9.
* The first integer that shows roundoff error is 3.
* The integer 100001 loses its last digit. 100001 -> unum -> float = 100000.
See the link at: https://www.reddit.com/r/programming/comments/4d08g0/a_radic...