This file documents @sc{cln}, a Class Library for Numbers.
Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
-Richard Kreckel, @code{<kreckel@@ginac.de>}.
+Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
-Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
+Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005.
+Copyright (C) Richard B. Kreckel 2000, 2001, 2002, 2003, 2004, 2005.
Permission is granted to make and distribute verbatim copies of
this manual provided the copyright notice and this permission notice
@author by Bruno Haible
@page
@vskip 0pt plus 1filll
-Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
+Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005.
+@sp 0
+Copyright @copyright{} Richard Kreckel 2000, 2001, 2002, 2003, 2004, 2005.
@sp 2
Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
@page
+@c Table of contents
+@contents
+
+
@node Top, Introduction, (dir), (dir)
@c @menu
@cindex Sch{@"o}nhage-Strassen multiplication
@end iftex
@ifinfo
-Schönhage-Strassen
-@cindex Schönhage-Strassen multiplication
+Schnhage-Strassen
+@cindex Schnhage-Strassen multiplication
@end ifinfo
multiplication, which is an asymptotically optimal multiplication
algorithm, for multiplication, division and radix conversion.
@subsection C++ compiler
To build CLN, you need a C++ compiler.
-Actually, you need GNU @code{g++ 2.90} or newer, the EGCS compilers will
-do.
-I recommend GNU @code{g++ 2.95} or newer.
+Actually, you need GNU @code{g++ 2.95} or newer.
The following C++ features are used:
classes, member functions, overloading of functions and operators,
The following C++ features are not used:
@code{new}, @code{delete}, virtual inheritance, exceptions.
-CLN relies on semi-automatic ordering of initializations
-of static and global variables, a feature which I could
-implement for GNU g++ only.
-
-@ignore
-@comment cl_modules.h requires g++
-Therefore nearly any C++ compiler will do.
-
-The following C++ compilers are known to compile CLN:
-@itemize @minus
-@item
-GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
-@item
-SGI @code{CC 4}
-@end itemize
-
-The following C++ compilers are known to be unusable for CLN:
-@itemize @minus
-@item
-On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
-in lines containing @code{#if} or @code{#elif} preprocessor commands.
-@item
-On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
-in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
-to have default constructors, and because it probably miscompiles the
-integer multiplication routines.
-@item
-On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
-@code{short}s to @code{int}s by zero-extend.
-@item
-GNU @code{g++ 2.5.8}
-@item
-On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
-initializations will not work.
-@end itemize
-@end ignore
+CLN relies on semi-automatic ordering of initializations of static and
+global variables, a feature which I could implement for GNU g++
+only. Also, it is not known whether this semi-automatic ordering works
+on all platforms when a non-GNU assembler is being used.
@subsection Make utility
@cindex @code{make}
To build CLN, you also need to have GNU @code{make} installed.
+Only GNU @code{make} 3.77 is unusable for CLN; other versions work fine.
+
@subsection Sed utility
@cindex @code{sed}
The @code{configure} command checks out some features of your system and
C++ compiler and builds the @code{Makefile}s. The @code{make} command
-builds the library. This step may take 4 hours on an average workstation.
+builds the library. This step may take about an hour on an average workstation.
The @code{make check} runs some test to check that no important subroutine
has been miscompiled.
CXX="g++ -V egcs-2.91.60" CXXFLAGS="-O -g" ./configure
$ CC="gcc -V 2.95.2" CFLAGS="-O2 -fno-exceptions" \
CXX="g++ -V 2.95.2" CFLAGS="-O2 -fno-exceptions" ./configure
+$ CC="gcc -V 3.0.4" CFLAGS="-O2 -finline-limit=1000 -fno-exceptions" \
+ CXX="g++ -V 3.0.4" CFLAGS="-O2 -finline-limit=1000 -fno-exceptions" \
+ ./configure
@end example
-@ignore
-@comment cl_modules.h requires g++
-You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
-compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
-
-@example
-$ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
-$ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
-@end example
-
-On SGI Irix 5, if you wish not to use @code{g++}:
-
-@example
-$ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
-@end example
-
-On SGI Irix 6, if you wish not to use @code{g++}:
-
-@example
-$ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
- ./configure --without-gmp
-$ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
- -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
- ./configure --without-gmp
-@end example
-@end ignore
Note that for these environment variables to take effect, you have to set
them (assuming a Bourne-compatible shell) on the same line as the
optimizing mode. So you should specify at least @code{-O} in the CXXFLAGS,
or no CXXFLAGS at all. (If CXXFLAGS is not set, CLN will use @code{-O}.)
-If you use @code{g++} version 2.8.x or egcs-2.91.x (a.k.a. egcs-1.1) or
-gcc-2.95.x, I recommend adding @samp{-fno-exceptions} to the CXXFLAGS.
-This will likely generate better code.
+If you use @code{g++} 3.x, I recommend adding @samp{-finline-limit=1000}
+to the CXXFLAGS. This is essential for good code.
+
+If you use @code{g++} gcc-2.95.x or gcc-3.x , I recommend adding
+@samp{-fno-exceptions} to the CXXFLAGS. This will likely generate better code.
+
+If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
+@samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
+CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
+routines. If you use @code{g++} older than 2.95.3 on Sparc you should
+also specify @samp{--disable-shared} because of bad code produced in the
+shared library. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
+won't work at all.
+
+If you use @code{g++} on OSF/1 or Tru64 using gcc-2.95.x, you should
+specify @samp{--disable-shared} because of linker problems with
+duplicate symbols in shared libraries. If you use @code{g++} from
+gcc-3.0.n, with n larger than 1, you should @emph{not} add
+@samp{-fno-exceptions} to the CXXFLAGS, since that will generate wrong
+code (gcc-3.1 is okay again, as is gcc-3.0).
-If you use @code{g++} version egcs-2.91.x (egcs-1.1) or gcc-2.95.x on Sparc,
-add either @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
-CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division routines.
-Also, if you have @code{g++} version egcs-1.1.1 or older on Sparc, you must
-specify @samp{--disable-shared} because @code{g++} would miscompile parts of
-the library.
+Also, please do not compile CLN with @code{g++} using the @code{-O3}
+optimization level. This leads to inferior code quality.
+
+If you use @code{g++} from gcc-3.1, it will need 235 MB of virtual memory.
+You might need some swap space if your machine doesn't have 512 MB of RAM.
By default, both a shared and a static library are built. You can build
CLN as a static (or shared) library only, by calling @code{configure} with
problems. Also, they are generally somewhat slower than static
libraries so runtime-critical applications should be linked statically.
+If you use @code{g++} from gcc-3.1 with option @samp{-g}, you will need
+some disk space: 335 MB for building as both a shared and a static library,
+or 130 MB when building as a shared library only.
+
@subsection Using the GNU MP Library
@cindex GMP
C++ terminology) are not provided. Instead, you can assert and check
that a value belongs to a certain subclass, and return it as element of that
class, using the @samp{As} and @samp{The} macros.
+@cindex cast
@cindex @code{As()()}
@code{As(@var{type})(@var{value})} checks that @var{value} belongs to
@var{type} and returns it as such.
Returns true if the @code{n}th bit (from the right) of @code{x} is set.
Bit 0 is the least significant bit.
-@item uintL logcount (const cl_I& x)
+@item uintC logcount (const cl_I& x)
@cindex @code{logcount ()}
Returns the number of one bits in @code{x}, if @code{x} >= 0, or
the number of zero bits in @code{x}, if @code{x} < 0.
The following functions operate on intervals of bits in integers.
The type
@example
-struct cl_byte @{ uintL size; uintL position; @};
+struct cl_byte @{ uintC size; uintC position; @};
@end example
@cindex @code{cl_byte}
represents the bit interval containing the bits
by @code{-y} bits to the right (if @code{y}<=0). In other words, this
returns @code{floor(x * expt(2,y))}.
-@item uintL integer_length (const cl_I& x)
+@item uintC integer_length (const cl_I& x)
@cindex @code{integer_length ()}
Returns the number of bits (excluding the sign bit) needed to represent @code{x}
in two's complement notation. This is the smallest n >= 0 such that
-2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
2^(n-1) <= x < 2^n.
-@item uintL ord2 (const cl_I& x)
+@item uintC ord2 (const cl_I& x)
@cindex @code{ord2 ()}
@code{x} must be non-zero. This function returns the number of 0 bits at the
right of @code{x} in two's complement notation. This is the largest n >= 0
such that 2^n divides @code{x}.
-@item uintL power2p (const cl_I& x)
+@item uintC power2p (const cl_I& x)
@cindex @code{power2p ()}
@code{x} must be > 0. This function checks whether @code{x} is a power of 2.
If @code{x} = 2^(n-1), it returns n. Else it returns 0.
@subsection Number theoretic functions
@table @code
-@item uint32 gcd (uint32 a, uint32 b)
+@item uint32 gcd (unsigned long a, unsigned long b)
@cindex @code{gcd ()}
@itemx cl_I gcd (const cl_I& a, const cl_I& b)
This function returns the greatest common divisor of @code{a} and @code{b},
@code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
rational number, this function returns true and sets *l = log(a,b), else
it returns false.
+
+@item int jacobi (signed long a, signed long b)
+@cindex @code{jacobi()}
+@itemx int jacobi (const cl_I& a, const cl_I& b)
+Returns the Jacobi symbol
+@tex
+$\left({a\over b}\right)$,
+@end tex
+@ifnottex
+(a/b),
+@end ifnottex
+@code{a,b} must be integers, @code{b>0} and odd. The result is 0
+iff gcd(a,b)>1.
+
+@item cl_boolean isprobprime (const cl_I& n)
+@cindex prime
+@cindex @code{isprobprime()}
+Returns true if @code{n} is a small prime or passes the Miller-Rabin
+primality test. The probability of a false positive is 1:10^30.
+
+@item cl_I nextprobprime (const cl_R& x)
+@cindex @code{nextprobprime()}
+Returns the smallest probable prime >=@code{x}.
@end table
defines the following operations.
@table @code
-@item @var{type} scale_float (const @var{type}& x, sintL delta)
+@item @var{type} scale_float (const @var{type}& x, sintC delta)
@cindex @code{scale_float ()}
@itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
Returns the sign @code{s} of @code{x} as a float. The value is 1 for
@code{x} >= 0, -1 for @code{x} < 0.
-@item uintL float_digits (const @var{type}& x)
+@item uintC float_digits (const @var{type}& x)
@cindex @code{float_digits ()}
Returns the number of mantissa bits in the floating-point representation
of @code{x}, including the hidden bit. The value only depends on the type
of @code{x}, not on its value.
-@item uintL float_precision (const @var{type}& x)
+@item uintC float_precision (const @var{type}& x)
@cindex @code{float_precision ()}
Returns the number of significant mantissa bits in the floating-point
representation of @code{x}. Since denormalized numbers are not supported,
@item cl_UP R->one()
@cindex @code{one ()}
-This returns @code{1 in R}, a polynomial of degree <= 0.
+This returns @code{1 in R}, a polynomial of degree == 0.
@item cl_UP R->canonhom (const cl_I& x)
@cindex @code{canonhom ()}
@cindex @code{degree ()}
Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
+@item sintL ldegree (const cl_UP& x)
+@cindex @code{degree ()}
+Returns the low degree of the polynomial. This is the degree of the first
+non-vanishing polynomial coefficient. The zero polynomial has ldegree @code{-1}.
+
@item cl_ring_element coeff (const cl_UP& x, uintL index)
@cindex @code{coeff ()}
Returns the coefficient of @code{X^index} in the polynomial @code{x}.
@cindex Sch{@"o}nhage-Strassen multiplication
@end iftex
@ifinfo
-Schönhage-Strassen
-@cindex Schönhage-Strassen multiplication
+Schnhage-Strassen
+@cindex Schnhage-Strassen multiplication
@end ifinfo
multiplication, which is an asymptotically optimal multiplication
algorithm.
different @samp{--prefix} than CLN, you will either have to manually
move @file{cln.m4} to automake's @file{$datadir/aclocal}, or give
aclocal the @samp{-I} option when running it. Here is a possible example
-to be included in your package's @file{configure.in}:
+to be included in your package's @file{configure.ac}:
@example
AC_PATH_CLN(1.1.0, [
LIBS="$LIBS $CLN_LIBS"
@printindex my
-@c Table of contents
-@contents
-
-
@bye
git://www.ginac.de / cln.git / blobdiff