Viewing profile — kraghen

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 coefficien…

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.70481…

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 ty…

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,…

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 …

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 lik…

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 wa…

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 floati…

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 intege…

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-le…

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 ; struct Add…

CMOV introduces a data dependency. Predictable branches, on the other hand, are basically free.

It's only described in my thesis, which is not yet publicly available. (It should be, but the university thesis publication process seems to have a latency measured in years...) Th…

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. …

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 im…

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 assum…

It might, I never really discussed this aspect with Fritz! For my thesis I was mostly focussed on applications to database queries, and I never encountered any concrete examples of…

I can't say I have had much success explaining my thesis clearly to anyone except people from the same department, but I can try to give my understanding of discrimination from an …

All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have …

I'm happy to see this excellent paper mentioned. Fritz Henglein (the author) was my thesis supervisor last year, and I worked on developing some of his ideas further. In particular…