Legendre prime counting function: Difference between revisions

Content added Content deleted
(→‎{{header|Haskell}}: added solution)
(→‎{{header|Haskell}}: simplified memoization)
Line 360:
 
Memoization utilities:
<lang haskell>typedata Memo2Memo a = Node a (Memo a) (Memo a)
 
data Memo a = Node a (Memo a) (Memo a)
deriving Functor
 
Line 370 ⟶ 368:
| odd n = memo l (n `div` 2)
| otherwise = memo r (n `div` 2 - 1)
 
memo2 :: Integral a => Memo2 b -> a -> a -> b
memo2 f = memo . memo f
 
nats :: Integral a => Memo a
nats = Node 0 ((+1).(*2) <$> nats) ((*2).(+1) <$> nats)
 
memoize :: Integral a => (a -> b) -> Memoa -> b
memoize f = memo (f <$> nats)
 
memoize2 :: (Integral a, Integral b) => (a -> b -> c) -> Memo2a -> b -> c
memoize2 f = memoize (memoize . f)
 
memoList :: [b] -> MemoInteger -> b
memoList (x:xs) = Node x (memoList l)memo (memoList. r)mkList
where (l,r) = split xs
mkList (x:xs) = Node splitx [](mkList =l) ([],[]mkList r)
where (l,r) = split [x] = ([x],[])xs
split (x:y:xs) = let (l,r) = split xs[] in= (x:l[], y:r[])</lang>
split [x] = ([x],[])
split (x:y:xs) = let (l,r) = split xs in (x:l, y:r)</lang>
 
Computation of Legendre function:
Line 401 ⟶ 398:
else go z (r `shiftR` 1) (q `shiftR` 2)
 
phiMphi = memoize2 phiphiM▼
p :: Memo Integer
where
p = memoList (undefined : primes)▼
phiM x 0 = x
 
phi phiM x a = memo2 phiMphi x (a-1) - memo2 phiMphi (x `div` memo p a) (a - 1)▼
phi :: Integer -> Integer -> Integer
phi x 0 = x
▲ p = memoList (undefined : primes)
▲phi x a = memo2 phiM x (a-1) - memo2 phiM (x `div` memo p a) (a - 1)
 
phiM :: Memo2 Integer
▲phiM = memoize2 phi
 
legendrePi :: Integer -> Integer
legendrePi n
| n < 2 = 0
| otherwise = memo2 phiMphi n a + a - 1 where a = legendrePi (isqrt n)
where a = legendrePi (floor (sqrt (fromInteger n)))
 
main = mapM_ (\n -> putStrLn $ show n ++ "\t" ++ show (legendrePi (10^n))) [1..97]</lang>
 
<pre>λ> main
Retrieved from "https://rosettacode.org/wiki/Legendre_prime_counting_function"