Reprezentowanie liczb Eisensteina bez liczb zmiennoprzecinkowych

9

Mam projekt, w którym muszę użyć pól kwadratowych. Dokładnie numery formularza $a + b \sqrt{-3}$ z $a,b \in \mathbb{Q}$ .

Oto na przykład liczby pierwsze w liczbach całkowitych Eisensteina :

Nie chcę używać szałwii. Chciałbym napisać własny typ danych do włączenia numpy. PARI byłby użyteczny - ale nie jest kompatybilny z Pythonem.

Dodawanie tych obiektów jest dość jasne $(a_{1} + b_{1} \sqrt{- 3}) + (a_{2} + b_{2} \sqrt{- 3}) = (a_{1} + a_{2}) + (b_{1} + b_{2}) \sqrt{- 3}$ $(a_1 + b_1 \sqrt{-3}) + (a_2 + b_2 \sqrt{-3}) = (a_1 + a_2) + (b_1+b_2) \sqrt{-3}$
Mnożenie jest nieco bardziej delikatne, ale możemy go również kodować na stałe $(a_{1} + b_{1} \sqrt{- 3}) \times (a_{2} + b_{2} \sqrt{- 3}) = (a_{1} a_{2} - 3 b_{1} b_{2}) + (a_{1} b_{2} + a_{2} b_{1}) \sqrt{- 3}$ $(a_1 + b_1 \sqrt{-3}) \times (a_2 + b_2 \sqrt{-3}) = (a_1 a_2 - 3 b_1 b_2) + (a_1 b_2 + a_2 b_1)\sqrt{-3}$
Mój typ danych musi również uwzględniać podział. Dla uproszczenia weźmy wzajemność: $\frac{1}{a + b \sqrt{- 3}} = \frac{a - b \sqrt{- 3}}{a^{2} + 3 b^{2}}$ $\frac{1}{a + b \sqrt{-3}} = \frac{a - b \sqrt{-3}}{a^2 + 3b^2}$

Czy istnieje naturalny sposób kodowania tych operacji oparty na macierzy, podobny do tego $\mathbb{C}$ można napisać w kategoriach $2 \times 2$ matryce?

(\begin{array}{cc} a & b \\ - b & a \end{array})

$\left( \begin{array}{cc} a & b \\ -b & a \end{array}\right)$

Może po prostu zaprogramuję operacje jako trzykrotnie z trzema operacjami opisanymi powyżej. Jakieś pomysły?

linear-algebra precision John Mangual
źródło

10

Dla $a+b\sqrt{-3}$ możesz użyć reprezentacji

(\begin{matrix} a & - 3 b \\ b & a \end{matrix})

$\begin{pmatrix}a&-3b\\b&a\end{pmatrix}$ Dodawanie działa oczywiście. W celu pomnożenia możesz zweryfikować

(\begin{matrix} a_{1} & - 3 b_{1} \\ b_{1} & a_{1} \end{matrix}) (\begin{matrix} a_{2} & - 3 b_{2} \\ b_{2} & a_{2} \end{matrix}) = (\begin{matrix} a_{1} a_{2} - 3 b_{1} b_{2} & - 3 (a_{1} b_{2} + b_{1} a_{2}) \\ a_{1} b_{2} + b_{1} a_{2} & a_{1} a_{2} - 3 b_{1} b_{2} \end{matrix})

$\begin{pmatrix}a_1&-3b_1\\b_1&a_1\end{pmatrix}\begin{pmatrix}a_2&-3b_2\\b_2&a_2\end{pmatrix} = \begin{pmatrix}a_1a_2-3b_1b_2&-3(a_1b_2+b_1a_2)\\a_1b_2+b_1a_2&a_1a_2-3b_1b_2\end{pmatrix}$ która zachowuje reprezentację, a zatem mamy homomorfizm pierścieniowy.

Biorąc wyznacznik macierzy daje (kwadrat) normę $a^2+3b^2$ , zatem odwrotność odpowiada odwrotnym macierzom, zgodnie z oczekiwaniami.

Rozważałeś już użycie potrójnych , przy których zakładam, że użyłbyś liczb całkowitych i wspólnego mianownika. Takie podejście może być również przydatne w reprezentacji macierzowej.

Aktualizacja : Ogólna metoda reprezentacji macierzy wykorzystuje macierz towarzyszącą . Załóżmy na przykład, że chcesz reprezentować $a+b\omega$ zamiast tego gdzie $\omega=\exp(\frac{2\pi\mathrm{i}}{3})$ w ten sposób $\omega^2+\omega+1=0$ . Macierz towarzysząca $\omega$ jest $\begin{pmatrix}0&-1\\1&-1\end{pmatrix}$ , i zachowuje się to we wszystkich powiązanych operacjach pierścienia, takich jak $\omega$ samo. Oczywiście, $1$ może być reprezentowany jako $\begin{pmatrix}1&0\\0&1\end{pmatrix}$ ; dlatego macierzowa reprezentacja $a+b\omega$ jest

(\begin{matrix} a & - b \\ b & a - b \end{matrix})

$\begin{pmatrix}a&-b\\b&a-b\end{pmatrix}$ Możesz sprawdzić, czy jest to homomorfizm pierścieniowy. Ponadto łatwo to zobaczyć. W przypadku mnożenia odpowiednie formuły są teraz

\begin{aligned} (a_{1} + b_{1} ω) (a_{2} + b_{2} ω) & = (a_{1} a_{2} - b_{1} b_{2}) + (a_{1} b_{2} + b_{1} a_{2} - b_{1} b_{2}) ω \\ (\begin{matrix} a_{1} & - b_{1} \\ b_{1} & a_{1} - b_{1} \end{matrix}) (\begin{matrix} a_{2} & - b_{2} \\ b_{2} & a_{2} - b_{2} \end{matrix}) & = (\begin{matrix} a_{1} a_{2} - b_{1} b_{2} & - (a_{1} b_{2} + b_{1} a_{2} - b_{1} b_{2}) \\ a_{1} b_{2} + b_{1} a_{2} - b_{1} b_{2} & a_{1} a_{2} - a_{1} b_{2} - b_{1} a_{2} \end{matrix}) \end{aligned}

$\begin{align} (a_1+b_1\omega)(a_2+b_2\omega)&=(a_1a_2-b_1b_2)+(a_1b_2+b_1a_2-b_1b_2)\omega \\\begin{pmatrix}a_1&-b_1\\b_1&a_1-b_1\end{pmatrix} \begin{pmatrix}a_2&-b_2\\b_2&a_2-b_2\end{pmatrix} &= \begin{pmatrix}a_1a_2-b_1b_2&-(a_1b_2+b_1a_2-b_1b_2)\\ a_1b_2+b_1a_2-b_1b_2&a_1a_2-a_1b_2-b_1a_2\end{pmatrix} \end{align}$

kukurydza
źródło

2

Zgaduję, że potrzebujesz dokładnej racjonalnej arytmetyki do wszystkiego, ponieważ mogą powodować błędy zmiennoprzecinkowe $1/z$ nie w $\mathbb{Q}[\sqrt{-3}]$ nawet jeśli $z$ jest. W tym celu możesz rzucić okiem na pakiet SymPy ; jeśli nie użyjesz ich racjonalnego typu danych bezpośrednio, może to posłużyć jako inspiracja dla Twojej ręcznie rozwijanej wersji. Następnie możesz zbudować typ pola kwadratowego na dowolnym wybranym typie liczby wymiernej.

Bez względu na to, jak reprezentujesz elementy swojego pola, możesz przeciążać operatorów w Pythonie za pomocą „magicznych metod”. Zobacz także ten post SO dotyczący tworzenia własnego typu liczbowego w języku Python.

Nie sądzę, aby było o wiele więcej pracy kodującej reprezentację elementu pola kwadratowego albo jako macierz 2 x 2 liczb wymiernych, albo jako parę liczb wymiernych, ponieważ operacje arytmetyczne nie są tak skomplikowane. Podejrzewam jednak, że drugie podejście będzie szybsze.

Daniel Shapero
źródło

1

Interesujące może być porównanie praktycznej wydajności numpyprzyspieszonych operacji macierzowych z wydajnością typów danych zdefiniowanych przez użytkownika. Nie jestem pewien, kto byłby zwycięzcą.

ccorn,

Tak, to prawda, numpy ma wiele ręcznie kodowanych optymalizacji po stronie C, aby przyspieszyć. Trzeba by to przerobić samemu, aby osiągnąć ten sam efekt. Niemniej jednak najpierw powinna pojawić się funkcjonalność, a później można się martwić szybkością.

Daniel Shapero

Reprezentowanie liczb Eisensteina bez liczb zmiennoprzecinkowych

Odpowiedzi: