1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
\contentsline {chapter}{\numberline {1}Introduction}{1}
\contentsline {section}{\numberline {1.1}What is \unhbox \voidb@x \hbox {\rm SACLIB}?}{1}
\contentsline {section}{\numberline {1.2}About this Guide}{2}
\contentsline {section}{\numberline {1.3}\unhbox \voidb@x \hbox {\rm SACLIB}\ Maintenance}{2}
\contentsline {chapter}{\numberline {2}List Processing}{4}
\contentsline {section}{\numberline {2.1}Mathematical Preliminaries}{4}
\contentsline {section}{\numberline {2.2}Purpose}{4}
\contentsline {section}{\numberline {2.3}Definitions of Terms}{4}
\contentsline {section}{\numberline {2.4}Functions}{5}
\contentsline {chapter}{\numberline {3}Arithmetic}{9}
\contentsline {section}{\numberline {3.1}Introduction}{9}
\contentsline {subsection}{\numberline {3.1.1}Purpose}{9}
\contentsline {subsection}{\numberline {3.1.2}Definitions of Terms}{9}
\contentsline {section}{\numberline {3.2}Integer Arithmetic}{10}
\contentsline {section}{\numberline {3.3}Modular Number Arithmetic}{13}
\contentsline {subsection}{\numberline {3.3.1}Modular Digit Arithmetic}{13}
\contentsline {subsection}{\numberline {3.3.2}Modular Integer Arithmetic}{13}
\contentsline {section}{\numberline {3.4}Rational Number Arithmetic}{14}
\contentsline {chapter}{\numberline {4}Polynomial Arithmetic}{15}
\contentsline {section}{\numberline {4.1}Introduction}{15}
\contentsline {subsection}{\numberline {4.1.1}Purpose}{15}
\contentsline {subsection}{\numberline {4.1.2}Definitions of Terms}{15}
\contentsline {section}{\numberline {4.2}Polynomial Input and Output}{17}
\contentsline {subsection}{\numberline {4.2.1}Recursive polynomials over ${\bf Z}$}{17}
\contentsline {subsection}{\numberline {4.2.2}Recursive polynomials over ${\bf Q}$}{18}
\contentsline {subsection}{\numberline {4.2.3}Distributive polynomials over ${\bf Z}$}{19}
\contentsline {subsection}{\numberline {4.2.4}Distributive polynomials over ${\bf Q}$}{19}
\contentsline {subsection}{\numberline {4.2.5}Conversion Between Recursive and Distributive\newline Representation}{19}
\contentsline {subsection}{\numberline {4.2.6}Polynomials over ${\bf Z}_m$}{19}
\contentsline {section}{\numberline {4.3}Domain Independent Polynomial Arithmetic}{20}
\contentsline {section}{\numberline {4.4}Integral Polynomial Arithmetic}{21}
\contentsline {section}{\numberline {4.5}Modular Polynomial Arithmetic}{24}
\contentsline {section}{\numberline {4.6}Rational Polynomial Arithmetic}{26}
\contentsline {section}{\numberline {4.7}Miscellaneous Representations}{26}
\contentsline {subsection}{\numberline {4.7.1}Sparse Distributive Representation}{26}
\contentsline {subsection}{\numberline {4.7.2}Dense Recursive Representation}{27}
\contentsline {chapter}{\numberline {5}Linear Algebra}{28}
\contentsline {section}{\numberline {5.1}Mathematical Preliminaries}{28}
\contentsline {section}{\numberline {5.2}Purpose}{28}
\contentsline {section}{\numberline {5.3}Methods and Algorithms}{28}
\contentsline {section}{\numberline {5.4}Functions}{29}
\contentsline {chapter}{\numberline {6}Polynomial GCD and Resultants}{31}
\contentsline {section}{\numberline {6.1}Mathematical Preliminaries}{31}
\contentsline {section}{\numberline {6.2}Purpose}{32}
\contentsline {section}{\numberline {6.3}Definitions of Terms}{32}
\contentsline {section}{\numberline {6.4}Methods and Algorithms}{33}
\contentsline {subsection}{\numberline {6.4.1}GCD Computations}{33}
\contentsline {subsection}{\numberline {6.4.2}Resultants}{33}
\contentsline {section}{\numberline {6.5}Functions}{34}
\contentsline {chapter}{\numberline {7}Polynomial Factorization}{37}
\contentsline {section}{\numberline {7.1}Mathematical Preliminaries}{37}
\contentsline {section}{\numberline {7.2}Purpose}{37}
\contentsline {section}{\numberline {7.3}Methods and Algorithms}{37}
\contentsline {section}{\numberline {7.4}Functions}{38}
\contentsline {chapter}{\numberline {8}Real Root Calculation}{40}
\contentsline {section}{\numberline {8.1}Mathematical Preliminaries}{40}
\contentsline {section}{\numberline {8.2}Purpose}{40}
\contentsline {section}{\numberline {8.3}Methods and Algorithms}{40}
\contentsline {section}{\numberline {8.4}Definitions of Terms}{41}
\contentsline {section}{\numberline {8.5}Functions}{41}
\contentsline {chapter}{\numberline {9}Algebraic Number Arithmetic}{44}
\contentsline {section}{\numberline {9.1}Mathematical Preliminaries}{44}
\contentsline {section}{\numberline {9.2}Purpose}{44}
\contentsline {section}{\numberline {9.3}Methods and Algorithms}{44}
\contentsline {section}{\numberline {9.4}Definitions of Terms}{46}
\contentsline {section}{\numberline {9.5}Representation}{46}
\contentsline {section}{\numberline {9.6}Functions}{47}
\contentsline {chapter}{\numberline {A}Calling \unhbox \voidb@x \hbox {\rm SACLIB}\ Functions from C}{51}
\contentsline {section}{\numberline {A.1}A Sample Program}{51}
\contentsline {section}{\numberline {A.2}Dynamic Memory Allocation in \unhbox \voidb@x \hbox {\rm SACLIB}}{51}
\contentsline {section}{\numberline {A.3}Declaring Global Variables to \unhbox \voidb@x \hbox {\rm SACLIB}}{54}
\contentsline {section}{\numberline {A.4}Initializing \unhbox \voidb@x \hbox {\rm SACLIB}\ by Hand}{55}
\contentsline {section}{\numberline {A.5}\unhbox \voidb@x \hbox {\rm SACLIB}\ Error Handling}{55}
\contentsline {section}{\numberline {A.6}Compiling}{56}
\contentsline {chapter}{\numberline {B}\unhbox \voidb@x \hbox {\rm ISAC}: An Interactive Interface to \unhbox \voidb@x \hbox {\rm SACLIB}}{57}
\contentsline {section}{\numberline {B.1}What is \unhbox \voidb@x \hbox {\rm ISAC}?}{57}
\contentsline {section}{\numberline {B.2}Supported \unhbox \voidb@x \hbox {\rm SACLIB}\ Algorithms}{57}
\contentsline {section}{\numberline {B.3}Command Line Options}{57}
\contentsline {section}{\numberline {B.4}Interface Functionality}{57}
\contentsline {section}{\numberline {B.5}Interface Grammar}{58}
\contentsline {chapter}{\numberline {C}Notes on the Internal Workings of \unhbox \voidb@x \hbox {\rm SACLIB}}{61}
\contentsline {section}{\numberline {C.1}Lists, GCA Handles, and Garbage Collection}{61}
\contentsline {subsection}{\numberline {C.1.1}Implementation of Lists}{61}
\contentsline {subsection}{\numberline {C.1.2}Implementation of GCA Handles}{62}
\contentsline {subsection}{\numberline {C.1.3}The Garbage Collector}{62}
\contentsline {section}{\numberline {C.2}Constants and Global Variables}{63}
\contentsline {chapter}{Index}{66}
|
