0

我目前正在尝试在 Haskell 中实施 Atkin 筛

在关于阿特金筛子的维基百科文章的第3 步中，我需要找到多个方程的整数解的数量。

然而，我对这些方程中的第一个方程的解（4x² + y² = n, x > 0, y > 0 其中 n 是正整数列表中的一个条目）在使用任何 n 进行查询时会产生无限循环。

到目前为止，这是我解决这部分问题的代码：

eq1 :: Integer -> Integer
eq1 n = eq1_ n []
eq1_ :: Integer -> [(Integer, Integer)] -> Integer
eq1_ n list     | (x > 0) && (y > 0) && (n == 4*(x^2) + (y^2)) && (notElem ((x,y)) list) = eq1_ n ([(x, y)] ++ list)
                | otherwise = toInteger (length list)
                where
                    x = floor (sqrt (fromIntegral ((n - y^2) `div` 4)))
                    y = floor (sqrt (fromIntegral (n - 4*(x^2))))

它被 WinGHCi 加载得很好，但是当我查询时，eq1 0它只是停留在一个无限循环中，并且在产生答案之前必须被中断。我怀疑它在 和 的两个分配之间x循环y。

我怎样才能防止这种情况？这甚至可能吗？

编辑：意识到无限循环必须在哪里。

4

1 回答 1

1

我将首先重新格式化您的代码以使其更具可读性。换行很有帮助！此外，运算顺序可以减少括号的权重。边注：

f x | e1 && e2 && e3 = e4

也可以写

f x | e1
    , e2
    , e3
    = e4

这可能对眼睛更容易。

eq1 :: Integer -> Integer
eq1 n = eq1_ n []

eq1_ :: Integer -> [(Integer, Integer)] -> Integer
eq1_ n list
  | x > 0 &&
    y > 0 &&
    n == 4*x^2 + y^2 &&
    notElem (x,y) list
  = eq1_ n ([(x, y)] ++ list)
  | otherwise
  = toInteger (length list)
  where
    isqrt = floor . sqrt . fromIntegral
    x = isqrt $ (n - y^2) `div` 4
    y = isqrt $ n - 4*(x^2)

现在我可以立即看到逻辑是不可靠的。给定n，您计算x和y。然后你要么停止，要么递归地调用函数。但是，在递归调用中，您一定会停止！所以即使你是对的，你肯定会遇到语义问题，总是返回 0 或 1。

但正如您所见，这不是唯一的问题。您还x根据y和y定义x。现在有一些重要的情况，这种相互递归是有用的。但是当相互递归的值是像整数这样的“原子”事物时，你肯定会得到一个无限循环。Haskell 不会为你解方程；那是你的工作！

这是我的建议：

从蛮力列表理解解决方案开始：

sols n
  = [(x,y)
    |x <- takeWhile (\p -> 4 * p^2 < n) [1..]
    ,y <- takeWhile (\q -> f x y <= n) [1..]
    ,f x y = n]
  where
    f x y = 4*x^2+y^2

接下来，您可以使用近似整数平方根来缩小 的搜索空间y：

sols n
  = [(x,y)
    |x <- takeWhile (\p -> 4 * p^2 < n) [1..]
    ,y <- takeWhile
            (\q -> f x y <= n)
          [floor(sqrt(fromIntegral(n-4*x^2)))..]
    ,f x y = n]
  where
    f x y = 4*x^2+y^2
于 2019-02-28T21:01:27.627 回答