Dear all,

I'm working on a program which uses power(x,y) and then mod the result with n. Since mod is an integer operator, I need to convert the result to integer using round, but what if the number is large?

{code}
var x,y,p:extended
n,r:integer
begin
....
p:=power(x,y);
r:=(round(p)) mod n;
edit.text:=inttostr(r);
....
{code}

I'll be working with numbers like 141^139 which would be over int64. Is there anyway to solve this problem? Since the number of y will be chosen by the user, would limiting the number of choice be the only way out? If so, then the application can only provide integers<10, which would be my very last resort.

Thank you.

If your numbers have integer values (X, Base=1..65535, Y>0) you can try this function (not tested)

{code}
function MyPower(X, Y, Base: cardinal): cardinal;
begin;
  if X=0 then begin;
    Result:=0;
    exit;
    end;
  Result:=1;
  while (Y>0) and (X>1) do begin;
    if Y and 1<>0 then Result:=Result * X mod Base;
    Y:=Y shr 1;
    X:=X * X mod Base;
    end;
  end;

procedure TForm1.bCalcClick(Sender: TObject);
begin;
  ShowMessage(IntToStr(MyPower(141,139,101))); //141^139 mod 101=93
  end;
{code}

--
Aleksandr
http://guildalfa.ru/alsha

> {quote:title=Aleksandr Sharahov wrote:}{quote}
> If your numbers have integer values (X, Base=1..65535, Y>0) you can try this function (not tested)
> 
> {code}
> function MyPower(X, Y, Base: cardinal): cardinal;
> begin;
>   if X=0 then begin;
>     Result:=0;
>     exit;
>     end;
>   Result:=1;
>   while (Y>0) and (X>1) do begin;
>     if Y and 1<>0 then Result:=Result * X mod Base;
>     Y:=Y shr 1;
>     X:=X * X mod Base;
>     end;
>   end;
> 
> procedure TForm1.bCalcClick(Sender: TObject);
> begin;
>   ShowMessage(IntToStr(MyPower(141,139,101))); //141^139 mod 101=93
>   end;
> {code}
> 
> --
> Aleksandr
> http://guildalfa.ru/alsha


Thank you so much!
But I have another question: is there any limits to the numbers x and y?

> {quote:title=Flame Y wrote:}{quote}
> But I have another question: is there any limits to the numbers x and y?

Yes.
1<=X<=65535, 1<=Base<=65535, 1<=Y<=4294967295. 

--
Aleksandr
http://guildalfa.ru/alsha

Thank you so much!
It was a great help!
The problem is solved now.
But if you don't mind, I would like to know what this part of the code means as I can't figure it out:

{code}
while (Y>0) and (X>1) do begin
    if Y and 1<>0 then Result:=Result * X mod Base;
    Y:=Y shr 1;
    X:=X * X mod Base;
    end;
{code}

The basic idea is to get x to multiple itself for y times, am I right?

Thanks again.

<Flame Y> schreef in bericht news:480112@forums.embarcadero.com...
> Thank you so much!
> It was a great help!
> The problem is solved now.
> But if you don't mind, I would like to know what this part of the code 
> means as I can't figure it out:
>

I think the limitation on X can be relaxed.
Tom

{code}
function modProduct(x,y,base : cardinal) : cardinal;
// result := (x^y) MOD base; base must be >0
// Based on:
// 1) (a*b) MOD base = ((a MOD base)*(b MOD base)) MOD base
//    Eg: 25*37 MOD 7 = (3*7+4)*(5*7+2) MOD 7 = 4*2 MOD 7 = 1
// 2) x^y = product of 2-powers of x
//    Eg: x^13 = x^8 * x^4 * x^1, i.e. the bits of 13: 1101 determine if a
//        2-power of x should be used or not.
// Limitations: (see notes in code)
//    intermediate result*x and x*x must fit in cardinal range
//    since x<base and intermediate result<base, this means that the only
//    limitation is that base<sqrt(cardinal max)
begin
  result:=1;
  x:=x MOD base;
  while (y>0) AND (x>1) do
  begin if y AND 1 = 1 // y odd: use current power of x
           then result:=(result*x) MOD base; // result*x <= cardinal
        x:=(x*x) MOD base; // x*x must fit in cardinal
        y:=y SHR 1;        // next bit of y
  end;
end;

> {quote:title=Tom deNeef wrote:}{quote}
> <Flame Y> schreef in bericht news:480112@forums.embarcadero.com...
> > Thank you so much!
> > It was a great help!
> > The problem is solved now.
> > But if you don't mind, I would like to know what this part of the code 
> > means as I can't figure it out:
> >
> 
> I think the limitation on X can be relaxed.
> Tom
> 
> {code}
> function modProduct(x,y,base : cardinal) : cardinal;
> // result := (x^y) MOD base; base must be >0
> // Based on:
> // 1) (a*b) MOD base = ((a MOD base)*(b MOD base)) MOD base
> //    Eg: 25*37 MOD 7 = (3*7+4)*(5*7+2) MOD 7 = 4*2 MOD 7 = 1
> // 2) x^y = product of 2-powers of x
> //    Eg: x^13 = x^8 * x^4 * x^1, i.e. the bits of 13: 1101 determine if a
> //        2-power of x should be used or not.
> // Limitations: (see notes in code)
> //    intermediate result*x and x*x must fit in cardinal range
> //    since x<base and intermediate result<base, this means that the only
> //    limitation is that base<sqrt(cardinal max)
> begin
>   result:=1;
>   x:=x MOD base;
>   while (y>0) AND (x>1) do
>   begin if y AND 1 = 1 // y odd: use current power of x
>            then result:=(result*x) MOD base; // result*x <= cardinal
>         x:=(x*x) MOD base; // x*x must fit in cardinal
>         y:=y SHR 1;        // next bit of y
>   end;
> end;

I get it now. Thank you so much!

> {quote:title=Flame Y wrote:}{quote}
> The basic idea is to get x to multiple itself for y times, am I right?

There are 2 ideas.
First is to get x^y by O(log2(y)) multiplications.
Second is to use identity (a*x) mod b = ((a mod b) * (x mod b)) mod b
--
Aleksandr
http://guildalfa.ru/alsha

Bug fixed.
Now result is valid when X^Y mod Base = 0.

{code}
function MyPower(X, Y, Base: cardinal): cardinal;
begin;
  Result:=0;
  if X>=Base then X:=X mod Base;
  if (X=0) or (Base<=1) then exit;
  inc(Result);
  while Y>0 do begin;
    if Y and 1<>0 then begin;
      Result:=Result * X mod Base;
      if X<=1 then break;
      end;
    X:=X * X mod Base;
    Y:=Y shr 1;
    end;
  end;

procedure TForm1.bCalcClick(Sender: TObject);
begin;
  ShowMessage(IntToStr(MyPower(141,139,101))); //141^139 mod 101=93
  ShowMessage(IntToStr(MyPower(4,2,8))); //4^2 mod 8=0
  end;
{code}

--
Aleksandr
http://guildalfa.ru/alsha

On Sun, 24 Jun 2012 17:35:54 -0700, Flame Y <> wrote:

>Dear all,
>
>I'm working on a program which uses power(x,y) and then mod the result with n. Since mod is an integer operator, I need to convert the result to integer using round, but what if the number is large?
>
>{code}
>var x,y,p:extended
>n,r:integer
>begin
>...
>p:=power(x,y);
>r:=(round(p)) mod n;
>edit.text:=inttostr(r);
>...
>{code}
>
>I'll be working with numbers like 141^139 which would be over int64. Is there anyway to solve this problem? Since the number of y will be chosen by the user, would limiting the number of choice be the only way out? If so, then the application can only provide integers<10, which would be my very last resort.
>
>Thank you.

You need a big integer library.  Note that the performance of such
operations sucks.

On Mon, 25 Jun 2012 01:36:28 -0700, Flame Y <> wrote:

>Thank you so much!
>It was a great help!
>The problem is solved now.
>But if you don't mind, I would like to know what this part of the code means as I can't figure it out:
>
>{code}
>while (Y>0) and (X>1) do begin
>    if Y and 1<>0 then Result:=Result * X mod Base;
>    Y:=Y shr 1;
>    X:=X * X mod Base;
>    end;
>{code}
>
>The basic idea is to get x to multiple itself for y times, am I right?
>
>Thanks again.

What he's doing is applying the Mod operation after each step in order
to keep the number from overflowing.

> {quote:title=Aleksandr Sharahov wrote:}{quote}
> Bug fixed.
> Now result is valid when X^Y mod Base = 0.
> 
> {code}
> function MyPower(X, Y, Base: cardinal): cardinal;
> begin;
>   Result:=0;
>   if X>=Base then X:=X mod Base;
>   if (X=0) or (Base<=1) then exit;
>   inc(Result);
>   while Y>0 do begin;
>     if Y and 1<>0 then begin;
>       Result:=Result * X mod Base;
>       if X<=1 then break;
>       end;
>     X:=X * X mod Base;
>     Y:=Y shr 1;
>     end;
>   end;
> 
> procedure TForm1.bCalcClick(Sender: TObject);
> begin;
>   ShowMessage(IntToStr(MyPower(141,139,101))); //141^139 mod 101=93
>   ShowMessage(IntToStr(MyPower(4,2,8))); //4^2 mod 8=0
>   end;
> {code}
> 
> --
> Aleksandr
> http://guildalfa.ru/alsha

I can't thank you enough.
Actually this is for an assignment, and thanks to you, I've just gotten past one of the biggest worries I've encountered while finishing this project!
Really, thank you so much!

<Flame Y> schreef in bericht news:480446@forums.embarcadero.com...

> I can't thank you enough.
> Actually this is for an assignment, and thanks to you, I've just gotten 
> past one of the biggest worries I've encountered while finishing this 
> project!
> Really, thank you so much!

So, you must have passed the test of finding someone who knows the answer.
In many cases that is more relevant than knowing the answer.
Tom