梅森旋轉算法是一種可以快速產生高級偽隨機數的算法,修正了很多以前的隨機速算法的缺陷(Ex:線性同於算法)。
這是專門用在蒙地卡羅測試用的,不要拿它來做持久化隨機二叉數的亂數產生器,會太慢
最為廣泛使用Mersenne Twister的一種變體是MT19937,可以產生32位整數序列,從C++11開始,C++也可以使用這種算法。在Boost C++,Glib和NAG數值庫中,作為插件提供。但是一般在競賽時可能會有不支援的情況發生,所以將它做成模板當作參考。
MT19937_64則是可以產生64位整數序列
以下提供模板:
\(
\newcommand{\ord}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\opord}{\operatorname{\mathcal{O}}}
\newcommand{\argmax}{\operatorname{arg\,max}}
\newcommand{\str}[1]{\texttt{"#1"}}
\)
2016年4月21日 星期四
2016年4月6日 星期三
2016年4月2日 星期六
[ Number Theoretic Transform ] 快速數論變換)(NTT)
這也不知道怎麼說明,應該是我數學太爛的關係,直接看連結吧
有以下幾點要注意:
long long 乘 long long 模 long long不溢位算法
只需要將code裡面所有的A*B%M的部分改掉即可
以下提供模板(bit_reverse參考自Morris):
有以下幾點要注意:
- P要是一個q*2^k+1的質數,G是P的原根
- N(數列長度)要是2的冪次
- (P-1)%N=0
- 做了逆轉換後的結果為原本數列mod P的結果,所以P要夠大
- 如果要求P是任意數的話,可以用中國剩餘定理處理
- 2615053605667*(2^18)+1,3
- 15*(2^27)+1,31
- 479*(2^21)+1,3
- 7*17*(2^23)+1,3
- 3*3*211*(2^19)+1,5
- 25*(2^22)+1,3
long long 乘 long long 模 long long不溢位算法
只需要將code裡面所有的A*B%M的部分改掉即可
以下提供模板(bit_reverse參考自Morris):
[ fast fourier transform - Cooley Tukey ] 快速傅立葉轉換(FFT)
因為不知道怎麼說明所以提供一些網址:
注意:
注意:
- N(數列長度)要是2的冪次
訂閱:
文章 (Atom)