Andrew Kozlík @

Počítačová algebra (cvičení), LS 2011/12


Literatura

Doplňující literatura

Mathematica

C++

Vývojová prostředí

GMP a NTL

Instalace a použití knihovny NTL na Linuxu

V některých Linuxových distribucích najdete NTL jako balíček, takže např. v Ubuntu nainstalujete NTL příkazem
sudo apt-get install libntl-dev
Hotovo.

Pokud se rozhodnete knihovnu přeložit sami, pak můžete použít následující posloupnost příkazů, která stáhne knihovnu NTL, rozbalí, nastaví, přeloží, ověří, že vše funguje, jak má, a nainstaluje do /usr/local. Pokud však nemáte možnost do tohoto adresáře zapisovat, pak si ji nainstalujte někam do domovského adresáře tak, že příkaz ./configure nahradíte např. ./configure PREFIX=$HOME/sw (v tomto případě pochopitelně vynechte sudo v posledním příkazu).

wget http://www.shoup.net/ntl/ntl-5.5.2.tar.gz
tar xzf ntl-5.5.2.tar.gz
cd ntl-5.5.2/src
./configure
make
make check
sudo make install

Adresář ntl-5.5.2 a soubor ntl-5.5.2.tar.gz můžete potom odstranit. Další podrobnosti najdete v návodu na stránkách Victora Shoupa.

Svůj program pak přeložíte příkazem
g++ nazev_zdrojaku.cc -o nazev_programu -lntl -lm
nebo pokud jste NTL instalovali do domovského adresáře, příkazem
g++ -I$HOME/sw/include nazev_zdrojaku.cc -o nazev_programu -L$HOME/sw/lib -lntl -lm
Přepínače -lntl a -lm musejí být na konci příkazu!

Instalace a použití knihovny NTL na Windows

Jestliže budete používat překladač MinGW (tj. např. prostředí Code::Blocks), pak postupujte podle návodu na stránkách Milana Straky.

Jestliže budete používat Microsoft Visual C++, pak si stáhněte tuto binárku, anebo pokud si chcete NTL přeložit sami, stáhněte si tento projekt pro Visual C++ Express 2008.

Pokud máte přístup k adresáři C:\Program Files\Microsoft Visual Studio 9.0\VC\include\ zkopírujte do něj složku NTL, která obsahuje hlavičkové soubory, a do adresáře C:\Program Files\Microsoft Visual Studio 9.0\VC\lib\ zkopírujte soubor ntl.lib. Pokud k těmto adresářům přístup nemáte, pak budete muset vždy při založení nového projektu sdělit vývojovému prostředí, kde se nacházejí hlavičkové soubory a soubor ntl.lib, takto:

  1. Do ProjectPropertiesConfiguration PropertiesC/C++GeneralAdditional Include Directories přidáte adresář include, ve kterém se nachází podadresář NTL s hlavičkovými soubory.
  2. Do ProjectPropertiesConfiguration PropertiesLinkerGeneralAdditional Library Directories přidáte adresář lib, ve kterém máte soubor ntl.lib.

Při založení každého nového projektu musíte sdělit překladači, že budete používat knihovnu NTL, tak, že do ProjectPropertiesConfiguration PropertiesLinkerInputAdditional Dependencies přidáte ntl.lib.

Instalace a použití knihovny GMP na Linuxu

Knihovna GMP je nainstalovaná v karlínském labu i na výpočetním clusteru Sněhurka.

Ve většině Linuxových distribucích najdete GMP jako balíček, takže např. v Ubuntu nainstalujete GMP příkazem
sudo apt-get install libgmp3-dev
Hotovo.

Pokud se rozhodnete knihovnu přeložit sami, musíte mít nainstalovaný procesor maker m4. Následující posloupnost příkazů nainstaluje m4 (na Ubuntu) a stáhne, přeloží a nainstaluje knihovnu GMP.

sudo apt-get install m4
wget ftp://ftp.gmplib.org/pub/gmp-5.0.4/gmp-5.0.4.tar.bz2
tar xjf gmp-5.0.4.tar.bz2
cd gmp-5.0.4
./configure --enable-cxx
make
make check
sudo make install

Adresář gmp-5.0.4 a soubor gmp-5.0.4.tar.bz2 můžete potom odstranit. Další podrobnosti najdete v manuálu na stránkách knihovny GMP.

Svůj program pak přeložíte příkazem
g++ nazev_zdrojaku.cc -o nazev_programu -lgmpxx -lgmp

Podmínky pro udělení zápočtu

Z níže uvedeného seznamu vám bude náhodně přiřazen jeden algoritmus. Pro získání zápočtu je třeba

Použitím knihovny NTL se rozumí, že váš program nebude omezen standardními datovými typy jako int nebo double, ale bude využívat např. typy ZZ, RR nebo ZZX z knihovny NTL a bude tak umět pracovat s libovolně velkými čísly, s polynomy libovolného stupně atp.

Pokud nejste spokojeni s přiřazeným algoritmem, můžete si vybrat jeden z algoritmů, které jsou označeny *. Tyto algoritmy se probírají na přednášce Počítačová algebra II, popřípadě na přednášce Teorie čísel a RSA (viz skripta Aleše Drápala).

AlgoritmusStudentZápočet
Čínská věta o zbytcích v Zp[x]: Lagrange vs. Garner Adéla Zajíčková ANO
Čínská věta o zbytcích v Q[x]: Lagrange vs. Garner Ondřej Väter
Násobení polynomů v Z[x]: školské vs. pomocí FFT v Zp[x] František Steinhauser ANO
Násobení polynomů v Z[x]: školské vs. pomocí FFT v C[x] Jakub Töpfer ANO
Dělení polynomů v Z[x]: školské vs. rychlé (Newton) Anežka Titěrová ANO
Dělení polynomů v Zp[x]: školské vs. rychlé (Newton) David Mařák ANO
Dělení v Z: Newtonova metoda vs. půlení intervalu vs. školské Radka Luňáčková ANO
NSD pomocí PRS v Z[x] Miloš Klouček ANO
NSD pomocí PRS v Z[x,y] Richard Dubiel ANO
NSD - modulární algoritmus v Z[x] Lukáš Gurník ANO
NSD - modulární algoritmus v Z[x] Michal Mutňanský ANO
Bezčtvercová faktorizace v Z[x] Lukáš Langer ANO
Bezčtvercová faktorizace v Zp[x] Marek Trunkát ANO
Berlekampův algoritmus (faktorizace v Zp[x]) Romana Linkeová ANO
Henselovo liftování a faktorizace v Z[x] Kristina Hostáková ANO
Testování ireducibility v Z[x] a v Zp[x] Bernd Mangold
Kroneckerův algoritmus (faktorizace v Z[x,y]) Adam Ivánek ANO
Buchbergerův algoritmus a redukce Gröbnerovy báze* Ludmila Divišová ANO
Rabin-Millerův a Solovay-Strassenův test prvočíselnosti* Zbyněk Chmela ANO

V knihovně NTL není implementována aritmetika v Q[x], použijte floating point aritmetiku. Aritmetikou v C[x] se rozumí floating point aritmetika. Pro dělení v Z[x] uvažujte pouze monické dělitele.

Odevzdání zápočtové úlohy

U většiny zápočtových programů mi bude stačit, když pošlete zdrojové kódy a stručnou dokumentaci emailem. V případě nejasností vás dodatečně požádám o osobní odevzdání a předvedení programu. Jako dokumentace postačí popis nebo příklad vstupu/výstupu a pár komentářů v kódu, abych se v něm mohl snadno zorientovat. Zejména pokud se váš program skládá z více algoritmů, tak je ve svém kódu označte komentářem. Nejlépe, když uvedete přímo číslo, kterým je algoritmus označen v učebnici. Pokud jste svou úlohu rozdělili do několika programů, tak ke každému napište popis vstupu/výstupu a jednou větou co dělá, není-li to na první pohled zřejmé.