kraghen

5 ms·

1.
by kraghen 4y ago
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
2.
by kraghen 6y ago
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% l
3.
by kraghen 6y ago
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
4.
by kraghen 9y ago
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,
5.
by kraghen 9y ago
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 th
6.
by kraghen 9y ago
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 potentiall
7.
by kraghen 9y ago
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.
8.
by kraghen 9y ago
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
9.
by kraghen 9y ago
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
10.
by kraghen 9y ago
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 quant
11.
by kraghen 9y ago
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 {
12.
by kraghen 9y ago
CMOV introduces a data dependency. Predictable branches, on the other hand, are basically free.
13.
by kraghen 9y ago
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...) The case for triangle joins is simple to describe, though
14.
by kraghen 9y ago
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 dis
15.
by kraghen 9y ago
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
16.
by kraghen 9y ago
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
17.
by kraghen 9y ago
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 orderings that couldn't be dealt with in an obvious wa
18.
by kraghen 9y ago
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 implementor's perspective. The succinct version is
19.
by kraghen 9y ago
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 an equivalence on B defined by x = y when f(x) = f(y). No
20.
by kraghen 9y ago
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, I generalised discrimination (and added a touch of li
21.
Why macros are not really worse than libraries(kraghen.blogspot.com)
1 points by kraghen 15y ago|0 comments