Asir

Asir User’s Manual Edition 2.0 for Asir-940420

May 1994

by Masayuki Noro and Takeshi Shimoyama English translation by Taku Takeshima

1 Introduction

1.1 Organization of the Manual

This manual is organized as follows.

1. Introduction Organization of the Manual and notation

2. Risa/Asir Summary of Asir, Installation

3. Types Types in Asir

4. Asir user language Description of Asir user language

5. Debugger Description of the debugger of Asir user language

6. Built-in function Detailed description of various built-in functions

7. Groebner bases Description of functions and operations for Groebner basis computation

8. Algebraic numbers Description of functions and operations for algebraic numbers

9. Appendix Syntax in detail, Risa/Asir for personal computers, description of sample files, References

1.2 Notation

In this manual, we shall use several notations, which is described here.

• The name of a function is written in a typewriter type.

gcd(), gr()

• For the description of a function, its argument is written in a slanted type. int, poly

• A file name is written in a ‘typewriter type with single quotes’.
‘dbxinit’, ‘asir_plot’

• An example is indented and written in a typewriter type.

[0] 1;
1
[1] quit;
• References are made by a typewriter type bracketed by [].
[Boehm,Weiser]

• Arguments (actual parameters) of a function are optional when they are bracketed by []’s. The repeatable items (including non-existence of the item) are bracketed by []*’s.

setprec([n]), diff(rat[,varn]*)

• The prompt from the shell (csh) is denoted, as it is, by %. The prompt, however, is denoted

by #, when you are assumed to be working as the root, for example, at the installation.

% cat afo
afo
bfo
% su
Password:XXXX
# cp asir /usr/local/bin
# exit
%

• The rational integer ring is denoted by Z, the rational number field by Q, the real number field by R, and the complex number field by C.

2 Risa/Asir

2.1 Risa and Asir

Risa is the name of whole libraries of a computer algebra system which is under development at FUJITSU LABORATORIES LIMITED. The structure of Risa is as follows.

• The basic algebraic engine This is the part which performs basic algebraic operations, such as arithmetic operations, to algebraic objects, e.g., numbers and polynomials, which are already converted into internal forms. It exists, like ‘libc.a’ of UNIX, as a library of ordinary UNIX system. The algebraic engine is written mainly in C language and partly in assembler. It serves as the basic operation part of Asir, a standard language interface of Risa. It can also be linked to various programs that need some symbolic and algebraic computation.

• Memory Manager Risa employs, as its memory management component (the memory manager), a free software distributed by Boehm. It is proposed by Boehm and Weiser, and developed by Boehm and his colleagues. The memory manager has a memory allocator which automatically reclaims garbages, i.e., allocated but unused memories, and refreshes them for further use. The algebraic engine gets all its necessary memories through the memory manager.

• Asir Asir is a standard language interface of Risa’s algebraic engine. It is one of the possible language interfaces, because one can develop one’s own language interface easily on Risa system. Asir is an example of such language interfaces. Asir has very similar syntax and semantics as C language. Furthermore, it has a debugger that provide a subset of commands of dbx, a widely used debugger of C language.

2.2 Features of Asir

As mentioned in the previous section, Asir is a standard language interface forRisa’s algebraic engine. Usually, it is provided as an executable file named asir. Main features supported for Version Asir-940420 is as follows.

• A C-like programming language • Arithmetic operations (addition, subtraction, multiplication and division) on numbers, poly-

nomials and rational expressions

• Operations on vectors and matrices

• List processing operations at the minimum

• Several Built-in functions (factorization, GCD computation etc.)

• Useful user defined functions(e.g., Groebner basis package)

• A dbx-like debugger

• Plotting of implicit functions

• Numerical evaluation of mathematical expressions including elementary transcendental functions at arbitrary precision (This feature is in force only if PARI system, described in a later section, is linked together.)

2.3 Installation

See ‘Installation Manual’ to install from source files. Here, we explain installation from binaries.

Any questions and any comments on this manual are well come by e-mails to the address

     noro@iias.flab.fujitsu.co.jp.

2.3.1 UNIX version

Following five (5) files are provided.

‘asir.gz’ Asir
‘asir_ping.gz’

A program for testing process communication facility.

‘asir_plot.gz’

A program for plotting implicit functions. (2-dimensional algebraic curves.)

‘asir.o.gz’

An utility file for adding binary functions.

‘asirlib.tar.gz’

Files containing user defined functions and files for help facility.

File ‘asir_ping.gz’ is optional. File ‘asir.o.gz’ is optional, too. This is used for making a new Asir which contains new additional Asir functions written in C. All above mentioned files are compressed by gzip. They should be expanded by gzip after getting them.

# gzip -dc asir > /usr/local/bin/asir
# gzip -dc asir_plot > /usr/local/bin/asir_plot
# chmod 755 /usr/local/bin/asir /usr/local/bin/asir_plot

Programs such as ‘asir’, ‘asir_plot’ and ‘asir_ping’ are usually located to a common command directory, e.g., ‘/usr/local/bin’, or to ‘$HOME/bin’ if they are used privately. Files in ‘asirlib.tar.gz’ are located to directory ‘/usr/local/lib/asir’ by default.

# mkdir /usr/local/lib/asir
# gzip -dc asirlib.tar.gz | ( cd /usr/local/lib/asir; tar xf - )

If you wish to place them to a different directory, you should set the directory to an environment

variable ASIR_LIBDIR.
% mkdir $HOME/lib/asir
% gzip -dc asirlib.tar.gz | ( cd $HOME/lib/asir; tar xf - )
% setenv ASIR_LIBDIR $HOME/lib/asir

After installing libraries, make a symbolic link from in the library directory to ‘asir’ with name

‘asir_symtab’.
% cd /usr/local/lib/asir
% ln -s /usr/local/bin/asir asir_symtab

Start ‘asir’, and Asir will immediately terminate leaving you a message as follows.

% /usr/local/bin/asir
asir_key not found.
ID for this machine is XXXXXXXX.
See the file ASIR_INSTALL to get the correct key.

For UNIX version of Asir, you need a key, a string, for each machine you want to run Asir. In order to get the key, you just need to send an e-mail consisting of a single line like

ASIR XXXXXXXX

to address

     risa@iias.flab.fujitsu.co.jp

Here, XXXXXXXX is the machine ID notified in the first message from Asir.

After a while, an e-mail will be returned containing only one line like

     YYYYYYYY YYYYYYYY YYYYYYYY

Then, you shall create a new file in the current directory named ‘asir_key’ containing the returned string in one line.

All after this, call again ‘asir’.

     % /usr/local/bin/asir
     This is Asir, Version 940420.
     Copyright (C) FUJITSU LABORATORIES LIMITED.
     3 March 1994. All rights reserved.
     [0]

If you get such a prompt (‘[0]’) from Asir, the key you have is valid to the machine you are currently running asir.

When the file ‘asir_key’ is located on the library directory, all the users of the machine can execute ‘asir’. The file ‘asir_key’ can contain several lines for several key’s. This enables users to run several machines sharing the same library directory by simply adding lines for machines to be used. We shall describe about the file for key’s in detail in Section 2.5 [Environment variable], page 9.

     # cp asir_key /usr/local/lib/asir

2.3.2 Macintosh version

For Macintoshes only the following one file is provided.

‘asir.sea’

Asir and files containing user defined functions.

A double click on this file will create a folder. This folder consists of asir executable file and a sub-folder containing files of user defined functions. No key is needed for Macintosh version. The asir executable file is ready to be executed. See Appendix for details.

2.3.3 DOS version

Three (3) files are provided for DOS version as follows.

‘asir.lzh’

Asir

‘asirlib.lzh’

Files of user defined functions.

‘go32.lzh’

‘go32.exe’ V1.10 for IBM-PC, PC98 and FUJITSU FM series

These three files are compressed by ‘lha.exe’, and will be melted by ‘lha.exe’.

     C> lha x asir
     C> lha x asirlib

No key is needed for DOS version. While no default library directory is set, it is necessary to set up environments ASIR_LIBDIR and ASIRLOADPATH. Note that the way to set up environments for DOS differs from that for UNIX.

     C> set ASIR_LIBDIR=C:\usr\lib\asir
     C> set ASIRLOADPATH=.;C:\usr\noro\lib\asir

If your machine has not yet ‘go32.exe’ installed, you have to install it and to set up its environments. We recommend to install ‘go32.exe’ with version V1.10 or newer. When older version is installed, depending on which device driver is installed to DOS, it sometimes happens to extremely slower Asir execution. Such a situation happens due to swap-out of Asir caused by failure of go32 to get memories. In ‘go32.lzh’, the following files are contained.

‘go32-pc.exe’

For IBM-PC clones

‘go32-98.exe’

For NEC PC98 series

‘go32-fm.exe’

For FUJITSU FMR and FMTOWNS

‘emu387’ 387 emulation module ‘readme’ readme of go32.

The version of ‘go32-xx.exe’ is 1.10. Choose the proper ‘go32’ executable for your machine. Then, place it on a convenient command directory with name ‘go32.exe’. Finally, set up environments GO32TMP and GO32. (See ‘readme’ of go32 for setting up environments.)

     C> set GO32TMP=C:\tmp
     C> set GO32=ansi

It is necessary to install and use ‘emu387’ for machines which have no hardware support for floating point number operations. (Machines which do not have 80387, or 486 machines which lack hardware floating point operation support.) In such a case, set, for example, the environment variable as follows.

     C> set GO32=emu C:\usr\djgpp\lib\emu387

See ‘readme’ of ‘go32’ for details. See Appendix for further operations and constraints for DOS version of Asir.

2.4 Command line options

Command-line options for the command ‘asir’ are as follows.

-heap number In Risa/Asir, 4KB is used as an unit, called block, for memory allocation. By default, 16 blocks (64KB) are allocated initially. This value can be changed by giving an option -heap a number parameter in unit block. Size of the heap area is obtained by a Built-in function heap(), the result of which is a number in Bytes.

-adj number Heap area will be stretched by the memory manager, if the size of reclaimed memories is less than 1/number of currently allocated heap area. The default value for number is 4. If you do not prefer to stretch heap area by some reason, perhaps by restriction of available memories, but if prefer to resort to reclaiming garbages as far as possible, then a large value should be chosen for number, e.g., 16.

-norc When this option is specified, Asir does not read the initial file ‘$HOME/.asirrc’.

-paristack number

This option specifies the private memory size for PARI. The unit is Bytes. By default, it is set to 1 MB. Note: 64KB for MS-DOS machines and Macintoshes, by default.

2.5 Environment variable

There are several environment variable for Asir execution.

• ASIR_KEY

Asir shall not work unless a key for the machine on which Asir is invoked is given. The key consists of a string which denotes 3 word hexadecimal number, each of which has 8 hexadecimal digits. In order to run Asir for several machines, several key’s can be written together on a same file as follows.

     % cat asir_key
     cf6f236c 61a35091 dddc4529 geisha
     82281685 d1929945 a8bd24ca yorktown
     34b75d30 63f8df93 3e881113 nyanchu

The text after each key is neglected to the end-of-line. This is convenient to comment on the respective key. Files containing key’s are searched by the following order.

1. File set to environment ASIR_KEY.

2. File ‘asir_key’ on the current directory.

3. Files on the directory specified by environment ASIR_LIBDIR. (File ‘asir_key’ on

    ‘/usr/local/lib/asir/’, if environment ASIR_LIBDIR is not set.)
• ASIR_LIBDIR

The library directory of Asir, i.e., the directory where , for example, files containing programs written in Asir. If not specified, ‘/usr/local/lib/asir’ is used by default. This environment will be useful in a case where Asir binaries are installed on a private directory of the user.

• ASIRLOADPATH

This environment specifies directories which contains files to be loaded by Asir command load(). Directories are separated by a ‘:’. The search order is from the left to the right. After searching out all directories in ASIRLOADPATH, or in case of no specification at all, the library directory will be searched.

2.6 Starting and Terminating an Asir session

Run Asir, then the copyright notice and the first prompt will appear on your screen, and a new Asir session will be started.

This is Asir, Version 940420.
Copyright (C) FUJITSU LABORATORIES LIMITED.
3 March 1994. All rights reserved.
[0]

When initialization file “$HOME/.asirrc’’ exists, Asir interpreter executes it at first taking it as a program file written in Asir.

The prompt indicates the sequential number of your input commands to Asir. The session will terminate when you input end; or quit; to Asir. Input commands are evaluated statement by statement. A statement normally ends with its terminator ‘;’ or ‘$’. (There are some exceptions. See, syntax of Asir.) The result will be displayed when the command, i.e. statement, is terminated by a ‘;’, and will not when terminated by a ‘$’.

% asir
[0] A;
0
[1] A=(x+y)^5;
x^5+5*y*x^4+10*y^2*x^3+10*y^3*x^2+5*y^4*x+y^5
[2] A;
x^5+5*y*x^4+10*y^2*x^3+10*y^3*x^2+5*y^4*x+y^5
[3] a=(x+y)^5;
evalpv : invalid assignment
return to toplevel
[3] a;
a
[4] fctr(A);
[[1,1],[x+y,5]]
[5] quit;
%

In the above example, names A, a, x and y are used to identify mathematical and programming objects. There, the name A denotes a program variable (some times called simply as a program variable.) while the other names, a, x and y, denote mathematical objects, that is, indeterminates. In general, program variables have names which begin with capital letters, while names of indeterminates begin with small letters. As you can see in the example, program variables are used to hold and keep objects, such as numbers and expressions, as their values, just like variables in C programming language. Whereas, indeterminates cannot have values so that assignment to indeterminates are illegal. If one wants to get a result by substituting a value for an indeterminate in an expression, it is achieved by the function subst as the value of the function.

2.7 Interruption

To interrupt the Asir execution, input an interrupt character from the keyboard. A ^C is usually used for it. (Notice: ^X for DOS version; command+‘.’ for Macintosh version.)

     @ (x+y)^1000;
     ^Cinterrupt ?(q/t/c/d/w/?)

Here, the meaning of options are as follows.

q Terminates Asir session. (Confirmation requested.)

t Returns to toplevel. (Confirmation requested.)

c Resumes to continue the execution.

d Enters debugging mode at the next statement of the Asir program, if Asir has been executing a program loaded from a file. Note that it will sometimes take a long time before entering debugging mode when Asir is executing basic functions in the algebraic engine, (e.g., arithmetic operation, factorization etc.) Detailed description about the debugger will be given in Chapter 5 [Debugger], page 31.

w Displays the calling sequence up to the interruption.

? Show a brief description of options.

2.8 Error handling

When arguments with illegal types are given to a built-in function, an error will be detected and the execution will be quit. In many cases, when an error is detected in a built-in function, Asir automatically enters debugging mode before coming back to toplevel. At that time, one can examine the state of the program, for example, inspect argument values just before the error occurred. Messages reported there are various depending on cases. They are reported after the internal function name. The internal function name sometimes differs from the built-in function name that is specified by the user program.

In the execution of internal functions, errors may happen by various reasons. The UNIX version of Asir will report those errors as one of the following internal error’s, and enters debugging mode just like normal errors.

SEGV
BUS ERROR

Some of the built-in functions transmit their arguments to internal operation routines without strict type-checking. In such cases, one of these two errors will be reported when an access violation caused by an illegal pointer or a NULL pointer is detected.

BROKEN PIPE

In the process communication, this error will be reported if a process attempts to read from or to write onto the partner process when the stream to the partner process does not already exist, (e.g., terminated process.)

For UNIX version, even in such a case, the process itself does not terminate because such an error can be caught by signal() and recovered. For DOS/go32 version and Macintosh version, however, the process itself will terminate because such an error cannot be detected to recover. To remove this weak point in personal computer versions, complete type checking of all arguments are indispensable at the entry of a built-in function, which requires an enormous amount of re-making efforts.

2.9 Referencing results and special numbers

An @ used for an escape character; rules currently in force are as follows.

@n The evaluated result of n-th input command @@ The evaluated result of the last command @i The unit of imaginary number, square root of -1. \sqrt{−1} @pi The number pi, the ratio of a circumference of the circle and its diameter. @e Napier’s number, the base of natural logarithm.

     [0] fctr(x^10-1);
     [[1,1],[x-1,1],[x+1,1],[x^4+x^3+x^2+x+1,1],[x^4-x^3+x^2-x+1,1]]
     [1] @@[3];
     [x^4+x^3+x^2+x+1,1]
     [2] eval(sin(@pi/2));
     1.000000000000000000000000000000000000000000000000000000000
     [3] eval(log(@e),20);

0.99999999999999999999999999998
[4] @0[4][0];
x^4-x^3+x^2-x+1
[5] (1+@i)^5;
(-4-4*@i)
[6] eval(exp(@pi*@i));
-1.0000000000000000000000000000

As you can see in the above example, results of toplevel computation can be referred to by @ convention. This is convenient for users, while it sometimes imposes a heavy burden to the garbage collector. It may happen that GC time will rapidly increase after computing a very large expression at the toplevel.

3 Data types

3.1 Types in Asir

In Asir, various objects described according to the syntax of Asir are translated to intermediate forms and by Asir interpreter further translated into internal forms with the help of basic algebraic engine. Such an object in an internal form has one of the following types listed below. In the list, the number coincides with the value returned by the built-in function type(). Each example shows possible forms of inputs for Asir’s prompt.

0  0

As a matter of fact, no object exists that has 0 as its identification number. The number 0 is implemented as a null (0) pointer of C language. For convenience’s sake, a 0 is returned for the input type(0).

1 number

     1 2/3  14.5  3+2*@i

Numbers have sub-types. See Section 3.2 [Types of numbers], page 16.

2 polynomial (but not a number)

     x  afo  (2.3*x+y)^10

Every polynomial is maintained internally in its full expanded form, represented as a nested univariate polynomial, according to the current variable ordering, arranged by the descending order of exponents. (See Section 7.1 [Distributed polynomial], page 87). In the representation, the indeterminate (or variable), appearing in the polynomial, with maximum ordering is called the main variable. Moreover, we call the coefficient of the maximum degree term of the polynomial with respect to the main variable the leading coefficient.

3 rational expression (not a polynomial)

     (x+1)/(y^2-y-x)  x/x

Note that in Risa/Asir a rational expression is not simplified by reducing the common divisors unless red() is called explicitly, even if it is possible. This is because the GCD computation of polynomials is a considerably heavy operation. You have to be careful enough in operating rational expressions.

4 list

     []  [1,2,[3,4],[x,y]]

Lists are all read-only object. A null list is specified by []. There are operations for lists: car(), cdr(), cons() etc. And further more, element referencing by indexing is available. Indexing is done by putting [index]’s after a program variable as many as are required. For example,

     [0] L = [[1,2,3],[4,[5,6]],7]$
     [1] L[1][1];
     [5,6]

Notice that for lists, matrices and vectors, the index begins with number 0. Also notice that referencing list elements is done by following pointers from the first element. Therefore, it sometimes takes much more time to perform referencing operations on a large list than on a vectors or a matrices with the same size.

5 vector

     newvect(3)  newvect(2,[a,1])

Vector objects are created only by explicit execution of newvect() command. The first example above creates a null vector object with 3 elements. The other example creates a vector object with 2 elements which is initialized such that its 0-th element is a and 1st element is 1. The second argument for newvect is used to initialize elements of the newly created vector. A list with size smaller or equal to the first argument will be accepted. Elements of the initializing list is used from the left to the right. If the list is too short to specify all the vector elements, the unspecified elements are filled with as many 0’s as are required. Any vector element is designated by indexing, e.g., [index]. Asir allows any type, including vector, matrix and list, for each respective element of a vector. As a matter of course, arrays with arbitrary dimensions can be represented by vectors, because each element of a vector can be a vector or matrix itself. An element designator of a vector can be a left value of assignment statement. This implies that an element designator is treated just like a simple program variable. Note that an assignment to the element designator of a vector has effect on the whole value of that vector.

     [0] A3 = newvect(3);
     [ 0 0 0 ]
     [1] for (I=0;I<3;I++)A3[I] = newvect(3);
     [2] for (I=0;I<3;I++)for(J=0;J<3;J++)A3[I][J]=newvect(3);
     [3] A3;
     [ [ [ 0 0 0 ] [ 0 0 0 ] [ 0 0 0 ] ] [ [ 0 0 0 ] [ 0 0 0 ] [ 0 0 0
     ] ]
     [ [ 0 0 0 ] [ 0 0 0 ] [ 0 0 0 ] ] ]
     [4] A3[0];
     [ [ 0 0 0 ] [ 0 0 0 ] [ 0 0 0 ] ]
     [5] A3[0][0];
     [ 0 0 0 ]

6 matrix

     newmat(2,2)  newmat(2,3,[[x,y],[z]])

Like vector objects, matrix objects are also created only by explicit execution of newmat() command. Initialization of the matrix elements are done in a similar manner with that of the vector elements except that the elements are specified by a list of lists. Each element, again a list, is used to initialize each row; if the list is too short to specify all the row elements, unspecified elements are filled with as many 0’s as are required. Like vectors, any matrix element is designated by indexing, e.g., [index][index]. Asir also allows any type, including vector, matrix and list, for each respective element of a matrix. An element designator of a matrix can also be a left value of assignment statement. This implies that an element designator is treated just like a simple program variable. Note that an assignment to the element designator of a matrix has effect on the whole value of that matrix. Note also that every row, (not column,) of a matrix can be extracted and referred to as a vector.

     [0] M=newmat(2,3);
     [ 0 0 0 ]
     [ 0 0 0 ]
     [1] M[1];
     [ 0 0 0 ]
     [2] type(@@);
     5

7 string

     ""  "afo"

Strings are used mainly for naming files. It is also used for giving comments of the results. Operator symbol + denote the concatenation operation of two strings.

     [0] "afo"+"take";
     afotake

8 structure

     newstruct(afo)

For type structure, we shall describe it in a later chapter.

9 distributed polynomial

     2*<<0,1,2,3>>-3*<<1,2,3,4>>

This is the short for ‘Distributed representation of polynomials.’ This type is specially devised for computation of Groebner bases. Though for ordinary users this type may never be needed, it is provided as a distinguished type that user can operate by Asir. This is because the Groebner basis package provided with Risa/Asir is written in the Asir user language. For details See Chapter 7 [Groebner bases], page 87.

3.2 Types of numbers

0 rational number Rational numbers are implemented by arbitrary precision integers (bignum). A rational number is always expressed by a fraction of lowest terms.

1 double precision floating point number (double float)

The numbers of this type are numbers provided by the computer hardware. By default, when Asir is started, floating point numbers in a ordinary form are transformed into numbers of this type. However, they will be transformed into bigfloat numbers when the switch bigfloat is turned on (enabled) by ctrl() command.

     [0] 1.2;
     1.2
     [1] 1.2e-1000;
     0
     [2] ctrl("bigfloat",1);
     1
     [3] 1.2e-1000;
     1.20000000000000000513 E-1000

A rational number shall be converted automatically to a double float number before the operation with another double float number and the result shall be computed as a double float number.

2 algebraic number

See Chapter 8 [Algebraic numbers], page 104.

3 bigfloat The bigfloat numbers of Asir is realized by PARI library. A bigfloat number of PARI has an arbitrary precision mantissa part. However, its exponent part admits only an integer with a single word precision. Floating point operations will be performed all in bigfloat after activating the bigfloat switch by ctrl() command. The default precision is about 9 digits, which can be specified by setprec() command.

     [0] ctrl("bigfloat",1);
     1
     [1] eval(2^(1/2));
     1.414213562373095048763788073031
     [2] setprec(100);
     9
     [3] eval(2^(1/2));
     1.41421356237309504880168872420969807856967187537694807317654396116148

Function eval() evaluates numerically its argument as far as possible. Notice that the integer given for the argument of setprec() does not guarantee the accuracy of the result, but it indicates the representation size of numbers with which internal operations of PARI are performed. (See Section 6.1.10 [pari], page 41,Section 6.1.9 [eval], page 40)

4 complex number A complex number of Risa/Asir is a number with the form a+b*@i, where @i is the unit of imaginary number, and a and b are either a rational number, double float number or bigfloat number, respectively. The real part and the imaginary part of a complex number can be taken out by real() and imag() respectively.

3.3 Types of indeterminates

An algebraic object is recognized as an indeterminate when it can be a (so-called) variable in polynomials. An ordinary indeterminate is usually denoted by a string that start with a small alphabetical letter followed by an arbitrary number of alphabetical letters, digits or ‘_’. In addition to such ordinary indeterminates, there are other kinds of indeterminates in a wider sense in Asir. Such indeterminates in the wider sense have type polynomial, and further are classified into subtypes of the type indeterminate.

0 ordinary indeterminate An object of this sub-type is denoted by a string that start with a small alphabetical letter followed by an arbitrary number of alphabetical letters, digits or ‘_’. This kind of indeterminates are most commonly used for variables of polynomials.

     [0] [vtype(a),vtype(aA_12)];
     [0,0]

1 unknown coefficient The function uc() creates an indeterminate which is denoted by a string that begins with ‘_’. Such an indeterminate cannot be directly input by its name. Other properties are the same as those of ordinary indeterminate. Therefore, it has a property that it cannot cause collision with the name of ordinary indeterminates input by the user. And this property is conveniently used to create unknown coefficients dynamically by programs.

     [1] U=uc();
     _0
     [2] vtype(U);
     1

2 function form A function call to a built-in function or to an user defined function is usually evaluated by Asir and retained in a proper internal form. Some expressions, however, will remain in the same form after evaluation. For example, sin(x) and cos(x+1) will remain as if they were not evaluated. These (unevaluated) forms are called ‘function forms’ and are treated as if they are indeterminates in a wider sense. Also, special forms such as @pi the ratio of circumference and diameter, and @e Napier’s number, will be treated as ‘function forms.’

     [3] V=sin(x);
     sin(x)
     [4] vtype(V);
     2
     [5] vars(V^2+V+1);
     [sin(x)]

3 functor A function call (or a function form) has a form fname(args). Here, fname alone is called a functor. There are several kinds of functors: built-in functor, user defined functor and functor for the elementary functions. A functor alone is treated as an indeterminate in a wider sense.

     [6] vtype(sin);

4 User language Asir

Asir provides many built-in functions, which perform algebraic computations, e.g., factorization and GCD computation, file I/O, extract a part of an algebraic expression, etc. In practice, you will often encounter a specific problem for which Asir does not provide a direct solution. For such cases, you have to write a program in a certain user language. The user language for Asir is also called Asir. In the following, we describe the Syntax and then show how to write a user program by several examples.

4.1 Syntax — Difference from C language

The syntax of Asir is based on C language. Main differences are as follows. In this section, a variable does not mean an indeterminate, but a program variable which is written by a string which begins with a capital alphabetical letter in Asir.

• No types for variables. As is already mentioned, any object in Asir has their respective types.

A program variable, however, is type-less, that is, any typed object can be assigned to it.

         [0] A = 1;
         1
         [1] type(A);
         1
         [2] A = [1,2,3];
         [1,2,3]
         [3] type(A);
         4

• Variables, together with formal parameters, in a function (procedure) are all local to the function by default. Variables can be global at the top level, if they are declared with the key

    word extern.

Thus, the scope rule of Asir is very simple. There are only two types of variables: global variables and local variables. A name that is input to the Asir’s prompt at the top level is denotes a global variable commonly accessed at the top level. In a function (procedure) the following rules are applied.

1. If a variable is declared as global by an extern statement in a function, the variable used in that function denotes a global variable at the top level. Furthermore, if a variable in a function is preceded by an extern declaration outside the function but in a file where the function is defined, all the appearance of that variable in the same file denote commonly a global variable at the top level.

2. A variable in a function is local to that function, if it is not declared as global by an extern declaration.

     % cat afo
     def afo() { return A;}
     extern A$
     def bfo() { return A;}
     end$
     % asir
     [0] load("afo")$
     [5] A = 1;
     1
     [6] afo();
     0
     [7] bfo();
     1

• Program variables and algebraic indeterminates are distinguished in Asir. The names of program variables must begin with a capital letter; while the names of indeterminates and functions must begin with a small letter.

This is an unique point that differs from almost all other existing computer algebra systems. The distinction between program variables and indeterminates is adopted to avoid the possible and usual confusion that may arise in a situation where a name is used as an indeterminate but, as it was, the name has been already assigned some value. To use different type of letters, capital and small, was a matter of syntactical convention like Prolog, but it is convenient to distinguish variables and indeterminates in a program.

• No switch statements, and goto statements. Lack of goto statement makes it rather bothering to exit from within multiple loops.

• Comma expressions are allowed only in A, B and C of the constructs for (A;B;C) or while(A).

This limitation came from adopting lists as legal data objects for Asir.

The above are limitations; extensions are listed as follows.

• Arithmetic for rational expressions can be done in the same manner as is done for numbers in C language.

• Lists are available for data objects.

Lists are conveniently used to represent a certain collection of objects. Use of lists enables to write programs more easily, shorter and more comprehensible than use of structure like C programs.

4.2 Writing user defined functions

4.2.1 User defined functions

To define functions by an user himself, ‘def’ statement must be used. Syntactical errors are detected in the parsing phase of Asir, and notified with an indication of where Asir found the error. If a function with the same name is already defined (regardless to its arity,) the new definition will override the old one, and the user will be told by a message,

     afo() redefined.

on the screen. Recursive definition, and of course, recursive use of functions are available. A call for an yet undefined function in a function definition is not detected as an error. An error will be detected at execution of the call of that yet undefined function.

     /* X! */
     def f(X) {
         if ( !X )
             return 1;
         else
             return X * f(X-1);
     }

/* _{i}C_{j} ( 0 ≤ i ≤ N, 0 ≤ j ≤ i ) */

     def c(N)
     {
         A = newvect(N+1); A[0] = B = newvect(1); B[0] = 1;
         for ( K = 1; K <= N; K++ ) {
             A[K] = B = newvect(K+1); B[0] = B[K] = 1;
             for ( P = A[K-1], J = 1; J < K; J++ )
                 B[J] = P[J-1]+P[J];
             }
         return A;
     }

In the second example, c(N) returns a vector, say A, of length N+1. A[I] is a vector of length I+1, and each element is again a vector which contains _{I}C_{J} as its elements.

In the following, the manner of writing Asir programs is exhibited for those who have no experience in writing C programs.

4.2.2 variables and indeterminates

As is already described, program variables and indeterminates are strictly distinguished concept in Asir.

variables (program variables)

A program variable is a string that begins with a capital alphabetical letter followed by any numbers of alphabetical letters, digits and ‘_’.

A program variable is thought of a box (a carrier) which can contain Asir objects of various types. The content is called the ‘value’ of that variable. When an expression in a program is to be evaluated, the variable appearing in the expression is first replaced by its value and then the expression is evaluated to some value and stored in the memory. Thus, no program variable appears in objects in the internal form. All the program variables are initialized to the value 0.

     [0] X^2+X+1; /* X is initialized to the value 0 by default. */
     1
     [1] X=2;
     2
     [2] X^2+X+1;
     7

indeterminates

An indeterminate is a string that begins with a small alphabetical letter followed by any numbers of alphabetical letters, digits and ‘_’.

An indeterminate is a transcendental element, so-called variable, which is used to construct polynomial rings. An indeterminate cannot have any value. No assignment is allowed to it.

     [3] X=x;
     x
     [4] X^2+X+1;
     x^2+x+1

4.2.3 Parameters and Arguments

def sum(N) {
for ( I = 1, S = 0; I <= N; I++ )
   S += I;
return S;
}

This is an example definition of a function that sums up integers from 1 to N. The N in sum(N) is called the (formal) parameter of sum(N). The example shows a function of the single argument. In general, any number of parameters can be specified by separating by commas (‘,’). A (formal) parameter accepts a value given as an argument (or an actual parameter) at a function call of the function. Since the value of the argument is given to the formal parameter, any modification to the parameter does not usually affect the argument (or actual parameter). However, there are a few exceptions: vector arguments and matrix arguments.

Let A be a program variable and assigned to a vector value [ a, b ]. If A is given as an actual parameter to a formal parameter, say V, of a function, then an assignment in the function to the vector element designator V[1], say V[1]=c;, causes modification of the actual parameter A resulting A to have an altered value [ a c ]. Thus, if a vector is given to a formal parameter of a function, then its element (and subsequently the vector itself) in the calling side is modified through modification of the formal parameter by a vector element designator in the called function. The same applies to a matrix argument. Note that, even in such case where a vector (or a matrix) is given to a formal parameter, the assignment to the whole parameter itself has only a local effect within the function.

     def clear_vector(M) {
         /* M is expected to be a vector */
         L = size(M)[0];
         for ( I = 0; I < L; I++ )
             M[I] = 0;
     }

This function will clear off the vector given as its argument to the formal parameter M and return a 0 vector.

Passing a vector as an argument to a function enables returning multiple results by packing each result in a vector element. Another alternative to return multiple results is to use a list. Which to use depends on cases.

4.2.4 comments

The text enclosed by ‘/*’ and ‘*/’ (containing ‘/*’ and ‘*/’) is treated as a comment and has no effect to the program execution as in C programs.

     /*
      * This is a comment.

      */

A comment can span to several lines, but it cannot be nested. Only the first ‘/*’ is effective no matter how many ‘/*’’s in the subsequent text exist, and the comment terminates at the first ‘*/’.

In order to comment out a program part that may contain comments in it, use the pair, #if 0 and #endif. (See Section 4.2.10 [preprocessor], page 29)

     #if 0
     def bfo(X) {
     /* empty */
     }
     #endif

4.2.5 Statements

An user function of Asir is defined in the following form.

     def name(parameter, parameter,...,parameter) {
         statement
         statement
         ...
         statement
     }

As you can see, the statement is a fundamental element of the function. Therefore, in order to write a program, you have to learn what the statement is. The simplest statement is the simple statement. One example is an expression with a terminator (‘;’ or ‘$’.)

     S = sum(N);

A ‘return statement’ and ‘break statement’ are also primitives to construct ‘statements.’ As you can see the syntactic definition of ‘if statement’ and ‘for statement’, each of their bodies consists of a single ‘statement.’ Usually, you need several statements in such a body. To solve this contradictory requirement, you may use the ‘compound statement.’ A ‘compound statement’ is a sequence of ‘statement’s enclosed by a left brace ‘{’ and a right brace ‘}’. Thus, you can use multiple statement as if it were a single statement.

     if ( I == 0 ) {
         J = 1;
         K = 2;
         L = 3;
     }

No terminator symbol is necessary after ‘}’, because ‘{’ statement sequence ‘}’ already forms a statement, and it satisfies the syntactical requirement of the ‘if statement.’

4.2.6 return statement

There are two forms of return statement.

     return expression;
     return;

Both forms are used for exiting from a function. The former returns the value of the expression as a function value. The function value of the latter is not defined.

4.2.7 if statement

There are two forms of if statement.

     if ( expression )             if ( expression )
          statement       and           statement
     else
          statement

The interpretation of these forms are obvious. However, be careful when another if statement comes at the place for ‘statement’. Let us examine the following example.

     if ( expression1 )
         if ( expression2 ) statement1
     else
         statement2

One might guess statement2 after else corresponds with the first if ( expression1 ) by its appearance of indentation. But, as a matter of fact, the Asir parser decides that it correspond with the second if ( expression2 ). Ambiguity due to such two kinds of forms of if statement is thus solved by introducing a rule that a statement preceded by an else matches to the nearest preceding if.

Therefore, rearrangement of the above example for improving readability according to the actual interpretation gives the following.

     if ( expression1 ) {
         if ( expression2 ) statement1 else statement2
     }

On the other hand, in order to reflect the indentation, it must be written as the following.

     if ( expression1 ) {
         if ( expression2 ) statement1
     } else
         statement2

4.2.8 loop, break, return, continue

There are three kinds of statements for loops (repetitions): the while statement, the for statement, and the do statement.

• while statement

It has the following form.

         while ( expression ) statement

This statement specifies that statement is repeatedly evaluated as far as the expression evaluates to a non-zero value. If the expression 1 is given to the expression, it forms an infinite loop.

• for statement

It has the following form.

         for ( expression list-1; expression; expression list-2 ) statement

This is equivalent to the program

         expression list-1 (transformed into a sequence of simple statement)
         while ( expression ) {
             statement
             expression list-2 (transformed into a sequence of simple statement)
         }

• do statement

     do {
         statement
     } while ( expression )

This statement differs from while statement by the location of the termination condition: This statement first execute the statement and then check the condition, whereas while statement does it in the reverse order.

As means for exiting from loops, there are break statement and return statement. The continue statement allows to move the control to a certain point of the loop.

• break

The break statement is used to exit the inner most loop.

• return

The return statement is usually used to exit from a function call and it is also effective in a loop.

• continue

The continue statement is used to move the control to the end point of the loop body. For example, the last expression list will be evaluated in a for statement, and the termination condition will be evaluated in a while statement.

4.2.9 various expressions

Major elements to construct expressions are the followings.

• addition, subtraction, multiplication, division, exponentiation The exponentiation is denoted by ‘^’. (This differs from C language.) Division denoted by ‘/’ is used to operate in a field, for example, 2/3 results in a rational number 2/3. For integer division and polynomial division, both including remainder operation, built-in functions are provided.

     x+1  A^2*B*afo X/3

• (Programming) variables with indices An element of a vector, a matrix or a list can be referred to by indexing. Note that the indices begin with number 0. When the referred element is again a vector, a matrix or a list, repeated indexing is also effective.

     V[0] M[1][2]

• comparison operation There are comparison operations ‘==’ for equivalence, ‘!=’ for non-equivalence, ‘>’, ‘<’,‘>=’, and ‘<=’ for larger or smaller. The results of these operations are either value 1 for the truth, or 0 for the false.

• logical expression There are two binary logical operations ‘&&’ for logical ‘conjunction’(and), ‘||’ for logical ‘disjunction’(or), and one unary logical operation ‘!’ for logical ‘negation’(not). The results of these operations are either value 1 for the truth, and 0 for the false.

• Assignment Value assignment of a program variable is usually done by ‘=’. There are special assignments combined with arithmetic operations. (‘+=’, ‘-=’, ‘*=’, ‘/=’, ‘^=’)

     A = 2;
     A *= 3 (the same as A = A*3; The other combination operations are alike.)

• function call A function call is also an expression.

• ‘++’, ‘--’ These operators are attached to or before a program variable, and denote special operations and values.

     A++  the expression value is the previous value of A, and A = A+1
     A--  the expression value is the previous value of A, and A = A-1
     ++A  A = A+1, and the expression value is the value after increment of A
     --A  A = A-1, and the expression value is the value after decrement of A

4.2.10 preprocessor

The Asir user language imitates C language. A typical features of C language include macro expansion and file inclusion by the preprocessor cpp. Also, Asir read in user program files through cpp. This enables Asir user to use #include, #define, #if etc. in his programs.

• #include

Include files are searched within the same directory as the file containing #include so that no arguments are passed to cpp.

• #define

This can be used just as in C language.

• #if, #endif

This is conveniently used to comment out a large part of a user program that may contain comments by /* and */, because such comments cannot be nested. the followings are the macro definitions in the header part of Groebner basis package ‘gr’.

#define FIRST(L) (L[0])
#define SECOND(L) (L[1])
#define THIRD(L) (L[2])
#define FOURTH(L) (L[3])
#define FIFTH(L) (L[4])
#define HM(p) dp_hm(p)
#define RP(p) dp_rest(p)
#define HT(p) dp_ht(p)
#define CO(p) dp_hc(p)
#define TD(p) dp_td(p)
#define ZERO(p) (!(p))
#define LCM(l) THIRD(l)
#define CPSUGAR(l) FOURTH(l)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define CPUTIME (time()[0])

As in the above macro definition, naming the list element by macro’s is a good way to increase readability of the program in which lists are used instead of structures.

5 Debugger

5.1 What is Debugger

A debugger dbx is available for C programs on Sun, VAX etc. In dbx, one can use commands such as setting break-point on a source line, stepwise execution, inspecting a variable’s value etc. Asir provides such a dbx-like debugger. In order to enter the debug-mode, type debug; at the top level of Asir.

     [10] debug;
     (debug)

Asir also enters the debug-mode by the following means or in the following situations.

• When it reaches a break point while executing a program.

• When the ‘d’ option is selected at an interruption.

• When it detects errors while executing a program. In this case, to continue the execution of the program is impossible. But because it reports the statement in the user defined function that caused the error, then enters the debug-mode, user can inspect the values of variables at the error state. This helps to analyze the error and debug the program.

• When built-in function error() is called.

5.2 Debugger commands

Only indispensable commands of dbx are supported in the current version. Generally, the effect of a command is the same as that of dbx. There are, however, slight differences: Commands step and next execute the next statement, but not the next line; therefore, if there are multiple statements in one line, one should issue such commands several times to proceed the next line. The debugger reads in ‘.dbxinit’, which allows the same aliases as is used in dbx.

step Executes the next statement; if the next statement contains a function call, then enters

the function.

next Executes the next statement. cont Exits from the debug-mode and continues execution. list [startline] list function

Displays ten lines in a source file from startline, the current line if the startline is not specified, or from the top line of current target function.

print expr

Displays expr.

func function

Set the target function to function.

stop at sourceline [if cond] stop in function

Set a break-point at the sourceline-th line of the source file, or at the top of the target function. Break-points are removed whenever the relevant function is redefined. When if statements are repeatedly encountered, Asir enters debug-mode only when the corresponding cond parts are evaluated to a non-zero value.

delete n Remove the break point specified by a number n, which can be known by the status

command.

status Displays a list of the break-points. where Displays the calling sequence of functions from the top level through the current level.

(Current version sometimes reports incorrectly.)

quit Exits the debug-mode. The same effect as cont is in force when executing functions.

The debugger command print can take almost all expressions as its argument. The ordinary usage is to print the values of (programming) variables. However, the following usage is worth to remember.

• overwriting the variable One might sometimes wish to continue the execution with several values of variables modified. For such an purpose, take the following procedure.

         (debug) print A
         A = 2
         (debug) print A=1
         A=1 = 1
         (debug) print A
         A = 1

• function call

A function call is also an expression, therefore, it can appear at the argument place of print.

         (debug) print length(List)
         length(List) = 14

In this example, the length of the list assigned to the variable List is examined by a function

length().
(debug) print ctrl("cputime",1)
ctrl("cputime",1) = 1

This example shows such a usage where measuring CPU time is activated from within the debug-mode, even if one might have forgotten to specify the activation of CPU time measurement.

It is also useful to save intermediate results to files from within the debug-mode by the built-in function bsave() when one is forced to quit the computation by any reason.

(debug) print bsave(A,"savefile")
bsave(A,"savefile") = 1

Note that continuation of the parent function will be impossible if an error will occur in the function call from within the debug-mode.

• Displaying trace information

Though trace command is not implemented yet, one can let Asir automatically display the values of variables etc. by stop if command.

[51] debug$
(debug) list gb
194     def gb(F,M,SUBST)
195     {
196             NFMOD = 0;
197             if ( M ) {
198                     PSM = newvect(PSLen);
199                     for ( I = 0; I < PSLen; I++ )
200                             if ( PSH[I] && !validhc(PS[I],M,SUBST) )
201                                     return 0;
202                             else
203                                     PSM[I] = dp_mod(PS[I],M,SUBST);
(debug) stop at 203 if (print(PSH[I]))
(0) stop at "/usr/local/lib/asir/gr":203 if  (print(PSH[I]))
(debug) quit
[52] grm(cyclic(5),[c0,c1,c2,c3,c4]);
(1)*<<1,1,1,1,1>>
(1)*<<1,1,1,1,0>>
(1)*<<1,1,1,0,0>>

Because the print() function always returns a value 0, the conditional expression of the debugger command if never becomes true, but print() is always executed leaving the value of PSH[I] displayed whenever the control passes through the break point.

5.3 Execution example of debugger

Here, the usage of the Debugger is explained by showing an example for debugging a program which computes the integer factorial by a recursive definition.

% asir
[0] load("fac")$
[3] debug$
(debug) list factorial
1   def factorial(X) {
2       if ( !X )
3           return 1;
4       else
5           return X * factorial(X - 1);
6   }
7   end$
(debug) stop at 5                     <-- setting a break point
(0) stop at "./fac":5
(debug) quit                          <-- leaving the debug-mode
[4] factorial(6);                     <-- call for factorial(6)
stopped in factorial at line 5 in file "./fac"
5           return X * factorial(X - 1);
(debug) where                         <-- display the calling sequence up to
factorial(), line 5 in "./fac"            this break point
(debug) print X                       <-- Display the value of X
X = 6
(debug) step                          <-- step execution (enters function)
stopped in factorial at line 2 in file "./fac"
2 if ( !X )
(debug) where
factorial(), line 2 in "./fac"
factorial(), line 5 in "./fac"
(debug) print X
X = 5
(debug) delete 0                      <-- delete the break point 0
(debug) cont                          <-- continue execution
720                                   <-- result = 6!
[5] quit;

5.4 Sample file of initialization file for Debugger

As is previously mentioned, Asir reads in the file ‘$HOME/.dbxinit’ at its invocation. This file is originally used to define various initializing commands for dbx debugger, but Asir recognizes only alias lines. For example, by the setting

% cat ~/.dbxinit
alias n next
alias c cont
alias p print
alias s step
alias d delete
alias r run
alias l list
alias q quit

one can use short aliases, e.g., p, c etc., for frequently used commands such as print, cont etc.

[100] grm(La,[a,b,c]);
[M,99999989,EVAL,[]]
stopped in gb at line 196 in file "/usr/local/lib/asir/gr"
196             NFMOD = 0;
(debug) p F
F = [0,1,2]
(debug) c
[1,2,NFT,0.01,NB,2,NAB,4,RP,2,(1)*<<1,3,1>>]

6 Built-in Function

6.1 Numbers

6.1.1 idiv, irem
idiv(i1,i2)

:: Integer quotient of i1 divided by i2.

irem(i1,i2)

:: Integer remainder of i1 divided by i2.

return integer i1,i2 integer

• Integer quotient and remainder of i1 divided by i2.

• i2 must not be 0.

• If the dividend is negative, the results are obtained by changing the sign of the results for absolute values of the dividend.

• One can use i1 % i2 for replacement of irem() which only differs in the point that the result is always normalized to non-negative values.

• Use sdiv(), srem() for polynomial quotient.

[0] idiv(100,7);
14
[0] idiv(-100,7);
-14
[1] irem(100,7);
2
[1] irem(-100,7);
-2
References
     sdiv, srem, %

6.1.2 fac

fac(i) :: The factorial of i. return integer i integer

• The factorial of i.

• Returns 0 if the argument i is negative.

     [0] fac(50);
     30414093201713378043612608166064768844377641568960512000000000000

6.1.3 igcd

igcd(i1,i2)

:: The integer greatest common divisor of i1 and i2.

return integer i1,i2 integer

• Function igcd() returns the integer greatest common divisor of the given two integers.

• An error will result if the argument is not an integer; the result is not valid even if one is returned.

• Use gcd(), gcdz() for polynomial GCD.

     [0] igcd(12,8);
     4
References
          gcd, gcdz

6.1.4 inv

inv(i,m) :: the inverse (reciprocal) of i modulo m. return integer

i,m integer

• This function computes an integer such that ia ≡ 1 mod (m).

• The integer i and m must be mutually prime. However, inv() does not check it.

[71] igcd(1234,4321);
1
[72] inv(1234,4321);
3239
[73] irem(3239*1234,4321);
1

References
     igcd

6.1.5 prime, lprime

prime(index)
lprime(index)

:: Returns a prime number.

return integer

index integer

• The two functions, prime() and lprime(), returns an element stored in the system table of prime numbers. Here, index is a non-negative integer and be used as an index for the prime tables. The function prime() can return one of 1229 primes which are at most 4 digit sized and indexed so that the smaller one has smaller index. The function lprime() can return one of 999 primes which are 8 digit sized and indexed so that the larger one has the smaller index. The two function always returns 0 for other indices.

• For more general function for prime generation, there is a PARI function pari(nextprime,number).

[95] prime(0);
2
[96] prime(1228);
9973
[97] lprime(0);
99999989

     [98] lprime(999);
     0
References
          pari
6.1.6 random

random() :: Generates random numbers. return integer

• Generates a sequence of random numbers, one at each call, over an integer interval from 0 to 134217727 (= 2^27-1).

• This is only available for UNIX version.

6.1.7 nm, dn

nm(rat) :: Numerator of a rational expression rat. dn(rat) :: Denominator of a rational expression rat. return integer or polynomial rat rational number or rational expression

• Numerator and denominator of a given rational expression.

• For a rational number, they return its numerator and denominator, respectively. For a rational expression whose numerator and denominator may contain rational numbers, they do not separate those rational coefficients to numerators and denominators.

• For a rational number, the denominator is always kept positive, and the sign is contained in the numerator.

• Risa/Asir does not cancel the common divisors unless otherwise explicitly specified by the user. Therefore, nm() and dn() return the numerator and the denominator as it is, respectively.

     [2] [nm(-43/8),dn(-43/8)];
     [-43,8]
     [3] dn((x*z)/(x*y));

     y*x
     [3] dn(red((x*z)/(x*y)));
     y
References
          red

6.1.8 conj, real, imag
real(comp)

:: Real part of comp.

imag(comp)

:: Imaginary part of comp.

conj(comp)

:: Complex conjugate of comp.

return, comp complex number

• Basic operations for complex numbers.

• These functions works also for polynomials with complex coefficients.

     [111] A=(2+@i)^3;
     (2+11*@i)
     [112] [real(A),imag(A),conj(A)];
     [2,11,(2-11*@i)]

6.1.9 eval

eval(obj[,prec])

:: Evaluate obj numerically.

return number or expression obj general expression prec integer • Evaluates the value of the functions contained in obj as far as possible.

• The computation is done by PARI (See Section 6.1.10 [pari], page 41).

• When prec is specified, computation will be performed with a precision of about prec-digits. If prec is not specified, computation is performed with the precision set currently. (See Section 6.1.11 [setprec], page 43)

• Currently available numerical functions are listed below. Note they are only a small part of

whole PARI functions.

         sin, cos, tan,
         asin, acos, atan,
         sinh, cosh, tanh,
         asinh, acosh, atanh,
         exp, log, pow(a,b) (a^b)

• Symbols for special values are as the followings.

@i unit of imaginary number @pi the number pi, the ratio of circumference to diameter @e Napier’s number (exp(1))

[118] eval(exp(@pi*@i));
-1.0000000000000000000000000000
[119] eval(2^(1/2));
1.414213562373095048763788073031
[120] eval(sin(@pi/3));
0.86602540378443864674620506632
[121] eval(sin(@pi/3)-3^(1/2)/2,50);
-2.78791084448179148471 E-58
References
     ctrl, setprec, pari

6.1.10 pari

pari(func,arg,prec)

:: Call PARI function func.

return Depends on func. func Function name of PARI. arg Arguments of func. prec integer

• This command connects Asir to PARI system so that several functions of PARI can be conveniently used from Risa/Asir.

• PARI [Batut et al.] is developed at Bordeaux University, and distributed as a free software. Though it has a certain facility to computer algebra, its major target is the operation of numbers (bignum, bigfloat) related to the number theory. It facilitates various function evaluations as well as arithmetic operations at a remarkable speed. It can also be used from other external programs as a library. It provides a language interface named ‘gp’ to its library, which enables a user to use PARI as a calculator which runs on UNIX. The current version is 1.38. It can be obtained by several ftp sites. (For example, megrez.ceremab.u-bordeaux.fr,

math.ucla.edu:/pub/pari)

• The last argument (optional) int specifies the precision in digits for bigfloat operation. If the precision is not explicitly specified, operation will be performed with the precision set by

setprec().

• Currently available functions of PARI system are as follows. Note these are only a part of functions in PARI system. For details of individual functions, refer to the PARI manual. (Some of them can be seen in the following example.)

abs, adj, arg, bigomega, binary, ceil, centerlift, cf, classno, classno2, conj, content,
denom, det, det2, detr, dilog, disc, discf, divisors, eigen, eintg1, erfc, eta, floor,
frac, galois, galoisconj, gamh, gamma, hclassno, hermite, hess, imag, image, image2,
indexrank, indsort, initalg, isfund, isprime, ispsp, isqrt, issqfree, issquare,
jacobi, jell, ker, keri, kerint, kerintg1, kerint2, kerr, length, lexsort, lift,
lindep, lll, lllg1, lllgen, lllgram, lllgramg1, lllgramgen, lllgramint, lllgramkerim,
lllgramkerimgen, lllint, lllkerim, lllkerimgen, lllrat, lngamma, logagm, mat, matinvr,
matrixqz2, matrixqz3, matsize, modreverse, mu, nextprime, norm, norml2, numdiv, numer,
omega, order, ordred, phi, pnqn, polred, polred2, primroot, psi, quadgen, quadpoly,
real, recip, redcomp, redreal, regula, reorder, reverse, rhoreal, roots, rootslong,
round, sigma, signat, simplify, smalldiscf, smallfact, smallpolred, smallpolred2,
smith, smith2, sort, sqr, sqred, sqrt, supplement, trace, trans, trunc, type, unit, vec,
wf, wf2, zeta

• Asir currently uses only a very small subset of PARI. We will improve Asir so that it can provide more functions of PARI.

 /* Eigen vectors of a numerical matrix */
 [0] pari(eigen,newmat(2,2,[[1,1],[1,2]]));
 [ -1.61803398874989484819771921990 0.61803398874989484826 ]
 [ 1 1 ]
 /* Roots of a polynomial */
 [1] pari(roots,t^2-2);
 [ -1.41421356237309504876 1.41421356237309504876 ]

References
          setprec

6.1.11 setprec
setprec([n])

:: Sets the precision for bigfloat operations to n digits.

return integer n integer

• When an argument is given, it sets the precision for bigfloat operations to n digits. The return value is always the previous precision in digits regardless of the existence of an argument.

• Bigfloat operations are done by PARI. (See Section 6.1.10 [pari], page 41)

• This is effective for computations in bigfloat. Refer to ctrl() for turning on the ‘bigfloat flag.’ • There is no upper limit for precision digits. It sets the precision to some digits around the

specified precision. Therefore, it is safe to specify a larger value.

     [1] setprec();
     9
     [2] setprec(100);
     9
     [3] setprec(100);
     96
References
          ctrl, eval, pari

6.2 operations with polynomials and rational expressions

6.2.1 var

var(rat) :: Main variable (indeterminate) of rat.

return indeterminate rat rational expression

• See Section 3.1 [Types in Asir], page 14 for main variable.

• Indeterminates (variables) are ordered by default as follows.

x, y, z, u, v, w, p, q, r, s, t, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o. The other variables will be ordered after the above noted variables so that the first comer will be ordered prior to the followers.

[0] var(x^2+y^2+a^2);
x
[1] var(a*b*c*d*e);
a
[2] var(3/abc+2*xy/efg);
abc

References
     ord, vars

6.2.2 vars

vars(obj) :: A list of variables (indeterminates) in an expression obj.

return list

obj arbitrary

• Returns a list of variables (indeterminates) contained in a given expression.

• Lists variables according to the variable ordering.

[0] vars(x^2+y^2+a^2);
[x,y,a]
[1] vars(3/abc+2*xy/efg);
[abc,xy,efg]
[2] vars([x,y,z]);
[x,y,z]

References
     var, uc, ord

6.2.3 uc

uc() :: Create a new indeterminate.

return kernel (indeterminate) with its vtype 1.

• At every evaluation of command uc(), a new indeterminate in the sequence of indeterminates _0, _1, _2, … is created successively.

• Indeterminates created by uc() cannot be input on the keyboard. By this property, you are free, no matter how many indeterminates you will create dynamically by a program, from collision of created names with indeterminates input from the keyboard or from program files.

• Functions, rtostr() and strtov(), are used to create ordinary indeterminates (indeterminates having 0 for their vtype).

• Kernel sub-type of indeterminates created by uc() is 1. (vtype(uc())=1)

     [0] A=uc();
     _0
     [1] B=uc();
     _1
     [2] (uc()+uc())^2;
     _2^2+2*_3*_2+_3^2
     [3] (A+B)^2;
     _0^2+2*_1*_0+_1^2
References
          vtype, rtostr, strtov

6.2.4 coef

coef(poly,deg[,var])

:: The coefficient of a polynomial poly at degree deg with respect to the variable var (main variable if unspecified).

return polynomial poly polynomial var indeterminate deg non-negative integer • The coefficient of a polynomial poly at degree deg with respect to the variable var.

• The default value for var is the main variable, i.e., var(poly).

• For multi-variate polynomials, access to coefficients depends on the specified indeterminates. For example, taking coef for the main variable is much faster than for other variables.

[0] A = (x+y+z)^3;
x^3+(3*y+3*z)*x^2+(3*y^2+6*z*y+3*z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
[1] coef(A,1,y);
3*x^2+6*z*x+3*z^2
[2] coef(A,0);
y^3+3*z*y^2+3*z^2*y+z^3

References
     var, deg

6.2.5 deg, mindeg

deg(poly,var)

:: The degree of a polynomial poly with respect to variable.

mindeg(poly,var)

:: The least exponent of the terms with non-zero coefficients in a polynomial poly with respect to the variable var. In this manual, this quantity is sometimes referred to the minimum degree of a polynomial for short.

return non-negative integer

poly polynomial

var indeterminate

• The least exponent of the terms with non-zero coefficients in a polynomial poly with respect to the variable var. In this manual, this quantity is sometimes referred to the minimum degree of a polynomial for short.

• Variable var must be specified.

[0] deg((x+y+z)^10,x);
10
[1] deg((x+y+z)^10,w);
0
[75] mindeg(x^2+3*x*y,x);

6.2.6 nmono
nmono(rat)

:: Number of monomials in rational expression rat.

return non-negative integer rat rational expression

• Number of monomials with non-zero number coefficients in the full expanded form of the given polynomial.

• For a rational expression, the sum of the numbers of monomials of the numerator and denominator.

• A function form is regarded as a single indeterminate no matter how complex arguments it has.

     [0] nmono((x+y)^10);
     11
     [1] nmono((x+y)^10/(x+z)^10);
     22
     [2] nmono(sin((x+y)^10));
     1
References
          vtype

6.2.7 ord

ord([varlist])

:: It sets the ordering of indeterminates (variables).

return list of variables (indeterminates) varlist list of variables (indeterminates)

• When an argument is given, this function rearranges the ordering of variables (indeterminates) so that the indeterminates in the argument varlist precede and the other indeterminates follow in the system’s variable ordering. Regardless of the existence of an argument, it always returns the final variable ordering.

• Note that no change will be made to the variable ordering of internal forms of objects which already exists in the system, no matter what reordering you specify. Therefore, the reordering should be limited to the time just after starting Asir, or to the time when one has decided himself to start a totally new computation which has no relation with the previous results. Note that unexpected results may be obtained from operations between objects which are created under different variable ordering.

[0] ord();
[x,y,z,u,v,w,p,q,r,s,t,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,_z,_u,_v,_w,_p,
_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,exp(_x),(_x)^(_y),
log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),(-_x^2+1)^(-1/2),cosh(_x),sinh(_x),
tanh(_x),(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]
[1] ord([dx,dy,dz,a,b,c]);
[dx,dy,dz,a,b,c,x,y,z,u,v,w,p,q,r,s,t,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,_z,_u,_v,
_w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,exp(_x),
(_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),(-_x^2+1)^(-1/2),
cosh(_x),sinh(_x),tanh(_x),(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]

6.2.8 sdiv, srem, sqr

sdiv(poly1,poly2)

:: Quotient of poly1 divided by poly2 provided that the division can be performed within polynomial arithmetic over the rationals.

srem(poly1,poly2)

:: Remainder of poly1 divided by poly2 provided that the division can be performed within polynomial arithmetic over the rationals.

sqr(poly1,poly2)

:: Quotient and remainder of poly1 divided by poly2 provided that the division can be performed within polynomial arithmetic over the rationals.

return  sdiv(), srem() : polynomial, sqr() : a list [quotient,remainder]

poly1 poly2 polynomial

• Regarding poly1 as an uni-variate polynomial in the main variable of poly2, i.e. var(poly2), sdiv() and srem() compute the polynomial quotient and remainder of poly1 divided by poly2.

• Division operation of polynomials is performed by the following steps: (1) obtain the quotient of leading coefficients; let it be Q; (2) remove the leading term of poly1 by subtracting, from poly1, the product of Q with some powers of main variable and poly2; obtain a new poly1; (3) repeat the above step until the degree of poly1 become smaller than that of poly2. For fulfillment, by operating in polynomials, of this procedure, the divisions at step (1) in every repetition must be an exact division of polynomials. This is the true meaning of what we say “division can be performed within polynomial arithmetic over the rationals.”

• There are typical cases where the division is possible: leading coefficient of poly2 is a rational number; poly2 is a factor of poly1.

• Use sqr() to get both the quotient and remainder at once.

• Use idiv(), irem() for integer quotient.

• For remainder operation on all integer coefficients, use %.

• These functions shall be improved to support divisions for an arbitrary specified main variable.

[0] sdiv((x+y+z)^3,x^2+y+a);
x+3*y+3*z
[1] srem((x+y+z)^2,x^2+y+a);
(2*y+2*z)*x+y^2+(2*z-1)*y+z^2-a
[2] X=(x+y+z)*(x-y-z)^2;
x^3+(-y-z)*x^2+(-y^2-2*z*y-z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
[3] Y=(x+y+z)^2*(x-y-z);
x^3+(y+z)*x^2+(-y^2-2*z*y-z^2)*x-y^3-3*z*y^2-3*z^2*y-z^3
[4] G=gcd(X,Y);
x^2-y^2-2*z*y-z^2
[5] sqr(X,G);
[x-y-z,0]
[6] sqr(Y,G);
[x+y+z,0]
[7] sdiv(y*x^3+x+1,y*x+1);
divsp: cannot happen
return to toplevel

References
     idiv, irem, %

6.2.9 tdiv

tdiv(poly1,poly2)

:: Tests whether poly2 divides poly1.

return Quotient if poly2 divides poly1, 0 otherwise.

poly1 poly2

polynomial • Tests whether poly2 divides poly1 in polynomial ring.

• One application of this function: Consider the case where a polynomial is certainly an irreducible factor of the other polynomial, but the multiplicity of the factor is unknown. Application of tdiv() to the polynomials repeatedly yields the multiplicity.

[11] Y=(x+y+z)^5*(x-y-z)^3;
x^8+(2*y+2*z)*x^7+(-2*y^2-4*z*y-2*z^2)*x^6+(-6*y^3-18*z*y^2-18*z^2*y-6*z^3)*x^5
+(6*y^5+30*z*y^4+60*z^2*y^3+60*z^3*y^2+30*z^4*y+6*z^5)*x^3+(2*y^6+12*z*y^5
+30*z^2*y^4+40*z^3*y^3+30*z^4*y^2+12*z^5*y+2*z^6)*x^2+(-2*y^7-14*z*y^6
-42*z^2*y^5-70*z^3*y^4-70*z^4*y^3-42*z^5*y^2-14*z^6*y-2*z^7)*x-y^8-8*z*y^7
-28*z^2*y^6-56*z^3*y^5-70*z^4*y^4-56*z^5*y^3-28*z^6*y^2-8*z^7*y-z^8
[12] for(I=0,F=x+y+z,T=Y; T=tdiv(T,F); I++);
[13] I;
5

References
     sdiv, srem

6.2.10 %

poly % m :: integer remainder to all integer coefficients of the polynomial.

return integer or polynomial

poly integer or polynomial with integer coefficients

m integer

• Returns a polynomial whose coefficients are remainders of the coefficients of the input polynomial divided by m.

• The resulting coefficients are all normalized to non-negative integers.

• An integer is allowed for poly. This can be used for an alternative for irem() except that the result is normalized to a non-negative integer.

• Coefficients of poly and m must all be integers, though the type checking is not done.

[0] (x+2)^5 % 3;
x^5+x^4+x^3+2*x^2+2*x+2
[1] (x-2)^5 % 3;
x^5+2*x^4+x^3+x^2+2*x+1
[2] (-5) % 4;
3
[3] irem(-5,4);

-1
References
     irem

6.2.11 subst, psubst
subst(rat[,varn,ratn]*)
psubst(rat[,var,rat]*)

:: Substitute ratn for varn in expression rat. (n=1,2,. . .. Substitution will be done successively from left to right if arguments are repeated.)

return rational expression rat,ratn rational expression varn indeterminate

• Substitutes rational expressions for specified kernels in a rational expression.

• subst(rat,var1,rat1,var2,rat2,…) has the same effect as subst(subst(rat,var1,rat1),var2,rat2,…).

• Note that repeated substitution is done from left to right successively. You may get different result by changing the specification order.

• Ordinary subst() performs substitution at all levels of a scalar algebraic expression creeping into arguments of function forms recursively. Function psubst() regards such a function form as an independent indeterminate, and does not attempt to apply substitution to its arguments. (The name comes after Partial SUBSTitution.)

• Since Asir does not reduce common divisors of a rational expression automatically, substitution of a rational expression to an expression may cause unexpected increase of computation time. Thus, it is often necessary to write a special function to meet the individual problem so that the denominator and the numerator do not become too large.

• The same applies to substitution by rational numbers.

[0] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2);
x^3-6*x^2+12*x-8
[1] subst(@@,x,-1);
-27
[2] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2,x,-1);
-27
[3] subst(x*y^3,x,y,y,x);
x^4

[4] subst(x*y^3,y,x,x,y);
y^4
[5] subst(x*y^3,x,t,y,x,t,y);
y*x^3
[6] subst(x*sin(x),x,t);
sin(t)*t
[7] psubst(x*sin(x),x,t);
sin(x)*t

6.2.12 diff

diff(rat[,varn]*)

diff(rat,varlist)

:: Differentiate rat successively by var’s for the first form, or by variables in varlist for the second form.

return expression

rat rational expression which contains elementary functions.

varn indeterminate

varlist list of indeterminates

• Differentiate rat successively by var’s for the first form, or by variables in varlist for the second form.

• differentiation is performed by the specified indeterminates (variables) from left to right. diff(rat,x,y) is the same as diff(diff(rat,x),y).

[0] diff((x+2*y)^2,x);
2*x+4*y
[1] diff((x+2*y)^2,x,y);
4
[2] diff(x/sin(log(x)+1),x);
(sin(log(x)+1)-cos(log(x)+1))/(sin(log(x)+1)^2)
[3] diff(sin(x),[x,x,x,x]);
sin(x)

6.2.13 res

res(var,poly1,poly2)

:: Resultant of poly1 and poly2 with respect to var. return polynomial var indeterminate poly1,poly2

polynomial

• Resultant of two polynomials poly1 and poly2 with respect to var.

• Sub-resultant algorithm is used to compute the resultant.

[0] res(t,(t^3+1)*x+1,(t^3+1)*y+t);
-x^3-x^2-y^3

6.2.14 fctr, sqfr
fctr(poly)

:: Factorize polynomial poly over the rationals.

sqfr(poly)

:: Gets a square-free factorization of polynomial poly.

return list poly polynomial with rational coefficients

• Factorizes polynomial poly over the rationals. fctr() for irreducible factorization; sqfr() for square-free factorization.

• The result is represented by a list, whose elements are a pair represented as [[num,1],[factor,multiplicity],...].

• Products of all factor^multiplicity and num is equal to poly.

• The number num is determined so that (poly/num) is an integral polynomial and its content (GCD of all coefficients) is 1. (See Section 6.2.16 [ptozp], page 55.)

[0] fctr(x^10-1);
[[1,1],[x-1,1],[x+1,1],[x^4+x^3+x^2+x+1,1],[x^4-x^3+x^2-x+1,1]]
[1] fctr(x^3+y^3+(z/3)^3-x*y*z);
[[1/27,1],[9*x^2+(-9*y-3*z)*x+9*y^2-3*z*y+z^2,1],[3*x+3*y+z,1]]
[2] A=(a+b+c+d)^2;
a^2+(2*b+2*c+2*d)*a+b^2+(2*c+2*d)*b+c^2+2*d*c+d^2
[3] fctr(A);
[[1,1],[a+b+c+d,2]]
[4] A=(x+1)*(x^2-y^2)^2;
x^5+x^4-2*y^2*x^3-2*y^2*x^2+y^4*x+y^4

[5] sqfr(A);
[[1,1],[x+1,1],[-x^2+y^2,2]]
[6] fctr(A);
[[1,1],[x+1,1],[-x-y,2],[x-y,2]]

References
     ufctrhint

6.2.15 ufctrhint

ufctrhint(poly,hint)

:: Factorizes uni-variate polynomial poly over the rational number field when the degrees of its factors are known to be some integer multiples of hint.

return list

poly uni-variate polynomial with rational coefficients

hint non-negative integer

• By any reason, if the degree of all the irreducible factors of poly is known to be some multiples of hint, factors can be computed more efficiently by the knowledge than fctr().

• When hint is 1, ufctrhint() is the same as fctr() for uni-variate polynomials. An typical application where ufctrhint() is effective: Consider the case where poly is a norm (See Chapter 8 [Algebraic numbers], page 104) of a certain polynomial over an extension field with its extension degree d, and it is square free; Then, every irreducible factor has a degree that is a multiple of d.

[10] A=t^9-15*t^6-87*t^3-125;
t^9-15*t^6-87*t^3-125
0msec
[11] N=res(t,subst(A,t,x-2*t),A);
-x^81+1215*x^78-567405*x^75+139519665*x^72-19360343142*x^69+1720634125410*x^66
-88249977024390*x^63-4856095669551930*x^60+1999385245240571421*x^57
-15579689952590251515*x^54+15956967531741971462865*x^51
...
+140395588720353973535526123612661444550659875*x^6
+10122324287343155430042768923500799484375*x^3
+139262743444407310133459021182733314453125
980msec + gc : 250msec
[12] sqfr(N);
[[-1,1],[x^81-1215*x^78+567405*x^75-139519665*x^72+19360343142*x^69
-1720634125410*x^66+88249977024390*x^63+4856095669551930*x^60

-1999385245240571421*x^57+15579689952590251515*x^54
...
-10122324287343155430042768923500799484375*x^3
-139262743444407310133459021182733314453125,1]]
20msec
[13] fctr(N);
[[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
[x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
+296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
[x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
[x^18+10773*x^12+2784051*x^6+307546875,1]]
167.050sec + gc : 1.890sec
[14] ufctrhint(N,9);
[[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
[x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
+296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
[x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3+31524548679,1],
[x^18+10773*x^12+2784051*x^6+307546875,1]]
119.340sec + gc : 1.300sec

References
     fctr

6.2.16 ptozp

ptozp(poly)

:: Converts a polynomial poly with rational coefficients to an integral polynomial such that GCD of all its coefficients is 1.

return polynomial

poly polynomial

• Converts the given polynomial by multiplying some rational number to an integral polynomial such that GCD of all its coefficients is 1.

• In general, operations on polynomials can be performed faster for integer coefficients than for rational number coefficients. Therefore, this function is conveniently used to improve efficiency.

• Function red does not convert rational coefficients of the numerator. You cannot obtain an integral polynomial by direct use of the function nm(). The function nm() returns the numerator of its argument, and a polynomial with rational coefficients is the numerator of itself and will be returned as it is.

[0] ptozp(2*x+5/3);
6*x+5
[1] nm(2*x+5/3);
2*x+5/3

References
     nm, dn

6.2.17 prim, cont

prim(poly)

:: Primitive part of poly.

cont(poly)

:: Content of poly.

return poly

polynomial with rational coefficients

• The primitive part and the content of a polynomial poly with respect to its main variable.

• Specification of the main variable is not available in the current implementation. In order to obtain the primitive part and the content with respect to an indeterminate not being the main variable, take the following.

First, examine by ord() the current variable ordering. Then, obtain a new polynomial in which variables are replaced by subst() so that the variable of your interest become highest in the ordering. Compute the primitive part and/or the content of the new polynomial. Then, replace back the variables of the result.

• These functions shall be improved to support computation for an arbitrary specified main variable.

[0] E=(y-z)*(x+y)*(x-z)*(2*x-y);
(2*y-2*z)*x^3+(y^2-3*z*y+2*z^2)*x^2+(-y^3+z^2*y)*x+z*y^3-z^2*y^2
[1] prim(E);
2*x^3+(y-2*z)*x^2+(-y^2-z*y)*x+z*y^2
[2] cont(E);
y-z
[3] subst(prim(subst(E,x,w,z,x)),x,z,w,x);
(y-z)*x-z*y+z^2

References
          var, ord

6.2.18 gcd, gcdz

gcd(poly1,poly2) gcdz(poly1,poly2)

:: The polynomial greatest common divisor of poly1 and poly2.

return polynomial poly1,poly2

polynomial

• Functions gcd() and gcdz() return the greatest common divisor (GCD) of the given two polynomials. Function gcd() returns an integral polynomial GCD over the rational number field. The coefficients are normalized such that their GCD is 1. It returns 1 in case that the given polynomials are mutually prime. Function gcdz() works for arguments of integral polynomials, and returns a polynomial GCD over the integer ring, that is, it returns gcd() multiplied by the contents of all coefficients of the two input polynomials.

• Polynomial GCD is computed by an improved algorithm based on Extended Zassenhaus algorithm.

     [0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
     x^3+3*x^2+3*x+1
     [0] gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
     6*x^3+18*x^2+18*x+6
References
          igcd

6.2.19 red

red(rat) :: Reduced form of rat by canceling common divisors.

return rational expression rat rational expression • Asir automatically performs cancellation of common divisors of rational numbers. But, without

an explicit command, it does not cancel common polynomial divisors of rational expressions. (Reduction of rational expressions to a common denominator will be always done.) Use command red() to perform this cancellation.

• Cancel the common divisors of the numerator and the denominator of a rational expression rat by computing their GCD.

• The denominator polynomial of the result is an integral polynomial which has no common divisors in its coefficients, while the numerator may have rational coefficients.

• Since GCD computation is a very hard operation, it is desirable to detect and remove by any means common divisors as far as possible. Furthermore, a call to this function after swelling of the denominator and the numerator shall usually take a very long time. Therefore, often, to some extent, reduction of common divisors is inevitable for operations of rational expressions.

[0] (x^3-1)/(x-1);
(x^3-1)/(x-1)
[1] red((x^3-1)/(x-1));
x^2+x+1
[2] red((x^3+y^3+z^3-3*x*y*z)/(x+y+z));
x^2+(-y-z)*x+y^2-z*y+z^2
[3] red((3*x*y)/(12*x^2+21*y^3*x));
(y)/(4*x+7*y^3)
[4] red((3/4*x^2+5/6*x)/(2*y*x+4/3*x));
(9/8*x+5/4)/(3*y+2)
References
     nm, dn, gcd, ptozp

6.3 Lists

6.3.1 car, cdr, cons, append, reverse, length

car(list) :: The first element of the given non-null list list. cdr(list) :: A list obtained by removing the first element of the given non-null list list.

cons(obj,list)

:: A list obtained by adding an element obj to the top of the given list list.

append(list1,list2)

:: A list obtained by adding all elements in the list list2 according to the order as it is to the last element in the list list1.

reverse(list)

:: reversed list of list

length(list)

:: Number of elements in a list list.

return  car() : arbitrary, cdr(), cons(), append(), reverse() : list, length() : non-negative

integer

list,list1,list2

list

obj arbitrary

• A list is written in Asir as [obj1,obj2,…]. Here, obj1 is the first element.

• Function car() outputs the first element of a non-null list. For a null list, the result should be undefined. In the current implementation, however, it outputs a null list. This treatment for a null list may subject to change in future, and users are suggested not to use the tentative treatment for a null list for serious programming.

• Function cdr() outputs a list obtained by removing the first element from the input non-null list. For a null list, the result should be undefined. In the current implementation, however, it outputs a null list. This treatment for a null list may subject to change in future, and users are suggested not to use the tentative treatment for a null list for serious programming.

• Function cons() composes a new list from the input list list and an arbitrary object obj by adding obj to the top of list.

• Function append() composes a new list, which has all elements of list1 in the same ordering followed by all elements of list2 in the same ordering.

• Function reverse() returns a reversed list of list.

• Function length() returns a non-negative integer which is the number of elements in the input list list. Note that function size should be used for counting elements of vector and matrix.

• Lists are read-only objects in Asir. There elements cannot be modified.

• The n-th element in a list can be referred to by applying the function cdr() n times repeatedly and cdr() at last. A more convenient way to access to the n-th element is the use of bracket notation, that is, to attach an index [n] like vectors and matrices. The system, however, follow the n pointers to access the desired element. Subsequently, much time is spent for an element located far from the top of the list.

• Function cdr() does not create a new cell (a memory quantity). Function append(), as a matter of fact, repeats cons() for as many as the length of list1 the first argument. Subsequently, append() consumes much memory space if its first argument is long. Similar argument applies to function reverse().

[0] L = [[1,2,3],4,[5,6]];
[[1,2,3],4,[5,6]]
[1] car(L);
[1,2,3]
[2] cdr(L);
[4,[5,6]]
[3] cons(x*y,L);
[y*x,[1,2,3],4,[5,6]]
[4] append([a,b,c],[d]);
[a,b,c,d]
[5] reverse([a,b,c,d]);
[d,c,b,a]
[6] length(L);
3
[7] L[2][0];
5

6.4 Arrays

6.4.1 newvect

newvect(len[,list])

:: Creates a new vector object with its length len.

return vector

len non-negative integer

list list

• Creates a new vector object with its length len and its elements all cleared to value 0. If the second argument, a list, is given, the vector is initialized by the list elements. Elements are used from the first through the last. If the list is short for initializing the full vector, 0’s are filled in the remaining vector elements.

• Elements are indexed from 0 through len-1. Note that the first element has not index 1.

• List and vector are different types in Asir. Lists are conveniently used for representing many data objects whose size varies dynamically as computation proceeds. By its flexible expressive power, it is also conveniently used to describe initial values for other structured objects as you see for vectors. Access for an element of a list is performed by following pointers to next elements. By this, access costs for list elements differ for each element.

In contrast to lists, vector elements can be accessed in a same time, because they are accessed by computing displacements from the top memory location of the vector object.

Note also, in Asir, modification of an element of a vector causes modification of the whole vector itself, while modification of a list element does not cause the modification of the whole list object.

By this, in Asir language, a vector element designator can be a left value of assignment statement, but a list element designator can NOT be a left value of assignment statement.

• No distinction of column vectors and row vectors in Asir. If a matrix is applied to a vector from left, the vector shall be taken as a column vector, and if from right it shall be taken as a row vector.

• The length (or size or dimension) of a vector is given by function size().

• When a vector is passed to a function as its argument (actual parameter), the vector element can be modified in that function.

• A vector is displayed in a similar format as for a list. Note, however, there is a distinction: Elements of a vector are separated simply by a ‘blank space’, while those of a list by a ‘comma.’

[0] A=newvect(5);
[ 0 0 0 0 0 ]
[1] A=newvect(5,[1,2,3,4,[5,6]]);
[ 1 2 3 4 [5,6] ]
[2] A[0];
1
[3] A[4];
[5,6]
[4] size(A);
[5]
[5] def afo(V)  V[0] = x;
[6] afo(A)$
[7] A;
[ x 2 3 4 [5,6] ]

References
     newmat, size

6.4.2 newmat

newmat(row,col [,[[a,b,…],[c,d,…],…]])

:: Creates a new matrix with row rows and col columns.

return matrix row,col non-negative integer

a,b,c,d arbitrary

• If the third argument, a list, is given, the newly created matrix is initialized so that each element of the list (again a list) initializes each of the rows of the matrix. Elements are used from the first through the last. If the list is short, 0’s are filled in the remaining matrix elements. If no third argument is given all the elements are cleared to 0.

• The size of a matrix is given by function size().

• Let M be a program variable assigned to a matrix. Then, M[I] denotes a (row) vector which corresponds with the I-th row of the matrix. Note that the vector shares its element with the original matrix. Subsequently, if an element of the vector is modified, then the corresponding matrix element is also modified.

• When a matrix is passed to a function as its argument (actual parameter), the matrix element can be modified within that function.

[0] A = newmat(3,3,[[1,1,1],[x,y],[x^2]]);
[ 1 1 1 ]
[ x y 0 ]
[ x^2 0 0 ]
[1] det(A);
-y*x^2
[2] size(A);
[3,3]
[3] A[1];
[ x y 0 ]
[4] A[1][3];
getarray : Out of range
return to toplevel

References
     newvect, size, det

6.4.3 size

size(vect|mat)

:: A list containing the number of elements of the given vector, [size of vect], or a list containing row size and column size of the given matrix, [row size of mat, column

     size of mat].

vect vector

mat matrix

• Return a list consisting of the dimension of the vector vect, or a list consisting of the row size and column size of the matrix matrix.

• Use length() for the size of list, and nmono() for the number of monomials with non-zero coefficients in a rational expression.

[0] A = newvect(4);
[ 0 0 0 0 ]
[1] size(A);
[4]
[2] B = newmat(2,3,[[1,2,3],[4,5,6]]);
[ 1 2 3 ]
[ 4 5 6 ]
[3] size(B);
[2,3]

References
     length, nmono

6.4.4 det

det(mat) :: Determinant of mat.

return expression

mat matrix

• Determinant of matrix mat.

• The fraction free Gaussian algorithm is employed. For matrices with multi-variate polynomial entries, minor expansion algorithm sometimes is more efficient than the fraction free Gaussian algorithm.

[91] A=newmat(5,5)$
[92] V=[x,y,z,u,v];
[x,y,z,u,v]
[93] for(I=0;I<5;I++)for(J=0,B=A[I],W=V[I];J<5;J++)B[J]=W^J;
[94] A;
[ 1 x x^2 x^3 x^4 ]
[ 1 y y^2 y^3 y^4 ]

 [ 1 z z^2 z^3 z^4 ]
 [ 1 u u^2 u^3 u^4 ]
 [ 1 v v^2 v^3 v^4 ]
 [95] fctr(det(A));
 [[1,1],[u-v,1],[-z+v,1],[-z+u,1],[-y+u,1],[y-v,1],[-y+z,1],[-x+u,1],[-x+z,1],
 [-x+v,1],[-x+y,1]]
References
      newmat

6.5 Types

6.5.1 type

type(obj) :: Returns an integer which identifies the type of the object obj in question.

return non-negative integer obj arbitrary

• Current assignment of integers for object types is listed below.

0  0

1 number 2 polynomial (not number) 3 rational expression (not polynomial) 4 list 5 vector 6 matrix 7 string 8 structure 9 distributed polynomial

• For further classification of number, use ntype(). For further classification of variable, use

vtype().
 [0] [0,type(0)];
 [0,0]                      /* 0 is of special type(0). */
 [1] [5*@i+1.1,type(5*@i+1.1)];

[(1.1+5*@i),1]            /* 5*@i+1.1 is a number(1). */
[2] [x^3-1/2*y^2,type(x^3-1/2*y^2)];
[x^3-1/2*y^2,2]            /* x^3-1/2*y^2 is a polynomial(2). */
[3] [x/y*z,type(x/y*z)];
[(z*x)/(y),3]              /* x/y*z is a rational expression(3). */
[4] [[0,a/b,[3]],type([0,a/b,[3]])];
[[0,(a)/(b),[3]],4]        /* [0,a/b,[3]] is a list(4). */
[5] [A=newvect(3,[1,2,3]),type(A)];
[[ 1 2 3 ],5]              /* A, here, is a vector(5). */
[6] [B=newmat(2,2,[[1,2],[3,4]]),type(B)];
[[ 1 2 ]
[ 3 4 ],6]                 /* B, here, is a matrix(6). */
[7] ["Example",type("Example")];
[Example,7]                /* "Example", here, is a string(7). */

References
     ntype, vtype

6.5.2 ntype

ntype(num)

:: Classifier of type num. Returns a sub-type number, an integer, for obj.

return non-negative integer

obj integer

• Sub-types for type number are listed below.

0 rational number

1 floating double (double precision floating point number)

2 algebraic number over rational number field

3 arbitrary precision floating point number (bigfloat)

4 complex number

• When arithmetic operations for numbers are performed, type coercion will be taken if their number sub-types are different so that the object having smaller sub-type number will be transformed to match the other object, except for algebraic numbers.

• A number object created by newalg(x^2+1) and the unit of imaginary number @i have different number sub-types, and it is treated independently.

• See Chapter 8 [Algebraic numbers], page 104 for algebraic numbers.

[0] [10/37,ntype(10/37)];
[10/37,0]
[1] [10.0/37.0,ntype(10.0/37.0)];
[0.27027,1]
[2] [newalg(x^2+1)+1,ntype(newalg(x^2+1)+1)];
[(#0+1),2]
[3] [eval(sin(@pi/6)),ntype(eval(sin(@pi/6)))];
[0.49999999999999999991,3]
[4] [@i+1,ntype(@i+1)];
[(1+1*@i),4]
References
     type

6.5.3 vtype
vtype(var)

:: Type of indetarminates var.

return non-negative integer var indeterminate

• Classify indeterminates into sub-types by giving an integer value as follows. For details See Section 3.3 [Types of indeterminates], page 18. 0 ordinary indeterminate, which can be directly typed in on a keyboard (a,b,x,afo,bfo,...,etc.) 1 Special indeterminate, created by uc() (_0, _1, _2, ... etc.)

2  function form (sin(x), log(a+1), acosh(1), @pi, @e, ... etc.)

3 functor (built-in functor name, user defined functor, functor for the elementary

functions) : sin, log, ... etc)

• Note: An input ‘a();’ will cause an error, but it changes the system database for identifiers. After this error, you will find ‘vtype(a)’ will result 3. (Identifier a is registered as a user defined functor).

• Usually @pi and @e are treated as indeterminates, whereas they are treated as numbers within functions eval() and pari().

References
     type, ntype, uc

6.6 Operations on functions

6.6.1 functor, args, funargs
functor(func)

:: Functor of function form func.

args(func)

:: List of arguments of function form func.

funargs(func)
     :: cons(functor(func),args(func)).

return functor() : indeterminate, args(), funargs() : list func function form

• See Section 6.5.3 [vtype], page 66 for function form.

• Extract the functor and the arguments of function form func.

• Assign a program variable, say F, to the functor obtained by functor(). Then, you can type (*F)(x) (, or (*F)(x,y,...) depending on the arity,) to input a function form with argument x.

[0] functor(sin(x));
sin
[0] args(sin(x));
[x]
[0] funargs(sin(3*cos(y)));
[sin,3*cos(y)]
[1] for (L=[sin,cos,tan];L!=[];L=cdr(L)) {A=car(L); print(eval((*A)(@pi/3)));}
0.86602540349122136831
0.5000000002
1.7320508058
References
     vtype

6.7 Strings

6.7.1 rtostr

rtostr(obj)

:: Convert obj to a string.

return string

obj arbitrary

• Convert an arbitrary object obj to a string.

• This function is convenient to create variables with numbered (or indexed) names by converting integers to strings and appending them to some name strings.

• Use strtov() for inverse conversion from string to indeterminate.

[0] A=afo;
afo
[1] type(A);
2
[2] B=rtostr(A);
afo
[3] type(B);
7
[4] B+"1";
afo1

References
     strtov, type

6.7.2 strtov

strtov(str)

:: Convert a string str to an indeterminate.

return indeterminate

str string which is valid to constitute an indeterminate.

• Convert a string that is valid for an indeterminate to an indeterminate which have str as its print name.

• The valid string for an indeterminate is such a string that begins with a small alphabetical letter possibly followed by any string composed of alphabetical letters, digits or a symbol ‘_’.

• Use the command to create indeterminates dynamically in programs.

[0] A="afo";
afo
[1] for (I=0;I<3;I++) {B=strtov(A+rtostr(I)); print([B,type(B)]);}
[afo0,2]
[afo1,2]
[afo2,2]
References
     rtostr, type, uc

6.8 Inputs and Outputs

6.8.1 end, quit
end, quit

:: Close the currently reading file. At the top level, terminate the Asir session.

• These two functions take no arguments. These functions can be called without a ‘()’. Either function close the current input file. This means the termination of the Asir session at the top level.

• An input file will be automatically closed if it is read to its end. However, if no end$ is written at the last of the input file, the control will be returned to the top level and Asir will be waiting for an input without any prompting. Thus, in order to avoid confusion, putting a end$ at the last line of the input file is strongly recommended.

[6] quit;
%
References
     load

6.8.2 load

load("filename")

:: Read a program file filename.

return (1|0) filename file (path) name

• See Chapter 4 [User language Asir], page 20 for practical programming. Since text files are read through cpp, the user can use, as in C programs, #include and #define in Asir program source codes.

• It returns 1 if the designated file exists, 0 otherwise.

• If the filename begins with ‘/’, it is understood as an absolute path name; with ‘.’, relative path name from current directory; otherwise, the file is searched first from directories assigned to an environmental variable ASIRLOADPATH, then if the search ends up in failure, the standard library directory (or directories assigned to ASIR_LIBDIR) shall be searched.

• We recommend to write an end command at the last line of your program. If not, Asir will not give you a prompt after it will have executed load command. (Escape with an interrupt character (see Section 2.7 [Interruption], page 11), if you have lost yourself.) Even in such a situation, Asir itself is still ready to read keyboard inputs as usual. It is, however, embarrassing and may cause other errors. Therefore, to put an end$ at the last line is desirable. (Command end; will work as well, but it also returns and displays verbose.)

References
      end, which

6.8.3 which
which("filename")

:: This returns the path name for the filename which load() will read.

return path name filename file name (path name) or 0

• This function searches directory trees according to the same procedure as load() will do. Then, returns a string, the path name to the file if the named file exists; 0 unless otherwise.

• For details of searching procedure, refer to the description about load().

 [0] which("gr");
 ./gb/gr
 [1] which("/usr/local/lib/gr");
 0
 [2] which("/usr/local/lib/asir/gr");
 /usr/local/lib/asir/gr
References
      load

6.8.4 output
output(["filename"])

:: Writes the return values and prompt onto file filename.

return 1 filename string describing a file name

• Standard output stream of Asir is redirected to the specified file. While Asir is writing its outputs onto a file, no outputs, except for keyboard inputs and some of error messages, are written onto the standard output. (You cannot see the result on the display.)

• To direct the Asir outputs to the standard output, issue the command without argument, i.e.,

output().

• If the specified file already exists, new outputs will be added to the tail of the file. If not, a file is newly created and the outputs will be written onto the file.

• When file name is specified without double quotes (""), or when protected file is specified, an error occurs and the system returns to the top level.

• If you want to write inputs from the key board onto the file as well as Asir outputs, put command ctrl("echo",1), and then redirect the standard output to your desired file.

• Contents which are written onto the standard error output, CPU time etc., are not written onto the file.

• Reading and writing algebraic expressions which contain neither functional forms nor unknown coefficients (vtype() References) are performed more efficiently, with respect to both time and

space, by bload() and bsave().

[83] output("afo");
fctr(x^2-y^2);
print("afo");
output();
1
[87] quit;
% cat afo
1
[84] [[1,1],[x+y,1],[x-y,1]]
[85] afo
0
[86]

References
     ctrl, bload, bsave

6.8.5 bsave, bload

bsave(obj,"filename")

:: This function writes obj onto filename in binary form.

bload("filename")

:: This function reads an expression from filename in binary form.

return bsave() : 1, bload() : the expression read

obj arbitrary expression which does not contain neither function forms nor unknown coefficients.

filename file name

• Function bsave() writes an object onto a file in its internal form (not exact internal form but very similar). Function bload() read the expression from files which is written by bsave(). Current implementation support arbitrary expressions, including lists, arrays (i.e., vectors and matrices), except for function forms and unknown coefficients (vtype() References.)

• The parser is activated to retrieve expressions written by output() , whereas internal forms are directly reconstructed by bload() from the bsave()’ed object in the file. The latter is much more efficient with respect to both time and space.

• It may happen that the variable ordering at reading is changed from that at writing. In such a case, the variable ordering in the internal expression is automatically rearranged according to the current variable ordering.

[0] A=(x+y+z+u+v+w)^20$
[1] bsave(A,"afo");
1
[2] B = bload("afo")$
[3] A == B;
1
[4] X=(x+y)^2;
x^2+2*y*x+y^2
[5] bsave(X,"afo")$
[6] quit;
% asir
[0] ord([y,x])$
[1] bload("afo");
y^2+2*x*y+x^2

References
     output

6.8.6 print

print(obj [,nl])

:: Displays (or outputs) obj.

return 0

obj arbitrary

nl flag (arbitrary)

• Displays (or outputs) obj.

• It normally adds linefeed code to cause the cursor moving to the next line. If 0 is given as the second argument, it does not add a linefeed.

• The return value of this function is 0. If command print(rat); is performed at the top level, first the value of rat will be printed, followed by a linefeed, followed by a 0 which is the value of the function and followed by a linefeed and the next prompt. (If the command is terminated by a ‘$’, e.g., print(rat)$, The last 0 will not be printed. )

• Formatted outputs are not currently supported. If one wishes to output multiple objects by a single print() command, use list like [obj1,...], which is not so beautiful, but convenient to minimize programming efforts.

[8] def cat(L) { while ( L != [] ) { print(car(L),0); L = cdr(L);} print("");
}

     [9] cat([xyz,123,"gahaha"])$
     xyz123gahaha

6.9 Interprocess communication

6.9.1 tcpinit, tcpdebug, tcpclose

tcpinit(host,command [,display])

:: Invokes command command on host host, and establishes communication with the invoked process.

tcpdebug(host,command [,display])

:: Returns shell command to invoke remote process.

tcpclose(id)

:: Closes I/O stream having process number id.

ping(obj) :: Passes an expression to the remote process, and returns the reply of that remote process.

return tcpinit() : integer, tcpdebug() : string, ping() : arbitrary host, command, display

string

id integer obj arbitrary expression which contains neither function forms nor unknown coefficients.

• Function tcpinit() invokes a process to execute command on a host host and enables Asir to communicate with that process.

• Integer returned is, as a matter of fact, the socket number of the opened TCP/IP stream.

• In UNIX version, graphics is processed by another process. The functions described here are used not only for such a graphic processing but used as general tools for distributed computing.

• The partners communicating with Asir are not necessarily processes running on the same machine. The communication will be successful even if the byte order is different from those of the partner processes, because the byte order for the communication is unified to the bigendian.

• The following preparations are necessary. Here, Let A be the host on which Asir is running, and B the host on which the partner process will run.

1. Set the command search path of csh on the remote host B so that your program, say P, can run on B. This is done by putting the directory of P to the command search path of csh on B. The program P is invoked by rsh or remsh. Thus, invocation of the program P shall fail unless it is found within the search path on the host B. For such a case, you can run the program P by either giving the absolute path or adding the directory of the program P to the search path description in your ‘~/.cshrc’. Note that the the ‘directory’ means the directory on the remote host B.

2. Register the hostname of the host A to the ‘~/.rhosts’ of the host B. That is, you should be allowed to access the host B from A without supplying a password.

3. For cases where connection to X is also used, let Xserver authorize the relevant hosts. Adding the hosts can be done by command xhost.

4. Some command’s consume much stack space. You are recommended to set the stack size to about 16MB large in ‘.cshrc’ for safe. To specify the size, put limit stacksize 16m for an example.

• When command opens a window on X, it uses the string specified for display; if the specification is omitted, it uses the value set for the environment variable DISPLAY.

• The function tcpdebug() takes the same arguments as tcpinit(), and returns a string, the command line which tcpinit() will use when it invokes a remote process through rsh. Moreover, Asir waits for the request of starting communication from the remote process as tcpinit() would do. This function helps to see the reason when tcpinit() failed to invoke a remote process by observing the behavior after issuing the returned string directly through the shell by hand on the host on which you wish to run the command command. It is also helpful to debug the command.

• The function tcpclose() closes the I/O stream having the number id, where id is the number returned by tcpinit(). Executing this function terminates the communication and the remote process.

• When Asir is terminated successfully, all I/O streams are automatically closed, and all the processes invoked are also terminated. However, some remote processes may not terminated when Asir is terminated abnormally. If ever Asir is terminated abnormally, you have to kill all the unterminated process invoked by Asir on every remote host. Check by ps command on the remote hosts to see if such processed are alive.

• The function ping() internally takes the program ‘asir_ping’ as command. It can be used after execution of tcpinit() to test whether the communication is correctly established and performed.

• Function ping() passes its argument to ‘asir_ping’ without any modification. Then, ‘asir_ping’ sends back the data to Asir immediately also without any modification, and finally ping() returns the data to the user.

 [15] tcpinit("localhost","asir_ping");

7
[16] ping(xyz);
xyz
[17] tcpclose(7);
0
[18] tcpdebug("localhost","asir_ping");
rsh localhost -n "asir_ping geisha 1040 otemoyan:0.0>&/dev/null&">/dev/null
------------------------------------
/* on machine `localhost'  */
% asir_ping geisha 1040 otemoyan:0.0
------------------------------------
7
[19] ping((x+y)^10);
x^10+10*y*x^9+45*y^2*x^8+120*y^3*x^7+210*y^4*x^6+252*y^5*x^5+210*y^6*x^4
+120*y^7*x^3+45*y^8*x^2+10*y^9*x+y^10
[20] tcpclose(7);
0

References
     ifplot

6.10 Plotting

6.10.1 ifplot, conplot, plot

ifplot(poly [,geometry] [,xrange] [,yrange] [,id] [,name])

:: Displays real zeros of a bi-variate polynomial.

conplot(poly [,geometry] [,xrange] [,yrange] [,zrange] [,id] [,name])

:: Displays real contour lines of a bi-variate polynomial.

plot(poly [,geometry] [,xrange] [,id] [,name])

:: Displays the graph of the function of an uni-variate polynomial.

plotover(poly,id,number)

:: Plots on the existing window real zeros of a bivariate polynomial.

return integer

poly polynomial

geometry, xrange, yrange, zrange

list id, number

integer

name string

• Function ifplot() draws a graph of real zeros of a bi-variate polynomial, i.e., plots an algebraic curves. Function conplot() plots the contour lines for a same argument. Function plot() draws the graph of the function regarding its argument uni-variate polynomial as a uni-variate function. These functions are available on UNIX version (on X11) and on Macintosh version.

• The plotting functions for UNIX version are realized on remote process facilities described previously. The command for this is ‘asir_plot’. Of course, it must be activated by tcpinit().

• In Macintosh version, these functions are available directly.

• Argument poly is indispensable. Other arguments are optional. The format of optional arguments and their default values (parenthesized) are listed below. geometry Window size is specified by [x,y] in unit ‘dot.’ ([400,400] for UNIX version;

[200,200] for Macintosh version.)

xrange, yrange Value ranges of the variables are specified by [v,vmin,vmax]. ([v,-2,2] for each variable.) If this specification is omitted, the indeterminate having the higher order in poly is taken for ‘x’ and the one with lower order is taken for ‘y’. To change this selection, specify explicitly by xrange and/or yrange. For an univariate polynomial, the specification is mandatory.

zrange This specification applies only to conplot(). The format is [v,vmin,vmax [,step ]]. If step is specified, the height difference of contours is set to (vmax-vmin)/step. ([z,-2,2,16].)

id This specifies the number of the remote process by which you wish to draw a graph.

(The number for the newest active process.)

name The name of the window. (Plot.) The created window is titled name:n/m which means the m-th window of the process with process number n. These numbers are

          used for plotover().

• The maximum number of the windows that can be created on a process is 128.

• Function plotover() superposes reals zeros of its argument bi-variate polynomial onto the specified window.

• Enlarged plot can be obtained for rectangular area which is specified, on an already existing window with a graph, by dragging cursor with the left button of mouse from the upper-left corner to lower-right corner and then releasing it. Then, a new window is created whose shape is similar to the specified area and whose size is determined so that the largest side of the new window has the same size of the largest side of the original window. If you wish to cancel the action, drag the cursor to any point above or left of the starting point.

This facility is effective when precise button switch is inactive. If precise is selected and active, the area specified by the cursor dragging will be rewritten on the same window. This will be explained later.

• A click of the right button will display the current coordinates of the cursor at the bottom area of the window.

• Place the cursor at any point in the right marker area on a window created by conplot(), and drag the cursor with the middle mutton. Then you will find the contour lines changing their colors depending on the movement of the cursor and the corresponding height level displayed on the upper right corner of the window.

• Several operations are available on the window: by button operations for UNIX version, and pull-down menus for Macintosh version. quit Destroys (kills) the window. While computing, quit the current computation.

wide (toggle)

Will display, on the same window, a new area enlarged by 10 times as large as the current area for both width-direction and height-direction. The current area will be indicated by a rectangle placed at the center. Area specification by dragging the cursor will create a new window with a plot of the graph in the specified area.

precise (toggle)

When selected and active, asir_plot redraws the specified area more precisely by integer arithmetic. This mode uses bisection method based on Sturm sequence computation to locate real zeros precisely. More precise plotting can be expected by this technique than by the default plotting technique, at the expense of significant increase of computing time. As you see by above explanation, this function is only effective to polynomials with rational coefficients. (Check how they differ for (x^2+y^2-1)^2.)

formula Displays the expression for the graph.

noaxis (toggle)

Erase the coordinates.

• Program ‘asir_plot’ may consume much stack space depending on which machine it is running. You are recommended to set the stack size to about 16MB as large in ‘.cshrc’ for safe. To specify the size, put limit stacksize 16m for an example.

• You can customize various resources of a window on X, e.g., coloring, shape of buttons etc. The default setting of resources is shown below. For plot*form*shapeStyle you can select

among rectangle, oval, ellipse, and roundedRectangle.
     plot*background:white
     plot*form*shapeStyle:rectangle
     plot*form*background:white
     plot*form*quit*background:white
     plot*form*wide*background:white

    plot*form*precise*background:white
    plot*form*formula*background:white
    plot*form*noaxis*background:white
    plot*form*xcoord*background:white
    plot*form*ycoord*background:white
    plot*form*level*background:white
    plot*form*xdone*background:white
    plot*form*ydone*background:white

[0] tcpinit("geisha","asir_plot");
7
[1] ifplot(x^2+y^2-1)$
[2] ifplot(x^5-2*y*x^2+y^5,[200,200])$
[3] ifplot(x^6+3*y^2*x^4+(3*y^4-4*y^2)*x^2+y^6)$
[4] ifplot(x^4+(2*y^2+3*y)*x^2+y^4-y^3)$
[5] conplot(2*x^4-3*x^2*y+y^2-2*y^3+y^4,[y,-1,3],"Mask")$
[6] conplot(x^6+(43/12*y^2-3)*x^4+(88/27*y^4+46/3*y^2+3)*x^2+64/729*y^6-
        16/27*y^4+4/3*y^2-1,[x,-3,3],[y,-3,3])$
[7] plot(256*x^8-512*x^6+304*x^4-48*x^2+1,[x,-1,1])$
[8] ifplot(364816*x^6+(9214800*y^2+8937600*y-121625)*x^4+(2520000*y^4-
        2250000*y^3-18877500*y^2-12656250*y+1880000)*x^2+4000000*y^6+
        3000000*y^5-8250000*y^4-4437500*y^3+6187500*y^2+1687500*y-1687500)$

References
     tcpinit, tcpclose

6.11 Miscellaneouses

6.11.1 ctrl

ctrl("switch",onoff )

:: Turns off switch switch if its argument is 0; turn on otherwise.

return 0 or 1

switch switch name

onoff flag (arbitrary)

• Asir has several switches. This command set and reset the switches. If its second argument is 0, the switch specified by the first argument switch will be turned off (reset), or otherwise turned on (set).

• Switches are specified by strings, namely, enclosed by two double quotes.

• Here are of switches of Asir.

cputime If ‘on’, CPU time and GC time is displayed at every top level evaluation of Asir command; if ‘off’, not displayed. See Section 6.11.6 [cputime tstart tstop], page 83. (The switch is also set by command cputime(1), and reset by cputime(0).)

nez Selection for EZGCD algorithm. It is set to 1 by default. Ordinary users need not

change this setting.

echo If ‘on’, inputs from the standard input will be echoed onto the standard output. When executing to load a file, the contents of the file will be written onto the standard output. If ‘off’, the inputs will not be echoed. This command will be useful when used with command output.

bigfloat If ‘on’, floating operations will be done by PARI system with arbitrary precision floating point operations. Default precision is set to 9 digits. To change the precision, use command setprec. If ‘off’, floating operations will be done by Asir’s own floating operation routines with a fixed precision operations of standard floating double.

• Returns 1 when the switch is successfully changed, 0 otherwise.

References
cputime, output, pari, setprec, eval

6.11.2 debug

debug :: Forces to enter into debugging mode.

• Function debug is a function with no argument. It can be called without ‘()’.

• In the debug-mode, you are prompted by (debug) and the debugger is ready for commands. Typing in quit (Note! without a semicolon.) brings you to exit the debug-mode.

• See Chapter 5 [Debugger], page 31 for details.

[1] debug;
(debug) quit
0
[2]

6.11.3 error

error(message)

:: Forces Asir to cause an error and enter debugging mode.

message string

• When Asir encounters a serious error such that it finds difficult to continue execution, it, in general, tries to enter debugging mode before it returns to top level. The command error() forces a similar behavior in a user program.

• The argument is a string which will be displayed when error() will be executed.

• You can enter the debug-mode when your program encounters an illegal value for a program variable, if you have written the program so as to call error() upon finding such an error in your program text.

% cat mod3
def mod3(A)
        if ( type(A) >= 2 )
                error("invalid argument");
        else
                return A % 3;
end$
% asir
[0] load("mod3");
1
[3] mod3(5);
2
[4] mod3(x);
invalid argument
stopped in mod3 at line 3 in file "./mod3"
3                       error("invalid argument");
(debug) print A
A = x
(debug) quit
return to toplevel
[4]

References
     debug

6.11.4 help

help(["function"])

:: Displays the description of function function.

return 0 function function name

• If invoked without argument, it displays rough usage of Asir.

• If a function name is given and if there exists a file with the same name in the directory ‘help’ under standard library directory, the file is displayed by a command set to the environmental variable PAGER or else command ‘more’.

• Not supported for Macintosh version.

6.11.5 time

time() :: Returns a three element list consisting of total CPU time and GC time elapsed and also total memory quantities requested from the start of current Asir session.

return list

• These are commands regarding CPU time and GC time.

• The GC time is the time regarded to spent by the garbage collector, and the CPU time is the time defined by subtracting the GC time from the total time consumed by command Asir. Their unit is ‘second.’

• Command time() returns total CPU time and GC time elapsed from the start of current Asir session. Time unit is ‘second.’ Moreover, it returns total memory quantities in words (usually 4 bytes) which are requested to the memory manager from the beginning of the current session.

• You can find the CPU time and GC time for some computation by taking the difference of the figure reported by time() at the beginning and the ending of the computation.

• Since arbitrary precision integers are NOT used for counting the total amount of memory request, the number will eventually happen to become meaningless due to integer overflow.

• When cputime switch is active by ctrl() or by cputime(), the execution time will be displayed after every evaluation of top level statement. In a program, however, in order to know the execution time for a sequence of computations, you have to use time() command, for an example.

• Many UNIX OS’s support getrusage(). Owing to this function, time() reports reliable figures on many UNIX OS’s. On DOS and Mac OS, however, we cannot but use the time of real world clock. Thus, on DOS and Mac OS the reported time is nothing but the elapsed time of the real world. Therefore, the time elapsed in the debug-mode and the time of waiting for a reply to interruption prompting are added to the elapsed time. Especially for PC98 platforms, the time is measured by ‘second’, and subsequently, the figure returned by time() has usually no information for a short computation. For some UNIX OS’s which do not support getrusage(), Asir obtains CPU time by clock(). But, by the nature of this function, the figure returned by time() become meaningless after a certain amount of time (2147 seconds for HP-UX.)

 [72] T0=time();
 [0.24,0.03,22861]
 [73] G=hgrm(katsura(4),[u4,u3,u2,u1,u0])$
 [74] T1=time();
 [2.48,1.37,1934543]
 [75] ["CPU",T1[0]-T0[0],"GC",T1[1]-T0[1]];
 [CPU,2.24,GC,1.34]
References
      cputime, tstart, tstop

6.11.6 cputime, tstart, tstop
cputime(onoff )

:: Stop displaying cputime if its argument is 0, otherwise start displaying cputime after every top level evaluation of Asir command.

tstart() :: Resets and starts timer for CPU time and GC time. tstop() :: Stops timer and then displays CPU time GC time elapsed from the last time when

timer was started.

return 0 onoff flag (arbitrary)

• Command cputime() with NON-ZERO argument enables Asir to display CPU time and GC time after every evaluation of top level Asir command. The command with argument 0 disables displaying them.

• Command tstart() starts measuring CPU time and GC time without arguments. The parentheses ‘()’ may be omitted.

• Command tstop() stops measuring CPU time and GC time and displays them without arguments. The parentheses ‘()’ may be omitted.

• Command cputime(onoff ) has same meaning as ctrl("cputime",onoff ).

• Nested use of tstart() and tstop() is not expected. If such an effect is desired, use time().

• On and off states by cputime() have effects only to displaying mode. Time for evaluation of every top level statement is always measured. Therefore, even after a computation has already started, you can let Asir display the timings, whenever you enter the debug-mode and execute

cputime(1).

[49] tstart$
[50] fctr(x^10-y^10);
[[1,1],[x+y,1],[x^4-y*x^3+y^2*x^2-y^3*x+y^4,1],[x-y,1],
[x^4+y*x^3+y^2*x^2+y^3*x+y^4,1]]
[51] tstop$
80msec + gc : 40msec
[52] grm(katsura(4),[u4,u3,u2,u1,u0])$
^Cinterrupt ?(q/t/c/d/w/?) d
stopped in gbcheck at line 186 in file "./gb/gr"
186                     if ( !ZERO(H) )
(debug) print cputime(1)
cputime(1) = 0
(debug) c
580msec + gc : 320msec
[53]

References
     time, ctrl

6.11.7 heap

heap() :: Heap area size currently in use.

return non-negative integer

• Command heap() returns an integer which is the byte size of current Asir heap area.

Heap is a memory area where various data for expressions and user programs of Asir and is managed by the garbage collector. While Asir is running, size of the heap is monotonously non-decreasing against the time elapsed. If it happens to exceed the real memory size, most (real world) time is consumed for swapping between real memory and disk memory.

• For a platform with little real memory, it is recommended to set up Asir configuration tuned for GC functions by -adj option at the activation of Asir. (See Section 2.4 [Command line options], page 8.)

% asir -adj 16
[0] load("fctrdata")$
0
[97] cputime(1)$
0msec
[98] heap();
524288
0msec
[99] fctr(Wang[8])$
3.190sec + gc : 3.420sec
[100] heap();
1118208
0msec
[101] quit;
% asir
[0] load("fctrdata")$
0
[97] cputime(1)$
0msec
[98] heap();
827392
0msec
[99] fctr(Wang[8])$
3.000sec + gc : 1.180sec
[100] heap();
1626112
0msec
[101] quit;

References

Section 2.4 [Command line options], page 8

6.11.8 version

version()

:: Version identification number of Asir.

return non-negative integer

• Command version() returns the version identification number , an integer of 6 digits, of Asir in use.

The first 2 digits represent the year, next 2 digits the month, and the last 2 digit the day of month.

[0] version();
940216

6.11.9 shell

shell(command)

:: Execute shell commands described by a string command.

return non-negative integer

command string

• Execute shell commands described by a string command by a C function system(). This returns the exit status of shell as its return value.

[0] shell("ls");
alg             da              katsura         ralg            suit
algt            defs.h          kimura          ratint          test
alpi            edet            kimura3         robot           texput.log
asir.o          fee             mfee            sasa            wang
asir_symtab     gr              mksym           shira           wang_data
base            gr.h            mp              snf1            wt
bgk             help            msubst          solve
chou            hom             p               sp
const           ifplot          proot           strum
cyclic          is              r               sugar
0

7 Groebner bases

7.1 Distributed polynomial

A distributed polynomial is a polynomial with a special internal representation different from the ordinary one.

An ordinary polynomial (having type 2) is internally represented in a format, called recursive representation. In fact, it is represented as an uni-variate polynomial with respect to a fixed variable, called main variable of that polynomial, where the other variables appear in the coefficients which may again polynomials in such variables other than the previous main variable. A polynomial in the coefficients is again represented as an uni-variate polynomial in a certain fixed variable, the main variable. Thus, by this recursive structure of polynomial representation, it is called the ‘recursive representation.’

(x + y + z)^{2} = 1 · x^{2} + (2 · y + (2 · z)) · x + ((2 · z) · y + (1 · z^{2}))

On the other hand, we call a representation the distributed representation of a polynomial, if a polynomial is represented, according to its original meaning, as a sum of monomials, where a monomial is the product of power product of variables and a coefficient. We call a polynomial, represented in such an internal format, a distributed polynomial. (This naming may sounds something strange.)

(x + y + z)^{2} = 1 · x^{2} + 2 · xy + 2 · xz + 1 · y^{2} + 2 · yz + 1 · z^{2}

For computation of Groebner basis, efficient operation is expected if polynomials are represented in a distributed representation, because major operations for Groebner basis are performed with respect to monomials. From this view point, we provide the object type distributed polynomial with its object identification number 9, and objects having such a type are available by Asir language.

Here, we provide several definitions for the later description.

term The power product of variables, i.e., a monomial with coefficient 1. In an Asir session, it is displayed in the form like

               <<0,1,2,3,4>>

and also can be input in such a form. This example shows a term in 5 variables. If we assume the 5 variables as a, b, c, d, and e, the term represents b*c^2*d^3*e^4 in the ordinary expression.

monomial The product of a term and a coefficient. In an Asir session, it is displayed in the form like

               2*<<0,1,2,3,4>>

and also can be input in such a form.

head monomial head term head coefficient

Monomials in a distributed polynomial is sorted by a total order. In such representation, we call the monomial that is maximum with respect to the order the head monomial, and its term and coefficient the head term and the head coefficient respectively.

7.2 Reading files

Facilities for computing Groebner bases are provided not by built-in functions but by a set of user functions written in Asir. The set of functions is provided as a file (sometimes called package), named ‘gr’. The facilities will be ready to use after you load the package by load(). The package ‘gr’ is placed in the standard library directory of Asir. Therefore, it is loaded simply by specifying its file name, unless the environment variable ASIR_LIBDIR is set to a non-standard one.

     [0] load("gr")$

7.3 Functions, Options

7.3.1 Functions

There are many functions and options defined in the package ‘gr’. Usually not so many of them are used. Top level functions for Groebner basis computation are the following four functions.

In the following description, plist stands for a list of polynomials and vlist stands for a list of variables (indeterminates.) gr(plist,vlist)

Function that computes Groebner bases by Gebauer-Moeller-Sugar algorithm. For ordinary computation, this function is used.

grm(plist,vlist)

A variant of gr() looking for higher speed by a modular technique. If the input ideal is 0-dimensional, that is, if the number of the common zeros of the input polynomials is finite, this variant sometimes show drastically high speed in computing the Groebner basis compared with gr(). Try whenever you can guess such a condition to hold.

hgr(plist,vlist)

A variant of gr() which computes Groebner bases through the homogenization technique. The real homogenization gives usually a stable strategy compared with the virtual homogenization by Sugar. A shortcoming is the increase of unnecessary pairs. Thus, usually hgrm() is better to employ. This function is in force only for variable orderings DegRevLex and Lex.

hgrm(plist,vlist)

An improved version of hgr(). It is effective, just like grm(), in case of 0-dimensional ideals. Especially, when even grm() is not successful, try this as the last resort.

7.3.2 Options

There are many environmental choices in the computation of Groebner bases. Such choices are specified by setting several global variables.

Ord Term ordering is determined by the value of the global variable Ord based on the variable ordering given by the argument vlist. We call a possible value of Ord a ‘type of term ordering.’ Details of the types of term ordering are described later.

PRINT When this option has a non-zero value, various intermediate information is displayed as the computation proceeds. Such information is very helpful, especially in a big computation, to make a decision to quit the current computation and re-compute with other choice of options.

NOREDUCE Usually a computed Groebner basis is a normalized Groebner basis which is mutually reduced, that is, every basis element is cannot further be reduced by other basis elements. If NOREDUCE has a non-zero value, such mutual reduction is suppressed.

NOSUGAR When NOSUGAR has value 0, the Sugar strategy is employed. When NOSUGAR has a non-

zero value, Buchberger’s Normal strategy is employed instead of the Sugar strategy.

NOCRIB When NOCRIB has a non-zero value, criterion B of the criteria for detection of unnecessary pairs is not applied.

NOGC When NOGC has a non-zero value, no check is done for confirming that the result is in fact a Groebner basis. This option applies for the modular variants: grm() and

hgrm().

NOMC When NOMC has a non-zero value, no check is done for confirming that the result is in fact gives the identical ideal to the input ideal. This option applies for the modular variants: grm() and hgrm().

All of these global variables have initial values 0. Moreover, ordinary users need not change the value of the options after NOREDUCE. You may set and reset the option PRINT at your need.

The most important ones are the choice of Ord option which determines a type of term ordering, and also the variable ordering given by the argument.

7.4 Ord, variable ordering

The value of Ord option specifies the type of term ordering. Option Ord can take one of the integer value from 0 up to 8. Three values, 0, 1 and 2, are used for the usual use.

0 (DegRevLex; Total degree Reverse Lexicographic Ordering)

In general, computation by this ordering shows the fastest speed in most Groebner basis computations. However, for the purpose to solve polynomial equations, this type of ordering is, in general, not so suitable. The Groebner bases obtained by this ordering is used for computing the number of solutions, solving ideal membership problem and seeds for conversion to other Groebner bases under different ordering.

1 (DegLex; Total degree Lexicographic Ordering)

By this type term ordering, Groebner bases are obtained fairly faster than Lex (lexicographic) ordering, too. Alike the DegRevLex ordering, the result, in general, cannot directly be used for solving polynomial equations. It is used, however, in such a way that a Groebner basis is computed in this ordering after homogenization to obtain the final lexicographic Groebner basis.

2 (Lex; Lexcographic Ordering)

Groebner bases computed by this ordering give the most convenient Groebner bases for solving the polynomial equations. The only and serious shortcoming is the enormously long computation time. It is often observed that the number coefficients of the result becomes very very long integers, especially if the ideal is 0-dimensional. For such a case, it is empirically true for many cases that the modular technique and the homogenization technique with modular technique are quite effective, i.e., computation by grm() and/or hgrm() may be quite effective.

For concrete definitions of term ordering and more information about Groebner basis, refer to, for

example, the book [Becker,Weispfenning].

Note that the variable ordering have strong effects on the computation time as well as the choice

of Ord.

[90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$
0msec
[91] Ord=2$
0msec
[92] gr(B,[x,y,z,t])$
[x^2-2*y^7+(-41*t^2-13*t-1)*y^2+(2*t^17-12*t^14+42*t^12+30*t^11-168*t^9
-40*t^8+70*t^7+252*t^6+30*t^5-140*t^4-168*t^3+2*t^2-12*t+16)*z^2*y
+(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5
-167*t^4-55*t^3+30*t^2+58*t-15)*z^4,
(y+t^2*z^2)*x+y^7+(20*t^2+6*t+1)*y^2+(-t^17+6*t^14-21*t^12-15*t^11+84*t^9
+20*t^8-35*t^7-126*t^6-15*t^5+70*t^4+84*t^3-t^2+5*t-9)*z^2*y+(6*t^16-36*t^13
+14*t^11+90*t^10-56*t^8-120*t^7-14*t^6+64*t^5+84*t^4+27*t^3-16*t^2-30*t+7)*z^4,
(t^3-1)*x-y^6+(-6*t^13+24*t^10-20*t^8-36*t^7+40*t^5+24*t^4-6*t^3-20*t^2-6*t-
1)*y
+(t^17-6*t^14+9*t^12+15*t^11-36*t^9-20*t^8-5*t^7+54*t^6+15*t^5+10*t^4-36*t^3
-11*t^2-5*t+9)*z^2,
-y^8-8*t*y^3+16*z^2*y^2+(-8*t^16+48*t^13-56*t^11-120*t^10+224*t^8+160*t^7
-56*t^6-336*t^5-112*t^4+112*t^3+224*t^2+24*t-56)*z^4*y+(t^24-8*t^21+20*t^19
+28*t^18-120*t^16-56*t^15+14*t^14+300*t^13+70*t^12-56*t^11-400*t^10-84*t^9
+84*t^8+268*t^7+84*t^6-56*t^5-63*t^4-36*t^3+46*t^2-12*t+1)*z,
2*t*y^5+z*y^2+(-2*t^11+8*t^8-20*t^6-12*t^5+40*t^3+8*t^2-10*t-20)*z^3*y+8*t^14
-32*t^11+48*t^8-t^7-32*t^5-6*t^4+9*t^2-t,
-z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2,
2*t^2*y^3+z^2*y^2+(-2*t^5+4*t^2-6)*z^4*y+(4*t^8-t^7-8*t^5+2*t^4-4*t^3+5*t^2-
t)*z,
z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2,
-t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2,
-t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4,
z^5-t^4]
530msec + gc : 280msec
[93] gr(B,[t,z,y,x]);
[x^10-t,x^8-z,x^31-x^6-x-y]
0msec + gc : 10msec

As you see in the above example, the Groebner base under variable ordering [x,y,z,t] has a lot of bases and each base itself is large. Under variable ordering [t,z,y,x], however, B itself is already the Groebner base. Roughly speaking, to obtain a Groebner base under the lexicographic ordering is to express the variables on the left (having higher order) in terms of variables on the right (having lower order). In the example, variables t, z, and y are already expressed by variable x, and the above explanation justifies such a drastic experimental results. In practice, however, optimum ordering for variables may not known beforehand, and some heuristic trial may be inevitable.

7.5 Groebner basis computation with rational expression coefficients

Such variables that appear within the input polynomials but not appearing in the input variable list are automatically treated as elements in the coefficient field by top level functions, such as

gr().
     [63] Ord=2$
     [64] gr([a*x+b*y-c,d*x+e*y-f],[x,y]);
     [(-e*a+d*b)*x-f*b+e*c,(-e*a+d*b)*y+f*a-d*c]

In this example, variables a, b, c, and d are treated as elements in the coefficient field. In this case, a Groebner basis is computed on a bi-variate polynomial ring F[x,y] over rational function field F = Q(a,b,c,d). Notice that coefficients are considered as a member in a field. As a consequence, polynomial factors common to the coefficients are removed so that the result, in general, is different from the result that would be obtained when the problem is considered as a computation of Groebner basis over a polynomial ring with rational function coefficients.

7.6 Functions for Groebner basis computation

7.6.1 gr, grm, hgr, hgrm

gr(plist,vlist) grm(plist,vlist) hgr(plist,vlist) hgrm(plist,vlist)

:: Groebner bases

return list plist, vlist list

• Defined in ‘gr’ of the standard library.

• Each one of them computes a Groebner base of the input polynomials in plist with respect to the variable ordering vlist.

• Argument vlist is the variable (indeterminate) list. Variables not appearing in vlist is regarded to belong to the coefficient field.

• Functions grm() and hgrm() employ modular techniques for speeding up, and hgr() and hgrm() employ homogenization techniques for stabilization.

• The value of the global variable Ord is used for the type of term ordering.

• When finite number of solutions are expected for the polynomial equations by some guess, functions grm() and hgrm() may effective.

[0] load("gr")$
[44] Ord=2$
[45] load("cyclic")$
[55] P=cyclic(5);
[c4*c3*c2*c1*c0-1,(((c3+c4)*c2+c4*c3)*c1+c4*c3*c2)*c0+c4*c3*c2*c1,
((c2+c4)*c1+c4*c3)*c0+c3*c2*c1+c4*c3*c2,(c1+c4)*c0+c2*c1+c3*c2+c4*c3,
c0+c1+c2+c3+c4]
[56] G=grm(P,[c0,c1,c2,c3,c4]);
[c0+c1+c2+c3+c4,...]
reference
     Ord

7.6.2 dp_ord
dp_ord(order)

:: used for setting the type of term ordering

return 1 order integer

• This function sets the type of term ordering to order. Top level functions such as gr() set the type of term ordering by using the value of the global variable Ord for the argument to

dp_ord().

• Type of term ordering must be correctly set by this function when functions other than top level functions are called directly.

[19] dp_ord(0)$

[20] <<1,2,3>>+<<3,1,1>>;
(1)*<<1,2,3>>+(1)*<<3,1,1>>
[21] dp_ord(2)$
[22] <<1,2,3>>+<<3,1,1>>;
(1)*<<3,1,1>>+(1)*<<1,2,3>>

Reference
     Ord

7.6.3 dp_ptod

dp_ptod(poly,vlist)

:: Converts an ordinary polynomial to a distributed polynomial.

return Distributed polynomial

poly polynomial

vlist list

• According to the variable ordering vlist and current type of term ordering, this function converts an ordinary polynomial to a distributed polynomial.

• Indeterminates not included in vlist are regarded to belong to the coefficient field.

[50] dp_ord(0);
1
[51] dp_ptod((x+y+z)^2,[x,y,z]);
(1)*<<2,0,0>>+(2)*<<1,1,0>>+(1)*<<0,2,0>>+(2)*<<1,0,1>>+(2)*<<0,1,1>>
+(1)*<<0,0,2>>
[52] dp_ptod((x+y+z)^2,[x,y]);
(1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>+(z^2)*<<0,0>>

Reference
     dp_dtop, dp_ord

7.6.4 dp_dtop

dp_dtop(dpoly,vlist)

:: return polynomial dpoly Distributed polynomial vlist list

• Converts a distributed polynomial to an ordinary polynomial by the given variable list.

• Any variable list can be used as far as its length matches the number of variables in the distributed polynomial.

     [53] T=dp_ptod((x+y+z)^2,[x,y]);
     (1)*<<2,0>>+(2)*<<1,1>>+(1)*<<0,2>>+(2*z)*<<1,0>>+(2*z)*<<0,1>>+(z^2)*<<0,0>>
     [54] P=dp_dtop(T,[a,b]);
     z^2+(2*a+2*b)*z+a^2+2*b*a+b^2

7.6.5 dp_nf

dp_nf(indexlist,dpoly,dpolyarray,fullreduce)

:: Computes the normal form of a distributed polynomial.

return Distributed polynomial indexlist list dpoly Distributed polynomial dpolyarray

vector

fullreduce flag

• Computes the normal form of a distributed polynomial dpoly.

• Argument dpolyarray is a vector whose elements are distributed polynomials. Argument indexlist is a list of indices for the argument dpolyarray used for normal form computation.

• When argument fullreduce has non-zero value, all terms are reduced. When it has value 0, only the head term is reduced.

• As for the polynomials specified by indexlist, one specified by an index placed at the preceding position has priority to be selected.

• In general, the result of the function may be different depending on indexlist. However, the result is unique for Groebner bases.

     [0] load("gr")$

[45] load("katsura")$
[50] K=katsura(4)$
[51] length(K)$
5
[52] Ord=2$
[53] dp_ord(2)$
[54] DP1=newvect(5)$
[55] V=[u0,u1,u2,u3,u4]$
[56] for(I=0;I<5;I++)DP1[I]=dp_ptod(K[I],V);
[57] G=gr(K,V)$
[58] length(G);
5
[59] DP2=newvect(5)$
[60] for(I=0;I<5;I++)DP2[I]=dp_ptod(G[I],V);
[61] T=dp_ptod((u0-u1+u2-u3+u4)^2,V)$
[62] dp_dtop(dp_nf([0,1,2,3,4],T,DP1,1),V);
u4^2+(6*u3+2*u2+6*u1-2)*u4+9*u3^2+(6*u2+18*u1-6)*u3+u2^2+(6*u1-2)*u2+9*u1^2-
6*u1+1
[63] dp_dtop(dp_nf([4,3,2,1,0],T,DP1,1),V);
-5*u4^2+(-4*u3-4*u2-4*u1)*u4-u3^2-3*u3-u2^2+(2*u1-1)*u2-2*u1^2-3*u1+1
[64] dp_dtop(dp_nf([0,1,2,3,4],T,DP2,1),V);
-1138087976845165778088612297273078520347097001020471455633353049221045677593
0005716505560062087150928400876150217079820311439477560587583488*u4^15+...
[65] dp_dtop(dp_nf([4,3,2,1,0],T,DP2,1),V);
-1138087976845165778088612297273078520347097001020471455633353049221045677593
0005716505560062087150928400876150217079820311439477560587583488*u4^15+...
[66] @64==@65;
1

Reference
     dp_dtop, dp_ord, p_nf

7.6.6 dp_hm, dp_ht, dp_hc, dp_rest

dp_hm(dpoly)

:: Gets the head monomial.

dp_ht(dpoly)

:: Gets the head term.

dp_hc(dpoly)

:: Gets the head coefficient.

dp_rest(dpoly)

:: Gets the remainder of the polynomial where the head monomial is removed. return dp_hm(), dp_ht(), dp_rest() : Distributed polynomial, dp_hc() : number or poly-

nomial

dpoly Distributed polynomial

• These are used to get various parts of a distributed polynomial.

• The next equations hold for a distributed polynomial p.

p = dp_hm(p) + dp_rest(p)
dp_hm(p) = dp_hc(p) dp_ht(p)
[87] dp_ord(0)$
[88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
[89] T=dp_ptod(X,[u3,u4,a46])$
[90] dp_hm(T);
(2160)*<<4,0,2>>
[91] dp_ht(T);
(1)*<<4,0,2>>
[92] dp_hc(T);
2160
[93] dp_rest(T);
(1512)*<<4,0,1>>+(315)*<<4,0,0>>+(-4000)*<<0,0,2>>+(-2800)*<<0,0,1>>
+(-490)*<<0,0,0>>

7.6.7 dp_td, dp_sugar, dp_true_sugar
dp_td(dpoly)

:: Gets the total degree of the head term.

dp_sugar(dpoly)

:: Gets the sugar of a polynomial.

dp_true_sugar([onoff ])

:: Selects and displays the meaning of dp_sugar(): the total degree or sugar, which?.

return integer dpoly Distributed polynomial onoff flag

• Function dp_td() returns the total degree of the head term, i.e., the sum of all exponent of variables in that term.

• Upon creation of a distributed polynomial, an integer called sugar is associated. This value is the total degree of that polynomial if the value set by dp_true_sugar() is 0; or else the total degree of the virtual homogenized one of the original polynomial. Value 0 is set by default. Therefore, dp_sugar() returns the total degree as a polynomial by default setting.

• Function dp_true_sugar() sets value 0 to an internal flag if the given argument is 0; or value 1 for the other argument. It returns the current state (after setting) of the internal flag regardless of the existence of an argument.

• The quantity sugar is an important guide to determine the selection strategy of critical pairs in Groebner basis computation.

[87] dp_ord(0)$
[88] X=ptozp((a46^2+7/10*a46+7/48)*u3^4-50/27*a46^2-35/27*a46-49/216)$
[89] T=dp_ptod(X,[u3,u4,a46])$
[90] dp_td(dp_rest(T));
5
[91] dp_true_sugar();
0
[92] dp_sugar(T);
6

7.6.8 dp_lcm

dp_lcm(dpoly1,dpoly2)

:: Returns the least common multiple of the head terms of the given two polynomials.

return Distributed polynomial

dpoly1, dpoly2

Distributed polynomial

• Returns the least common multiple of the head terms of the given two polynomials, where coefficient is always set to 1.

[100] dp_lcm(<<1,2,3,4,5>>,<<5,4,3,2,1>>);
(1)*<<5,4,3,4,5>>

Reference
     dp_ht

7.6.9 dp_redble

dp_redble(dpoly1,dpoly2)

:: Checks whether one head term is divisible by the other head term.

return integer dpoly1, dpoly2

Distributed polynomial

• Returns 1 if the head term of dpoly2 divides the head term of dpoly1; otherwise 0.

• Used for finding candidate terms at reduction of polynomials.

[148] C;
(1)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>+(1)*<<1,0,0,1,1>>
[149] T;
(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>+(6)*<<1,1,1,0,0>>
[150] for ( ; T; T = dp_rest(T)) print(dp_redble(T,C));
0
0
0
1
Reference
     dp_red

7.6.10 dp_subd

dp_subd(dpoly1,dpoly2)

:: Returns the quotient monomial of the head terms.

return Distributed polynomial dpoly1, dpoly2

Distributed polynomial

• Gets dp_ht(dpoly1)/dp_ht(dpoly2). The coefficient of the result is always set to 1.

• Divisibility assumed.

[162] dp_subd(<<1,2,3,4,5>>,<<1,1,2,3,4>>);
(1)*<<0,1,1,1,1>>

Reference
     dp_red

7.6.11 dp_red

dp_red(dpoly1,dpoly2,dpoly3)

:: Single reduction operation

return list dpoly1, dpoly2, dpoly3

Distributed polynomial

vlist

• Reduces a distributed polynomial, dpoly1 + dpoly2, by dpoly3 for single time.

• The term to be reduced is the head term of dpoly2. This implies that the divisibility of the head term of dpoly2 by the head term of dpoly3 is assumed.

• When integral coefficients, computation is so carefully performed that no rational operations appear in the reduction procedure. It is computed for integers a and b, and a term t as: a(dpoly1 + dpoly2)-bt dpoly3.

• the result is a list of form [a dpoly1,a dpoly2 - bt dpoly3].

[157] D=(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>;
(3)*<<2,1,0,0,0>>+(3)*<<1,2,0,0,0>>+(1)*<<0,3,0,0,0>>
[158] R=(6)*<<1,1,1,0,0>>;
(6)*<<1,1,1,0,0>>
[159] C=12*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>;
(12)*<<1,1,1,0,0>>+(1)*<<0,1,1,1,0>>+(1)*<<1,1,0,0,1>>
[160] dp_red(D,R,C);
[(6)*<<2,1,0,0,0>>+(6)*<<1,2,0,0,0>>+(2)*<<0,3,0,0,0>>,(-1)*<<0,1,1,1,0>>
+(-1)*<<1,1,0,0,1>>]
Reference
     dp_nf

7.6.12 p_nf

p_nf(poly,plist,vlist,otype)

:: Computes the normal form of the given polynomial.

return polynomial poly polynomial plist,vlist list otype integer

• Defined in the package ‘gr’.

• Obtains the normal form of a polynomial by a polynomial list.

• This is an interface to dp_nf().

• The polynomial poly and the polynomials in plist is converted, according to the variable ordering vlist and type of term ordering otype, into their distributed polynomial counterparts and passed to dp_nf().

• function dp_nf() is called with value 1 for fullreduce.

• The result is converted back to an ordinary polynomial.

• It executes dp_ord(otype) internally, and the effective setting of term ordering may differ from that of the global variable Ord.

     [78] Ord = 2$
     [79] K = katsura(5)$
     [80] V = [u5,u4,u3,u2,u1,u0]$
     [81] NOCRIB = 1$
     [82] G = grm(K,V)$
     [83] p_nf(K[1],G,V,2);
     0
     [84] p_nf(K[1],G,V,1);
     2*u4*u0+(2*u3+2*u5)*u1+u2^2-u4
Reference
          dp_ptod, dp_dtop, dp_ord, dp_nf

7.6.13 p_terms
p_terms(poly,vlist)

:: Monomials appearing in the given polynomial is collected into a list. poly polynomial vlist list

• Defined in the package ‘gr’.

• This returns a list which contains all non-zero monomials in the given polynomial. The monomials are ordered according to the current type of term ordering and vlist.

• Since polynomials in a Groebner base often have very large coefficients, examining a polynomial as it is may sometimes be difficult to perform. For such a case, this function enables to examine which term is really exists.

[232] Ord=2$
[233] G=grm(katsura(5),[u5,u4,u3,u2,u1,u0])$
[234] p_terms(G[0],[u5,u4,u3,u2,u1,u0]);
[u5,u0^31,u0^30,u0^29,u0^28,u0^27,u0^26,u0^25,u0^24,u0^23,u0^22,u0^21,u0^20,
u0^19,u0^18,u0^17,u0^16,u0^15,u0^14,u0^13,u0^12,u0^11,u0^10,u0^9,u0^8,u0^7,
u0^6,u0^5,u0^4,u0^3,u0^2,u0,1]

7.6.14 katsura, hkatsura, cyclic, hcyclic
katsura(n)
hkatsura(n)
cyclic(n)
hcyclic(n)

:: Generates a polynomial list of standard benchmark.

return list n integer

• Function katsura() is defined in ‘katsura’, and function cyclic() in ‘cyclic’.

• These functions generate a series of polynomial sets, respectively, which are often used for testing and bench marking: katsura, cyclic and their homogenized versions.

• Polynomial set cyclic is sometimes called by other name: Arnborg, Lazard, and Davenport.

[74] load("katsura")$
[79] load("cyclic")$
[89] katsura(5);
[u0+2*u4+2*u3+2*u2+2*u1+2*u5-1,2*u4*u0-u4+2*u1*u3+u2^2+2*u5*u1,
2*u3*u0+2*u1*u4-u3+(2*u1+2*u5)*u2,2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3-u2+u1^2,

2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2-u1,
u0^2-u0+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
[90] hkatsura(5);
[-t+u0+2*u4+2*u3+2*u2+2*u1+2*u5,
-u4*t+2*u4*u0+2*u1*u3+u2^2+2*u5*u1,-u3*t+2*u3*u0+2*u1*u4+(2*u1+2*u5)*u2,
-u2*t+2*u2*u0+2*u2*u4+(2*u1+2*u5)*u3+u1^2,
-u1*t+2*u1*u0+(2*u3+2*u5)*u4+2*u2*u3+2*u1*u2,
-u0*t+u0^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2+2*u5^2]
[91] cyclic(6);
[c5*c4*c3*c2*c1*c0-1,
((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
(((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
(c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]
[92] hcyclic(6);
[-c^6+c5*c4*c3*c2*c1*c0,
((((c4+c5)*c3+c5*c4)*c2+c5*c4*c3)*c1+c5*c4*c3*c2)*c0+c5*c4*c3*c2*c1,
(((c3+c5)*c2+c5*c4)*c1+c5*c4*c3)*c0+c4*c3*c2*c1+c5*c4*c3*c2,
((c2+c5)*c1+c5*c4)*c0+c3*c2*c1+c4*c3*c2+c5*c4*c3,
(c1+c5)*c0+c2*c1+c3*c2+c4*c3+c5*c4,c0+c1+c2+c3+c4+c5]

Reference
     dp_dtop, Ord

8 Algebraic numbers

8.1 Representation of algebraic numbers

Algebraic number fields as mathematical objects are not defined in Asir. Instead, individual algebraic numbers are defined by some means. Though you cannot directly define an algebraic number field, you can virtually operate in an algebraic number field, when you handle such algebraic numbers. Thus, in Asir an algebraic number field is defined virtually as a number field obtained by adjoining a finite number of algebraic numbers to the rational number field.

A new algebraic number is introduced in Asir in such a way where it is defined as a root of an uni-variate polynomial whose coefficients include already defined algebraic numbers as well as rational numbers. We shall call such a newly defined algebraic number a root. Also, we call such an uni-variate polynomial the defining polynomial of that root.

     [0] A0=newalg(x^2+1);
     (#0)
     [1] A1=newalg(x^3+A0*x+A0);
     (#1)
     [2]  [type(A0),ntype(A0)];
     [1,2]

In this example, the algebraic number assigned to A0 is defined as a root of a polynomial x^2+1; that of A1 is defined as a root of a polynomial x^3+A0*x+A0, which you see contains the previously defined root (A0) in its coefficients.

The argument to newalg(), i.e., the defining polynomial, must satisfy the following conditions.

1. Uni-variateness A defining polynomial must be an uni-variate polynomial.

2. Rationality of the leading coefficient A defining polynomial is used to simplify expressions containing that algebraic number. The procedure of such simplification is performed by an internal routine similar to the built-in function srem(), where the defining polynomial is used for the second argument, the divisor. By this reason, the leading coefficient of the defining polynomial must be a rational number (must not be an algebraic number.)

3. successiveness Every coefficients of a defining polynomial must be a ‘(multi-variate) polynomial’ in already defined root’s. Here, ‘(multi-variate) polynomial’ means a mathematical concept, not the object type ‘polynomial’ in Asir.

4. Irreducibility A defining polynomial must be irreducible over the field that is obtained by adjoining all root’s contained in its coefficients to the rational number field.

Only the first two conditions (1 and 2) are checked by function newalg(). Among all, it should be emphasized that no check is done for the irreducibility at all. The reason is that the irreducibility test requires enormously much computation time. You are trusted whether to check it at your own risk.

Once a root has been defined by newalg() function, it is given the type identifier for a number, and furthermore, the sub-type identifier for an algebraic number. (See Section 6.5.1 [type], page 64, Section 6.5.2 [ntype], page 65.) Also, any rational combination of rational numbers and root’s is an algebraic number.

     [87] N=(A0^2+A1)/(A1^2-A0-1);
     ((#1+#0^2)/(#1^2-#0-1))
     [88] [type(N),ntype(N)];
     [1,2]

As you see it in the example, a root is displayed as #n. But, you cannot input that root in its immediate output form. You have to refer to a root by a program variable assigned to the root, or to get it by alg(n) function, or by several other indirect means. A strange use of newalg(), with a same argument polynomial (except for the name of its main variable), will yield the old root instead of a new root though it is apparently inefficient.

     [90] alg(0);
     (#0)
     [91] newalg(t^2+1);
     (#0)

The defining polynomial of a root can be obtained by defpoly() function.

     [96] defpoly(A0);
     t#0^2+1
     [97] defpoly(A1);
     t#1^3+t#0*t#1+t#0

Here, you see a strange expression, t#0 and t#1. They are a specially indeterminates generated and maintained by Asir internally. Indeterminate t#0 corresponds to root #0, and t#0 to #1. These indeterminates also cannot be input directly by a user in their immediate forms. You can get them by several ways: by var() function, or algv(n) function.

     [98] var(@);
     t#1
     [99] algv(0);
     t#0
     [100]

8.2 Operations over algebraic numbers

In the previous section, we explained about the representation of algebraic numbers and their defining method. Here, we describe operations on algebraic numbers. Only a few functions are built-in, and almost all functions are provided as user defined functions. The file containing their definitions is ‘sp’, and it is placed under the same directory as ‘gr’ is placed, i.e., the standard library directory of Asir. It should be mentioned that some of the functions in ‘sp’ use functions defined in ‘gr’, and it may be convenient to load ‘sp’ and ‘gr’ at once.

     [0] load("gr")$
     [1] load("sp")$

Or if you always need them, it is more convenient to include the load commands in ‘$HOME/.asirrc’.

Like the other numbers, algebraic numbers can get arithmetic operations applied. Simplification, however, by defining polynomials are not automatically performed. It is left to users to simplify their expressions. A fatal error shall result if the denominator expression will be simplified to 0. Therefore, be careful enough when you will create and deal with algebraic numbers which may denominators in their expressions.

Use simpalg() function for simplification of algebraic numbers by defining polynomials.

     [49] T=A0^2+1;
     (#0^2+1)
     [50] simpalg(T);

Function simpalg() simplifies algebraic numbers which have the same structures as rational expressions in their appearances.

[39] A0=newalg(x^2+1);
(#0)
[40] T=(A0^2+A0+1)/(A0+3);
((#0^2+#0+1)/(#0+3))
[41] simpalg(T);
(3/10*#0+1/10)
[42] T=1/(A0^2+1);
((1)/(#0^2+1))
[43] simpalg(T);
div : division by 0
stopped in invalgp at line 258 in file "/usr/local/lib/asir/sp"
258                     return 1/A;
(debug)

This example shows an error caused by zero division in the course of program execution of simpalg(), which attempted to simplify an algebraic number expression of which the denominator is 0.

Function simpalg() also can take a polynomial as its argument and simplifies algebraic numbers in its coefficients.

[43] simpalg(1/A0*x+1/(A0+1));
(-#0)*x+(-1/2*#0+1/2)

Thus, you can operate in polynomials which contain algebraic numbers as you do usually in ordinary polynomials, except for proper simplification by simpalg(). You may sometimes feel needs to convert root’s to indeterminates, especially when you are working for norm computation in algorithms for algebraic factorization. Function algptorat() is used for such cases.

[83] A0=newalg(x^2+1);
(#0)
[84] A1=newalg(x^3+A0*x+A0);
(#1)
[85] T=(2*A0+A1*A0+A1^2)*x+(1+A1)/(2+A0);
(#1^2+#0*#1+2*#0)*x+((#1+1)/(#0+2))
[86] S=algptorat(T);
(((t#0+2)*t#1^2+(t#0^2+2*t#0)*t#1+2*t#0^2+4*t#0)*x+t#1+1)/(t#0+2)
[87] algptorat(coef(T,1));
t#1^2+t#0*t#1+2*t#0

As you see by the example, function algptorat() converts root’s, #n, in polynomials and numbers to its associated indeterminates, t#n. As was already mentioned those indeterminates cannot be directly input in their immediate form. The restriction is adopted to avoid the confusion that might happen if the user could input such internally generatable indeterminates.

The associated indeterminate to a root is reversely converted to the root by rattoalgp() function.

     [88] rattoalgp(S,[alg(0)]);
     (((#0+2)/(#0+2))*t#1^2+((#0^2+2*#0)/(#0+2))*t#1+((2*#0^2+4*#0)/(#0+2)))*x
     +((1)/(#0+2))*t#1+((1)/(#0+2))
     [89] rattoalgp(S,[alg(0),alg(1)]);
     (((#0^3+6*#0^2+12*#0+8)*#1^2+(#0^4+6*#0^3+12*#0^2+8*#0)*#1+2*#0^4+12*#0^3
     +24*#0^2+16*#0)/(#0^3+6*#0^2+12*#0+8))*x+(((#0+2)*#1+#0+2)/(#0^2+4*#0+4))
     [90] rattoalgp(S,[alg(1),alg(0)]);
     (((#0+2)*#1^2+(#0^2+2*#0)*#1+2*#0^2+4*#0)/(#0+2))*x+((#1+1)/(#0+2))
     [91] simpalg(@89);
     (#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)
     [92] simpalg(@90);
     (#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)

Function rattoalgp() takes as the second argument a list consisting of root’s that you want to convert, and converts them successively from the left. This example shows that apparent difference of the results due to the order of such conversion will vanish by simplification yielding the same result. Functions algptorat() and rattoalgp() can be conveniently used for your own simplification.

8.3 Operations for uni-variate polynomials over an algebraic number field

In the file ‘sp’ are provided functions for uni-variate polynomial factorization and uni-variate polynomial GCD computation over algebraic numbers, and furthermore, as an application of them, functions to compute splitting fields of univariate polynomials.

8.3.1 GCD

Greatest common divisors (GCD) over algebraic number fields are computed by gcda() function. This function is realized by using functions for Groebner basis computation in the package ‘gr’. Though the method based on modular techniques is currently recognized practically best, Asir does not implement the method. The method using Groebner basis is implemented as a second best choice.

[0] X=x^6+3*x^5+6*x^4+x^3-3*x^2+12*x+16;
x^6+3*x^5+6*x^4+x^3-3*x^2+12*x+16
[1] A=newalg(X);
(#0)
[2] S = x^3+(3*A+3)*x^2+(3*A^2+6*A+3)*x+(A^3+3*A^2+3*A+4);
x^3+(3*#0+3)*x^2+(3*#0^2+6*#0+3)*x+(#0^3+3*#0^2+3*#0+4)
[3] load("gr")$
[47] load("sp")$
[86] gcda(X,S);
12*x^2+(-#0^5-#0^4-2*#0^3+7*#0^2+13*#0+8)*x+(-2*#0^5-4*#0^4-8*#0^3+14*#0^2
+16*#0-16)

8.3.2 Square-free factorization and Factorization

For square-free factorization (of uni-variate polynomials over algebraic number fields), we employ the most fundamental algorithm which begins first to compute GCD of a polynomial and its derivative. As a consequence, the algorithm takes the longest computation time when the polynomial is square-free. The function to do this factorization is asq().

[116] A=newalg(x^2+x+1);
(#4)
[117] T=simpalg((x+A+1)*(x^2-2*A-3)^2*(x^3-x-A)^2);
x^11+(#4+1)*x^10+(-4*#4-8)*x^9+(-10*#4-4)*x^8+(16*#4+20)*x^7+(24*#4-6)*x^6
+(-29*#4-31)*x^5+(-15*#4+28)*x^4+(38*#4+29)*x^3+(#4-23)*x^2+(-21*#4-7)*x
+(3*#4+8)
[118] asq(T);
[[x^5+(-2*#4-4)*x^3+(-#4)*x^2+(2*#4+3)*x+(#4-2),2],[x+(#4+1),1]]

Like factorization over the rational number field, the result is presented, commonly to both square-free factorization and factorization, as a list whose elements are pairs (list of two elements) in the form [factor, multiplicity] without the constant multiple part.

Here, it should be noticed that the products of all factors of the result may DIFFER from the input polynomial by a constant. The reason is that the factors are normalized so that they have integral leading coefficients for the sake of readability.

This incongruity may happen to square-free factorization and factorization commonly.

The algorithm employed for factorization over algebraic number fields is an improvement of the norm method by Trager. It is especially very effective to factorize a polynomial over a field obtained by adjoining some of its root’s to the base field.

     [119] af(T,[A]);
     [[x^3-x+(-#4),2],[x^2+(-2*#4-3),2],[x+(#4+1),1]]

The function takes two arguments: The second argument is a list of root’s. Factorization is performed over a field obtained by adjoining the root’s to the rational number field. It is important to keep in mind that the ordering of the root’s must obey a restriction: Last defined should come first. The automatic re-ordering is not done. It should be done by yourself.

     [120] B=newalg(x^2-2*A-3);
     (#5)
     [121] af(T,[B,A]);
     [[x+(#5),2],[x^3-x+(-#4),2],[x+(-#5),2],[x+(#4+1),1]]

8.3.3 Splitting fields

This operation may be somewhat unusual and for specific interest. (Galois Group for example.) Procedurally, however, it is easy to obtain the splitting field of a polynomial by repeated application of algebraic factorization described in the previous section. The function is sp().

     [103] sp(x^5-2);
     [[x+(-#1),2*x+(#0^3*#1^3+#0^4*#1^2+2*#1+2*#0),2*x+(-#0^4*#1^2),2*x
     +(-#0^3*#1^3),x+(-#0)],[[(#1),t#1^4+t#0*t#1^3+t#0^2*t#1^2+t#0^3*t#1+t#0^4],
     [(#0),t#0^5-2]]]

Function sp() takes only one argument. The result is a list of two element: The first element is a list of linear factors, and the second one is a list whose elements are pairs (list of two elements) in the form [root, algptorat(defining polynomial)].

The second element, a list of pairs of form [root,algptorat(defining polynomial)], corresponds to the root’s which are adjoined to eventually obtain the splitting field. They are listed in the reverse order of adjoining. Each of the defining polynomials in the list is, of course, guaranteed to be irreducible over the field obtained by adjoining all root’s defined before it.

The first element of the result, a list of linear factors, contains all irreducible factors of the input polynomial over the field obtained by adjoining all root’s in the second element of the result.

Because such field is the splitting field of the input polynomial, factors in the result are all linear as the consequence.

Similarly to function af(), the product of all resulting factors may yield a polynomial which differs by a constant.

8.4 Summary of functions for algebraic numbers

8.4.1 newalg
newalg(defpoly)

:: Creates a new root.

return algebraic number (root) defpoly polynomial

• Creates a new root (algebraic number) with its defining polynomial defpoly.

• For constraints on defpoly, See Section 8.1 [Representation of algebraic numbers], page 104.

     [0] A0=newalg(x^2-2);
     (#0)
Reference
          defpoly
8.4.2 defpoly
defpoly(alg)

:: Returns the defining polynomial of root alg.

return polynomial alg algebraic number (root)

• Returns the defining polynomial of root alg.

• If the argument alg, a root, is #n, then the main variable of its defining polynomial is t#n.

     [1] defpoly(A0);
     t#0^2-2
Reference
          newalg, alg, algv

8.4.3 alg

alg(i) :: Returns a root which correspond to the index i. return algebraic number (root) i integer

• Returns #i, a root.

• Because #i cannot be input directly, this function provides an alternative way: input alg(i).

     [2] x+#0;
     syntax error
     0
     [3] alg(0);
     (#0)
Reference
          newalg, algv

8.4.4 algv

algv(i) :: Returns the associated indeterminate with alg(i). return polynomial i integer

• Returns an indeterminate t#i

• Since indeterminate t#i cannot be input directly, it is input by algv(i).

[4] var(defpoly(A0));
t#0
[5] t#0;
syntax error
0
[6] algv(0);
t#0

Reference
     newalg, defpoly, alg

8.4.5 simpalg

simpalg(rat)

:: Simplifies algebraic numbers in a rational expression.

return rational expression

rat rational expression

• Defined in the file ‘sp’.

• Simplifies algebraic numbers contained in numbers, polynomials, and rational expressions by the defining polynomials of root’s contained in them.

• If the argument is a number having the denominator, it is rationalized and the result is a polynomial in root’s.

• If the argument is a polynomial, each coefficient is simplified.

• If the argument is a rational expression, its denominator and numerator are simplified as a polynomial.

[7] simpalg((1+A0)/(1-A0));
simpalg undefined
return to toplevel
[7] load("sp")$
[46] simpalg((1+A0)/(1-A0));
(-2*#0-3)
[47] simpalg((2-A0)/(2+A0)*x^2-1/(3+A0));
(-2*#0+3)*x^2+(1/7*#0-3/7)
[48] simpalg((x+1/(A0-1))/(x-1/(A0+1)));
(x+(#0+1))/(x+(-#0+1))

8.4.6 algptorat
algptorat(poly)

:: Substitutes the associated indeterminate for every root in a polynomial.

return polynomial poly polynomial

• Defined in the file ‘sp’.

• Substitutes the associated indeterminate t#n for every root #n in a polynomial.

     [49] algptorat((-2*alg(0)+3)*x^2+(1/7*alg(0)-3/7));
     (-2*t#0+3)*x^2+1/7*t#0-3/7
Reference
          defpoly, algv
8.4.7 rattoalgp
rattoalgp(poly,alglist)

:: Substitutes a root for the associated indeterminate with the root.

return polynomial poly polynomial alglist list

• Defined in the file ‘sp’.

• The second argument is a list of root’s. Function rattoalgp() substitutes a root for the associated indeterminate of the root.

     [51] rattoalgp((-2*algv(0)+3)*x^2+(1/7*algv(0)-3/7),[alg(0)]);
     (-2*#0+3)*x^2+(1/7*#0-3/7)
Reference
          alg, algv

8.4.8 gcda

gcda(poly1,poly2)

:: GCD of two uni-variate polynomials over an algebraic number field.

return polynomial

poly1, poly2

polynomial

• Defined in the file ‘sp’.

• Finds the GCD of two uni-variate polynomials.

• This function is based on Groebner basis computation. Therefore, loading ‘gr’ is necessary.

[52] X=simpalg((x-A0-2)^2*(x+A0-1)^3);
x^5+(#0-7)*x^4+(-8*#0+15)*x^3+(17*#0-13)*x^2+(-6*#0+14)*x+(2*#0-2)
[53] Y=simpalg((x-A0-2)^3*(x+A0-1)^2);
x^5+(-#0-8)*x^4+(4*#0+21)*x^3+(#0-14)*x^2+(-12*#0-10)*x+(-2*#0-4)
[54] gcda(X,Y);
grm undefined
stopped in gcda at line 357 in file "/usr/local/lib/asir/sp"
357             L = grm(ML,cons(var(P1),VL));
(debug) quit
return to toplevel
[54] load("gr")$
[98] gcda(X,Y);
-x^4+6*x^3+(2*#0-9)*x^2+(-6*#0)*x-2

Reference
     gr, asq

8.4.9 sp_norm

sp_norm(alg,var,poly,alglist)

:: Norm computation over an algebraic number field.

return polynomial

var The main variable of poly

poly uni-variate polynomial

alg root alglist root list

• Defined in the file ‘sp’.

• Computes the norm of poly with respect to alg. Namely, if we write K = Q(alglist \ {alg}), The function returns a product of all conjugates of poly, where the conjugate of polynomial poly is a polynomial in which the algebraic number alg is substituted for its conjugate over K.

• The result is a polynomial over K.

• Computation is performed by function res() and Chinese Remainder algorithm.

   [0] load("sp")$
   [39] A0=newalg(x^2+1)$
   [40] A1=newalg(x^2+A0)$
   [41] sp_norm(A1,x,x^3+A0*x+A1,[A1,A0]);
   x^6+(2*#0)*x^4+(#0^2)*x^2+(#0)
   [42] sp_norm(A0,x,@@,[A0]);
   x^12+2*x^8+5*x^4+1
Reference
        res, af

8.4.10 asq, af

asq(poly) :: Square-free factorization of polynomial poly over an algebraic number field. af(poly,alglist)

:: Factorization of polynomial poly over an algebraic number field.

return list poly polynomial alglist list of root

• Both defined in the file ‘sp’. These function require file ‘gr’ loaded.

• If the inputs contain no root’s, these functions run fast since they invoke functions over the integers. In contrast to this, if the inputs contain root’s, they sometimes take a long time, since gcda() is invoked.

• Function af() requires the specification of base field, i.e., list of root’s for its second argument.

• In the second argument alglist, root defined last must come first.

• The result is a list, as a result of usual factorization, whose elements is of the form [factor, multiplicity].

• The product of all factors with multiplicities counted may differ from the input polynomial by a constant.

[99] asq(-x^4+6*x^3+(2*alg(0)-9)*x^2+(-6*alg(0))*x-2);
[[-x^2+3*x+(#0),2]]
[100] af(-x^2+3*x+alg(0),[alg(0)]);
[[x+(#0-1),1],[-x+(#0+2),1]]

Reference
     gcda, sqfr

8.4.11 sp

sp(poly) :: Finds the splitting field of polynomial poly and splits.

return list

poly polynomial

• Defined in the file ‘sp’. The function requires file ‘gr’ loaded.

• Finds the splitting field of poly, an uni-variate polynomial over with rational coefficients, and splits it into its linear factors over the field.

• The result consists of a two element list: The first element is the list of all linear factors of poly; the second element is a list which represents the successive extension of the field.

• The splitting field is represented as a list of pairs of form [root,algptorat(defpoly(root))]. In more detail, the list is interpreted as a representation of successive extension obtained by adjoining root’s to the rational number field. Adjoining is performed from the right root to the left.

[101] L=sp(x^9-54);
[[x+(-#2),-54*x+(#1^6*#2^4),54*x+(#1^6*#2^4+54*#2),54*x+(-#1^8*#2^2),
-54*x+(#1^5*#2^5),54*x+(#1^5*#2^5+#1^8*#2^2),-54*x+(-#1^7*#2^3-54*#1),
54*x+(-#1^7*#2^3),x+(-#1)],[[(#2),t#2^6+t#1^3*t#2^3+t#1^6],[(#1),t#1^9-54]]]
[102] for(I=0,M=1;I<9;I++)M*=L[0][I];
[111] M=simpalg(M);
-1338925209984*x^9+72301961339136
[112] ptozp(M);
-x^9+54

Chapter 8: Algebraic numbers 118

Reference
          af, defpoly, algptorat

Appendix A Details of Syntax

<expression>:
`('<expression>`)'
<expression> <binary operator> <expression>
`+' <expression>
`-' <expression>
<left value>
<left value> <assignment operator> <expression>
<left value> `++'
<left value> `--'
`++' <left value>
`--' <left value>
`!' <expression>
<expression> `?' <expression> `:' <expression>
<function> `(' <expr list> `)'
<string>
<exponent vector>
<atom>
<list>

(See Section 4.2.9 [various expressions], page 28)

<left value>:
<program variable> [`['<expression>`]']*

<binary operator>:
`+' `-' `*' `/' `%' `^'(exponentiation)
`==' `!=' `<' `>' `<=' `>=' `&&' `||'

Note: Operator ‘+’ can be used for string concatenation.

<assignment operator>:
`=' `+=' `-=' `*=' `/=' `%=' `^='

<expr list>:
<empty>
<expression> [`,' <expression>]*

<list>:
`[' <expr list> `]'

<program variable>:

Sequence of alphabetical letters or numeric digits or _
that begins with a capital alphabetical letter
(X,Y,Japan etc.)

(See Section 4.2.2 [variables and indeterminates], page 23)

<function>:
Sequence of alphabetical letters or numeric digits or _
that begins with a small alphabetical letter
(fctr,gcd etc.)

<atom>:
<indeterminate>
<number>

<indeterminate>:
Sequence of alphabetical letters or numeric digits or _
that begin with a small alphabetical letter
(a,bCD,c1_2 etc.)

(See Section 4.2.2 [variables and indeterminates], page 23)

<number>:
<rational number>
<floating point number>
<algebraic number>
<complex number>

(See Section 3.2 [Types of numbers], page 16)

<rational number>:
0, 1, -2, 3/4

<floating point number>:
0.0, 1.2e10

<algebraic number>:
newalg(x^2+1), alg(0)^2+1

(See Chapter 8 [Algebraic numbers], page 104)

<complex number>:
1+@i, 2.3*@i

<string>:
character sequence enclosed by two `"''s.

<exponent vector>:
`<<' <expr list> `>>'

<statement>:
<expression> <terminator>
<compound statement>
`break' <terminator>
`continue' <terminator>
`return' <terminator>
`return' <expression> <terminator>
`if' `(' <expr list> `)' <statement>
`if' `(' <expr list> `)' <statement> `else' <statement>
`for' `(' <expr list> `;' <expr list> `;' <expr list> `)' <statement>
`do' <statement> `while' `(' <expr list> `)' <terminator>
`while' `(' <expr list> `)' <statement>
`def' <function> `(' <expr list> `)' `{' <variable declaration> <stat list>
`}'
`end(quit)' <terminator>

(See Section 4.2.5 [Statements], page 25)

<terminator>:
`;' `$'

<variable declaration>:
[`extern' <program variable> [`,' <program variable>]* <terminator>]*

<compound statement>:
`{' <stat list> `}'

<stat list>:
[<statement>]*

Appendix B Risa/Asir for Macintosh

B.1 File organization

     dist --- asir    asir for 680X0 (X>=2)
           |
           |- asir-sc asir for 680X0 (X>=2) without co-processor
           |
           |- asir-00 asir for 68000
           |
           |- params parameters for memory management
           |
           |- lib    --- gr      Groebner basis package
                      |
                      |- wang    test program for factoring
                      |
                      |- defs.h
                      |
                      |- ...

B.2 params

The contents of params are as follows.

     stacksize=xxx adj=xxx paristack=xxx fontsize=xxx rows=xxx cols=xxx

where xxx’s are decimal numbers: Their meanings are as follows.

stacksize Stack size for Asir. Unit=byte.

adj Lager adj increases the frequency of garbage collection.

paristack Heap size for PARI. The default is 64 kbytes. Unit=byte.

fontsize Font size for display.

rows Lines of contained in the window.

cols Number of characters that a line can contain.

Default partition size is set up for Asir. This can be referred to and modified by command+i (i.e., typing i while holding down the command-key.) Because available memory size is limited by the partition size, you may need to change it for your purpose. When virtual memory is enabled on System 7, the available partition size can exceed the real memory. However, if computation requires memories larger than the real memory size, computation speed shall slow down very seriously.

B.3 Starting up

Click doubly the icon Asir, and a window named ‘Asir’ will open. After that all session procedures are alike as those of UNIX version.

B.4 Differences from UNIX version

Command line editing facility is incorporated. It facilitates an emacs key binding and history substitution. Only ‘!!’ and ‘!string’ type history referencing is available. The history is saved to the file ‘history’ under the same directory as ‘asir’, and saved as many as 100 command lines.

To read in program files, type as the following.

     [1] load(":dir_a:dir_b:...:filename");

The first colon (:) superfluous if the file path start at the current directory. For user’s convenience, reading-in by mini-finder is provided. To open the mini-finder for file loading, choose ‘Load’ in ‘File’ menu, or type command+‘L’ (i.e., typing ‘L’ while holding down the command key.)

To interrupt Asir execution, type command+‘.’ (i.e., type a period ‘.’ while holding down the command key.)

Appendix C Risa/Asir for MS-DOS/DOS-Extender

C.1 Running environments

Asir can run on a MS-DOS personal computer with i80386 or i80486 CPU under two kind of DOS-Extender, namely, go32 and run386. In the following we only explain about go32 version.

First of all, you have to obtain go32 which runs on your personal computer. If your machine is one of the clones of IBM-PC or NEC PC98, you may easily obtain go32 by anonymous ftp, through JUNET, and personal computer communication networks, (e.g., Nikkei MIX, NIFTY etc.) For FUJITSU FM series machines it can also be obtained through NIFTY. Binaries of go32.exe of ver1.10 is included in the distribution binaries.

Set well according to the manual of go32 for necessary environments of go32. If your machine does not have a floating point co-processor, it is necessary to set the environment variable EMU so that go32 can use the proper emulator. A directory which has a sufficiently large space must be assigned to GO32TMP because a large file will be created whenever Asir is suspended to invoke shell. At least 10 MB is recommended for GO32TMP. If this space is short the suspension will fail and control is returned to DOS, not to go32.

For more details of installation including the way to obtain Risa/Asir, See Section 2.3 [Installation], page 4.

C.2 Usage of DOS version

One standard starting up method is to type the following.

     A> go32 asir
     <messages>
     [0]

Or, in the case of ‘asir.exe’, which is generated by concatenating ‘stub.exe’ before asir, simply type the following.

     A> asir
     <messages>

     [0]

The other operations are similar to those for UNIX version. One IMPORTANT difference: To interrupt Asir execution, type ^X. Note that ^C, the usual interrupting command for UNIX, cannot be used, because, in MS-DOS, it terminates go32. Typing ^Z suspends the Asir session and invokes shell (normally command.com). This shell will be terminated by the exit command, and the suspended Asir session will be resumed to continue.

Graphics and dynamic loading of object programs are not supported yet.

As it is already mentioned, DOS version has more defects and instability in various point than UNIX version. Here, we summaries them.

• Asir itself will be terminated by an internal error. (See Section 2.8 [Error handling], page 11)

• To interrupt Asir, use ^X. This is because an ^C shall terminate Asir itself. (See Section 2.7 [Interruption], page 11)

• Interrupts are not accepted when PARI is invoked. This is because interrupts are detected by Asir’s memory manager.

• When another program is invoked by a ^Z or help(), go32 swaps almost all memory used by Asir onto disk. By this, if Asir is using much memory for a large problem, the time to swap may be very large. If the swap space is short, Asir shall be terminated, and sometimes MS-DOS may be terminated in the worst case.

• The ‘CPU time’ reported by time() is, as a matter of fact, the difference of the time stamp of the real world clock from the start to the end of the computation. (See Section 6.11.5 [time], page 82)

Appendix D Augmenting functions by C programs

In this section is described facilities that are available only when Risa/Asir is delivered with source codes.

D.1 Incremental loading

There are several files for incremental loading written in C in a sub-directory ‘o’ under the source directory. See the library manual for details. These programs will be ready to load when it is ‘make’ed under ‘o’. Platforms for which incremental loading is supported are Sun, VAX, DECStation, and RISC NEWS. Information for other platforms is found in the next section.

For example, compile a program file ‘o/xxx.c’.

     % cd o
     % make xxx.o

Then, you will get ‘xxx.o’. And you can load it into Asir by load("xxx.o").

For platforms with CPU’s R3000 and R4000, you have to add -G 0 to CFLAGS. This operation is necessary to avoid reference to global data by the global pointer register. Moreover, library files which are linked together must be compiled with -G 0 option.

D.2 Adding functions with asir.o

There is another way to add functions written in C to Asir, besides the incremental loading method described in the previous section. It is a way to create a new binary file of Asir with ‘asir.o’. This is the one and only way to extend the functions of Asir for those platforms that do not support incremental loading. File ‘asir.o’ is installed under the standard library directory.

(‘/usr/local/lib/asir’ by default.)

Binary file ‘asir.o’ has the same functions as ‘asir’ except for reg_sysf() is undefined. An executable file is created by linking ‘asir.o’ with another object file that contains reg_sysf(). Here, if reg_sysf() is in fact a function for registration of built-in functions, then such functions registered by it can become available just like loading them by incremental loading. For such an object file that has reg_sysf() you may use the ‘xxx.o’ created under ‘o’ in the previous section.

<For platforms with CPU R3000 or R4000.>

     % cc -Wl,-D -Wl,2000000 /.../asir.o xxx.o -o yyy

<And for the other platforms.>

     % cc /.../asir.o xxx.o -o yyy

By compilation above, ‘yyy’ is created. As a result, ‘yyy’ is an extended version of Asir which incorporates functions in ‘xxx.o’. Here, option value 2000000 in the former example, must be substituted by the value specified to HEAP_START_ADDR in ‘include/Risa.tmpl’ at installation. The default is the value here (2000000.)

Appendix E Files of user defined functions

There are several files of user defined functions under the standard library directory. (‘/usr/local/lib/asir’ by default.) Here, we explain some of them.

‘gr’ Groebner basis package. (See Chapter 7 [Groebner bases], page 87) ‘sp’ Operations over algebraic numbers and factorization, Splitting fields. (See Chapter 8

[Algebraic numbers], page 104)

‘alpi’
‘bgk’
‘cyclic’
‘katsura’

‘kimura’ Example polynomial sets for benchmarks of Groebner basis computation. (See Sec-

tion 7.6.14 [katsura hkatsura cyclic hcyclic], page 102)

‘defs.h’ Macro definitions. (See Section 4.2.10 [preprocessor], page 29)

‘fctrtest’

Test program of factorization of integral polynomials. It includes ‘factor.tst’ of REDUCE and several examples for large multiplicity factors. If this file is load()’ed, computation will begin immediately. You may use it as a first test whether Asir at you hand runs correctly.

‘fctrdata’

This contains example polynomials for factorization. It includes polynomials used in ‘fctrtest’. Polynomials contained in vector Alg[] is for the algebraic factorization af() (See Section 8.4.10 [asq af], page 116).

               [0] load("gr")$
               [45] load("sp")$
               [84] load("fctrdata")$
               [175] cputime(1)$
               0msec
               [176] Alg[5];
               x^9-15*x^6-87*x^3-125
               0msec
               [177] af(Alg[5],[newalg(Alg[5])]);
               [[1,1],[75*x^2+(10*#0^7-175*#0^4-470*#0)*x+(3*#0^8-45*#0^5-261*#0^2),1],
               [75*x^2+(-10*#0^7+175*#0^4+395*#0)*x+(3*#0^8-45*#0^5-261*#0^2),1],
               [25*x^2+(25*#0)*x+(#0^8-15*#0^5-87*#0^2),1],[x^2+(#0)*x+(#0^2),1],
               [x+(-#0),1]]
               3.600sec + gc : 1.040sec

‘ifplot’ Examples for plotting (See Section 6.10.1 [ifplot conplot plot], page 76). Vector IS[] contains several famous algebraic curves. Variables H, D, C, S contains something like the suits (Heart, Diamond, Club, and Spade) of cards.

‘num’ Examples of simple operations on numbers. ‘mat’ Examples of simple operations on matrices. ‘ratint’ Indefinite integration of rational functions. For this, files ‘sp’ and ‘gr’ is necessary.

A function ratint() is defined. Its returns a rather complex result. This will be explained later.

     [0] load("gr")$
     [45] load("sp")$
     [84] load("ratint")$
     [102] ratint(x^6/(x^5+x+1),x);
     [1/2*x^2,
     [[(#2)*log(-140*x+(-2737*#2^2+552*#2-131)),161*t#2^3-23*t#2^2+15*t#2-
     1],
     [(#1)*log(-5*x+(-21*#1-4)),21*t#1^2+3*t#1+1]]]

In this example, indefinite integral of the rational function x^6/(x^5+x+1) is computed. The result is a list which comprises two elements: The first element is the rational part of the integral; The second part is the logarithmic part of the integral. The logarithmic part is again a list which comprises finite number of elements, each of which is of form [root*log(poly),defpoly]. This pair should be interpreted to sum up the expression root*log(poly) through all root’s root’s of the defpoly. Here, poly contains root, and substitution for root is equally applied to poly. The logarithmic part in total is obtained by applying such interpretation to all element pairs in the second element of the result and then summing them up all.

Appendix F References

[Becker,Weispfenning]

Becker, T., Weispfenning, V., "Groebner Bases", Graduate Texts in Math. 141, Springer-Verlag, 1993.

[Boehm,Weiser]

Boehm, H., Weiser, M., "Garbage Collection in an Uncooperative Environment", Software Practice & Experience, September 1988, 807-820.

[Batut et al.]

Batut, C., Bernardi, D., Cohen, H., Olivier, M., "User’s Guide to PARI-GP", 1993.

[Gebauer,Moeller]

Gebauer, R., Moeller, H. M., "An installation of Buchberger’s algorithm", J. of Symbolic Computation 6, 275-286.

[Giovini et al.]

Giovini, A., Mora, T., Niesi, G., Robbiano, L., Traverso, C., ""One sugar cube, please" OR Selection strategies in the Buchberger algorithm", Proc. ISSAC’91, 49-54.

[Noro,Takeshima]

Noro, M., Takeshima, T., "Risa/Asir – A Computer Algebra System", Proc. ISSAC’92, 387-396.

Index 131

Index

%

% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

A

af . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 alg. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 algptorat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 algv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 append . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 args. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 asq. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

B

bload . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 bsave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

C

car . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 cdr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 coef. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 conj. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 conplot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 cons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 cputime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 ctrl. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 cyclic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

D

debug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 defpoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 deg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 det . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 diff. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 dn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 dp dtop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 dp hc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 dp hm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 dp ht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 dp lcm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 dp nf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 dp ord. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 dp ptod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 dp red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 dp redble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 dp rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 dp subd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 dp sugar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 dp td . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 dp true sugar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

E

end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 eval. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

F

fac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 fctr. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 funargs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 functor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

G

gcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 gcda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 gr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 grm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

H

hcyclic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 heap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 help. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 hgr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 hgrm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 hkatsura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

I

idiv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ifplot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Index 132

igcd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 inv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 irem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

K

katsura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

L

length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 load. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 lprime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

M

mindeg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

N

newalg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 newmat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 newvect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 nm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 nmono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 ntype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

O

ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

P

p nf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 p terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 pari. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 plot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 prim. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 prime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 print . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 psubst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 ptozp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

Q

quit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

R

random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 rattoalgp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 res . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 reverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 rtostr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

S

sdiv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 setprec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 simpalg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 sp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 sp norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 sqfr. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 sqr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 srem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 strtov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 subst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

T

tcpclose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 tcpdebug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 tcpinit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 tdiv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 tstart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 tstop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 type. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

U

uc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 ufctrhint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

V

var . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 vars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 vtype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

W

which . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 P_{PARI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40, 41, 43, 80}

Index 133

Short Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Risa/Asir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

3 Data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 User language Asir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 5 Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Built-in Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 7 Groebner bases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 8 Algebraic numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Appendix A Details of Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Appendix B Risa/Asir for Macintosh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Appendix C Risa/Asir for MS-DOS/DOS-Extender . . . . . . . . . . . . . . . . 124 Appendix D Augmenting functions by C programs . . . . . . . . . . . . . . . . . 126 Appendix E Files of user defined functions . . . . . . . . . . . . . . . . . . . . . . . 128 Appendix F References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Table Of Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Organization of the Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Risa/Asir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1 Risa and Asir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Features of Asir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3.1 UNIX version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3.2 Macintosh version. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 2.3.3 DOS version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4 Command line options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Environment variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.6 Starting and Terminating an Asir session . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.7 Interruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.8 Error handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.9 Referencing results and special numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.1 Types in Asir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Types of numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Types of indeterminates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18

4 User language Asir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

4.1 Syntax — Difference from C language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Writing user defined functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21

4.2.1 User defined functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.2 variables and indeterminates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.3 Parameters and Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.4 comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.5 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.6 return statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2.7 if statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2.8 loop, break, return, continue . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.9 various expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28 4.2.10 preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.1 What is Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Debugger commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.3 Execution example of debugger. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34 5.4 Sample file of initialization file for Debugger . . . . . . . . . . . . . . . . . . . . . . . 34

6 Built-in Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

6.1 Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36 6.1.1 idiv, irem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.1.2 fac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.1.3 igcd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 6.1.4 inv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.1.5 prime, lprime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.1.6 random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.1.7 nm, dn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.1.8 conj, real, imag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.1.9 eval. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 6.1.10 pari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.1.11 setprec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2 operations with polynomials and rational expressions . . . . . . . . . . . . . . 43 6.2.1 var . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.2.2 vars. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 6.2.3 uc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2.4 coef. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45 6.2.5 deg, mindeg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.2.6 nmono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.2.7 ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.2.8 sdiv, srem, sqr. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48 6.2.9 tdiv. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49 6.2.10 % . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2.11 subst, psubst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.12 diff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.2.13 res. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52 6.2.14 fctr, sqfr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2.15 ufctrhint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.2.16 ptozp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.2.17 prim, cont . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.2.18 gcd, gcdz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.2.19 red. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57

6.3 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.3.1 car, cdr, cons, append, reverse, length . . . . . . . . . . . . . . . . 58

6.4 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.4.1 newvect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.4.2 newmat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.4.3 size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 6.4.4 det . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.5 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.5.1 type. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64 6.5.2 ntype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.5.3 vtype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

6.6 Operations on functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.6.1 functor, args, funargs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.7 Strings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67

6.7.1 rtostr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.7.2 strtov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6.8 Inputs and Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.8.1 end, quit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69 6.8.2 load. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .70 6.8.3 which . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6.8.4 output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.8.5 bsave, bload . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.8.6 print . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.9 Interprocess communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.9.1 tcpinit, tcpdebug, tcpclose . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.10 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.10.1 ifplot, conplot, plot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.11 Miscellaneouses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.11.1 ctrl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.11.2 debug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.11.3 error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.11.4 help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.11.5 time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.11.6 cputime, tstart, tstop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.11.7 heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.11.8 version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.11.9 shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

7 Groebner bases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87

7.1 Distributed polynomial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87 7.2 Reading files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.3 Functions, Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

7.3.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.3.2 Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.4 Ord, variable ordering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90 7.5 Groebner basis computation with rational expression coefficients … 92 7.6 Functions for Groebner basis computation . . . . . . . . . . . . . . . . . . . . . . . . . 92

7.6.1 gr, grm, hgr, hgrm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 7.6.2 dp ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.6.3 dp ptod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.6.4 dp dtop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.6.5 dp nf. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95 7.6.6 dp hm, dp ht, dp hc, dp rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.6.7 dp td, dp sugar, dp true sugar . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.6.8 dp lcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.6.9 dp redble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.6.10 dp subd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 7.6.11 dp red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.6.12 p nf. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100 7.6.13 p terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.6.14 katsura, hkatsura, cyclic, hcyclic . . . . . . . . . . . . . . . . . . 102

8 Algebraic numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104

8.1 Representation of algebraic numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.2 Operations over algebraic numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 8.3 Operations for uni-variate polynomials over an algebraic number field 108

8.3.1 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 8.3.2 Square-free factorization and Factorization . . . . . . . . . . . . . . 109 8.3.3 Splitting fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

8.4 Summary of functions for algebraic numbers. . . . . . . . . . . . . . . . . . . . . .111 8.4.1 newalg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.4.2 defpoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.4.3 alg. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112 8.4.4 algv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 8.4.5 simpalg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 8.4.6 algptorat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8.4.7 rattoalgp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8.4.8 gcda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.4.9 sp norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.4.10 asq, af . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 8.4.11 sp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117

Appendix A Details of Syntax . . . . . . . . . . . . . . . . . . . . . . 119 Appendix B Risa/Asir for Macintosh . . . . . . . . . . . . . . 122

B.1 File organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 B.2 params. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122 B.3 Starting up. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123 B.4 Differences from UNIX version. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123

Appendix C Risa/Asir for MS-DOS/DOS-Extender 124

C.1 Running environments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .124 C.2 Usage of DOS version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Appendix D Augmenting functions by C programs 126

D.1 Incremental loading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 D.2 Adding functions with asir.o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126

Appendix E Files of user defined functions. . . . . . . .128

Appendix F References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131