473,320 Members | 2,029 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

power of a large int and a modular airthmetic problems.

Hi,

I am calculating an integer to the pwer of a large integer, e.g.
2^5000.

It turns out that the result I always get is zero. I am sure that the
result is too large to store in such type as u_int64_t and long int
etc.

My power function is as follows: for(i=0; i<5000; i++) result *= 2;

Are there any ways of storing this large a number while/when
calculating this number to the power of a large number?

Assume that I could get the large number stored correctly. I will
have to carry out the number mod p, which is result%p.

The problem is if I stored the large number using linked list (which I
don't know how), for example, how would I carry out the mod p?

Thanks,
Nov 13 '05 #1
18 5584
On Wed, 27 Aug 2003 00:49:21 -0700, Zero wrote:
Hi,

I am calculating an integer to the pwer of a large integer, e.g.
2^5000.

It turns out that the result I always get is zero. I am sure that the
result is too large to store in such type as u_int64_t and long int
etc.

My power function is as follows: for(i=0; i<5000; i++) result *= 2;

Are there any ways of storing this large a number while/when
calculating this number to the power of a large number?

Assume that I could get the large number stored correctly. I will
have to carry out the number mod p, which is result%p.

The problem is if I stored the large number using linked list (which I
don't know how), for example, how would I carry out the mod p?


You'll have to make your own datatype, maybe something like:

typedef struct {
size_t num_bytes;
unsigned char *bytes;
} huge_number;

And functions for any kind of arithmetic operation you want to do on the
numbers.

void huge_times_2(huge_number *h);
huge_number mod(huge_number *h, int m);

// -1: a<b 0: a==b 1: a>b
int compare(huge_number *a, int b);
void sub(huge_number *h, int s);

huge_number *mod(huge_number *h, int m)
{
while ( compare(huge_number,m) >= 0) {
sub(huge_number,m);
}

return h;
}


This is probably not the best design but you get the general idea: define
your own type to represent the numbers, and operations on that type. Since
you asked about modulo I included an example, the algoritm is basically

substract m from the target until you get a result that is less than m,
then return it.
hth
NPV
Nov 13 '05 #2
Ema

"Zero" <sb********@yahoo.com> ha scritto nel messaggio
news:73**************************@posting.google.c om...
Hi,

I am calculating an integer to the pwer of a large integer, e.g.
2^5000.

It turns out that the result I always get is zero. I am sure that the
result is too large to store in such type as u_int64_t and long int
etc.

My power function is as follows: for(i=0; i<5000; i++) result *= 2;

Are there any ways of storing this large a number while/when
calculating this number to the power of a large number?

Assume that I could get the large number stored correctly. I will
have to carry out the number mod p, which is result%p.

The problem is if I stored the large number using linked list (which I
don't know how), for example, how would I carry out the mod p?

Thanks,


Don't know if it could be of help:

I don't remember if it true the following:

((A*B) % p) = ((A % p) * (B % p)) % p

but if it's true then

2^k % p =
(2 * 2^(k-1)) % p =
((2 % p) * (2^(k-1) % p)) % p =
((2 % p) * (((2 % p) * (2^(k-2) % p)) % p)) % p =
....
if (p==2) then the result is 0
if (p > 2)
((2 % p) * (((2 % p) * (2^(k-2) % p)) % p)) % p
becomes
(2 * ((2 * (2^(k-2) % p)) % p)) % p

and you can try to find an algorithm to calculate this without falling in
overflow.

Bye
Ema
Nov 13 '05 #3
Zero wrote:
Hi,

I am calculating an integer to the pwer of a large integer, e.g.
2^5000.

It turns out that the result I always get is zero. I am sure that the
result is too large to store in such type as u_int64_t and long int
etc.


2 to tne nth power requires n+1 bits; a type with 64 bits does not have
5001 bits, does it?


--
Martin Ambuhl

Nov 13 '05 #4
Use lcc-win32

#include <stdio.h>
#include <qfloat.h>
int main(void)
{
qfloat a;

printf("2^5000=\n");
a = pow(2q,5000q);
printf("%.60qe\n",a);
return 0;
}

Output:
---------

2^5000=
1.412467032139426036835209667016147333668896175184 54111681369e+1505

But beware: those are floating point numbers, not integers.
"Zero" <sb********@yahoo.com> wrote in message
news:73**************************@posting.google.c om...
Hi,

I am calculating an integer to the pwer of a large integer, e.g.
2^5000.

It turns out that the result I always get is zero. I am sure that the
result is too large to store in such type as u_int64_t and long int
etc.

My power function is as follows: for(i=0; i<5000; i++) result *= 2;

Are there any ways of storing this large a number while/when
calculating this number to the power of a large number?

Assume that I could get the large number stored correctly. I will
have to carry out the number mod p, which is result%p.

The problem is if I stored the large number using linked list (which I
don't know how), for example, how would I carry out the mod p?

Thanks,

Nov 13 '05 #5
> "Zero" <sb********@yahoo.com> wrote in message
news:73**************************@posting.google.c om... On Wed, 27 Aug 2003 15:58:38 +0200, jacob navia wrote:
The problem is if I stored the large number using linked list (which I
don't know how), for example, how would I carry out the mod p?

But beware: those are floating point numbers, not integers.


So how do you do modulo on that floating point number then?
NPV
Nov 13 '05 #6
Paul Hsieh wrote:
If p is small, there is a standard way of doing this. You don't need bignum
libraries, and you don't need to store the big number. Ema's answer is the
closest I see posted so far, but this is really a sci.math question, not a
comp.lang.c question:

unsigned int i, x, y;
x = 2;
y = 1;
for (i=5000; i >= 0; i >> 2) {
Two errors in one line:
- i will always be >= 0
- i >> 2 is a no-op
if (i & 1) y = (y * x) % p;
What is p?
x *= x;
This will overflow _very_ soon.
}
return y;


You should have answered this in sci.math, as you suggested. :-)

Jirka

Nov 13 '05 #7
Paul Hsieh wrote:

If p is small, there is a standard way of doing this. You don't need bignum
libraries, and you don't need to store the big number. Ema's answer is the
closest I see posted so far, but this is really a sci.math question, not a
comp.lang.c question:

unsigned int i, x, y;
x = 2;
y = 1;
for (i=5000; i >= 0; i >> 2) {
if (i & 1) y = (y * x) % p;
x *= x;
}
return y;


Infinite loop as written; `i >> 2' should probably
be `i >>= 1'.

Unfortunately, even with the correction this will
produce the answer zero on any reasonable machine because
the `x *= x' will eventually exceed `UINT_MAX' and will
store the value zero into `x'. (The "mathematical" value
of `x' would be two-to-the-large, and this value is exactly
divisible by `UINT_MAX+1' == two-to-the-smaller.)

--
Er*********@sun.com
Nov 13 '05 #8

"Nils Petter Vaskinn" <no@spam.for.me.invalid> wrote in message
news:pa****************************@spam.for.me.in valid...
"Zero" <sb********@yahoo.com> wrote in message
news:73**************************@posting.google.c om...

On Wed, 27 Aug 2003 15:58:38 +0200, jacob navia wrote:
The problem is if I stored the large number using linked list (which I
don't know how), for example, how would I carry out the mod p?

But beware: those are floating point numbers, not integers.


So how do you do modulo on that floating point number then?
NPV


Without resorting to bignums we can still do:

#include <qfloat.h>
#include <stdio.h>
int main(void)
{

printf("(2^5000) %%10000=%qf\n",qfmod(pow(2q,5000q),10000q));
return 0;
}

and it prints
(2^5000) %10000=9376
as it should, the same number I obtain with the bignums package.
Nov 13 '05 #9
>I am calculating an integer to the pwer of a large integer, e.g.
2^5000.

It turns out that the result I always get is zero. I am sure that the
result is too large to store in such type as u_int64_t and long int
etc.

My power function is as follows: for(i=0; i<5000; i++) result *= 2;
You need an integer with at least 5001 bits; most implementations
don't have such a thing. Floating point numbers often don't have
enough range in the exponent to represent this, either. A standard
IEEE double won't.
Are there any ways of storing this large a number while/when
calculating this number to the power of a large number?

Assume that I could get the large number stored correctly. I will
have to carry out the number mod p, which is result%p.


It is often simpler to calculate result%p by a means other than
calculating result, then doing the %p operation.

For example:
c = a * b
(c % p) = ((a % p) * (b % p) ) % p

If p fits in a long, so do a%p and b%p. (a%p)*(b%p) will fit in
something twice the size of a long. You can do exponentiation by
repeated multiplication.

If you really need to compute with large numbers, there are a
number of "bignum" packages which can deal with large or
arbitrarily large numbers.

Gordon L. Burditt
Nov 13 '05 #10
As others have pointed out, my post contained errors, though oddly they didn't
bother to fix them. Here's the program with corrections:

unsigned int twotothe5000modp (unsigned int p) {
unsigned int i, x, y;
x = 2;
y = 1;
for (i=5000; i; i >>= 1) {
if (i & 1) y = (y * x) % p;
x = (x * x) % p;
}
return y;
}

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Nov 13 '05 #11
On Wed, 27 Aug 2003 20:52:02 +0200, jacob navia wrote:
"Nils Petter Vaskinn" <no@spam.for.me.invalid> wrote in message
So how do you do modulo on that floating point number then?

Without resorting to bignums we can still do:

#include <qfloat.h>
#include <stdio.h>
int main(void)
{

printf("(2^5000) %%10000=%qf\n",qfmod(pow(2q,5000q),10000q));
return 0;
}

and it prints
(2^5000) %10000=9376
as it should, the same number I obtain with the bignums package.


How does that work? For modulo to have any meaning you cannot lose
precision. Does qfloat use all the digits in the calculations? And if they
do we're using bigfloats where we could have used bigintegers (with the
assumption that algorithms for integers can be made more efficient than
algorithms for floating point numbers, that can't be a good choice)

regards
NPV
Nov 13 '05 #12
> How does that work? For modulo to have any meaning you cannot lose
precision. Does qfloat use all the digits in the calculations? And if they
do we're using bigfloats where we could have used bigintegers (with the
assumption that algorithms for integers can be made more efficient than
algorithms for floating point numbers, that can't be a good choice)


Qfloat has only 350 bits. It gives the right result because the numbers are
a power of two exactly, and therefore they have 100% precision even in floating point
because they are exactly representable. If we would do 3^5000 it would not
work.

It is better to use the bignums package, even it is slower.

jacob
Nov 13 '05 #13
Yes. Now it gives (2^5000) % 10000 == 9376, as the bignum package
does.

I tried to correct it, and got right the i >>= 1 but couldn't figure out
that (x*x) must be taken modulo p...

"Paul Hsieh" <qe*@pobox.com> wrote in message
news:MP************************@news.sf.sbcglobal. net...
As others have pointed out, my post contained errors, though oddly they didn't
bother to fix them. Here's the program with corrections:

unsigned int twotothe5000modp (unsigned int p) {
unsigned int i, x, y;
x = 2;
y = 1;
for (i=5000; i; i >>= 1) {
if (i & 1) y = (y * x) % p;
x = (x * x) % p;
}
return y;
}

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Nov 13 '05 #14

"Paul Richards" <pa***********@sun.com> wrote in message
news:bi**********@news1brm.Central.Sun.COM...
It's amazing how many replies the original poster got which didn't take
advantage of taking the modulo every iteration. Is quite scary that
there are so many programmers out there who would blindly try to
calculate 2^5000 % 10000 the long way.
jacob navia wrote:
Yes. Now it gives (2^5000) % 10000 == 9376, as the bignum package
does.


Scaring?

Why should anyone be 100% up-to-date in such a problem?

You are a researcher Paul. Please do not be scared.

Many people are not
researchers and do not know how to take calculate (2^5000) % p in an
efficient way.

So what?

Besides, I feel more confident in the solution now that the bignum
package gives the same answer.

jacob
Nov 13 '05 #15
"jacob navia" <ja*********@jacob.remcomp.fr> wrote:
"Paul Richards" <pa***********@sun.com> wrote:
It's amazing how many replies the original poster got which didn't take
advantage of taking the modulo every iteration. Is quite scary that
there are so many programmers out there who would blindly try to
calculate 2^5000 % 10000 the long way.

jacob navia wrote:
Yes. Now it gives (2^5000) % 10000 == 9376, as the bignum package
does.


Scaring?
Why should anyone be 100% up-to-date in such a problem?
You are a researcher Paul. Please do not be scared.


This is a 1st or 2nd year college problem. Of course we *ALL* forgot
Fermat's Little theorem:

2^(p-1) == 1 (mod p)

I.e.:

/* Assuming p is a prime, otherwise (p - 1) needs to be
replaced by phi(p) */
unsigned int twotothe5000modp (unsigned int p) {
unsigned int i, x, y;
x = 2;
y = 1;
i = 5000;
if (5001 > p) i %= (p - 1);
for (; i; i >>= 1) {
if (i & 1) y = (y * x) % p;
x = (x * x) % p;
}
return y;
}

Which should lead to a speed up for p < 4096.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Nov 13 '05 #16

"Peter "Shaggy" Haywood" <ph******@alphalink.com.au.STOP.SPAM> wrote in message
news:3f**************@news.alphalink.com.au...
Groovy hepcat jacob navia was jivin' on Wed, 27 Aug 2003 15:58:38
+0200 in comp.lang.c.
Re: power of a large int and a modular airthmetic problems.'s a cool
scene! Dig it!
Use lcc-win32

#include <stdio.h>
#include <qfloat.h>
Non-standard header.


Yes. That header defines the interface of the qfloat type. By the way
the include directive can be used to include any type of file, not
only the ones defined in the standard.
int main(void)
{
qfloat a;
Non-standard type.


Of course. qfloat features 350 bits... Far more than the maximum of
64 bits offered by long double
printf("2^5000=\n");
a = pow(2q,5000q);


Non-standard constants.


Yes. Following the standard 100L 100LL lcc-win32 adds 100q. The "q"
suffix specifies a constant with extended precision.

printf("%.60qe\n",a);


Non-standard conversion specifier.


Yes. It applies to qfloats only
return 0;
}


Even if all these non-standard features were standard, you still may
not get a very accurate result, since pow() takes arguments of type
double and returns a double, not qfloat (whatever that is).

As you may know, pow() is a type generic function that should work with
any real floating type. Since qfloats are real floating types albeit with
a more extended range and precision, this use of pow() is perfectly
within the constraints of the C language

Nov 13 '05 #17
jacob navia wrote:

Use lcc-win32


Off topic.

--
pete
Nov 13 '05 #18
On Wed, 03 Sep 2003 04:07:19 GMT, ph******@alphalink.com.au.STOP.SPAM
(Peter "Shaggy" Haywood) wrote:
Groovy hepcat jacob navia was jivin' on Sat, 30 Aug 2003 12:49:42
+0200 in comp.lang.c.
Re: power of a large int and a modular airthmetic problems.'s a cool
scene! Dig it!
"Peter "Shaggy" Haywood" <ph******@alphalink.com.au.STOP.SPAM> wrote in message
news:3f**************@news.alphalink.com.au...
Groovy hepcat jacob navia was jivin' on Wed, 27 Aug 2003 15:58:38
+0200 in comp.lang.c.
Re: power of a large int and a modular airthmetic problems.'s a cool
scene! Dig it!
[ solution using LCC-extension qfloat -- rejected as nonstandard ]
As you may know, pow() is a type generic function that should work with
any real floating type. Since qfloats are real floating types albeit with
a more extended range and precision, this use of pow() is perfectly
within the constraints of the C language


Just plain wrong. pow() is a function that takes, as I said, two
doubles and returns a double. Look it up in the standard, K&R or any
other decent C book.


In C99 (which IIRC Jacob's LCC partially implements) pow(), like all
<math.h> functions, is optionally (if you use <tgmath.h>) type-generic
across all the standard floating-point (real and complex) types.

Jacob's extension to qfloat is nonstandard since qfloat itself is, but
I think quite in the spirit of the standard.

- David.Thompson1 at worldnet.att.net
Nov 13 '05 #19

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

36
by: Andrea Griffini | last post by:
I did it. I proposed python as the main language for our next CAD/CAM software because I think that it has all the potential needed for it. I'm not sure yet if the decision will get through, but...
5
by: Tim | last post by:
Dear All, I have been working with VB.NET for the last 5 months or so as a solo developer for a small business. I have already started developing the application but have hit a snag with the...
6
by: Stephane Belzile | last post by:
Is there a way I can detect in vb.Net the power has switched to a UPS unit in case of power failure? Thanks
0
by: Thiva Charanasri | last post by:
http://www.poweroflanguage.org Track: Computer Language 1st World Congress on the Power of Language: Theory, Practice and Performance Date: March 6 - 10, 2006 Bangkok, Thailand On this...
0
by: Thiva Charanasri | last post by:
http://www.poweroflanguage.org Track: Computer Language 1st World Congress on the Power of Language: Theory, Practice and Performance Date: March 6 - 10, 2006 Bangkok, Thailand On this...
4
by: Nick Goloborodko | last post by:
Hi, I'm in the process of conceptualizing a new ASP.NET application. I'm a relative newbie in ASP.NET / .NET in general, so any comments will be greatly appreciated. Basically i need to make...
26
by: I_AM_DON_AND_YOU? | last post by:
This is the scenario: I have a VB.Net project comprising of a few Forms. On Form1 I have more than 20 buttons. There is a very lenghty code written in click event of each and every button. Right...
2
by: Canice | last post by:
I'm working on a web application where 90% of it is common 'product' code an the other 10% is customer specific. I want some method of separating the customer specific presentation, business and...
12
by: calimero22 | last post by:
Hi I'musing the GMP Libraries Mathematics. I need to calculate 12345678987654321.1234567876554456 ^ 9876543212344556676.676767676 How can i do ? The two variables are type MPF. Thanks
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.