DouKaku? 4926 omoikani: 独自のpowでさらに枝刈り。20桁での時...(Meertens数)

Comment detail

This comment is reply for 4921 kozima: 面白くはないけど、これでちょっと速くなり...(Meertens数). Go to thread root.

独自の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