Haskell: Как найти число целочисленных решений уравнения для использования в Sieve of Atkin?

Question

В настоящее время я пытаюсь внедрить Сито Аткина в Haskell

На шаге 3 статьи Википедия о Сите Аткина Мне нужно найти число решений Integer для несколькихуравнения.

Однако мое решение первого из этих уравнений (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.

Как я могу предотвратить это?Возможно ли это вообще?

Редактировать: Понял, где должен быть бесконечный цикл.

Answer 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

Далее вы можете использовать приблизительное целое числоroot, чтобы сузить область поиска для 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