power of a large int and a modular airthmetic problems.

Z

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,
 
N

Nils Petter Vaskinn

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
 
E

Ema

Zero said:
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
 
M

Martin Ambuhl

Zero said:
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?
 
J

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.41246703213942603683520966701614733366889617518454111681369e+1505

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

Jirka Klaue

Paul said:
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?

This will overflow _very_ soon.
}
return y;

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

Jirka
 
E

Eric Sosman

Paul said:
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.)
 
J

jacob navia

Nils Petter Vaskinn said:
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.
 
G

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
 
P

Paul Hsieh

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;
}
 
N

Nils Petter Vaskinn

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
 
J

jacob navia

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
 
J

jacob navia

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...
 
J

jacob navia

Paul Richards said:
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.

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
 
P

Peter Shaggy Haywood

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.
int main(void)
{
qfloat a;

Non-standard type.
printf("2^5000=\n");
a = pow(2q,5000q);

Non-standard constants.
printf("%.60qe\n",a);

Non-standard conversion specifier.
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).

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?
 
P

Paul Hsieh

jacob navia said:
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.
 
J

jacob navia

Peter "Shaggy" Haywood said:
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!


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.
Non-standard type.

Of course. qfloat features 350 bits... Far more than the maximum of
64 bits offered by long double
Non-standard constants.

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

Non-standard conversion specifier.

Yes. It applies to qfloats only
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
 
P

Peter Shaggy Haywood

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!
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.

Yes, but that makes it off topic here in Standard C Land.
Of course. qfloat features 350 bits... Far more than the maximum of
64 bits offered by long double

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

Off topic.
Yes. It applies to qfloats only

Off topic.
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.

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,480
Members
44,900
Latest member
Nell636132

Latest Threads

Top