(A ^ B) % C

~Zero

以免有人看不懂,
^ 是次方的意思. 6 ^ 2 = 6 的平方 = 36
% 是 modulus. 就是余数. 23 % 10 = 23 除 10 的余数 = 3

如果我的 A 和 B 数目都有可能很大, 甚至一个 long 都装不下,
例如:
A = 1111
B = 2222
C = 3333
那么 A ^ B = 1111 ^ 2222. 不能用平常的方法来算, 有什么办法解决?

我目前是用这个概念的:
(A ^ B) % C = (A^2 % C) ^ (B/2) % C
然后一直 recursion 到 B/2 = 1 为止.

有没有更好, 更快, 还是更容易的方法?

Super-Tomato

以免有人看不懂,
^ 是次方的意思. 6 ^ 2 = 6 的平方 = 36
% 是 modulus. 就是余数. 23 % 10 = 23 除 10  ...
~Zero 发表于 2010-4-28 11:29 PM

呃~~~ 在我概念上我會改成這樣计算, 只是是否正确就你自己去測試了，在某些條件下也許會超出范围吧

1. ((A % C) ^ B) % C

复制代码

~Zero

依你的方法，在我给的

A = 1111
B = 2222
C = 3333

根本解决不了。

((A % C) ^ B) % C
= ((1111 % 3333) ^ 2222) % 3333
= (1111 ^ 2222) % 3333 <-- 做不下了，打回原形。

~Zero

我的方法，供参考。（java）
听我老师说还有更容易的方法，还给提示说把 p 弄成 binary。

1. 
   
2.     // INPUT: input, p, n
   
3.     // OUTPUT: output
   
4.     // ALGORITHM: output = (input ^ p) % n
   
5.     public static int pow_mod(int input, int p, int n) {
   
6.         if (p == 0)
   
7.             return 1;
   
8.         else if (p == 1)
   
9.             return input;
   
10.         else if (p == 2)
    
11.             return (int)Math.pow(input, 2) % n;
    
12.         else {
    
13.             if ((p % 2) == 1)
    
14.                 return (input * pow_mod((int)Math.pow(input, 2)%n, (p-1)/2, n)) % n;
    
15.             else
    
16.                 return pow_mod((int)Math.pow(input, 2)%n, p/2, n) % n;
    
17.         }
    
18.     }
    

复制代码

Super-Tomato

依你的方法，在我给的

A = 1111
B = 2222
C = 3333

根本解决不了。

((A % C) ^ B) % C
= ((1 ...
~Zero 发表于 2010-4-30 05:54 PM

抱歉, 可能我沒寫清楚我所表達的意思

(A^2 % C) ^ (B/2) % C

因為理論上只要使用者輸入 A 為你數值型態的 MAX(9223372036854775807) 那麼只要一執行必定會出錯, 所以簡單來說先把 A % C 後所得的 A 代入你的公式會比較能夠減少溢出的機率

~Zero

其实, 最大的问题不是 A, 是 B.
就算 A = 2 罢了, B 只要上千就算不出了.

这是 encryption 里面的其中一个步骤, 我可以把 A 和 B 控制在一定的范围内 (几位数的 block size).
但是不可以太小, 不然 encryption 就没意义了.
而且, 如果 user 输入 int 的最大值, 我可以勉勉强强把 result 存在 long 或 double 里面.
最难解决的问题是, B 和 A 是成正比的. 当 A 越大, B 就会越大. 但是 A 不可以太小, 4 位数已经算太小了.

Super-Tomato

其实, 最大的问题不是 A, 是 B.
就算 A = 2 罢了, B 只要上千就算不出了.

这是 encryption 里面的其中一 ...
~Zero 发表于 2010-5-2 11:46 PM

應該是 looping 因計算太過频繁而當掉的問題，而我剛要測試你說的 binary，但想想也最多只能到 64bits 啊....
回到你最初學習数学時候的方式就容易许多了，因為這系統没安裝 Java 所以我簡單用了 Javascript 來測試我所提到理论

演示

~Zero

演示没有东西的?

binary 是没有限制 64-bit 还是什么的, 可以用 String 或 int[] 来存.
这个方法我不是很清楚, 要 google 也不知道什么关键字.
我再翻翻书研究研究. 知道了再发上来分享.

Super-Tomato

演示没有东西的?

binary 是没有限制 64-bit 还是什么的, 可以用 String 或 int[] 来存.
这个方法我不是 ...
~Zero 发表于 2010-5-3 01:11 AM

多亏我們有为的 ISP， 我上傳速度不到50kbps, 剛剛才上傳好


p/s: http://java.sun.com/docs/books/t ... olts/datatypes.html
String 所储存的最大空間是程式所建立的 4GB ，并非无限
如果你真的有空去寫 2's complement 的計算的話... 我覺得倒不如做些其他的

~Zero

我找到了!!!
http://en.wikipedia.org/wiki/Modular_exponentiation