Windows in-line code procedure - MultMod

From: [at]} <robert.d.campbell{>
Date: Thu, 29 Jun 2000 14:07:52 +0000 (GMT)

Thanks to everyone who wrote to help with my in-line code procedure.

The routine below seems to work correctly. It returns a * b MOD m. If a * b is
negative it returns (a * b MOD m) - m.
I haven't investigated what happens for negative m (and I don't really care!).


PROCEDURE [code] MultMod* (a, b, m : INTEGER) : INTEGER
  05AH (* pop b -> edx *)
  059H, (* pop m -> ecx *)
  0F7H, 0EAH, (* edx:eax := eax * edx = a * b *)
  0F7H, 0F9H, (* eax := edx:eax / ecx = a * b DIV m *)
               (* edx = a * b MOD m *)
  08BH, 0C2H; (* move eax, edx (edx -> eax) *)


The resulting speed improvement (test routine: multi-million point Fast Number
Theoretic Transform) is approximately:

None - on a 500 MHz Pentium Zeon II
A factor of 2 - on a 233 MHz AMD K6.

A related procedure calculates a^pwr MOD m.


PROCEDURE PwrMod* (a, pwr, m : INTEGER) : INTEGER;
  VAR
    res : INTEGER;
  BEGIN
    ASSERT (pwr >= 0, 20);
    IF m = 1 THEN RETURN 0 END;
    ASSERT (m > 0, 21);
    IF pwr = 0 THEN RETURN 1 END; (* 0^0 = 1, as it should ! *)
    IF a = 0 THEN RETURN 0 END;
    res := 1; a := a MOD m;
    WHILE pwr > 1 DO
      IF ODD (pwr) THEN res := MultMod (res, a, m) END;
      a := MultMod (a, a, m);
      pwr := ASH (pwr, -1)
    END;
    RETURN MultMod (res, a, m)
  END PwrMod;


I believe these routines are efficient, correct, and do not suffer overflow
problems for inputs upto MAX (INTEGER). Let me know if I am wrong.


In the definition file MultMod is declared as a [code] PROCEDURE.
Math.Sqrt is not. Does this mean that the Math library does not produce
efficient in-line code, despite the implication in Platform-Specific Issues?


Regards

Robert Campbell
robert.d.campbell{([at]})nowhere.xy
29 June 2000


--------------------------------------------

To unsubscribe from this mailing list, send a message containing the word "unsubscribe" to:
   blackbox-request{([at]})nowhere.xy

To get a list of valid e-mail commands and instructions on their usage, send a message containing the word "help" to the above address.

Send any problem reports or questions related to this email list to the list owner at
   owner-blackbox{([at]})nowhere.xy
Received on Thu Jun 29 2000 - 14:07:52 UTC