日曜プログラミング

休日趣味でやってるプログラミング関連記事をダラダラと

Project Euler 向け(?)ユーティリティ関数とか

Project Euler を解いて行くに当たって多分探せばどっかに転がっていそうだけど(math-numerictowerとか)何となく自作したもの。今日ググってたら同じようなの見つけて何とも言えない微妙な気持ちになって晒してみたくなりました。

自作分

(defn lcm [& nums]
  " n 個以上の nums の最小公倍数を求める"
  (letfn [(gcd-2 [m n] (if (zero? n) m (recur n (mod m n))))
          (lcm-2 [m n] (/ (* m n) (gcd-2 m n)))]
    (reduce lcm-2 (sort > nums))))

(defn digit-seq [n]
  "数値 n を各数値の桁に分解したシーケンスで返す"
  (letfn [(digits-1 [n]
            (when-not (zero? n)
              (cons (mod n 10) (digits-1 (quot n 10)))))]
    (reverse (digits-1 n))))

(defn expt [base power]
  "べき乗を求める。インターフェースは Common Lisp 由来(多分)"
  (reduce * (repeat power base)))

(defn range1
  "1 or start から end までのシーケンスを返す"
  ([end] (range 1 (inc end)))
  ([start end] (range start (inc end))))

車輪の再発明とかライブラリ化すればとかライブラリ利用すればと言うには確かに規模が小さすぎるコードなんだけど同じようなの見ちゃうと、ね。digit-seq なんかは lazy-seq 化しておいた方がいいけどそれはまた必要になった時に。

最後のは n <= 100 までとか 2 <= n <= 20 までとか問題でよく見るので地味に使ってたりする。けど多分 Project Euler 限定だろうなあ。

clojure.lang.BigInt について

「プログラミング Clojure」情報古くなったなー、と言おうと思ったら

プログラミングClojure 第2版

プログラミングClojure 第2版

出てるじゃないですか。バージョンも 1.3 対応かー。
アマゾンで衝動的にポチっちゃったけど届くの割と先だなあ。もう通読はしないだろうけど手元に1冊は持っておきたいんだよね。Gauche 見るといつの間にか Github に移って shiro さんも地道に更新してるみたいだなあ。

と言うヨタ話はさておき、多分 1.3 から?追加されたのか clojure.lang.BigInt ってのはなんじゃらほいと言うのが気になったのでちょっと調べてみた。

user> (type 1)
java.lang.Long
user> (type 1L) ; Java での Long リテラル表記
NumberFormatException Invalid number: 1L  clojure.lang.LispReader.readNumber (LispReader.java:258)
RuntimeException Unmatched delimiter: )  clojure.lang.Util.runtimeException (Util.java:219)
user> Long/MAX_VALUE
9223372036854775807
user> (type 9223372036854775807)
java.lang.Long
user> (type 9223372036854775808)
clojure.lang.BigInt
user> (type 1N)
clojure.lang.BigInt

user> (.nextProbablePrime 9223372036854775808)
IllegalArgumentException No matching field found: nextProbablePrime for class clojure.lang.BigInt  clojure.lang.Reflector.getInstanceField (Reflector.java:271)
user> (.nextProbablePrime (biginteger 9223372036854775808))
9223372036854775837
user> (defn nextprime [n] (->> (biginteger n) (.nextProbablePrime) bigint))
#'user/nextprime

user> (nextprime 9223372036854775808)
9223372036854775837N
user> (type (nextprime 9223372036854775808))
clojure.lang.BigInt

うん、つまりは java.math.BigInteger に素数判定するメソッドがあるからそのまま使えるのか試してみたかっただけ。最初はエラストテネスの篩とか使って自前で素数の並びとか作ってたりしてたんだが StackOverFlow 出たりで文字通り頭が StackOverFlow しだして面倒になってきちゃって。同名サイトでも似たような人はいるみたいで java.math.BigInteger に素数判定メソッドが存在している事もそこで知った。

ただまあ素数判定アルゴリズム改善の話自体は結構面白そうな所ではあるんで今後もちょいちょいつまみ食いはしてみたいかな。