[fpc-devel] Question to developers

[J. Gareth Moreton]

Hi everyone,

I have a question for third-party developers, especially mathematical, 
scientific and games programmers...

How often would you use a construct akin to "case x mod n of", where n 
is a constant and not a power of 2?  I ask because while I wait for my 
"(x mod n) = 0" optimisation to be approved, I've discovered that it 
could be extended to cover remainders other than 0.  For example, 
starting with (x mod 3) = 0 (unsigned 32-bit using Intel notation):

MOV EAX, x
IMUL EAX, $AAAAAAAB
CMP EAX, $55555555
JBE @Remainder0

For (x mod 3) = 1:

MOV EAX, x
IMUL EAX, $AAAAAAAB
SUB EAX, $AAAAAAAB
CMP EAX, $55555554
JBE @Remainder1

Which in this case, can be simplified to:

MOV EAX, x
IMUL EAX, $AAAAAAAB
CMP EAX, $AAAAAAAB
JAE @Remainder1

To keep with the simple case of n and 2^32 being relatively prime (i.e. 
n is odd), this is due to the fact that for a given divisor n, you can 
calculate its multiplicative inverse r such that nr = 1 (mod 2^32).  
Then if x is a multiple of n, it can be written as kn for some integer 
k, and (kn)r = k (mod 2^32), and because n and 2^32 are relatively 
prime, the domain has an exact one-to-one mapping onto the range, so the 
output k cannot be produced by any other input after being multiplied by 
r, and k falls in the range 0 to floor(2^32 / n), which is 0 to 
$55555555 for n = 3.

For remainder 1, x has the form kn + 1, and when multipled by r, the 
result is congruent to k + r (mod 2^32).  Because of the 1-to-1 mapping, 
the ranges of k and k + r will not overlap, and in the case for a 
divisor of 3 and a remainder of 1, maps onto the linear range $AAAAAAAB 
(k = 0) to $FFFFFFFF (k = $55555554).  For completion, for divisor 3 and 
a remainder of 2, the range is $55555556 to $AAAAAAAA (note that 2r = 
$55555556 (mod 2^32)).

I still got a couple of nuances to figure out, such as what to do with 
even values of n and the exact length of each range (for n = 3, k can 
range from 0 to $55555555 for remainder 0, but only 0 to $55555554 for 
remainders 1 and 2... this is because $FFFFFFFF is an exact multiple of 3).

So long story short, would optimisations for "(x mod n) = c" and "case 
(x mod n) of" be welcome, or is it overkill and "(x mod n) = 0" more 
than enough?

Gareth aka. Kit


-- 
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus