大int的力量和模块化的airthmetic问题。 [英] power of a large int and a modular airthmetic problems.
问题描述
我正在计算一个整数到大整数的pwer，例如
2 ^ 5000。
事实证明，我总是得到的结果为零。我确定
的结果太大了，无法以u_int64_t和long int
等类型存储。
我的功率函数如下：for（i = 0; i <5000; i ++）result * = 2;
有没有什么方法可以存储这个大数字同时/何时
计算这个数字到一个大数的幂？
假设我可以正确存储大数字。我将
必须执行数字mod p，这是结果％p。
问题是如果我使用链表存储大号（其中我不知道如何），例如，我将如何执行mod p？
谢谢，
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,
推荐答案
2003年8月27日星期三00:49:21 -0700，Zero写道：
On Wed, 27 Aug 2003 00:49:21 -0700, Zero wrote:
我正在计算一个大整数的pwer的整数，例如
2 ^ 5000。
结果我得到的结果是零。我确信
结果太大，无法存储在u_int64_t和long int
等类型中。
我的幂函数如下：for（i = 0; i< 5000; i ++）结果* = 2;
是否有任何方法可以存储这么大的数字/当
计算这个数字到一个大数字的力量？
假设我可以正确存储大量数字。我将
必须执行数字mod p，这是结果％p。
问题是如果我使用链表存储大号（我不会'我不知道如何执行mod？
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?
你必须制作自己的数据类型，可能是这样的： br />
typedef struct {
size_t num_bytes;
unsigned char * bytes;
} huge_number;
和你想要在
数字上进行任何算术运算的函数。
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）
{
而（compare（huge_number，m）> = 0）{
sub（huge_number，m）;
}
返回h;
}
这可能不是最好的设计，但你得到了一般的想法：定义
你自己的类型到表示该类型的数字和操作。既然
你问过模数我包含了一个例子，那么算法基本上是从目标中减去m b $ b，直到你得到一个小于m的结果，
然后退货。
hth
NPV
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
零 < SB ******** @ yahoo.com> ha scritto nel messaggio
news：73 ************************** @ posting.google.c om .. 。
"Zero" <sb********@yahoo.com> ha scritto nel messaggio
news:73**************************@posting.google.c om...
我正在计算一个整数到大整数的pwer，例如
2 ^ 5000。
它事实证明，我总是得到的结果为零。我确信
结果太大，无法存储在u_int64_t和long int
等类型中。
我的幂函数如下：for（i = 0; i< 5000; i ++）结果* = 2;
是否有任何方法可以存储这么大的数字/当
计算这个数字到一个大数字的力量？
假设我可以正确存储大量数字。我将
必须执行数字mod p，这是结果％p。
问题是如果我使用链表存储大号（我不会'不知道怎么样，例如，我该如何执行mod？
谢谢，
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,
不知道是否它可能有所帮助：
我不记得是否真的如下：
（（A * B）％p ）=（（A％p）*（B％p））％p
但是如果它是真的那么
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 =
....
如果（p == 2）则结果为0
if（p> 2）
（（2％p）*（（（2％p）*（2 ^（k-2）％p））％p））％p
变为
（2 *（（2 *（2 ^（k-2）％p））％p））％p
您可以尝试找到算法计算这个，而不是落入
溢出。
再见
Ema
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
Zero写道：
Zero wrote:
我正在计算一个整数到pwer一个大整数，例如
2 ^ 5000。
结果我总得到的结果是零。我确信
结果太大，无法存储在u_int64_t和long int
等类型中。
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到n th power需要n + 1位;一个64位的类型没有
5001位，是吗？
-
Martin Ambuhl
2 to tne nth power requires n+1 bits; a type with 64 bits does not have
5001 bits, does it?
--
Martin Ambuhl
这篇关于大int的力量和模块化的airthmetic问题。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
