Meertens数
Posted feedbacks - StandardML
omoikani
#4866()
[
StandardML
]
MLtonでコンパイルして、符号無し32bit整数までで約2時間40分。64bitでは834174年。遅すぎですね。 mlton meertes.sml ./meertes 4294967295
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | fun goedel n = let
open IntInf
val p = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71
]
val a = map (valOf o Int.fromString o str) ((explode o toString) n)
in
ListPair.foldl (fn (x, y, z) => pow (x, y) * z) 1 (p, a)
end
fun meertens n = let
fun loop i =
if i > n then ()
else
if goedel n = n then (print (IntInf.toString n ^ "\n"); loop (i + 1))
else loop (i + 1)
in
loop 0
end
val _ = (meertens o valOf o IntInf.fromString o hd o CommandLine.arguments) ()
|
omoikani
#4903()
[
StandardML
]
SMLにも移植。爆速になったけど、MLtonでもSBCLより遅い。。。 10桁で0.79秒、20桁で9時間56分。 ./110 10 0.79s user 0.00s system 99% cpu 0.795 total ./110 20 35746.36s user 4.25s system 99% cpu 9:56:05.18 total
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | val p = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71
] : IntInf.int list
fun basis n = (rev o map (fn x => IntInf.pow (10, x)) o List.tabulate) (n, fn x => x)
fun meertens n = let
val lst = List.tabulate (n, fn x => x + 1)
open IntInf
fun loop _ [] _ prod sum _ =
if prod = sum then print (toString sum ^ "\n") else ()
| loop (p::ps) (b::bs) bound prod sum start = let
fun f x = let
val pp = pow (p, x)
in
if pp <= bound then
loop ps bs (bound div pp) (prod * pp) (sum + b * fromInt x) 0
else ()
end
open Int
val lst = List.tabulate (10 - start, fn x => x + start)
in
app f lst
end
in
app (fn i => loop p (basis i) (IntInf.pow (10, i)) 1 0 1) lst
end
val _ = (meertens o valOf o Int.fromString o hd o CommandLine.arguments) ()
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]