% (C) 2007, William Hart, David Harvey
%   This file is part of FLINT.

%   FLINT is free software; you can redistribute it and/or modify
%   it under the terms of the GNU General Public License as published by
%   the Free Software Foundation; either version 2 of the License, or
%   (at your option) any later version.

%   FLINT is distributed in the hope that it will be useful,
%   but WITHOUT ANY WARRANTY; without even the implied warranty of
%   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%   GNU General Public License for more details.

%   You should have received a copy of the GNU General Public License
%   along with FLINT; if not, write to the Free Software
%   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA

\documentclass[a4paper,10pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{eucal}
\usepackage{amscd}
\usepackage{url}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{wrapfig}
\urlstyle{sf}

\addtolength{\oddsidemargin}{-0.75in}
\addtolength{\evensidemargin}{-0.75in}
\addtolength{\textwidth}{1.5in}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Pee}{\mathbb{P}}
\newcommand{\EuO}{\mathcal{O}}
\newcommand{\Qbar}{\overline{\mathbb{Q}}}
\newcommand{\fn}{\hfill[Function]}
\newcommand{\macro}{\hfill[Macro]}
\newcommand{\gmp}{\hfill[GMP]}

\newcommand{\ljk}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\modulo}[1]{\;\left(\mbox{mod}\;#1\right)}
\newcommand{\fr}{\mathfrak}

\def\notdivides{\mathrel{\kern-3pt\not\!\kern4.5pt\bigm|}}
\def\nmid{\notdivides}
\def\nsubseteq{\mathrel{\kern-3pt\not\!\kern2.5pt\subseteq}}

\parindent=0pt
\parskip 4pt plus 2pt minus 2pt

%\email{w.b.hart@maths.warwick.ac.uk}

\title{FLINT: Fast Library for Number Theory}
\author{William B. Hart}

\begin{document}
\maketitle
\lstset{language=c}
\lstset{escapeinside=\%\%}

\section{Introduction}
FLINT is a C library for doing number theory. It is released under the GPL and we encourage interested people to contribute and/or fork our code.

FLINT will eventually have implementations of algorithms in number theory, specifically algebraic number theory, including p-adics. We have no plans to implement algebraic geometry, group theory or elliptic curve algorithms, but this may change if a suitable maintainer is found who would like to oversee such a project.

FLINT is currently maintained by Bill Hart from Warwick University and David Harvey from Harvard.

Although FLINT is designed as a standalone C library for direct use in C programs by number theorists, parts of FLINT will be made available for use in SAGE, maintained by William Stein. 

FLINT 1.0 is the first version of FLINT which will be a standalone C library with a documented interface which can be used by an end user. Its release date is December 1st 2007. 

\subsection{Code Base}
FLINT is written entirely in C and all code must conform to the C99 standard. It must compile with the GCC toolset, available on most unix based systems. FLINT should depend only on tightly coded, highly respected libraries. In particular any function from GMP may be used. There is also an intention to add the packages fpLLL, mpfr, gf2x and GMP-ECM to FLINT in the near future.

The code is maintained at a sourceforge SVN repository. The main development code is available at:

https://flint.svn.sourceforge.net/svnroot/flint/trunk/

Released versions of FLINT are forked from the main trunk and stored in separate folders in the repository, e.g. FLINT 1.0 is at

https://flint.svn.sourceforge.net/svnroot/flint/flint-1.0/

Various experimental branches are held at:

https://flint.svn.sourceforge.net/svnroot/flint/branches/

Programmers who wish to fiddle with some new ideas can start a branch ad libitum and play with FLINT files there without affecting the main development code.

\subsection{Website}
The FLINT website is found at:

http://www.flintlib.org/

Information about FLINT (pre)releases, progress updates and future directions can be found there. Profiles will also be displayed on the website for comparison with other comparable packages and projects.

In addition, programmers can access the FLINT sourceforge project at:

http://www.sourceforge.org/flint/

\subsection{Development forums}
Sourceforge provides us with a development forum. Developers who wish to be added to the FLINT development list can send an email requesting addition to hart\_wb@yahoo.com

In addition, on occasion, FLINT developers find it useful to discuss things on IRC. The channel for this is flint-dev on the irc.freenode.net server. 

\subsection{Performance}
The aim is for all FLINT functions to be at least as fast as the comparable functions available in the open source projects of a similar nature. The more elaborate functions will be faster in FLINT than in other open source projects where possible, and sometimes significantly faster.

In particular FLINT will perform as well as or better than NTL, Pari and LiDIA, which seem to be the most popular open source alternatives. FLINT will be regularly profiled and compared against these packages on a function by function basis. The more elaborate functions will have more elaborate profiles.

We also aim to beat MAGMA where possible, however it won't be a condition for a release of FLINT to be made that all functions in FLINT perform better eveywhere, than their MAGMA counterparts. 

Profiles comparing FLINT with MAGMA will also be done regularly. However such a comparison is not fair to either FLINT or MAGMA, since MAGMA is an interpreted package, not a C library, and MAGMA is closed source and non-free, whereas FLINT is free and open source.

\subsection{Testing}
All functions available to an end user in FLINT will have a corresponding test function (to be written by the person who wrote the function, if no one else volunteers to do it for them). Also, all sufficiently sophisticated internal FLINT functions must have a corresponding test function. One line functions, which for example just return the value of some field of a structure, need not have a test function.

The general strategies used for testing FLINT functions are:

1) Send a large amount of random data of varying sizes and parameters to the function where possible. 

2) Use the special GMP functions for generating random integers with long strings of 1's and 0's where this is possible.

3) If there is an associated function which should undo the effect of the function being tested (e.g. an addition function and a corresponding subtraction function), test the functions against one another.

4) If possible, get the function to do a standard computation, the result of which can be checked, e.g. check a factoring function by feeding numbers which are the known product of random integers and check the result. 

5) If no other form of testing is possible, write a very simple version of the function which performs very poorly perhaps, or which uses a much simpler algorithm but produces the same result and compare the outputs. 

6) Always do sufficient "eyeball" tests, i.e. get the function to print its output to the screen and look at the output to see if it looks like it is returning vaguely reasonable looking results to the eye.

7) Check boundary cases and just either side of them.

If it is only possible to test a function in situ (i.e. as part of a larger function which calls it), and a simpler version cannot be implemented to test against, insert checkpoints within each branch of the function and run random data through the function until such time as all branches have been worked. Explicitly check that all branches did what they were supposed to. 

For convenience, a macro called FLINT\_ASSERT is available. It works like a function which takes a condition as a parameter. If at that point in the code, the condition fails, then the assert will pick that up and tell you the line number where the assert failed. These are particularly useful to check that certain conditions were met after a branch executed. For FLINT\_ASSERT's to be operational, one needs to set the appropriate flag in flint.h.

The functions for testing the functions in the module fmpz\_poly.c should all be in a file called fmpz_poly-test.c, etc.

The final version of a test file should take approximately 1-2 seconds to test each function in the file being tested, where possible (sometimes a much longer time may be necessary). However, much more extensive tests should be run by the programmer when the function is first written, to ensure that the function works as expected in every conceivable situation, especially if the function is very involved. Such test code should be retained, but need not execute when a user executes a make test.

Each final test function should print which function is being tested and then ok or fail. Examples of easy ways to set up such a test file can be found in the trunk of the development code, e.g. fmpz\_poly-test.c 

\subsection{Parallel Processing}
FLINT will eventually support parallel processing at the thread level using pthreads. All functions that are sufficiently complicated will allow threads to be used. A global \#define USE\_THREADS in flint.h will specify whether threads should be used, and flint files using threads should contain 

\begin{verbatim}#include "flint.h"

#ifdef USE_THREADS
//code that makes use of threads
#else
//code that doesn't use threads
#endif\end{verbatim}

The files flint-threads.h and flint-threads.c will contain a flint thread manager. It will have a function which can be accessed which gives an upper limit on the number of new threads that should be created by a function which wants to create some new threads. All threaded functions should check how many threads it is allowed to create before creating any.

It will also have various other helper functions for implementing more complicated threaded scenarios where threads will be kept hanging around waiting for work and woken up when work is available for them, or for implementing work stealing etc.

\subsection{Memory Manager}
FLINT has a memory manager. When we were implementing polynomial multiplication, we found that just allocating memory as needed with malloc, was too slow. It is hopelessly bad if the function is recursive.

At the very least, functions should allocate as much of the memory as they need up front, then break it up as needed, rather than allocate lots of small chunks. But even this approach slows some things down. Thus we introduced a memory manager.

The FLINT memory manager is included in files memory-manager.h and memory-manager.c. It is a stack based memory manager (or will be). 

Since stack based memory management is not ideal for threaded programs, it is implemented in a slightly strange way. Flint memory allocation functions automatically determine the current thread number. So if there are numerous threads running within a FLINT function (or indeed a program running multiple threads, each calling different FLINT functions), each thread that is started will have a different stack of memory allocated to it. 

However, the implementation details of the memory manager are irrelevant, since it will just work, regardless of how it is implemented. The only constraint in actual programming is that since the memory manager is stack based, any given thread will free memory in the reverse order to what it was allocated in the first place, e.g.

\begin{verbatim}mp_limb_t * data1 = (mp_limb_t *) flint_stack_alloc(1000);
mp_limb_t * data2 = (mp_limb_t *) flint_stack_alloc(2000);
mp_limb_t * data3 = (mp_limb_t *) flint_stack_alloc(300);

// intervening code

flint_stack_release(); //free data3
flint_stack_release(); //free data2
flint_stack_release(); //free data1
\end{verbatim}

Flint will automatically determine which thread made the call and allocate/deallocate from the correct stack.

\subsection{FLINT modules}
FLINT is implemented as a series of modules which perform related functions. Examples of modules are fmpz\_poly, fmpz, ZmodF, ZmodF_poly, mpz\_poly, etc.

Each module has associated .c and .h files named after it, and an associated test file. E.g. the module fmpz\_poly contains functions for doing arithmetic with polynomials over the integers all of which are contained in fmpz\_poly.c and fmpz\_poly.h. The test file for fmpz\_poly will be called fmpz\_poly-test.h. Running ``make test'' will compile and run all test files in FLINT. To run a specific test program, one can just type the name of the module, e.g. ./fmpz\_poly-test, after all the test files have compiled. 

Files with names like fmpz\_poly-profile.c are for generating profiles for functions in fmpz\_poly. All such profile files are similar. To make all the profile files, one types ``make profile''. To run a specific profile, one types for example ./fmpz\_poly-profile once they have all compiled and a list of profile targets wil be given.

Eventually FLINT will have all of the following modules:

mpz\_extras - Arithmetic for GMP mpz\_t integers

fmpz - Arithmetic for the FLINT ``flat'' multi=precision integer format

long\_extras - Arithmetic for long/unsigned long integers including modulo arithmetic

mpn\_extras - Arithmetic for integers in GMP mpn format

ZmodF - Arithmetic for integers modulo a Fermat number $p = 2^nB+1$ where $B$ is the number of bits per limb

Zmod - Arithmetic for $Z/nZ$ for a multi precision modulus $n$

Zp - padic arithmetic

FF - Arithmetic for finite fields 

GF2 - Functions for arithmetic over GF2

\vspace{5mm}

mpz\_poly - Polynomials over mpz\_t integers

fmpz\_poly - Polynomials over integers in fmpz format

ZmodF\_poly - Polynomial functions for polys mod a Fermat number

Zmod\_poly - Polynomials over $Z/nZ$ for multiprecision $n$

zmod\_poly - Polynomials over $Z/nZ$ for $n$ an unsigned long

Zp\_poly - Polys over padics

GF2\_poly - Polys over GF2

\vspace{5mm}

mpz\_mat - Linear Algebra over mpz\_t integers

fmpz\_mat - Linear Algebra over integers in fmpz format

Zmod\_mat - Linear Algebra over $Z/nZ$ for multiprecision $n$

zmod\_mat - Linear Algebra over $Z/nZ$ for an unsigned long $n$

Zp\_mat - Linear Algebra over padics

GF2\_mat - Linear Algebra over GF2

\vspace{5mm}

QFB - Binary quadratic forms

QNF - Quadratic number fields

QZeta - Cyclotomic number fields

NF - General Number Fields

\subsection{Introduction to the FLINT C files}
The file flint.h contains all the univeral \#defines for flint, including ones that specify how many bits per limb the machine has, whether threads should be used and many other useful pieces of information.

\section{mpz\_poly}
The mpz\_poly interface has functions for doing arithmetic with polynomials defined over integers implemented as GMP mpz\_t's. 

The ``alloc'' field of the mpz\_poly\_t type specifies the number of coefficients which have been allocated and the ``length'' field specifies the current length of the polynomial. Alloc must be at least 1 but length can be 0 for the zero polynomial. Alloc should always be less than or equal to length.

\section{fmpz\_poly}
The fmpz\_poly interface has functions for doing arithmetic with polynomials defined over integers implemented as a special flint type which has a sign and magnitude. Each coefficient has a sign limb, followed by zero or more limbs (the number of which is specified by the absolute value of the sign limb) which contain a multiprecision coefficient. If the coefficient is zero, the sign limb is zero. If the sign limb is negative, the coefficient is interpreted to be negative, etc.

However, each coefficient is allocated exactly the same number of limbs (even if not all of them are used in each coefficient). The number of limbs allocated for each limb (excluding the sign limb) is specified in the ``limbs'' field of the fmpz\_poly\_t type. The length of the polynomial is given by the ``length'' field and the ``alloc'' field specifies the number of currently allocated coefficients (length should always be less than or equal to alloc). Alloc may be 0 and length can be 0 for the zero polynomial. 

The fmpz\_poly module is divided into two halves. The first half implements functions beginning fmpz\_poly, which manage everything for the user. In particular, if the result of a function returns a polynomial which is too long to fit in the allocated space of the output polynomial the whole output polynomial is reallocated automatically.

The other half of the module implements functions beginning \_fmpz\_poly. These functions do not allocate extra space and require the user to do the allocation in advance. This includes increasing the number of allocated coefficients and increasing the number of limbs allocated for each coefficient, as necessary.

The useful feature of the \_fmpz\_poly functions is that one can specify a subset of the coefficients of a polynomial and operate on just those coefficients without copying them out to another polynomial first. As such, no such function should modify the ``limbs'' field of any fmpz\_poly\_t's that are passed to it. These functions should also never even look at the ``alloc'' field, since it is not even guaranteed to be set. 

\end{document}