Re: (x * x) % y

Olivier Langlois (olanglois@sympatico.ca)
Fri, 23 Apr 1999 08:10:17 -0400

• Next message: Ben Laurie: "Re: (x * x) % y"
• Previous message: Enzo Michelangeli: "Re: (x * x) % y"
• Maybe in reply to: Olivier Langlois: "(x * x) % y"
• Next in thread: Enzo Michelangeli: "Re: (x * x) % y"

Hi,

The generated assembly routine by your test routine is equivalent to the
original one.

See, imul is the signed multiplication instruction and the 2 operand version
of this instruction store the multiplication product in the 32 bits
destination register.

Here is what I've done to work around the problem:

// Return (x*y)%z
inline mulmod( unsigned x, unsigned y, unsigned z )
{
#ifndef __GNUG__
  __asm
  {
     mov eax, x
  mul y
  div z
  mov eax, edx
  }
#else
  unsigned xy = x*y;
  if( xy < x || xy < y ) throw PEx(PX_OVERFLOW);
  return xy%z;
#endif
}

The other platform on which I'm gonna use this function is a Sun station and
I don't know Sparc assembly so I'll live with the possibility that sometimes
an overflow can occur (which should happen too often).
>
>However, this seems to work nicely:
>
>unsigned test( unsigned i, unsigned j )
>{
> register __int64 ii;
> ii = i*i;
> return (ii%j);
>}
>
>as it produces a tight:
>
>------------- 8< -------------
>; File q.c
>_i$ = 8
>_j$ = 12
>_test PROC NEAR
>; Line 5
> mov eax, DWORD PTR _i$[esp-4]
> sub edx, edx <---------- you also need to zero edx!
> imul eax, eax
> div DWORD PTR _j$[esp-4]
> mov eax, edx
>; Line 6
> ret 0
>------------- 8< -------------
>
>There is still life for the old "register" keyword :-)
>
>Cheers --
>
>Enzo
>
>
>-----Original Message-----
>From: Olivier Langlois <olanglois@sympatico.ca>
>To: Derek Atkins <warlord@MIT.EDU>
>Cc: CodherPlunks@toad.com <CodherPlunks@toad.com>
>Date: Friday, April 23, 1999 5:16 PM
>Subject: Re: (x * x) % y
>
>

• Next message: Ben Laurie: "Re: (x * x) % y"
• Previous message: Enzo Michelangeli: "Re: (x * x) % y"
• Maybe in reply to: Olivier Langlois: "(x * x) % y"
• Next in thread: Enzo Michelangeli: "Re: (x * x) % y"