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?

Answer 1

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.