1 | Approximately Equals Operator |
---|
2 | ============================= |
---|
3 | |
---|
4 | This is a proposal for the inclusion of two new operators into Cforall. |
---|
5 | |
---|
6 | Approximate equality is a very useful concept for floating point arithmetic. |
---|
7 | Due to floating point error values are very rarely the same when they are |
---|
8 | supposed to be. Because of this it is standard practice to provide some |
---|
9 | wrapper function (or in C++ an entire class) when doing these operations. |
---|
10 | |
---|
11 | This proposal offers to do the same thing, but introduces a new trinary |
---|
12 | operator to provide an easy to read interface for this operation. |
---|
13 | |
---|
14 | For example if you have two floats `a` and `b` to see if they are equal with |
---|
15 | error `e` you would write `a ~== b : e`. The underlying function might look |
---|
16 | like the following: |
---|
17 | |
---|
18 | ``` |
---|
19 | bool ?~==?:?(float lhs, float rhs, float epsilon) { |
---|
20 | return lhs <= rhs + epsilon && rhs <= lhs + epsilon |
---|
21 | } |
---|
22 | ``` |
---|
23 | |
---|
24 | Approximately Inequals Operator |
---|
25 | ------------------------------ |
---|
26 | |
---|
27 | Called `?~!=?:?` and usually written as `a ~!= b : e`, this is the negated |
---|
28 | variant of approximately equals. That's it one should always be equal to the |
---|
29 | negation of the other. |
---|
30 | |
---|
31 | Although this is not commonly considered a basic operation it is included to |
---|
32 | ease negating a condition. |
---|
33 | |
---|
34 | Default Implementation |
---|
35 | ---------------------- |
---|
36 | |
---|
37 | The provided operations do not have to example provided above. The behaviour |
---|
38 | should be to return true if the absolute value of the difference between the |
---|
39 | compared values is less than or equal to the error value. So approximate |
---|
40 | equality with error of zero should be the same as equality. |
---|
41 | |
---|
42 | Each implementation could be provided individually or it could be provided |
---|
43 | through a generic function, as in the following: |
---|
44 | |
---|
45 | ``` |
---|
46 | forall(otype T | { T ?+?(T, T); bool ?<=?(T, T); }) |
---|
47 | bool ?~==?:?(float lhs, float rhs, float epsilon) { |
---|
48 | return lhs <= rhs + epsilon && rhs <= lhs + epsilon |
---|
49 | } |
---|
50 | ``` |
---|
51 | |
---|
52 | This could be organized like the concurrency extensions. That is the minimal |
---|
53 | syntax is provided but to get full use a library include is required. If so |
---|
54 | the library might be called `approx.hfa`. |
---|
55 | |
---|
56 | Required Syntax |
---|
57 | --------------- |
---|
58 | |
---|
59 | We will need `~==` and `~!=` as new operator tokens. `?~==?:?` and `?~!=?:?` |
---|
60 | must be recognized as two new special operator names. Then the operators |
---|
61 | have to be included in the grammar as a new type of expression. |
---|
62 | |
---|
63 | Because of the natural use it should bind more tightly than logical operations |
---|
64 | so that `b && x ~== y : e` is the same as `b && (x ~== y : e)` but not as much |
---|
65 | arithmetic operations so `n + x ~== y : e` is the same as `(n + x) ~== y : e`. |
---|
66 | Either at the same precedence as equality or in-between equality and |
---|
67 | comparison. |
---|
68 | |
---|
69 | Choice of Symbols |
---|
70 | ----------------- |
---|
71 | |
---|
72 | The first operator symbols (`~==` and `~!=`) were chosen considering that the |
---|
73 | only two operations we are adding approximate variants for. (See end of |
---|
74 | section for details.) If only approximately equals was included then `~=` |
---|
75 | might be the better choice for consistency with `!=`, `<=` and `>=`. However |
---|
76 | that would make it less consistent with `~!=` and we can't use both `~` and |
---|
77 | `!` to replace the first symbol in that case. |
---|
78 | |
---|
79 | The `:` for the second separator was used because of symmetry with the |
---|
80 | conditional operator `?:`. The symmetry is not perfect, the colon on the |
---|
81 | conditional is a divider that separates two equivalent options while here it |
---|
82 | adds an extra detail to the main operation, but the additional separator for |
---|
83 | a third argument remains the same. In addition `:` is already a token and it |
---|
84 | never appears to begin something so it is unlikely to ever cause conflicts. |
---|
85 | |
---|
86 | ### Why Not Add More Approximate Operators? |
---|
87 | To begin with very few operations have a meaningful error value in them. |
---|
88 | Besides some exotic recursive calculation it is limited to comparisons. |
---|
89 | |
---|
90 | With equality and inequality covered that leaves use with the ordering |
---|
91 | comparisons. In these cases because one side (above or below) is covered in |
---|
92 | its entirety adding an error simply shifts (down or up) by that amount. This |
---|
93 | is a less useful operation and easier to code in line. For example: |
---|
94 | |
---|
95 | `( a ~<= b : epsilon ) == ( a <= b + epsilon )` |
---|
96 | |
---|
97 | Default Epsilon |
---|
98 | --------------- |
---|
99 | |
---|
100 | For primitive (or library) types that have approximate equality defined on |
---|
101 | them it may also be useful to provide a general default for the error. Some |
---|
102 | epsilon that is small, but large enough to catch the usual build up of error |
---|
103 | when someone is doing just a bit of math with these types. |
---|
104 | |
---|
105 | However it should probably not be called epsilon to avoid any confusion with |
---|
106 | machine epsilon, which in many cases would be much smaller than the default |
---|
107 | error value. |
---|
108 | |
---|
109 | Even if the default implementations are in the prelude and not a library, |
---|
110 | these might be useful contexts of `approx.hfa`. |
---|