Полиномиальная факторизация в Хаскеле - PullRequest
Новая
       36

Полиномиальная факторизация в Хаскеле

8 голосов
/ 07 октября 2011

С помощью Хаммара Я сделал шаблон Haskell, который компилирует 

$(zModP 5)

до 

newtype Z5 = Z5 Int
instance Additive.C Z5 where
  (Z5 x) + (Z5 y) = Z5 $ (x + y) `mod` 5
...

Сейчас я сталкиваюсь с проблемой, которую не думаю, что смогу решить таким образом.

Замечательный факт о полиномах состоит в том, что они неприводимы в рациональных числах, если они неприводимы по модулю некоторого простого p. У меня уже есть метод, который грубой силой пытается разложить полиномы по заданному (конечному) полю.

Я хочу попробовать запустить эту функцию для нескольких полей. Вот то, что я хочу: 

isIrreducible :: (FiniteField.C a) => Poly.T a -> Bool
isIrreducible p = ...

intPolyIrreducible :: Poly.T Int -> Bool
intPolyIrreducible p = isIrreducible (p :: Poly.T Z2) ||
                       isIrreducible (p :: Poly.T Z3) ||
                       isIrreducible (p :: Poly.T Z5) ||
                       ...

По сути, я хочу попробовать запустить алгоритм факторинга для большого числа определений «деления».

Я думаю, что это возможно сделать с TH, но кажется, что это займет вечность. Я задаюсь вопросом, будет ли проще просто передать мои арифметические операции в качестве параметра в isIrreducible?

В качестве альтернативы может показаться, что с этим может помочь модуль Newtype, но я не могу думать о том, как он будет работать без использования TH таким способом, который был бы столь же сложным ...

У кого-нибудь есть мысли о том, как лучше всего это сделать?

Ответы [ 2 ]

3 голосов
/ 08 октября 2011

Вы можете выполнять вычисления в конечных полях, используя числовые значения уровня типа, например, с пакетом type-level: 

{-# LANGUAGE ScopedTypeVariables #-}
module Mod where
import Data.TypeLevel.Num (Nat,toNum, reifyIntegral)

data Z p = Z Integer

instance Eq (Z p) where Z x == Z y = x == y
instance Ord (Z p) where -- dummy instance
instance Show (Z p) where show (Z n) = show n

instance Nat p => Num (Z p) where
    Z x + Z y = Z $ (x + y) `mod` toNum (undefined :: p)
    Z x - Z y = Z $ (x - y) `mod` toNum (undefined :: p)
    Z x * Z y = Z $ (x * y) `mod` toNum (undefined :: p)
    fromInteger n = Z (n `mod` toNum (undefined :: p))
    -- etc

-- Compute x^2-6 (mod p)
poly :: Nat p => Z p -> Z p
poly x = x*x-6

-- Computes whether x^2-6==0 (mod p), for x=3
checkPoly :: Integer -> Bool
checkPoly n = reifyIntegral n test
  where
    test :: forall p . Nat p => p -> Bool
    test _ = poly (3::Z p) == 0

test1 = map checkPoly [2,3,5]
-- Result: [False,True,False]

Этот подход имеет то преимущество, что не требует нового экземпляра haskell шаблона для каждого числового значения.тип.Недостатком является то, что он, вероятно, медленнее, чем шаблонное решение haskell, поскольку каждая операция передает размер конечного поля через словарь классов.

2 голосов
/ 07 октября 2011

Это немного зависит от того, как выглядит Poly.T, но вы можете написать функцию типа (например) 

fmap :: (a -> b) -> (Poly.T a -> Poly.T b)

? Если это так, то может иметь смысл иметь тип Z, операции которого не выполняются во время выполнения, когда их модуль не совпадает: 

data Z = Z Int Int
instance Applicative.C Z where
    (Z m v) + (Z m' v')
        | m == m' = Z m ((v + v') `mod` m)
        | otherwise = error "mismatched modulus"

Тогда вы можете написать что-то вроде этого на простом старом Хаскеле: 

intPolyIrreducible :: Poly.T Int -> Bool
intPolyIrreducible p = any isIrreducible [fmap (Z m) p | m <- [2,3,5,7,11,13]]

Конечно, это немного менее безопасно для типов. Но из параметричности ясно, что fmap (Z m) не будет вводить несовпадающих модулей.

...