このたび、笹川さんが電子書籍「まったく初めての人のためのISLisp」を出版されました。ご出版、おめでとうございます。先日、笹川さんからご著書を献本して頂きました。本当にありがとうございました。本書は Lisp のエッセンスがギュッと詰まっていて、最後まで楽しく読むことができました。二次方程式の解や行列の計算など、数学を題材にしているところもよかったです。やっぱり Lisp プログラミングは面白いな、と改めて思いました。
今まで使っていたパソコン (Windows 7, 32 bit) が壊れたので、新しいパソコン (Windows 10, 64 bit) を買いました。CPU は CORE i5 (2.3 GHz) ですが、メモリを 8 G byte 搭載したのでパソコンの動作は快適です。特に、パソコンの起動やシャットダウンが Windows 7 よりも格段に速くなったのには驚きました。
せっかくメモリをたくさん搭載したので、VirtualBox のメモリを 2 G byte に設定して、いろいろな Linux を試してみました。この場合、ライブCDの部屋 のライブイメージを使うと簡単です。作者様に深く感謝いたします。たいていの Linux は動作するのですが、重量級のデスクトップを VirtulaBox で動かすには、CPU のパワーがちょっと足りないようです。そこで、今回は xubuntu をインストールすることにしました。
ご参考までに「たらいまわし関数」の実行結果を下表に示します。
処理系 | 秒 |
---|---|
Python (ver 2.7.12+) | 71.0 |
Ruby (ver 2.3.1p112) | 29.4 |
Gauche (ver 0.9.4) | 22.9 |
ocamlc (ver 4.02.3) | 16.6 |
SBCL (ver 1.3.3) | 5.20 |
JavaScript (Node.js v4.2.6) | 3.17 |
SML/NJ (ver 110.79) | 3.14 |
Julia (ver 0.4.7) | 2.06 |
Go (ver 1.6.3) | 1.97 |
SBCL (最適化) | 1.67 |
C# (Mono, ver 4.2.1.0) | 1.63 |
GCC -O2 (ver 6.2.0) | 1.40 |
Clang -O2 (ver 3.8.1) | 1.20 |
Rust -O (ver 1.18) | 1.20 |
ocamlopt (ver 4.02.3) | 1.11 |
ホスト OS との比較は GCC と Rust しか試していませんが、ほぼ同じ実行結果になりました。VirtualBox は本当に凄いなあ、と改めて実感しました。Rust は Mozilla が開発しているプログラミング言語で、最近 M.Hiroi が関心を持っている言語のひとつです。Windows, MacOS, Linux で動作するので、興味のある方は調べてみてください。
さて、最近は JavaScript や TypeScript を勉強しているのですが、そこで役に立っているのが Visual Studio Code (VSCode) というエディタです。
Microsoft 社が開発しているオープンソースのエディタで、Windows だけではなく MacOS や Linux でも動作します。高機能なエディタなのですが、デフォルトのままでも便利に使うことができます。TypeScript の場合、プログラムを打ち込むたびに構文をチェックしてくれるので、勉強がとてもはかどりました。xyzzy や Emacs もいいのですが、しばらくは VSCode を使ってみようかなと思っています。
自然数 n 以上 m 未満の区間にある素数を求めることを考えます。この場合、sqrt(m) 以下の素数表があれば、「エラトステネスの篩」で高速に求めることができます。参考 URL 1 によると、これを「区間ふるい」と呼ぶそうです。
一般に、エラトステネスの篩は配列を使った方が高速に動作しますが、ここではリストを使って簡単にプログラムを作ることにします。まあ、区間の幅が大きくなければ、リストでもそこそこに動作します。Gauche (Scheme) でプログラムを作ると次のようになります。
リスト : 区間ふるい (use srfi-1) (use math.prime) ;; 反転して連結する (define (reverse-append xs ys) (let loop ((xs xs) (ys ys)) (if (null? xs) ys (loop (cdr xs) (cons (car xs) ys))))) ;; 素数表の生成 (define (first-sieve n) (let loop ((xs (iota (- n 2) 2)) (ps '())) (if (> (* (car xs) (car xs)) n) (reverse-append ps xs) (loop (remove (lambda (x) (zero? (mod x (car xs)))) (cdr xs)) (cons (car xs) ps))))) ;; 素数表 (define prime-list (first-sieve 65536)) ;; 区間ふるい (define (segment-sieve low high) (let loop ((xs (iota (- high low) low)) (ps prime-list)) (if (>= (* (car ps) (car ps)) high) xs (loop (remove (lambda (x) (and (zero? (mod x (car ps))) (not (= x (car ps))))) xs) (cdr ps))))) (define (segment-sieve1 low high) (let loop ((xs (iota (- high low) low)) (ps *primes*)) (if (>= (* (car ps) (car ps)) high) xs (loop (remove (lambda (x) (and (zero? (mod x (car ps))) (not (= x (car ps))))) xs) (cdr ps)))))
関数 first-sieve は 2 以上 n 未満の素数表を作ります。たとえば、65536 までの素数表を作れば、符号付き 32 bit 整数の範囲であれば、区間ふるいを実行することができます。関数 segment-prime は low 以上 high 未満の素数を区間ふるいで求めます。区間と素数表が重なる場合があるので、remove で要素を削除するとき、要素 x が素数で割り切れるだけではなく、x が素数自身ではないことを確認しています。segment-sieve1 は Gauche の素数列 (無限リスト) を使ったバージョンです。
簡単な実行例を示します。
gosh> (segment-sieve 2 100) (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) gosh> (segment-sieve #x7fffff00 #x7fffffff) (2147483399 2147483423 2147483477 2147483489 2147483497 2147483543 2147483549 2147483563 2147483579 2147483587 2147483629) gosh> (segment-sieve1 2 100) (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) gosh> (segment-sieve1 #x80000000 #x80000100) (2147483659 2147483693 2147483713 2147483743 2147483777 2147483783 2147483813 2147483857 2147483867 2147483869 2147483887 2147483893)
最後の例のように、segment-sieve1 は符号付き 32 bit 整数の上限値 (2147483647) を超えても区間ふるいを実行することができます。
1 月 1 日に出題したパズルの 解答 です。
29 と 2017 は素数なので、それに関する問題を考えてみました。
Ruby (ruby 2.3) には素数を扱うライブラリ prime と遅延評価を行う Enumerator::Lazy があるので簡単に答えを求めることができます。
irb> require 'prime' => true irb> Prime.each.take_while {|x| x <= 2017}.length => 306 irb> Prime.each.take(2017)[-1] => 17539 irb> def digitSum(x) irb> a = 0 irb> while x > 0 irb> a += x % 10 irb> x /= 10 irb> end irb> a irb>end => :digitSum irb> Prime.each.take_while{|x| x <= 5000}.select{|x| digitSum(x) == 10} => [19, 37, 73, 109, 127, 163, 181, 271, 307, 433, 523, 541, 613, 631, 811, 1009, 1063, 1117, 1153, 1171, 1423, 1531, 1621, 1801, 2017, 2053, 2143, 2161, 2251, 2341, 2503, 2521, 3061, 3313, 3331, 3511, 4051, 4231] irb> Prime.each.take_while{|x| x <= 10000}.select{|x| digitSum(x) == 29} => [2999, 3989, 4799, 4889, 5879, 5897, 5987, 6599, 6689, 6779, 6869, 6959, 6977, 7499, 7589, 7877, 7949, 8597, 8669, 8849, 8867, 9479, 9497, 9587, 9677, 9749, 9767, 9839, 9857, 9929] irb> Prime.each.each_cons(2).lazy.select{|p, r| r - p == 2}.take(2017).force[-1] => [183509, 183511]
Gauche (version 0.9.4) にも素数を扱うライブラリ math.prime と遅延リストを扱う gauche.lazy があるので簡単に答えを求めることができます。
gosh> (use math.prime) #<undef> gosh> (use srfi-1) #<undef> gosh> (use gauche.lazy) #<undef> gosh> (length (take-while (lambda (x) (<= x 2017)) (primes))) 306 gosh> (list-ref (primes) (- 2017 1)) 17539 gosh> (define (digit-sum n) (let loop ((n n) (a 0)) (if (zero? n) a (loop (quotient n 10) (+ a (mod n 10)))))) digit-sum gosh> (filter (lambda (x) (= (digit-sum x) 10)) (take-while (lambda (x) (<= x 5000)) (primes))) (19 37 73 109 127 163 181 271 307 433 523 541 613 631 811 1009 1063 1117 1153 1171 1423 1531 1621 1801 2017 2053 2143 2161 2251 2341 2503 2521 3061 3313 3331 3511 4051 4231) gosh> (filter (lambda (x) (= (digit-sum x) 29)) (take-while (lambda (x) (<= x 10000)) (primes))) (2999 3989 4799 4889 5879 5897 5987 6599 6689 6779 6869 6959 6977 7499 7589 7877 7949 8597 8669 8849 8867 9479 9497 9587 9677 9749 9767 9839 9857 9929) gosh> (define pair-primes (lmap (lambda (a b) (cons a b)) (primes) (drop (primes) 1))) pair-primes gosh> (list-ref (lfilter (lambda (x) (= (- (cdr x) (car x)) 2)) pair-primes) (- 2017 1)) (183509 . 183511)
拙作のページ お気楽 Haskell プログラミング入門 の 遅延評価 で作成した「素数列の生成」を使って解を求めました。
リスト : 素数列の生成 (primes.hs) checkPrime :: Integer -> Bool checkPrime n = all (\x -> mod n x /= 0) (takeWhile (\x -> x * x <= n) primes) primesFrom :: Integer -> [Integer] primesFrom n | checkPrime n = n : primesFrom (n + 2) | otherwise = primesFrom (n + 2) primes = 2 : 3 : 5 : primesFrom 7 splitDigit :: Integer -> [Integer] splitDigit 0 = [] splitDigit n = n `mod` 10 : splitDigit(n `div` 10) digitSum :: Integer -> Integer digitSum n = sum (splitDigit n)
Prelude> :l primes.hs [1 of 1] Compiling Main ( primes.hs, interpreted ) Ok, modules loaded: Main. *Main> length (takeWhile (\x -> x <= 2017) primes) 306 *Main> primes !! (2017 - 1) 17539 *Main> filter (\x -> digitSum x == 10) (takeWhile (\x -> x <= 5000) primes) [19,37,73,109,127,163,181,271,307,433,523,541,613,631,811,1009,1063,1117,1153, 1171,1423,1531,1621,1801,2017,2053,2143,2161,2251,2341,2503,2521,3061,3313,3331, 3511,4051,4231] *Main> filter (\x -> digitSum x == 29) (takeWhile (\x -> x <= 10000) primes) [2999,3989,4799,4889,5879,5897,5987,6599,6689,6779,6869,6959,6977,7499,7589,7877, 7949,8597,8669,8849,8867,9479,9497,9587,9677,9749,9767,9839,9857,9929] *Main> (filter (\(a, b) -> b - a == 2) (zip primes (tail primes))) !! (2017 - 1) (183509,183511)
なお、Haskell には素数を扱うライブラリ Data.Numbers.Primes があるので、それをインストールすると高速に処理することができます。ライブラリは次のコマンドで簡単にインストールすることができます。
cabal install primes
Prelude> import Data.Numbers.Primes Prelude Data.Numbers.Primes> let {splitDigit 0 = []; splitDigit n = n `mod` 10 : splitDigit(n `div` 10)} Prelude Data.Numbers.Primes> let digitSum n = sum (splitDigit n) Prelude Data.Numbers.Primes> length (takeWhile (\x -> x <= 2017) primes) 306 Prelude Data.Numbers.Primes> primes !! (2017 - 1) 17539 Prelude Data.Numbers.Primes> filter (\x -> digitSum x == 10) (takeWhile (\x -> x <= 5000) primes) [19,37,73,109,127,163,181,271,307,433,523,541,613,631,811,1009,1063,1117,1153, 1171,1423,1531,1621,1801,2017,2053,2143,2161,2251,2341,2503,2521,3061,3313,3331, 3511,4051,4231] Prelude Data.Numbers.Primes> filter (\x -> digitSum x == 29) (takeWhile (\x -> x <= 10000) primes) [2999,3989,4799,4889,5879,5897,5987,6599,6689,6779,6869,6959,6977,7499,7589,7877, 7949,8597,8669,8849,8867,9479,9497,9587,9677,9749,9767,9839,9857,9929] Prelude Data.Numbers.Primes> (filter (\(a, b) -> b - a == 2) (zip primes (tail primes))) !! (2017 - 1) (183509,183511)
拙作のページ 続・お気楽 Java プログラミング入門 で作成した immutable な遅延ストリーム を使ったプログラムです。
リスト : 「素数で遊ぼう」の解答 import immutable.*; import static immutable.LazyStream.*; public class primeproblem { // 素数列 static LazyStream<Integer> primes = cons(2, () -> cons(3, () -> cons(5, () -> primesFrom(7)))); static int nextPrime(int n) { while (true) { LazyStream<Integer> ps = primes; while (true) { int p = ps.first(); if (p * p > n) return n; if (n % p == 0) break; ps = ps.rest(); } n += 2; } } static LazyStream<Integer> primesFrom(int n) { int p = nextPrime(n); return cons(p, () -> primesFrom(p + 2)); } static int digitSum(int n) { int a = 0; while (n > 0) { a += n % 10; n /= 10; } return a; } public static void main(String[] args) { System.out.println("----- Q01 -----"); System.out.println(primes.takeWhile(x -> x <= 2017).size()); System.out.println("----- Q02 -----"); System.out.println(primes.get(2017 - 1)); System.out.println("----- Q03 -----"); System.out.println(primes.filter(x -> digitSum(x) == 10).takeWhile(x -> x < 5000)); System.out.println("----- Q04 -----"); System.out.println(primes.filter(x -> digitSum(x) == 29).takeWhile(x -> x < 10000)); System.out.println("----- Q05 -----"); LazyStream<Pair<Integer, Integer>> twin = LazyStream.zipWith((x, y) -> Pair.pair(x, y), primes, primes.rest()).filter(p -> p.getSnd() - p.getFst() == 2); System.out.println(twin.get(2017 - 1)); } }
C>java primeproblem ----- Q01 ----- 306 ----- Q02 ----- 17539 ----- Q03 ----- [19, 37, 73, 109, 127, 163, 181, 271, 307, 433, 523, 541, 613, 631, 811, 1009, 1063, 1117, 1153, 1171, 1423, 1531, 1621, 1801, 2017, 2053, 2143, 2161, 2251, 2341, 2503, 2521, 3061, 3313, 3331, 3511, 4051, 4231] ----- Q04 ----- [2999, 3989, 4799, 4889, 5879, 5897, 5987, 6599, 6689, 6779, 6869, 6959, 6977, 7499, 7589, 7877, 7949, 8597, 8669, 8849, 8867, 9479, 9497, 9587, 9677, 9749, 9767, 9839, 9857, 9929] ----- Q05 ----- (183509, 183511)