回答編集履歴

別解3を追加

2017/02/04 13:06

投稿

raccy

スコア21737

test CHANGED Viewed

@@ -209,3 +209,29 @@
 ```
+---
+【別解3】
+-1は奇数乗か偶数乗かだけで切り替わることに気付いた。
+```JavaScript
+let val = (x => ((-1)**x * ((x - x % 2) / 2 + 1)))(Math.floor(6 * Math.random()));
+```
+IE等の古いブラウザ用に書き直すと
+```JavaScript
+var val = function (x) {return Math.pow(-1, x) * ((x - x % 2) / 2 + 1);}(Math.floor(6 * Math.random()));
+```

説明がちょっとおかしかったのを修正

2017/02/04 13:06

投稿

raccy

スコア21737

test CHANGED Viewed

@@ -190,7 +190,7 @@
 ```
-これに最初の2nを掛けて床関数をとって2足すをMath.random()にしたものを与えるようにする。
+これに最初の2nを掛けて床関数で整数化したものを与えると[0,1)を均等に配分できる。
 ```JavaScript

別解2が整数の最大値を超える場合がるため、修正。

2017/02/04 12:52

投稿

raccy

スコア21737

test CHANGED Viewed

@@ -2,7 +2,7 @@
 1. 乱数生成は1度のみ行う。
-2. 任意の整数`n`に対して、`-n`, `-n+1`, ... `-2`, `-1`, `1`, `2`, ... `n-1`, `n`の計n*2個の整数の内一つを返す。ランダム性は1.で生成した乱数を用いること。ただし、`n`は`1`以上`2**52-1`以下とする。(`2**52`以上の場合は`2*n`が`Number.MAX_SEFE_INTEGER`を越えるため)
+2. 任意の整数`n`に対して、`-n`, `-n+1`, ... `-2`, `-1`, `1`, `2`, ... `n-1`, `n`の計n*2個の整数の内一つを返す。ランダム性は1.で生成した乱数を用いること。ただし、`n`は`1`以上`2**52-1`以下とする。(`2**52`以上の場合は`2*n`が`Number.MAX_SAFE_INTEGER`を越えるため)
@@ -118,15 +118,19 @@
 【別解2】
+※ 途中の演算で`Math.MAX_SAFE_INTEGER`を越える場合があるため修正。
 Math.floorを一回だけにする方法を考える。他にも演算はなるべく1回とする。
-2n倍したものにfloorをとり、2を足せば2, 3, ... 2n, 2n+1になる。
+2n倍したものにfloorをとると0, 1, ... 2n-2, 2n-1になる。
 これを2を除数とした商と剰余を考えると、下記になる。
-商: 1, 1, 2, 2, ... 2n-1, 2n-1, 2n, 2n
+商: 0, 0, 1, 1, ... 2n-2, 2n-2, 2n-1, 2n-1
 剰余: 0, 1, 0, 1, ... 0, 1, 0, 1
@@ -134,7 +138,7 @@
 剰余: 0, 1, 0, 1, ... 0, 1, 0, 1 => 1, -1, 1, -1 ... 1, -1, 1, -1
-が得られるため、後は商と掛ければ、
+が得られるため、後は商に1足した物と掛ければ、
 1, -1, 2, -2, ... 2n-1, -2n+1, 2n, -2n
@@ -148,7 +152,7 @@
 // q 商、r 剰余
-const g = r => q => (-1)**r * q;
+const g = r => q => (-1)**r * (q + 1);
 ```
@@ -174,15 +178,15 @@
 // 関数を展開する。
-const f = x => (r_ => (r => q => (-1)**r * q)(r)((d => m => r => (d - r) / m)(x)(2)(r_)))(x % 2);
+const f = x => (r_ => (r => q => (-1)**r * (q + 1))(r)((d => m => r => (d - r) / m)(x)(2)(r_)))(x % 2);
 // rはr_と同じ、xとdは同じであり、mは2固定で冗長のためまとめる。
-const f = x => (r => (q => (-1)**r * q)((m => (x - r) / 2)()))(x % 2);
+const f = x => (r => (q => (-1)**r * (q + 1))((m => (x - r) / 2)()))(x % 2);
 // 固定の所は評価をしてしまって。qもなくす。
-const f = x => (r => (x - r) / 2 * (-1)**r)(x % 2);
+const f = x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2);
 ```
@@ -190,7 +194,7 @@
 ```JavaScript
-const f_ = n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2);
+const f_ = n => y => (x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2))(Math.floor(2 * n * y));
 ```
@@ -200,8 +204,8 @@
 ```JavaScript
-let val = (n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2))(3)(Math.random());
+let val = (n => y => (x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2))(Math.floor(2 * n * y)))(3)(Math.random());
-```
+```

別解2を追加

2017/02/04 04:37

投稿

raccy

スコア21737

test CHANGED Viewed

@@ -111,3 +111,97 @@
 ```
 となる。
+---
+【別解2】
+Math.floorを一回だけにする方法を考える。他にも演算はなるべく1回とする。
+2n倍したものにfloorをとり、2を足せば2, 3, ... 2n, 2n+1になる。
+これを2を除数とした商と剰余を考えると、下記になる。
+商: 1, 1, 2, 2, ... 2n-1, 2n-1, 2n, 2n
+剰余: 0, 1, 0, 1, ... 0, 1, 0, 1
+つまり、剰余部分は-1を底にしてその値を冪指数にした冪を求めれば
+剰余: 0, 1, 0, 1, ... 0, 1, 0, 1 => 1, -1, 1, -1 ... 1, -1, 1, -1
+が得られるため、後は商と掛ければ、
+1, -1, 2, -2, ... 2n-1, -2n+1, 2n, -2n
+が得られる。
+JavaScriptにすると次のような関数になる。
+```JavaScript
+// q 商、r 剰余
+const g = r => q => (-1)**r * q;
+```
+JavaScriptには商を直接求める演算子や関数がないため剰余から求める関数を考える。
+```JavaScript
+// d 被除数、m 除数
+const h = d => m => r => (d - r) / m;
+```
+除数は2で固定であるため、これを用いると次のようになり、展開しながら変形していく。
+```JavaScript
+const f = x => g(x % 2)(h(x)(2)(x % 2));
+// `x % 2`は冗長のためさらに書き替える。
+const f = x => (r => g(r)(h(x)(2)(r)))(x % 2);
+// 関数を展開する。
+const f = x => (r_ => (r => q => (-1)**r * q)(r)((d => m => r => (d - r) / m)(x)(2)(r_)))(x % 2);
+// rはr_と同じ、xとdは同じであり、mは2固定で冗長のためまとめる。
+const f = x => (r => (q => (-1)**r * q)((m => (x - r) / 2)()))(x % 2);
+// 固定の所は評価をしてしまって。qもなくす。
+const f = x => (r => (x - r) / 2 * (-1)**r)(x % 2);
+```
+これに最初の2nを掛けて床関数をとって2足すをMath.random()にしたものを与えるようにする。
+```JavaScript
+const f_ = n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2);
+```
+n=3のときのため、最終的に次のようになる。
+```JavaScript
+let val = (n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2))(3)(Math.random());
+```

別解を追加

2017/02/04 00:01

投稿

raccy

スコア21737

test CHANGED Viewed

@@ -56,4 +56,58 @@
-数学っぽく考えたつもりですが、`Math.random()`がまったく数学っぽくない時点でなんとも言えないです。
+数学っぽく考えたつもりですが、`Math.random()`に副作用があるのでまったく数学っぽくない時点でなんとも言えないです。
+---
+【別解】
+[0,1) => -n, -n+1, ... -2, -1, 1, 2, ... n-1, n
+となる写像関数を直接考える。
+1. 2倍すれば[0,2)となるため、[0,1), [1,2)に分離でき、floorをとれば0, 1になる。
+2. -1を底、1.の値を冪指数とする冪を求めると、1, -1になる。
+3. 2n倍すれば[0,2n)となるため、[0,1), [1,2), ... [n-1, n), [n, n+1), ... [2n-2,2n-1), [2n-1,2n)に分離でき、floorをとれば0, 1, ... n-1, n, ... 2n-2, 2n-1となる。
+このうちの前半は1.の0(2.の1)に、後半は1.の1(2.の-1)に相当する。
+4. さらにnでの余りを求めると0, 1, ... n-1, 0, ... n-2, n-1と前半と後半が同じである。
+5. さらに1足せば1, 2, ... n, 1, ... n-1, nとなる。
+6. 2.と5.を組み合わせれば、目的の写像が得られる。
+f(n)(x) = (-1)^[2x]*([2nx]%n+1)
+※ fはカリー化されている。^ ... 冪乗。[z] ... ガウス記号、床関数。% ... 剰余。
+これをJavaScriptで表すと下記になる。
+```JavaScript
+const f = n => x => (-1)**Math.floor(2 * x) * (Math.floor(2 * n * x) % n + 1)
+```
+写像関数が得られたので、n=3の時にxが[0,1)分布の乱数を与えることで答えは
+```JavaScript
+let v = (n => x => (-1)**Math.floor(2 * x) * (Math.floor(2 * n * x) % n + 1))(3)(Math.random());
+```
+となる。