推 suhorng:阿 我誤解了他的 linear time 跟 exponential time 意思了 01/13 12:59
→ suhorng:原來他的 exp time 是指一直加........ 01/13 12:59
→ DJWS:我想它指的exp-time演算法，應該就是只用加法來計算乘法 01/13 13:03
※ 引述《initial1635 (AmazingTWman)》之銘言：
: 有一個Hint是
: The “double and add” strategy helps you come out a linear time
: implementation of scalar multiplication instead of exponential time
: 但是我看不懂這是要幹嘛= =
: 把變數宣告改成double連算都沒法算 然後沒有在C++裡面看過add 所以不知道是幹嘛的@@
: 這種20位數以上的運算有辦法算嗎@@?
double and add 是乘兩倍、加上去的意思。
那是一個演算法，用來計算兩數相乘的結果。
程式碼大概長這樣：
// x = a * b % m;
// 二進位直式乘法，一邊算一邊加。
long long int mul(long long int a, long long int b, long long int m)
{
unsigned long long int x = 0, t = a;
for (; b > 0; b >>= 1)
{
if (b & 1) x = (x + t) % m;
t = (t + t) % m;
}
return x;
}
long long int 支援到 2^63 - 1
由於兩個 long long int 相加有可能溢位，
所以就轉型成 unsigned long long int 支援到 2^64 - 1
範圍剛好是原本的兩倍（再加一），相加就不會溢位了。
（反覆平方法是另外一個東西，用來計算次方的，原理很類似、程式碼也很相像。）
（http://en.wikipedia.org/wiki/Exponentiation_by_squaring）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.132.121
※ 編輯: DJWS 來自: 36.225.132.121 (01/13 12:56)