1

totients のリスト用にふるいベースのジェネレーターを作成し、合計を 1000000 にしたいと考えています。

applyEvery :: (a -> a) -> Int -> [a] -> [a]
applyEvery f n xs = xf ++ (\(y:ys) -> f y : applyEvery f n ys) xb
  where
    (xf, xb) = splitAt (n - 1) xs

totients :: [Int]
totients = 1 : sieve [2..] [2..]
  where 
    sieve (x:xs) (y:ys) 
        | x == y    = (y - 1) : sieve xs (propagatePrime x ys)  
        | otherwise = y : sieve xs ys
    propagatePrime j = applyEvery (\x -> (quot x j)*(j - 1)) j

totientSum :: Int -> Int
totientSum n = sum $ take n totients

totientSum n40000を超える計算をn行うと、ghci は評価に時間がかかり、膨大な量のメモリを消費し始めます。実行可能ファイルへのコンパイルは役に立ちません。これは、Haskell が遅延評価を処理する方法と関係があると思います。

上記の関数のメモリ消費を改善するために厳密性を選択的に適用して、最大 1000000 までの合計を計算できるかどうかを知りたいです。また、リストを使用してこれを行うより良い方法があるかどうかも知りたいです。ランダム アクセス データ構造を使用する必要がある場合。全合計を計算するためのより高速なアルゴリズムを知っている場合は、参考文献を共有してください。

の定義がapplyEvery違うのではないかと思い、以下の他の実装も試してみましたが、どちらも上記の定義よりも多くのメモリを消費しているようでした。

-- <https://www.reddit.com/2tpqip/>
applyEvery' :: (a -> a) -> Int -> [a] -> [a]
applyEvery' f n = zipWith ($) (cycle (replicate (n - 1) id ++ [f]))

applyEvery'' :: (a -> a) -> Int -> [a] -> [a]
applyEvery'' f n xs = xf ++ (\(y:ys) -> f y : applyEvery'' f n ys) xb
  where
    xf = take (n - 1) xs
    xb = drop (n - 1) xs
4

1 に答える 1

2

オイラー積の公式を実装する場合:

オイラー積公式

範囲内のすべての数値に対してオイラーファイ数値を計算しているという事実を利用できます[1..n]

そうすることで、最初に範囲内のすべての素数を見つけてから、各数値の素約数[1..n]を見つける代わりに、各素数のすべての倍数を見つけることができます。明らかに、後者の方がはるかに効率的に実行できます。

可能な実装は次のとおりです。

import Data.Int (Int64)
import Control.Applicative ((<$>))
import Data.Array.Unboxed (UArray, elems, accum, listArray)

primes :: Integral a => [a]
primes = 2: 3: filter pred (chain [5,11..] [7,13..])
    where
    chain (x:xs) (y:ys) = x: y: chain xs ys
    pred a = all (\i -> a `mod` i /= 0) $ takeWhile (\i -> i * i <= a) primes

euler_phi :: Int64 -> [Int64]
euler_phi n = elems $ accum (\a p -> a - a `div` p) arr inc
    where
    val = takeWhile (<= n) primes
    idx = map (\i -> takeWhile (<= n) [i,2 * i..]) val

    inc = concat $ zipWith (\i j -> ($j) <$> (,) <$> i) idx val
    arr = listArray (1, n) [1..n] :: UArray Int64 Int64

main = getLine >>= print . sum . euler_phi . read

それから：

\> euler_phi 20
[1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8]

最初の 20 個の数値のオイラー totient 関数になります。フラグを付けてコンパイルする-O2と、かなりまともなパフォーマンスで累積合計を計算できます。

$ ghc --make -O2 euler_phi.hs
[1 of 1] Compiling Main             ( euler_phi.hs, euler_phi.o )
Linking euler_phi ...

$ time echo 40000 | ./euler_phi
486345716

real    0m0.091s
user    0m0.040s
sys     0m0.006s
于 2016-02-08T22:46:59.420 に答える