Fixed-point modulo edge cases

Question

I'm implementing a Q31.32 fixed-point numeric type based on System.Int64 in C#. Right now I'm trying to get the modulo operation correctly (%).

All implementations of fixed-point arithmetic I've seen define Qm.n modulo simply in terms of integer modulo, i.e. the modulo of two Qm.n numbers is the modulo of their underlying integer representation. This works in the general case but fails in two specific cases:

x % y throws an OverflowException if x == Int64.MinValue and y == -1. I can easily deal with this with an if statement and returning 0 in this case, although this is strange behavior (and unchecked is of no help here).
x % y incorrectly returns 0 for some small values of x and y. For example, if the integer representations of x and y are -413 and 59 (decimal: ~-0.000000096159 and ~0,000000013737), the modulo is 0 (decimal: 0) while the modulo of their decimal value is (according to System.Decimal) ~-0.000000013737. This error is about 60 times greater than the maximum precision of the type (2^-32), so it cannot be considered a rounding error.

What is the cause of this last error and is there anything I can do to obtain better accuracy?

what kind of modulo division you use ? maybe the problem is there. to be clear (integer or fixed/floating point division?) if you use shifted integer division there should be no error, on floating dividers there is always some error for small numbers — Spektre
Not sure you understand the question. I'm implementing fixed-point modulo based on Int64 modulo. In general, this just works, except in the aforementioned cases. You can see the implementation here: github.com/asik/FixedMath.Net/blob/master/Fix64.cs — Asik
I understood perfectly. I see you use long modulo so there are two options 1st. long modulo is wrong (improbable) or 2nd. your print is rounded try to print raw_values to check if modulo is OK. In that case you need to write your own print routine which will be more precise or reconfigure old one to match precision. — Spektre
Long modulo is not wrong, and my conversion operation from Fix64 to decimal or double is not wrong either. The problem is that implementing Q31.32 modulo in terms of long modulo creates large inaccuracies for specific values (while it works perfectly for the vast majority of them), and I don't quite get why. — Asik

Spektre Spektre · Accepted Answer · 2013-10-14T18:37:32

I found out the problem.

-413 % 59 = 0 is correct !!!

because -7 * 59 = -413

Your assumed correct result is mostly probable taken from 2s complement of -413 which leads to confusion.

[edit 1]

At Asik's suggestion I use calculator and my last comment to his question was right. The problem is in his print accuracy and not on above 2s complement or modulo see this:

413 >> 32 = 0.00000009615905582904815673828125  
 59 >> 32 = 0.00000001373700797557830810546875

0.00000009615905582904815673828125 / 0.00000001373700797557830810546875 = 7
0.00000009615905582904815673828125 % 0.00000001373700797557830810546875 = 0

for more info about printing numbers see this: https://stackoverflow.com/a/18401040/2521214

P.S. how exactly did you obtain result that modulo should be ~-0.000000013737 ? it is suspiciously equal to the -59>>32 ... maybe your reference can not handle signed numbers correctly (-413)<(59) and throw result of modulo simply 59 because of it (to avoid division) with signum combined from both numbers.

Fixed-point modulo edge cases

1 Answers