power of a large int and a modular airthmetic problems.

[Zero]

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,

[Nils Petter Vaskinn]

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(hu ge_number *h);
huge_number mod(huge_number *h, int m);

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

huge_number *mod(huge_numbe r *h, int m)
{
while ( compare(huge_nu mber,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

[Ema]

"Zero" <sb********@yah oo.com> ha scritto nel messaggio
news:73******** *************** ***@posting.goo gle.com...

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

[Martin Ambuhl]

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

[jacob navia]

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.4124670321394 260368352096670 161473336688961 751845411168136 9e+1505

But beware: those are floating point numbers, not integers.
"Zero" <sb********@yah oo.com> wrote in message
news:73******** *************** ***@posting.goo gle.com...

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,

[Nils Petter Vaskinn]

> "Zero" <sb********@yah oo.com> wrote in message

news:73******** *************** ***@posting.goo gle.com... 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

[Jirka Klaue]

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

[Eric Sosman]

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 "mathematic al" 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

[jacob navia]

"Nils Petter Vaskinn" <[e-mail] .invalid> wrote in message
news:pa******** *************** *****@spam.for. me.invalid...

"Zero" <sb********@yah oo.com> wrote in message
news:73******** *************** ***@posting.goo gle.com...

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,50 00q),10000q));
return 0;
}

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

[Gordon Burditt]

>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