JBTALKS.CC

标题: (A ^ B) % C [打印本页]

作者: ~Zero 时间: 2010-4-28 11:29 PM
标题: (A ^ B) % C
本帖最后由 ~Zero 于 2010-4-30 05:52 PM 编辑

以免有人看不懂,
^ 是次方的意思. 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 时间: 2010-4-30 02:26 PM

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

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

((A % C) ^ B) % C

复制代码

作者: ~Zero 时间: 2010-4-30 05:54 PM
依你的方法，在我给的

A = 1111
B = 2222
C = 3333

根本解决不了。

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

作者: ~Zero 时间: 2010-4-30 06:00 PM
我的方法，供参考。（java）
听我老师说还有更容易的方法，还给提示说把 p 弄成 binary。

// INPUT: input, p, n
// OUTPUT: output
// ALGORITHM: output = (input ^ p) % n
public static int pow_mod(int input, int p, int n) {
if (p == 0)
return 1;
else if (p == 1)
return input;
else if (p == 2)
return (int)Math.pow(input, 2) % n;
else {
if ((p % 2) == 1)
return (input * pow_mod((int)Math.pow(input, 2)%n, (p-1)/2, n)) % n;
else
return pow_mod((int)Math.pow(input, 2)%n, p/2, n) % n;
}
}

复制代码

作者: Super-Tomato 时间: 2010-5-1 03:28 AM
本帖最后由 Super-Tomato 于 2010-5-1 03:33 AM 编辑

依你的方法，在我给的

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 时间: 2010-5-2 11:46 PM
其实, 最大的问题不是 A, 是 B.
就算 A = 2 罢了, B 只要上千就算不出了.

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

作者: Super-Tomato 时间: 2010-5-3 12:51 AM

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

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

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

演示

作者: ~Zero 时间: 2010-5-3 01:11 AM
演示没有东西的?

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

作者: Super-Tomato 时间: 2010-5-3 01:15 AM
本帖最后由 Super-Tomato 于 2010-5-3 01:27 AM 编辑

演示没有东西的?

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 时间: 2010-5-3 01:29 AM
我找到了!!!
http://en.wikipedia.org/wiki/Modular_exponentiation

作者: ~Zero 时间: 2010-5-3 01:33 AM

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

p/s:
String 所储存的最大空間是程 ...
Super-Tomato 发表于 2010-5-3 01:15 AM

不需要 2's compliment 这种 binary 计算方法啦,
只是把 power 变成 binary, 然后就可以在一个 for loop 里面完成,
那时候的 power 就变成只是 1 和 0 罢了.

A ^ 1 = A
A ^ 0 = 1

这种 loop 方法. 详细的就看看我刚刚发的 wikipedia, 有兴趣的我以后再发 code 上来,
没兴趣的就... 关帖了吧~ 我已经找到答案了.

作者: Super-Tomato 时间: 2010-5-3 01:45 AM

不需要 2's compliment 这种 binary 计算方法啦,
只是把 power 变成 binary, 然后就可以在一个 for loop ...
~Zero 发表于 2010-5-3 01:33 AM

谢谢，這和我在 JS 做的差不多，而這是叫位移 bitwise，而不是轉換为 binary

欢迎光临 JBTALKS.CC (https://www.jbtalks.cc/)