The definition of "basic step", which includes arithmetic on unbounded integers, is suspicious. And I don't see any attempt at establishing an upper bound on the size of coefficients. I wouldn't be surprised if they grow exponentially.
This might be it. Good catch. A machine that can perform all integer arithmetic operations (+, -, *) in constant time can solve all problems in PSPACE in polynomial time.
Yup. Just at a glance, I don't see even a cursory attempt to prove that the upper bound on the proposed algorithm's time complexity is actually a polynomial. It depends on the "serial numbers of [...] monomials, in the natural order of monomials". But the number of different possible monomials in a polynomial with bounded length is obviously exponential.
The closest the paper gets to actually talking about time complexity is:
> As it is mentioned in [3], there is no sense to make use of the formal definition of Turing machine for this problem. From practical point of view, it is much more useful to show existence of a polynomial-time constructive algorithm for solving it ([2]). Therefore, in the next section we will introduce our own definitions and notations, describing a kind of a formal computer, more practically oriented, but resembling that of a Turing machine.
But the so-called "formal computer" is only described in extremely hand-wavy and informal terms, and no attempt is made to relate the number of "steps" it would perform to the running time of a corresponding Turing machine.
I sometimes wonder if using logarithms would be more appropriate in most cases. Then we can simply add up the numbers as one "would expect".
We could choose the base to be ~2.7048138 such that 1% regular growth corresponds to 1% logarithmic growth. For low percentages they would mostly agree. But +40% would become +34% while -40% would become -51%, thus making the combined effect more apparent.
I work on developing better tools for solving computational geometry problems robustly and efficiently, so I got quite excited when this paper first appeared.
However, while the type theoretic developments based on Abstract Stone Duality is interesting, they mostly ignore the problem of efficiency by simply representing every real number as a Dedekind cut. Thus, it doesn't scale without significant advances in compiling real arithmetic. A problem I'm working on presently, but it might take a few years...
This sounds like unums, a proposed alternative to IEEE floats, where roughly speaking the significand can have variable size thus only boasting as much precision as the accuracy warrants.
Does it solve the equality issue? An epsilon tracker would allow you to say it's equal within the margin of error for the computation.
If so that makes them much more interesting to me. Floating point bugs manifest themselves at non linear parts such as equality and comparison operators.
I haven't really seen the issue of equality dealt with explicitly, but it appears that you can extract the bounds of the interval implied by a given unum. Essentially, it seems like an alternative to interval arithmetic with potentially tighter bounds and faster computation.
It gets even worse: (1 + 2 ^ 53) - 2 ^ 53 evaluates to 0 while 1 + (2 ^ 53 - 2 ^ 53) evaluates to 1 (the correct result), which means that even the operation of adding three floating point numbers has unbounded relative error in the general case.
This is a great source of frustration in computational geometry, where this turns from a quantitative issue to a qualitative one, since if we get the sign of an expression wrong our data structures might no longer reflect the actual topology of the problem.
> which means that even the operation of adding three floating point numbers has unbounded relative error in the general case.
Its not quite "in the general case".
In "any case with subtraction", there is unbounded relative error. And remember that addition with negative numbers can become subtraction.
Error-management is very important. But if you can GUARANTEE that your operations have the same sign, and that you're only using addition, multiplication, and division... then error is easier to track.
Its that subtraction (aka: cancellation error) that gets ya.
It is true that cancellation errors are often the source of wrong results.
However, computations involving IEEE floating point arithmetic can go horribly wrong even if there is no addition and no subtraction whatsoever, no divisions, and only a very small number of rounding errors. Here is one such example:
Even professional users working in this domain will have a hard time to locate the cause of such problems involving IEEE floating point arithmetic. The format is extremely error-prone to use for casual users and experts alike.
Ehhh... I think that paper kinda "tricks" you with point #3.
> Only 257 algebraic operations, so no hordes of rounding errors
Rounding errors in Floating-point math grows exponentially in the common case. So 257 operations is more than enough to wipe out 53-bits of precision. Its not "hordes" of rounding errors that cause issues. Its the exponential nature of rounding errors, exponentially increasing every step of the way.
Well, the general case is that there might be a subtraction. In IEEE arithmetic the sum (or difference) of two numbers is guaranteed to be within 1 ulp, which is a very good bound on the relative error. The problem begins when you feed this slightly inaccurate result into some other computation that magnifies the error.
Now, one might have hoped to derive some bound on the relative error of sums with a small number of addends. My point is that already with three terms this is a lost cause.
Of course with extra assumptions on the nature of the input it's possible to state something stronger. In my example of computational geometry this is never the case since unstable arithmetic corresponds to geometric singularities and the real world is never in general position.
> Now, one might have hoped to derive some bound on the relative error of sums with a small number of addends. My point is that already with three terms this is a lost cause.
Difficult? Yes. Lost cause? Nope. Although it really helps to define error in terms of your largest addend.
The proper solution to addition / subtraction problems in IEEE754 Floating point is to sort the numbers by magnitude. That ensures that the smallest numbers have the best chance of being "detected" in the floating point operation.
For example... 1 + 2^53 + 1 needs to be sorted into 1 + 1 + 2^53.
Or 1 + 2^53 + 1 - 2^53 needs to be sorted into 1 + 1 + 2^53 - 2^53 (which equals 2. Hurrah! We're exactly correct!).
If all the numbers are sorted from smallest to largest, then the worst case error is relative to 2^53, the largest number in this addend sequence.
I admit that I'm cheating and moving the goalposts a little bit... But that's what you gotta do when you work with Doubles.
----------
> Well, the general case is that there might be a subtraction. In IEEE arithmetic the sum (or difference) of two numbers is guaranteed to be within 1 ulp, which is a very good bound on the relative error. The problem begins when you feed this slightly inaccurate result into some other computation that magnifies the error.
Overall, this statement rings true. In practice, all that sorting and stuff only minimizes the cancellation error. Because the "relative error" as you define it is most important in multiplication and division problems, and as you noted... relative error is unbounded.
But if you keep positives and negatives separated, you can ensure that only one cancellation occurs in any sequence. IE:
2 * (25 * sum(array1) - sum(array2))
Normally, this has a cancellation error, which is then multiplied with the 2 (which makes the cancellation error grow). You distribute the multiply and split the arrays as follows:
This sequence guarantees one cancellation error at the very end, and it also ensures that there are no multiplications that occur after the cancellation error.
I wouldn't call this a "lost cause", but this sort of finagling is tedious, error prone, and certainly difficult. But necessary if you want to maximize accuracy in a long-running simulation.
The lost cause I am referring to is deriving a useful relative error bound on evaluating a+b+c. The implied conclusion is not that floating point arithmetic itself is a lost cause, merely that it's a minefield from step one.
Of course, if you move the goalposts and measure the error compared to the magnitude of the largest number it gets significantly more manageable! Such a situation is benign, relatively speaking.
In my primary domain of computational geometry we don't have this luxury as the sign must be correct. Even ordering by magnitude is insufficient then; for example evaluating 2^54 - 2^54 + 2 - 1 using this method gives 0 when it should have been 1 (and incidentally, in this case a simple left associative ordering would have gotten it right so it's not even guaranteed to improve matters -- not that anyone said otherwise, but it's yet another example that extreme caution is warranted).
Eventually you end up with ideas like http://www.cs.cmu.edu/~quake/robust.html. The effort that goes into getting even the sign of a sum of products correct in every case is absurd.
Unfortunately, most of the computational geometry code I see usually involves starting with the naive implementation and when things go awry various tricks like Kahan sums or ordering by magnitude are applied hoping that the problem goes away or becomes sufficiently obscure, but never is there an attempt to clarify the exact numerical requirements of the result. Even expensive industrial software is prone to this and will sometimes crash if you happen to present it with a slightly unusual piece of geometry.
Using pairwise addition is a very good alternative with the added benefit that it can be easily parallelized.
Personally, I would gladly use a number format that does not require such special considerations for summing a set of numbers, and still yields good results. I am really looking forward to alternative representations.
I have a suspicion that all non-trivial C++ programs contain undefined behaviour (e.g. not checking for or preventing overflow at every arithmetic operation involving signed integers), so trying to understand the semantics of these programs is kind of a moot point.
On the other hand, if anyone tried to formalise the semantics of C++ and prove some kind of soundness theorem they would probably find that the language definition is technically inconsistent.
Paraphrasing Feynman, if you think you understand C++ then you don't understand C++.
One important aspect of programming with functors is the ability to quantify over them, i.e. higher-kinded types. This is crucial for building reusable components on the functor-level of abstraction.
In modern OOP this would amount to quantifying over interfaces which is typically not even possible in those languages.
The C++17 equivalent would be something like the following (not tested):
using NumberExpr = int;
using VarExpr = std::string;
struct AddExpr;
using Expr = std::variant<NumberExpr, AddExpr, VarExpr>;
struct AddExpr {
std::unique_ptr<Expr> a;
std::unique_ptr<Expr> b;
}
Of course, this being C++, you need forward declarations and a firm grasp of the rules of incomplete types to be confident about declaring a simple AST type.
To completely address JoshTriplett's point, yes, you can just define another struct for the SubExpr variant to disambiguate it from the AddExpr case.
Requiring this kind of wrapping is awkward compared to e.g. Rust or Haskell's treatment of sum types, which unlike C++17 and std::visit both have powerful pattern matching features built into the language. Saying this as someone who writes C++ all day: std::visit and std::variant are weaksauce.
On the other hand, the C++ way gives you an actual type for each element of the sum; you can write a function which only takes AddExpr. The Rust way doesn't (yet).
Given that you have to define those types manually, I don't see why you couldn't do the same in Rust; it just doesn't force you to if you don't need it
That's rather disingenuous, because Haskell forces you to use `newtype` wrappers for lots of things you shouldn't need them for and don't need them for in C++.
Can you name an instance in Haskell where newtype is conceptually unnecessary but required by the language? In the sense that you may be able to derive the same set of logical guarantees that newtype gets you without using it, in principle.
Discrimination runs in linear time not in the number of items but in the total size of the data. If you have n items each of size k it takes O(kn). Conventional sorting often assumes that you can compare keys of size k in constant time and therefore gets O(n lg n) but a more honest analysis would yield O(kn log n) for (say) merge sort.
The bound on string sorting is typically written as O(n log n + D), where D is the sum of distinguishing prefixes, ie input length minus some fluff. Since D >= n log n we already have linearity on input length.
Are you saying that you can sort strings in O(n log n + D) using a conventional sorting algorithm such as merge sort? If so, I don't understand why D would be an additive factor implying that each string is only involved in a constant number of comparisons.
(I wasn't, by the way, only considering strings when discussing variable sized keys -- the beauty of discrimination is that we essentially reduce all sorting problems to string sorting.)
When people say "conventional" sorting algorithms, they're usually talking about sorting algorithms based around pairwise comparison functions.
I note on slide 14 of this presentation, it looks like this is sort of the discriminator for selecting a better partitioning scheme. So it looks to me like this actually leverages a similar principle?
As we've seen in this thread and others, there are some other ways to measure and/or process that have different characteristics. Surely all of these deserve attention! So, thanks very much for sharing this.
Sorry, I was being imprecise. By conventional I meant comparison-based sorting functions that are polymorphic in the element type and thus not allowed to examine individual bytes.
Multikey Quicksort indeed looks like a special case of discrimination, exploiting some of the same principles.
