asked on

modPower() math function

Hi all,

I'm trying to look for some math function that do mod and power. I've found this on the web..

function Mod_power(Base,Exp,n:integer):integer;

{this procedure will perform a modulus for:

exp
Base MOD n (base^exp mod n)

without causing overflows}

var
count,value,i:integer;

begin
count := exp div 2;
value := 1;
for i := 1 to count do begin
value := (value * base * base) mod n;
end;
if odd(exp) then value := (value * base) mod n;
Mod_power := value;
end;

but it would not return the correct answer for 32 bit number integer.

has anyone got any best solution?

iqmedia

LasseRempe

First of all: Why do you think it give the wrong answer? I have tested it on a couple of numbers, and it seems to work just fine, as it should, as long as (n-1)*base^2 does not exceed the range of the cardinal type you are using (integer, in this case).

However, I may add that I cannot discern the value of dividing the exponent by two before commencing, as done in the code you cite. (If that was of actual use, we might instead want to divide it by three if the base is small enough etc ...) It just seems to be a mindless hack. In any case, the program should use (base^2 mod n) as the multiplier rather than base^2 in order to avoid unnecessary overflows.

So I think the following would be clearer. It works as long as (n-1)*base does not cause an overflow; in particular it works as long as n lies below 2^(30/2) = sqrt(2) * 32768.

function mod_exp(base,exp,value:integer): integer ;
var basemodn, value
: integer ;
begin
basemodn := base mod n ;
value := 1 ;
for i := 1 to exp do
value := (value * basemodn ) mod n ;
result := value ;
end;

If you want to use this functions on larger values of n, I suggest for simplicity's sake that you just replace integer by int64.

I would think though that there must be better (and faster) methods for taking powers in co-groups than this brute-force method. Check for algorithms literature on number-theoretic problems.

Lasse

iqmedia

ASKER

I'll try it first Lasse...

& base are 16 bit and n = 32 bit integer.

try it on bigger integer number that is almost towards 32 bit. for smaller number, yes i have it right..

iqmedia

ASKER CERTIFIED SOLUTION

LasseRempe

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

iqmedia

ASKER

hi,

there is no solution, the overflow still occur.
i've change it to 16 bit... anyway
i'll give u grade B.

i'm using D3.

thanks

iqmedia

LasseRempe

Hi. It's strange that you still get an overflow; I have tried it under Delphi 4, and there is no problem even with the highest value in the integer range. You might try doing all intermediate calculations in int64, as follows.

function Mod_power(Base,Exp,n:integer):integer;

var
value, newbase, newn :int64;
i : integer ;

begin
value := 1;
newbase := base mod n ;
newn := int64(n) ;
for i := 1 to Exp do begin
value := (value * newbase ) mod newn;
end;
Mod_power := value;
end;

In general, the problem is that you have to make sure that your number range supports the highest number that can result in any operation. In this case, the operation value * newbase is the critical operation. value might be as large as n-1, and so might newbase, so if n is a 32-bit number, the result would be a 64 bit number. This is why it works (at least under Delphi 4), if you use int64.

If you want to use larger numbers, then you should write your own multiplication routines, eg by going down to the bitwise level. For example, you could multiply two 64-bit integers and obtain the result in two separate 64-bit numbers (one for the low part and one for the high part of the result). Then use a corresponding division algorithm to obtain the result.

Lasse