Modulo Bug?

[Thiez]

On Sunday, 12 August 2012 at 08:43:53 UTC, Alex Rønne Petersen 
wrote:
> On 11-08-2012 20:54, Thiez wrote:
>> On Saturday, 11 August 2012 at 17:15:21 UTC, Norbert Nemec 
>> wrote:
>>> On 11.08.2012 18:13, bearophile wrote:
>>>> David:
>>>>
>>>>> Thanks! I thought modulo should alawys yield the same ... 
>>>>> seems like I
>>>>> was wrong ;)
>>>>
>>>> It's C design that's wrong.
>>>
>>> And it's the processor design that makes it inefficient to 
>>> correct it
>>> nowadays.
>>>
>>> Python's definition of modulo is far more useful than C's. 
>>> Implemented
>>> in machine code, however, it takes several additional 
>>> commands because
>>> the integer division is hardwired to the C definition. I 
>>> guess that
>>> hardware integer division in processors became popular only 
>>> when C was
>>> already widely in use.
>>
>> A few extra instructions (a CMOV followed by ADD should 
>> suffice, yes?)
>> seems like a small price to pay if it can prevent bugs. Why 
>> hasn't the
>> Python-modulo been made the default back when D was designed? 
>> The
>> ever-so-slightly more efficient C-modulo could be provided in 
>> a library.
>> Of course it's way too late to change it now...
>
> Keep in mind that not all CPUs have cmov, so you end up having 
> to branch based on whether the CPU has it or not.

I think the following trick would work even on the 80386 (386+ 
should have the SETcc instructions):
assume divident in AEX, divisor in EBX or ECX (not EDX, 
obviously). I'll assume it's in EBX.
  CDQ // sign extend EAX to EDX:EAX
  IDIV EBX // signed division
  XOR EAX,EAX // clear EAX
  BT EDX,31 // check if sign-bit of remainder is set
  SETNC AL // AL = (EDX negative ? 0 : 1)
  DEC AEX // EAX = (EDX negative ? 0xFFFF : 0)
  AND EAX,EBX // EAX = (EDX negative ? EBX : 0)
  ADD EDX,EAX // EAX = the correct modulo result

Obviously it's less appealing than a CMOV, but it should work (in 
theory, I didn't test it...) and perhaps someone smarter could 
make it even shorter. Apart form the IDIV, all instructions 
should take only a single clock cycle on most x86s as far as I'm 
aware.

As for other CPU architectures, perhaps those actually have a 
'sane' modulo operator, which would make the hypothetical 
presence or absence of a CMOV irrelevant :)