Converting large numbers to integer

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.
0
Flame
6/25/2012 12:35:54 AM
embarcadero.delphi.general 4258 articles. 0 followers. Follow

12 Replies
875 Views

Similar Articles

[PageSpeed] 58
Get it on Google Play
Get it on Apple App Store

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
0
Aleksandr
6/25/2012 6:16:31 AM
> {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?
0
Flame
6/25/2012 6:52:49 AM
> {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
0
Aleksandr
6/25/2012 7:57:47 AM
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.
0
Flame
6/25/2012 8:36:28 AM
<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;
0
Tom
6/25/2012 8:41:19 AM
> {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!
0
Flame
6/25/2012 10:27:24 AM
> {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
0
Aleksandr
6/25/2012 1:20:31 PM
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
0
Aleksandr
6/25/2012 3:47:25 PM
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.
0
Loren
6/25/2012 8:20:41 PM
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.
0
Loren
6/25/2012 8:20:41 PM
> {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!
0
Flame
6/26/2012 11:45:42 AM
<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
0
Tom
6/26/2012 3:07:24 PM
Reply:

Similar Artilces:

Convert number to integer
Right now I have a form that has people enter there numbers, I do some calculations and then send the projections back to them. In the form I have them enter the value without commas. I would like to make easier for people by letting them enter their values with commas (i.e. 20,000). How do I filter out the commas so that I have just the numeric value? I have to be able to evaluate thousand and millions, no decimal values. cheers; Hi there, this really isnt to difficult, you should be able to do something like this cint(replace(num, ",","")) Set your input variable to be a string, the c...

converting a string to number or integer
erm... how is this done in c#? or convert an object to and number or integer? I need to get the below as a number or int: TotalRecords = conSelProdCount.ExecuteScalar().ToString(); So i can use it in: ProductItem[] arrNews = new ProductItem[TotalRecords]; int rwcnt = 0; while ( dtrProducts.Read()) { string NewVar = dtrProducts["ProductName"].ToString(); arrNews[rwcnt] = new ProductItem(); arrNews[rwcnt].rowcount = @TotalRecords; arrNews[rwcnt].ProductName = dtrProducts["Pro...

convert to integer without rounding a number
Hallo,i have a simple question:Lets say i have a decimal, 1.7 for eg and i want to convert it to integer,but WITHOUT ROUNDING THE NUMBER.So i tryed many different aproaches to do this but all failed, just the example below.I get a integer 2 instead of 1 so that means the number is rounded.If somebody knows how to do the same thing but without rounding the number please let me knowthanxSub Page_load()           Dim d As Double           d = 1.7        &nb...

how do I convert a fractional number to a integer in javascript?
like if I want 3 as a result from this: (19 / 6) as oposed to 3.1999... var number = (19 / 6) then how do I convert this to value of 3 How about using parseInt: var result = parseInt(number);C# <---> VB.Net Translator Yep!...

converting an integer to a 2 decimal place number
hey.. say i have an integer, or a double, or any number that is less then 2 decimal places how can i make it 2 decimal places? eg 1 = 1.00  Cheers           Dim d As Double = 1        Response.Write(d.ToString("0.00")) Website Design Darlington - http://mdssolutions.co.ukhttp://lessthandot.com - Experts, Information, Ideas & Knowledgehttp://aspnetlibrary.com - An online resource for professional ASP.NET developersPlease remember to click "Mark as Answer" on this post if it helped y...

General question on the concept of integer handling in Delphi 2009
I found in system.pas new names "NativeInt" and "NativeUInt". According to all computer languages worldwide, Integer (and Cardinal) is *already* a native integer that represents the CPU register for best performance etc... What will happen in Delphi 2010 Win64 ??? I don't want to change Integer to NativeInt in my code thousand times to get adequate performance. > {quote:title=Ralf Stocker wrote:}{quote} > I found in system.pas new names "NativeInt" and "NativeUInt". Interesting. > According to all computer languages wor...

C# to VB : Want to convert whole project with large number of files.
Hi Experts, I am looking for a freeware (preferrably desktop app) that can convert a .net 2.0 project with large number of files from C# to VB - and of course it should be most accurate as wellI have a shareware called Instant VB (desktop app) that allows me to convert a project with maximum of 500 LoCTelerik batch converter being an online app asks me to upload each and every file individuallyDeveloper fusion code converter (online app) allows only single file at a timeAny from stated above will not help me much as the whole project needs to be convertedCan't recollect which one bu...

How to convert a hexadecimal number to normal number?
In VB.NET, how can I convert a hexadecimal number (like FF) to normal number (like 255) ?? Come on, gurus, this must be a piece of cake for you!:-) Any help appreciated, thanks, Hooker try to use System.Convert.ToInt16(your parameter) hope this work...if this doesn't work there should be some method in the 'convert' class.Toronto Trade show displays | Toronto Printing Solutions | Toronto Printing...

converting delphi code to delphi .NET
Hi,I'm looking at converting quite a bit of old delphi code to delphi .NET .  I'm wondering can it be converted to VB.NET for certain ?  Or perhaps there are some unsupported functions etc in delphi and I should keep the code delphi ?  There are about 10,000 lines of code.   Anyone brave enough to take an estimate on how long it would take to convert 10,000 lines ?is going from delphi to delphi.NET smooth ?   Would going to another language cause complications ?Thanks! mike123   Mike123,   Sorry I can not help, however, I have the s...

Converting from Delphi 2005 to Delphi XE5
I have developed a number of Windows applications in Delphi 2005. I recently purchased Delphi XE5. I have started by trying to compile an existing 2005 application. I am getting a 7 errors about FMXTeeEditor. [dcc32 Error] E1026 File not found: 'FMXTee.Editor.Brush.fmx' Not able to find a solution to this. Any help greatly appreciated. Did you open every form before compiling? The old forms get updated with new properties when they are opened. I would make a copy of the old project before doing any of this. maybe you have links to the older tchart files....i.e its not usi...

Convert another C++ code convert to delphi
Hello, I need the following code convert to Delphi DWORD files_count; bool error_flag = false; bool bResult; for(DWORD i=0; i < files_count && bResult && !error_flag; i++) { if(std::find(delete_file.begin(), delete_file.end(), i)==delete_file.end()) ........ here delete_file is as std::vector<int> delete_file How to convert this loop and if condition? -- Best Regards Md. Shariful Alam Khan "Md. Shariful Alam Khan" <murad_mouri@yahoo.com> wrote in message news:36441@forums.codegear.com.....

Convert Delphi 7 to Delphi 2009 [Edit]
Hi! Please, I have a code done in Delphi 7... Now I want to convert Delphi 7 to Delphi 2009 but I'm having problems when compile the code. Error message: +[DCC Fatal Error] Far.dpr(9): F2063 Could not compile used unit 'System.pas'+ Please can somebody help me? Source Download (349KB): http://rapidshare.com/files/256191328/FileManager.rar.html Mirror Source Download: http://www.megaupload.com/?d=12GYLPT0 Password: delphi Thank u so much! (sorry for my bad english, it is not my native language) Edited by: loquax loquax on Jul 15, 2009 12:24 PM Sorry, bu...

Converting Delphi for Win32 to Delphi .Net(Prism)
Hi, I am currently migrating a project from Delphi for Win32 to Delphi.net. Part of my code currently goes into a directory and pulls out a random file from this directory and loads the contents of the file for me. This code doesn't seem to work in Delphi.Net. It uses PString and a number of functions in SysUtils that don't seem to be present in Delphi.net's SysUtils file. If anyone can help me please, it would be greatly appreciated! Many thanks, Jonathan Mackey Jonathan Mackey a écrit : > I am currently migrating a project from Delphi for Win32 to &...

Delphi 2010
*Upgrading from Delphi 2007 to Delphi 2010* (as of February 1, 2010) I bought a new computer in December and decided to upgrade from Delphi 2007 to Delphi 2010. Here are some lessons learned related to the Delphi upgrade, which I hope will make a similar transition easier for others. I still have an insurmountable problem with the speed of the IDE (#13 below). As background, my old system had 3 GB of RAM, 40GB of unused disk, a 3.8 GHz CPU, and ran under Windows XP. My new system has 12 GB of RAM, 770GB of unused disk, a quad core 2.67 GHz CPU, and runs under Win7 Home Edition. ...

Web resources about - Converting large numbers to integer - embarcadero.delphi.general

PastBook’s Filepicker.io Integration Eases Process Of Converting Facebook Content To Books
PastBook , one of several companies that allow Facebook users to publish their content on the social network in actual books , announced the ...

Facebook No Longer Converting Groups Into Pages
Back when Facebook first launched Facebook Pages, many businesses and brands who had built up substantial audiences in their Facebook Groups ...

Zwartz Laminating-Converting B.V. on the App Store on iTunes
Get Zwartz Laminating-Converting B.V. on the App Store. See screenshots and ratings, and read customer reviews.


"Occupier" Thanked Former Soviet Citizen for "Converting" Him to Capitalism, Pro-Israel, Pro-USA - YouTube ...
May Day Demonstration on Union Square in New York City Zionism & Birth of Modern Israel in 1948: Former Soviet Citizen Pays Tribute to Ben-Gurion ...

Click go fears of converting print files
Is there a way to convert a print queue item to a .RTF or .PDF file? I like to save or email them. - The Sydney Morning Herald

Sudanese woman ordered to hang under sharia law for converting to Christianity gives birth
Khartoum, Sudan: A Christian Sudanese woman sentenced to hang for apostasy has given birth in jail, a Western diplomat said on Tuesday.

Imams warn against radicalism to Aboriginal inmates converting to Islam
The prison system has enlisted the help of ASIO to crack down on radicalisation behind bars amid revelations that Aboriginals are converting ...

Converting the world's companies one by one - The Science Show - ABC Radio National (Australian Broadcasting ...
Image: Trucks carrying logs make their way up a road in Jambi, Indonesia. A vast area of the Sumatran forest, and orangutan habitat, is being ...

Converting Churches Into Homes Is The Latest Hollywood Trend
You don't have to be a believer to be moved by the beauty of a church.

Resources last updated: 12/30/2015 8:48:52 AM