DouKaku? 4903 omoikani: SMLにも移植。爆速になったけど、MLt...(Meertens数)

Comment detail

This comment is reply for 4882 kozima: Haskell の勉強にと移植してみまし...(Meertens数). Go to thread root.

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

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) ()

面白くはないけど、これでちょっと速くなりました。

SBCL との差は……あまり自信ありませんが、loop の中でクロージャを作って呼び出すオーバーヘッドとか？

       end

       open Int
-      val lst = List.tabulate (10 - start, fn x => x + start)
+      val lst = if start = 0 then [0,1,2,3,4,5,6,7,8,9]
+                else [1,2,3,4,5,6,7,8,9]
     in
       app f lst
     end

独自のpowでさらに枝刈り。20桁での時間は約4時間までになりました。

--- 110.sml     2007-12-21 19:45:26.606130399 +0000
+++ 110-3.sml   2007-12-21 20:58:19.679130289 +0000
@@ -13,16 +13,30 @@
   fun loop _ [] _ prod sum _ =
     if prod = sum then print (toString sum ^ "\n") else ()
     | loop (p::ps) (b::bs) bound prod sum start = let
+      fun pow (x, y) = let
+        fun loop r 0 = 1
+          | loop r 1 = r
+          | loop r n = let
+              val z = r * x
+            in
+              if z <= bound then loop z (n - 1)
+              else bound + 1
+            end
+      in
+        loop x y
+      end
+
       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
+          loop ps bs (bound div pp) (prod * pp) (sum + b * x) 0
         else ()
       end

       open Int
-      val lst = List.tabulate (10 - start, fn x => x + start)
+      val lst = if start = 0 then [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+                else [1, 2, 3, 4, 5, 6, 7, 8, 9]
     in
       app f lst
     end

そっか、そこ刈れてなかったんですね。それなら f の繰り返しを再帰呼び出しにするとまだ速くなります。

--- 4926.sml    2007-12-22 15:37:01.000000000 +0900
+++ meertens.sml        2007-12-22 15:36:18.000000000 +0900
@@ -26,11 +26,12 @@
         loop x y
       end

-      fun f x = let
+      fun f [] = ()
+        | f (x::xs) = let
         val pp = pow (p, x)
       in
         if pp <= bound then
-          loop ps bs (bound div pp) (prod * pp) (sum + b * x) 0
+          (loop ps bs (bound div pp) (prod * pp) (sum + b * x) 0; f xs)
         else ()
       end

@@ -38,7 +39,7 @@
       val lst = if start = 0 then [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
                 else [1, 2, 3, 4, 5, 6, 7, 8, 9]
     in
-      app f lst
+      f lst
     end
 in
   app (fn i => loop p (basis i) (IntInf.pow (10, i)) 1 0 1) lst

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq