参照記事：
99 Haskell Problems より、[31] でもその前に
Haskellで素数 2 自分でもやってみた。
Pythonで素数 2 Pythonでやってみた。 この記事はこれの改良版です。 改良になってなかった。Python版と同じに戻しました。
Javascript: スプレッド構文とジェネレーターを使ってtransducerっぽいことをする ジェネレーター関連のこと。 本題からずれて無駄に難しくなるので、関数合成関連のコードは削除しました。
Haskell界隈でやられている方法を以前教えていただいたので、JavaScriptでどうできるか、やってみました。
理屈はめんどくさいですが、何かと効率がいいようです。
letとかwhileとか使いまくりで、何が関数型か?思いっきり手続き型じゃない?という感じですが、Haskellの遅延評価を使ったクールなコードを、何とかJavaScriptのジェネレーターで実現しようとした爪痕です。
暖かい眼で見てやってください。
//最大公約数。
const gcd = x => y => y === 0 ? x : gcd( y )( x % y )
// 配列をジェネレーターにする。
const arrayToG = xs => function*(){
yield* xs;
}();
//ジェネレーターg1にg2を継ぎ足したジェネレーターを返す。
const chain = g1 => g2 =>function*(){
yield* g1;
yield* g2;
}();
// sに 6*n+1 型の自然数、pに素数をとって、
// s から p*p-2 までの2と3の倍数を除いた素数の候補を返すジェネレーター。
const croppedPrimables = s => p => function*(){
let x = s;
while(x <= p * p - 2 ){
yield x;
yield x = x + 4;
x = x + 2;
}
}();
// m に 2,3 以外の p 未満の素数を全てかけた数、
// sに 6*n+1 型の自然数、pに素数をとって、
//s から p*p-2 までの素数を返すジェネレーター。
const zonedPrimes = m => s => p => function*(){
const nG = croppedPrimables(s)(p);
let x;
while(!( x = nG.next()).done ){
if(gcd(m)(x.value) === 1)yield x.value;
}
}();
//素数を返すジェネレーター。
const primes = () => function*(){
let x;
let primeG = arrayToG([2, 3, 5]);
let [m, s, p] = [1, 7, 5];
let seedG = arrayToG([]);
while(true){
while( !( x = primeG.next() ).done ) yield x.value;
primeG = zonedPrimes(m)(s)(p);
seedG = chain(seedG)(zonedPrimes(m)(s)(p));
[m, s, p] = [ m * p , p * p , seedG.next().value ];
}
}();
//100以下の素数を表示する。
{
const primesGen = primes();
let x;
while((x = primesGen.next()).value <= 100) console.log(x.value);
}
//=>結果
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
仕組み
ジェネレーター croppedPrimable は：
- 引数sに6n+1型の整数をとることで
- p^2-2 までの2と3の倍数を除いた素数候補を、
- 呼ばれるたびに一個ずつ返します。
なんでわざわざこんなことを?とも思うのですが、次の素数を選別する処理が重くてロスが大きいので、なるべく候補を絞って効率良く、ということなのでしょうたぶん。
ジェネレーター zonedPrimes は：
- croppedPrimables(s)(p)から一個ずつ値をとり
- mとの最大公約数が1になる値を一個ずつ返します。
mには、最初は1、その後、2,3を除いたp未満の素数(5,7,11...)を全てかけた数がはいります。
ジェネレーターprimesは呼ばれるたびに素数を一個ずつ返します。
内部にふたつのジェネレーターがあります。
- primeG(初期値[2,3,5]):外部に素数を返す用
- seedG(初期値[]):内部でprimeG の再充填に使う p を供給する用
ふたつとも素数を返すジェネレーターに違いはありませんが、値を消費する速度がだいぶ違います。
このふたつを使ってhaskellの遅延評価の部分をなんとか実現しようとしています。
- primeGが素数を一個ずつ返し、
- primeGが空になったら、zonedPrimes(m)(s)(p)でprimeGを再充填する
- seedGの後ろにzonedPrimes(m)(s)(p)を継ぎ足す。
- primeGの再充填のためのパラメータ m, s, p を再設定する
という流れです。
いい考えだと思ったんだけど...
だめでした。2207以下だったらいいんだけど、それ以降になるとおかしくなってしまう...
残念! この方法では2207までしか計算できない...
教えていただいたHaskellのコード(ちょっとだけ簡単にしてある)で2207の次の素数を求めてみました。
primes::Integral a => [a]
primes = [2, 3] ++ primes'
where
primes' = [5] ++ f 1 7 primes'
f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
main = print . take 1 . dropWhile(<=2207) $ primes
-- 結果：
[2213] -- 正しい
上で作ったJavaScriptのジェネレーターprimesを使って、同様に2207の次の素数を求めてみました。
{
const primesGen = primes();
let x;
while( (x = primesGen.next().value)<=2207);
console.log(x);
}
=>2209 // = 47*47 正しくない
理由は、gcdを計算するための m が 素数を順にかけていく内にどんどん大きくなってNumber.MAX_SAFE_INTEGERを越えてしまうからでした。
Number.MAX_SAFE_INTEGER
=> 9007199254740991
5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43
// Haskell:
=> 2180460221945005 // 正しい
// JavaScript:
=> 2180460221945005 // Number.MAX_SAFE_INTEGER以下。 正しい
5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47
// Haskell:
=> 102481630431415235 // 正しい
// JavaScript:
=> 102481630431415230 // Number.MAX_SAFE_INTEGERを超えている。正しくない
なんとか解決する方法を考えてみました。
JavaScriptで素数 2