能否在O(nlogn)時間內實現大數的進位轉換？
對於一個長度為n+1的多項式用數組存儲各項係數，其係數均為非負整數且小於10，則其可代表一個十進位數。 即
。同理也可以定義二進位、八進位、十六進位、三十六進位等。
對於一個A進位大數，對應數值相等的B進位大數是唯一的。有比較高效的從
獲得
的方法嗎？其中
。
先解決其中的兩種特例，再通過和2進位相互轉換的方式解決其它情況。這裡默認用到的a或者b進位的係數本身的加減乘除運算都是O(1)的，不考慮2^1000-1進位這種情況。
第一種最簡單，如果a和b存在正整數m和n滿足 ，那麼這個轉換是很容易的，只需要a進位每m位轉換成b進位n位即可，這個應該很好理解，就不具體說了。
第二種我們考慮a和b互質的情況，這裡考慮應用歐拉定理，對於任意的正整數k，有：
這裡 是歐拉函數，代表1-n中與n互質的數的個數。注意到與
互質的數一定與b也互質，很容易得到
也就有
我們可以將同餘式改寫成
注意到有
將 本身用b進位表示的話，這個遞推式本身是需要乘法的，這裡需要應用多項式快速乘法的原理，將所有的b進位數都表示成FFT變換的形式（FFT的大小可以提前通過最大需要的位數估算出來），這樣多項式的b次方的計算可以通過FFT計算，複雜度可以降到
，由於
的位數不超過
，當k為
時算出
到
整體的複雜度也是
現在，將一個n位a進位數A轉換為b進位，且a與b互質時，我們首先取k使得
然後將這個數分解成後 位和前面的位數，這兩個分解後的a進位數分別記為B和C，即
根據前面的討論，有
如果遞歸計算出B和B+C的b進位表達式，接下來同樣用FFT計算一次乘法，再移位、相加，額外的複雜度為 ，而B和C的長度不超過
，整體複雜度應該不超過
。如果中間保留FFT結果（B和C都遞歸計算出FFT結果），考慮到FFT結果可以以
的時間複雜度進行乘法、加法、移位和擴張（點數加倍），整體複雜度可以降到
，但是需要證明這種情況下進位處理的複雜度不會增加。
接下來我們來處理a和b不互質的情況，考慮到如果我們可以將所有進位的數都和2進位進行 的相互轉換，那也就等於所有進位之間都可以互相轉換了，所以我們接下來的重點考慮和2進位的相互轉換。奇數進位、
進位的情況前面解決了，我們接下來解決
，其中q是大於或等於3的奇數的情況。
首先是a進位向2進位轉換，跟之前一樣我們有
跟之前一樣寫成
兩邊同時乘以一個係數有
即
剩下的和之前做法差不多，首先將n位數A分解為
然後變成
遞歸轉換B和C，然後通過相同的方法做乘法、移位、加法，就可以實現轉換。
接下來是2進位向a進位轉換，和之前一樣有
寫成
同時乘以 得
也就是
之後也是分解
和剛才略有不同的是，這次是先移位相加，然後再分別轉換，但複雜度是一樣的。
至此，所有進位都可以和2進位相互轉換，因此所有進位之間也都可以進行相互轉換了。
參見 Numerical Recipes in C: The Art of Scientific Computing. Second Edition by William H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery 第922頁，書裏實現的是 的方法，但是書裏說了
NOTE: For simplicity, this routine implements a slow
algorithm. Fast
, more complicated, radix conversion algorithms do exist.
書裏前一段是這麼說的
It is possible to do the radix conversion as a fast operation by a "divide and conquer" strategy.
所以應該是用分治法。
抱著學習的心態嘗試著答這道題目
思路
主體思路是分治，思路來源[1]。
首先將A進位轉化為二進位：
- 將N位的數字
分成兩半：
- 遞歸的將high， low兩部分轉化為二進位
- 計算
那麼最後X就是二進位狀態，遞歸的時間複雜度為 ，
用FFT計算複雜度為
，（
轉化為二進位的時間複雜度咋算啊？？）總複雜度為
將二進位轉化為B進位：
, M為表示的位數
- 遞歸去計算high， low部分，將兩者相合，即可得到答案。
總時間複雜度為
這也是劍靈大佬評論區裡面的解法。
實現
GMP源碼?github.com我們主要學習mpn/generic/set_str.c (radix-&>binary) 和 mpn/generic/get_str.c (binary-&>radix) ，結合說明文檔[2] 。最大進位目前支持256進位。
並且如果字元串的大小沒有超過設置的閾值SET_STR_DC_THRESHOLD那麼就是用樸素的 演算法
mpn_bc_xx() ,否則會使用分治演算法mpn_dc_xxx() 。
不知道有沒有OI/ACM大佬能不能把這個出成一個模板題 orz，跪求鏈接和板子
參考
- ^http://www.numberworld.org/y-cruncher/internals/radix-conversion.html
- ^https://gmplib.org/manual/Binary-to-Radix.html#Binary-to-Radix
這裡有些乾貨, 看了其他的答案,似乎沒什麼特別好的回答.
f(x) = a0*x^0 + a1*x^1 + a2*x^2 + a3*x^3 + a4*x^4 + ....
=B0*x^0 + B1*x^1 + B2*x^2 + B3*x^3 + B4*x^4 + …. (1)
= (B0 + B1*x^1)*x^0 + (B2+B3*x)*x^2 + (B4 + B5*x)*x^4 + …..
= C0*x^0 + C2*x^2 + C4*x^4 + ….. (2)
= D0*x^0 + D4*x^4 + …. (3)
.
.
.
= N0*x^0 + N(n/2) * x^(n/2) (t)
= M
簡單起見, 合理假設k * k 長度的乘法複雜度是 k logk
複雜度計算位
(1) (2) (3) ….(t)
每行的複雜度為 N / k * k logk = N * logk
共 logN行
O(N) = N * log1 + N * log2 + N * log4 + N * log8 + ….NlogN
= N * LogN * (1/LogN + ….1 / 4 + 1/3 + 1/2 + 1/1) (準確值)
= N*logN
PS:
這裡有幾個地方是是有較大的修正:
1)在實際工程上, (1/LogN + ….1 / 4 + 1/3 + 1/2 + 1/1) 這一坨 這裡N 可以認為不可能大於 2^32次方, 因此這裡基本上就是一個很小的常數K,
2)由於以上的計算只是簡單地把 k * k位乘法看成 klogk的乘法,實際上,這個估算是估算大了,如果k不大的情況下,k * k 有比klogk的FFT更好的演算法.
3)每一層 * x^k這個乘法,由於 *x^K在每層都是固定的, 實際上FFT裡面的3次傅裏葉變換,有一次傅裏葉變換在每層裡面都是可以共用的. 因此 每次* x^k 實際上平均下來相當於只要2次變換多一些就可以了
因此這個
(準確值) 裡面的 NlogN 的係數實際上並不大.
另外,
這個演算法跟多少進位轉換到多少進位無關.
如果這個問題的答案有了，你是不是就想顛覆現有計算機的數學架構哦？
從這個數可以確定一組泛函。轉換前後的兩個不同數制的數組，分別以整數的形式落在兩個一元多項式上，如果可以快速轉換，各種不同的數制平行計算即可實現，我理解這實際上就是量子模擬計算。
從實數出發，這一想法已經被5次以上無根式解鎖定，現在就看有沒有其它捷徑了。
以二進位轉十進位為例：
已知大數 B0，可以通過貪心演算法得到小於但是接近 B0 的十進位數 D0 (10^n, n = 2^x)
將 B0 轉成 D0 進位的 B1
將 B1 轉成 D1 (10^(n / 2)) 進位的 B2
...
按上述方式迭代至 Dm = 10 得到的 Bm 為期望解，且符合期望時間複雜度
...
突然剛發現 貪心演算法部分需要用到 n*n 複雜度的乘法，乖乖用模板元生查找表成然後二分查找吧
如果假設A,B是常數， ，首先找到
並轉換成
進位，那麼
，於是分治的複雜度是
。
推薦閱讀：
