如何加速这个haskell lastDigits xy函数？

Question

我有一个haskell 赋值，其中我必须创建一个包含2 个参数的函数lastDigit xy 来计算所有[x^x | (0..x)]，我的太慢了，我需要加快速度。任何人有任何想法？

list  :: Integral x=>x->[x]
list 0 = []
list x = list(div x 10) ++ [(mod x 10)] 

sqrall :: Integer->[Integer]
sqrall x y = [mod (mod x 10^y)^x 10^y  | x <- [1..x]]

lastDigits :: Integer -> Int -> [Integer]
lastDigits x y = drop (length((list(sum (sqrall x y))))-y) (list(sum (sqrall x)))

Answer 1

这将花费太长时间的主要原因是因为您计算了 的全部数量x^x，这以超指数方式扩展。这意味着即使对于非常小的x，它仍然需要相当长的时间。

然而，关键是您不需要计算整个数字。实际上，您可以利用x×y mod n = (x mod n) × (y mod n) mod n的事实。例如 Haskell 的arithmoi包使用了这个[src]：

powMod :: (Integral a, Integral b) => a -> b -> a -> a
powMod x y m
  | m <= 0    = error "powModInt: non-positive modulo"
  | y <  0    = error "powModInt: negative exponent"
  | otherwise = f (x `rem` m) y 1 `mod` m
  where
    f _ 0 acc = acc
    f b e acc = f (b * b `rem` m) (e `quot` 2)
      (if odd e then (b * acc `rem` m) else acc)

我们可以为模 10 制作一个特定的版本：

pow10 :: Integral i => i -> i
pow10 x = go x x
    where go 0 _ = 1
          go i j | odd i = rec * j `mod` 10
                 | otherwise = rec
               where rec = go (div i 2) ((j*j) `mod` 10)

这然后匹配x^x `mod` 10，除了我们不需要计算整个数字：

Prelude> map pow10 [1 .. 20]
[1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9,0]
Prelude> [x^x `mod` 10 | x <- [1..20]]
[1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9,0]

现在我们有了这个，我们还可以计算最后两位数字的总和，整数范围最多为 18：

sum10 :: Int -> Int -> Int
sum10 x y = (x + y) `mod` 10

因此，我们可以计算最后一位数字：

import Data.List(foldl')

lastdigit :: Int -> Int
lastdigit x = foldl' sum10 0 (map pow10 [0 .. x])

例如对于x = 26，我们得到：

Prelude Data.List> lastdigit 26
4
Prelude Data.List> sum [ x^x | x <- [0 .. 26] ]
6246292385799360560872647730684286774

我把它作为一个练习来概括上面的内容来计算最后y位数字。只要y相对较小，这将是有效的，因为这样数字永远不会占用大量内存。此外，如果数字有上限，则加法、乘法等都是在恒定时间内完成的。但是Integer，如果您使用 an ，则数字可以是任意大的，因此加法之类的操作不是恒定的。