Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
-Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002.
-Copyright (C) Richard B. Kreckel 2000, 2001, 2002, 2003, 2004.
+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, 2001, 2002.
+Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005.
@sp 0
-Copyright @copyright{} Richard Kreckel 2000, 2001, 2002.
+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.
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}
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++} 3.0.x or 3.1, I recommend adding
-@samp{-finline-limit=1000} to the CXXFLAGS. This is essential for good 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.
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,
@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.
@printindex my
-@c Table of contents
-@contents
-
-
@bye
git://www.ginac.de / cln.git / blobdiff