Floating Point Problem

Questions
1

Hey folks,
I already figured, that it’s some kind of floating point issue, but I’m really not sure, how to fix it…
I wrote a method:


+ Collection {
	groupWithinBandwidth {arg bandwidth = 0;
		var sorted = this.sort;
		var groups = [];

		sorted.do { |item, i|
			if (groups.size == 0){
				groups = groups.add([item]); 
			}{
				if ((groups[groups.size-1].first.postln) >= (item-bandwidth)){
				groups[groups.size-1] = groups[groups.size-1].add(item)}{
					groups = groups.add([item])
				}
			};
		};

		^groups
	}

}

the minimal version of my problem is like this:

if I run it with integers:

a = [21,54,51,24,70]
a.groupWithinBandwidth(3)
-> [ [ 21, 24 ], [ 51, 54 ], [ 70 ] ]

it works just fine, but with floating point numbers:

a = [2.1, 5.1, 2.4,5.4,7]
a.groupWithinBandwidth(0.3)
-> [ [ 2.1, 2.4 ], [ 5.1 ], [ 5.4 ], [ 7 ] ]

it somehow doesn’t

but:

a = [2.1, 5.1, 2.4,5.4,7]*10
a.groupWithinBandwidth(3)
-> [ [ 21.0, 24.0 ], [ 51.0, 54.0 ], [ 70 ] ]

works…

when I investigate, I find that at around 2.pow(-52) a problem occurs:

a = [2.1, 5.1, 2.4,5.4,7]
a.groupWithinBandwidth(0.3+2.pow(-51))
-> [ [ 2.1, 2.4 ], [ 5.1, 5.4 ], [ 7 ] ]

but

a.groupWithinBandwidth(0.3+2.pow(-52))
-> [ [ 2.1, 2.4 ], [ 5.1 ], [ 5.4 ], [ 7 ] ]

I would love to understand, what is happening here

Best

Sem

2

The problem is the >=.

There is no guarantee in floating point arithmetic for equality. For example, a + b - b == a can be false, in could be greater or smaller.

You should instead invert the inequality, check that the right hand side is significantly less. Say by 0.0001 or something.

The precision argument could be a new argument to the method.

1 Like
3

thanks for your answer!
wow, that is crazy…

is this a super collider specific problem, or does it happen in other languages as well?

4

Nope it isn’t specific to SC, computers just can’t do maths properly!!

Sticking to integers is generally safe, so long as you don’t over or underflow (supercollider only has access to i32s mind you).

Someone made a Rational class which represents numbers as fractions, this is even better, but much slower to compute.

There are some specific methods on the Float class to make ‘comparisons’ easier, have a look, you might find an easier way to express what you want.

Fyi, if memory serves, 2^-52 is about as small as f64s can go (without denormals, but that’s another topic). The term here is ‘floating point epsilon’.

1 Like
5

Let’s do (1/7) + 10 - 10 in floating point, with 4 digits of decimal precision.

1/7 to 4 digits is 0.1429 – “0.142857142857…” but the 5th digit is 5 or more, so, round up.

The floating point way of writing numbers is to put exactly one digit left of the point, and multiply by base ^ n to shift it to the right value. So:

  1.429 * 10^(-1)
1.000   * 10^1
---------
1.014 * 10^1

Adding 10 shifted the point, and precision below the point is fixed (moving the point to the left doesn’t turn 4 digits of precision into 6), so 2 digits of the fraction got lost.

Then when you subtract the 10 again, the digits don’t magically reappear, so you get 1.400 * 10^(-1), != 1.429 * 10^(-1).

Floating point works very well for multiplication and division, but addition and subtraction with different orders of magnitude do lose information. It’s a trade-off: floating point ops are a lot faster than unlimited-precision ops, but less accurate in the case above.

In binary, any denominator with any prime factor != 2 is a repeating fraction, thus an approximation. That includes 0.1, which looks to us like it should be easy but in binary, it’s 0.00011001100110011001100… which is rounded off eventually.

hjh

1 Like
6

Often when dealing with floating point comparisons in SC, it’s useful to do the comparison using the SimpleNumber method equalWithPrecision.

(a + b - b).equalWithPrecision(a)

For more control, if desired you can explicitly specify an argument with absolute (defaults to 0.0001) or relative (to the larger-magnitude number) precision.

2 Likes
7

related question: Float equality of unqualifed precision (i.e., something == 0.5) does come up in sc code, are there rules of thumb as to what that means exactly (e.g., error never larger than some tolerance x)?
I guess this might depend on the build, and the context of the computation, but still the fact that it’s being used suggests that it isn’t completely unpredictable? Sorry if this is obvious to the more informed folks…

8

Are you asking if == considers precision for you? If so, the answer is no.

== is exact bitwise equality. It does not consider precision. 0.1 + 0.1 + 0.1 == 0.3 is false.

If you want to use precision, which you should, then you need to use the specific methods defined in SimpleNumber.

1 Like
9

Ah I see. Well I wasn’t planning to use it (I swear!), but I had just looked at some things in the class library that do…

10

you can get away with using == with floats if you are not doing math: ([0.5, 0.5].choose == 0.5) // true - I made myself some operators with tolerance 0.00001 to save typing…

1 Like
11

The example from the class lib I was thinking of is Pcauchy, which has this code in it:

while({
		ran = 1.0.rand;
		ran == 0.5
});
inval = ((spreadVal * (ran * pi).tan) + meanVal).yield;

I think the idea is to avoid (0.5 * pi).tan because undefined. I guess this also depends on how .rand works, whether it does any “math” in the above sense or not…

Another question is whether that precaution is necessary/useful at all, because (pi/2).tan does in fact output a (large) number. So I imagine that for a ran that is very close to but not euqal to 0.5, that number is probably comparably large, even though it passes the test (i.e., gets out of the while loop)?

12

One can use the method equalWithPrecision or simply write it down:

(0.1 + 0.1 + 0.1 - 0.3).abs < 1e-10

(Reminder: there is also a Rational class quark that makes sense in some situations)