fujidig fujidig
fujidig
/ mt-state-action.html
Created
January 7, 2016 22:35
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html lang="ja"> | |
| <head> | |
| <meta charset="utf-8" /> | |
| <title></title> | |
| <style> | |
| html, body, canvas { | |
| margin: 0; | |
| padding: 0; | |
| } |
fujidig
/ linear-automata-period.rb
Last active
January 13, 2016 08:42
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require "matrix" | |
| require "set" | |
| require_relative "finite_fields.rb" # https://github.com/robertzk/FiniteFields | |
| class FiniteField | |
| public :all_elements | |
| def size() @prime ** @exponent end | |
| end | |
| class FiniteFieldElement |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require "matrix" | |
| require "prime" | |
| require "set" | |
| Infinity = Float::INFINITY | |
| CHARS = [+1, -1, +2, -2] | |
| A = Matrix[[1, 2], [0, 1]] | |
| B = Matrix[[1, 0], [2, 1]] |
fujidig
/ mt19937-period.rb
Created
January 28, 2016 05:16
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| P = 19937 | |
| N = 624 | |
| M = 397 | |
| W = 32 | |
| R = 31 | |
| MATRIX_A = 0x9908b0df | |
| UMASK = 0x80000000 | |
| LMASK = 0x7fffffff | |
| MAG01 = [0, MATRIX_A] |
fujidig
/ mt19937-period.rs
Last active
January 29, 2016 08:38
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const P : usize = 19937; | |
| const N : usize = 624; | |
| const M : usize = 397; | |
| const W : usize = 32; | |
| const R : usize = 31; | |
| const MATRIX_A : u32 = 0x9908b0df; | |
| const LMASK : u32 = (1 << R) - 1; | |
| const UMASK : u32 = LMASK ^ 0xffffffff; | |
| struct State { |
fujidig
/ mt19937-period.cpp
Last active
January 29, 2016 13:15
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <cstdint> | |
| #include <ctime> | |
| #include <array> | |
| typedef uint32_t u32; | |
| const int P = 19937, N = 624, M = 397, W = 32, R = 31; | |
| const u32 MATRIX_A = 0x9908b0df; | |
| const u32 LMASK = (1u << R) - 1; | |
| const u32 UMASK = ~LMASK; |
fujidig
/ isprimitive.gp
Created
February 4, 2016 09:57
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| isprimitive(g, n)= | |
| { | |
| local(factors, p); | |
| factors = factor(n); | |
| for (i = 1, matsize(factors)[1], | |
| p = factors[i, 1]; | |
| if (g^(n/p) == 1, return(0);); | |
| ); | |
| return(1); | |
| } |
fujidig
/ xorshift-period.gp
Last active
February 5, 2016 11:45
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \\ determine that order of g equals to n | |
| isprimitive(g, n, e=1) = { | |
| my(factors, p); | |
| if (g^n != e, return(0)); | |
| factors = factor(n); | |
| for (i = 1, matsize(factors)[1], | |
| p = factors[i, 1]; | |
| if (g^(n/p) == e, return(0))); | |
| return(1); | |
| } |
fujidig
/ integer-sqrt.rb
Last active
February 29, 2016 02:29
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 整数での平方根 | |
| # isqrt1, isqrt2はBabylonian methodを使う | |
| # isqrt3は二分探索 | |
| # http://www001.upp.so-net.ne.jp/y_yutaka/labo/math_algo/math_algo.html | |
| # http://cpplover.blogspot.jp/2010/11/blog-post_20.html | |
| def isqrt1(n) | |
| x = n | |
| while true |
fujidig
/ triangular-inv.rb
Created
February 29, 2016 02:50
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # T_n = 1 + 2 + ... + n としたとき | |
| # 与えられたnに対してT_k <= n < T_{k+1} を満たすkを返すプログラム | |
| # Babylonian method | |
| def isqrt(n) | |
| return 0 if n == 0 | |
| s, t = 1, n | |
| while s < t | |
| s *= 2 | |
| t /= 2 |