Legendre prime counting function: Difference between revisions

Content added Content deleted

Inline

@@ Line 231: / Line 231: @@
 {{libheader|Go-rcu}}
 ===Memoized===
-This runs in about 2.2 seconds which is surprisingly slow for Go. However, Go has the same problem as Wren in not being able to use lists for map keys. I tried using a 2-element array for the key but this was a second slower than the Cantor function.
+This runs in about 1.9 seconds which is surprisingly slow for Go. However, Go has the same problem as Wren in not being able to use lists for map keys. I tried using a 2-element array for the key but this was a second slower than the Cantor function.
 The alternative of sieving a billion numbers and then counting them takes about 4.8 seconds using the present library function though this could be cut to 1.2 seconds using a third party library such as primegen.
@@ Line 242: / Line 242: @@
     "rcu"
 )
-var limit = int(math.Sqrt(1e9))
-var primes = rcu.Primes(limit)
-var memoPhi = make(map[int]int)
 func cantorPair(x, y int) int {
@@ Line 252: / Line 248: @@
     }
     return (x*x + 3*x + 2*x*y + y + y*y) / 2
-}
-func phi(x, a int) int {
-    if a == 0 {
-        return x
-    }
-    key := cantorPair(x, a)
-    if v, ok := memoPhi[key]; ok {
-        return v
-    }
-    pa := primes[a-1]
-    memoPhi[key] = phi(x, a-1) - phi(x/pa, a-1)
-    return memoPhi[key]
 }
@@ Line 271: / Line 254: @@
         return 0
     }
+    if n == 2 {
-    a := pi(int(math.Sqrt(float64(n))))
+        return 1
+    }
+    primes := rcu.Primes(int(math.Sqrt(float64(n))))
+    a := len(primes)
+    memoPhi := make(map[int]int)
+    var phi func(x, a int) int // recursive closure
+    phi = func(x, a int) int {
+        if a < 1 {
+            return x
+        }
+        if a == 1 {
+            return x - (x >> 1)
+        }
+        pa := primes[a-1]
+        if x <= pa {
+            return 1
+        }
+        key := cantorPair(x, a)
+        if v, ok := memoPhi[key]; ok {
+            return v
+        }
+        memoPhi[key] = phi(x, a-1) - phi(x/pa, a-1)
+        return memoPhi[key]
+    }
     return phi(n, a) + a - 1
 }