1 \input texinfo @c -*-texinfo-*-
4 @settitle CLN, a Class Library for Numbers
5 @c @setchapternewpage off
6 @c I hate putting "@noindent" in front of every paragraph.
7 @c For `info' and TeX only.
11 @dircategory Mathematics
13 * CLN: (cln). Class Library for Numbers (C++).
18 @c Don't need the other types of indices.
29 This file documents @sc{cln}, a Class Library for Numbers.
31 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
32 Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
34 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008.
35 Copyright (C) Richard B. Kreckel 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008.
37 Permission is granted to make and distribute verbatim copies of
38 this manual provided the copyright notice and this permission notice
39 are preserved on all copies.
42 Permission is granted to process this file through TeX and print the
43 results, provided the printed document carries copying permission
44 notice identical to this one except for the removal of this paragraph
45 (this paragraph not being relevant to the printed manual).
48 Permission is granted to copy and distribute modified versions of this
49 manual under the conditions for verbatim copying, provided that the entire
50 resulting derived work is distributed under the terms of a permission
51 notice identical to this one.
53 Permission is granted to copy and distribute translations of this manual
54 into another language, under the above conditions for modified versions,
55 except that this permission notice may be stated in a translation approved
61 @c prevent ugly black rectangles on overfull hbox lines:
64 @title CLN, a Class Library for Numbers
66 @author @uref{http://www.ginac.de/CLN}
68 @vskip 0pt plus 1filll
69 Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008.
71 Copyright @copyright{} Richard B. Kreckel 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008.
74 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
75 Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
77 Permission is granted to make and distribute verbatim copies of
78 this manual provided the copyright notice and this permission notice
79 are preserved on all copies.
81 Permission is granted to copy and distribute modified versions of this
82 manual under the conditions for verbatim copying, provided that the entire
83 resulting derived work is distributed under the terms of a permission
84 notice identical to this one.
86 Permission is granted to copy and distribute translations of this manual
87 into another language, under the above conditions for modified versions,
88 except that this permission notice may be stated in a translation approved
108 * Ordinary number types::
109 * Functions on numbers::
113 * Symbolic data types::
114 * Univariate polynomials::
116 * Using the library::
120 --- The Detailed Node Listing ---
125 * Building the library::
126 * Installing the library::
137 * Using the GNU MP Library::
139 Ordinary number types
142 * Floating-point numbers::
148 * Constructing numbers::
149 * Elementary functions::
150 * Elementary rational functions::
151 * Elementary complex functions::
153 * Rounding functions::
155 * Transcendental functions::
156 * Functions on integers::
157 * Functions on floating-point numbers::
158 * Conversion functions::
159 * Random number generators::
160 * Modifying operators::
164 * Constructing integers::
165 * Constructing rational numbers::
166 * Constructing floating-point numbers::
167 * Constructing complex numbers::
169 Transcendental functions
171 * Exponential and logarithmic functions::
172 * Trigonometric functions::
173 * Hyperbolic functions::
177 Functions on integers
179 * Logical functions::
180 * Number theoretic functions::
181 * Combinatorial functions::
185 * Conversion to floating-point numbers::
186 * Conversion to rational numbers::
190 * Internal and printed representation::
196 * Modular integer rings::
197 * Functions on modular integers::
204 Univariate polynomials
206 * Univariate polynomial rings::
207 * Functions on univariate polynomials::
208 * Special polynomials::
213 * Memory efficiency::
215 * Garbage collection::
222 * Debugging support::
223 * Reporting Problems::
228 * Floating-point underflow::
230 * Customizing the memory allocator::
235 @chapter Introduction
238 CLN is a library for computations with all kinds of numbers.
239 It has a rich set of number classes:
243 Integers (with unlimited precision),
249 Floating-point numbers:
259 Long float (with unlimited precision),
266 Modular integers (integers modulo a fixed integer),
269 Univariate polynomials.
273 The subtypes of the complex numbers among these are exactly the
274 types of numbers known to the Common Lisp language. Therefore
275 @code{CLN} can be used for Common Lisp implementations, giving
276 @samp{CLN} another meaning: it becomes an abbreviation of
277 ``Common Lisp Numbers''.
280 The CLN package implements
284 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
285 comparisons, @dots{}),
288 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
291 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
292 functions and their inverse functions).
296 CLN is a C++ library. Using C++ as an implementation language provides
300 efficiency: it compiles to machine code,
302 type safety: the C++ compiler knows about the number types and complains
303 if, for example, you try to assign a float to an integer variable.
305 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
306 @code{==}, @dots{} operators as in C or C++.
310 CLN is memory efficient:
314 Small integers and short floats are immediate, not heap allocated.
316 Heap-allocated memory is reclaimed through an automatic, non-interruptive
321 CLN is speed efficient:
325 The kernel of CLN has been written in assembly language for some CPUs
326 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
329 On all CPUs, CLN may be configured to use the superefficient low-level
330 routines from GNU GMP version 3.
332 It uses Karatsuba multiplication, which is significantly faster
333 for large numbers than the standard multiplication algorithm.
335 For very large numbers (more than 12000 decimal digits), it uses
337 Sch{@"o}nhage-Strassen
338 @cindex Sch{@"o}nhage-Strassen multiplication
342 @cindex Schoenhage-Strassen multiplication
344 multiplication, which is an asymptotically optimal multiplication
345 algorithm, for multiplication, division and radix conversion.
347 @cindex binary splitting
348 It uses binary splitting for fast evaluation of series of rational
349 numbers as they occur in the evaluation of elementary functions and some
354 CLN aims at being easily integrated into larger software packages:
358 The garbage collection imposes no burden on the main application.
360 The library provides hooks for memory allocation and throws exceptions
364 All non-macro identifiers are hidden in namespace @code{cln} in
365 order to avoid name clashes.
370 @chapter Installation
372 This section describes how to install the CLN package on your system.
377 * Building the library::
378 * Installing the library::
382 @node Prerequisites, Building the library, Installation, Installation
383 @section Prerequisites
392 @subsection C++ compiler
394 To build CLN, you need a C++ compiler.
395 Actually, you need GNU @code{g++ 3.0.0} or newer.
397 The following C++ features are used:
398 classes, member functions, overloading of functions and operators,
399 constructors and destructors, inline, const, multiple inheritance,
400 templates and namespaces.
402 The following C++ features are not used:
403 @code{new}, @code{delete}, virtual inheritance.
405 CLN relies on semi-automatic ordering of initializations of static and
406 global variables, a feature which I could implement for GNU g++
407 only. Also, it is not known whether this semi-automatic ordering works
408 on all platforms when a non-GNU assembler is being used.
411 @subsection Make utility
414 To build CLN, you also need to have GNU @code{make} installed.
416 Only GNU @code{make} 3.77 is unusable for CLN; other versions work fine.
419 @subsection Sed utility
422 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
423 This is because the libtool script, which creates the CLN library, relies
424 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
428 @node Building the library
429 @section Building the library
431 As with any autoconfiguring GNU software, installation is as easy as this:
439 If on your system, @samp{make} is not GNU @code{make}, you have to use
440 @samp{gmake} instead of @samp{make} above.
442 The @code{configure} command checks out some features of your system and
443 C++ compiler and builds the @code{Makefile}s. The @code{make} command
444 builds the library. This step may take about half an hour on an average
445 workstation. The @code{make check} runs some test to check that no
446 important subroutine has been miscompiled.
448 The @code{configure} command accepts options. To get a summary of them, try
454 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
456 You can specify the C compiler, the C++ compiler and their options through
457 the following environment variables when running @code{configure}:
461 Specifies the C compiler.
464 Flags to be given to the C compiler when compiling programs (not when linking).
467 Specifies the C++ compiler.
470 Flags to be given to the C++ compiler when compiling programs (not when linking).
473 Flags to be given to the C/C++ preprocessor.
476 Flags to be given to the linker.
482 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
485 $ CC="gcc -V 3.2.3" CFLAGS="-O2 -finline-limit=1000" \
486 CXX="g++ -V 3.2.3" CXXFLAGS="-O2 -finline-limit=1000" \
487 CPPFLAGS="-DNO_ASM" ./configure
490 $ CC="gcc-4.2" CFLAGS="-O2" CXX="g++-4.2" CXXFLAGS="-O2" ./configure
493 Note that for these environment variables to take effect, you have to set
494 them (assuming a Bourne-compatible shell) on the same line as the
495 @code{configure} command. If you made the settings in earlier shell
496 commands, you have to @code{export} the environment variables before
497 calling @code{configure}. In a @code{csh} shell, you have to use the
498 @samp{setenv} command for setting each of the environment variables.
500 Currently CLN works only with the GNU @code{g++} compiler, and only in
501 optimizing mode. So you should specify at least @code{-O} in the
502 CXXFLAGS, or no CXXFLAGS at all. If CXXFLAGS is not set, CLN will be
503 compiled with @code{-O}.
505 The assembler language kernel can be turned off by specifying
506 @code{-DNO_ASM} in the CPPFLAGS. If @code{make check} reports any
507 problems, you may try to clean up (see @ref{Cleaning up}) and configure
508 and compile again, this time with @code{-DNO_ASM}.
510 If you use @code{g++} 3.2.x or earlier, I recommend adding
511 @samp{-finline-limit=1000} to the CXXFLAGS. This is essential for good
514 If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
515 @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
516 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
517 routines. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
520 Also, please do not compile CLN with @code{g++} using the @code{-O3}
521 optimization level. This leads to inferior code quality.
523 Some newer versions of @code{g++} require quite an amount of memory.
524 You might need some swap space if your machine doesn't have 512 MB of
527 By default, both a shared and a static library are built. You can build
528 CLN as a static (or shared) library only, by calling @code{configure}
529 with the option @samp{--disable-shared} (or @samp{--disable-static}).
530 While shared libraries are usually more convenient to use, they may not
531 work on all architectures. Try disabling them if you run into linker
532 problems. Also, they are generally slightly slower than static
533 libraries so runtime-critical applications should be linked statically.
537 * Using the GNU MP Library::
540 @node Using the GNU MP Library
541 @subsection Using the GNU MP Library
544 CLN may be configured to make use of a preinstalled @code{gmp} library
545 for some low-level routines. Please make sure that you have at least
546 @code{gmp} version 3.0 installed since earlier versions are unsupported
547 and likely not to work. Using @code{gmp} is known to be quite a boost
548 for CLN's performance.
550 By default, CLN will autodetect @code{gmp} and use it. If you do not
551 want CLN to make use of a preinstalled @code{gmp} library, then you can
552 explicitly specify so by calling @code{configure} with the option
553 @samp{--without-gmp}.
555 If you have installed the @code{gmp} library and its header files in
556 some place where the compiler cannot find it by default, you must help
557 @code{configure} and specify the prefix that was used when @code{gmp}
558 was configured. Here is an example:
561 $ ./configure --with-gmp=/opt/gmp-4.2.2
564 This assumes that the @code{gmp} header files have been installed in
565 @file{/opt/gmp-4.2.2/include/} and the library in
566 @file{/opt/gmp-4.2.2/lib/}. More uncommon GMP installations can be
567 handled by setting CPPFLAGS and LDFLAGS appropriately prior to running
571 @node Installing the library
572 @section Installing the library
575 As with any autoconfiguring GNU software, installation is as easy as this:
581 The @samp{make install} command installs the library and the include files
582 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
583 if you haven't specified a @code{--prefix} option to @code{configure}).
584 This step may require superuser privileges.
586 If you have already built the library and wish to install it, but didn't
587 specify @code{--prefix=@dots{}} at configure time, just re-run
588 @code{configure}, giving it the same options as the first time, plus
589 the @code{--prefix=@dots{}} option.
595 You can remove system-dependent files generated by @code{make} through
601 You can remove all files generated by @code{make}, thus reverting to a
602 virgin distribution of CLN, through
609 @node Ordinary number types
610 @chapter Ordinary number types
612 CLN implements the following class hierarchy:
620 Real or complex number
629 +-------------------+-------------------+
631 Rational number Floating-point number
633 <cln/rational.h> <cln/float.h>
635 | +--------------+--------------+--------------+
637 cl_I Short-Float Single-Float Double-Float Long-Float
638 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
639 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
642 @cindex @code{cl_number}
643 @cindex abstract class
644 The base class @code{cl_number} is an abstract base class.
645 It is not useful to declare a variable of this type except if you want
646 to completely disable compile-time type checking and use run-time type
651 @cindex complex number
652 The class @code{cl_N} comprises real and complex numbers. There is
653 no special class for complex numbers since complex numbers with imaginary
654 part @code{0} are automatically converted to real numbers.
657 The class @code{cl_R} comprises real numbers of different kinds. It is an
661 @cindex rational number
663 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
664 integers. There is no special class for non-integral rational numbers
665 since rational numbers with denominator @code{1} are automatically converted
669 The class @code{cl_F} implements floating-point approximations to real numbers.
670 It is an abstract class.
675 * Floating-point numbers::
681 @section Exact numbers
684 Some numbers are represented as exact numbers: there is no loss of information
685 when such a number is converted from its mathematical value to its internal
686 representation. On exact numbers, the elementary operations (@code{+},
687 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
690 In CLN, the exact numbers are:
694 rational numbers (including integers),
696 complex numbers whose real and imaginary parts are both rational numbers.
699 Rational numbers are always normalized to the form
700 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
701 are coprime integers and the denominator is positive. If the resulting
702 denominator is @code{1}, the rational number is converted to an integer.
704 @cindex immediate numbers
705 Small integers (typically in the range @code{-2^29}@dots{}@code{2^29-1},
706 for 32-bit machines) are especially efficient, because they consume no heap
707 allocation. Otherwise the distinction between these immediate integers
708 (called ``fixnums'') and heap allocated integers (called ``bignums'')
709 is completely transparent.
712 @node Floating-point numbers
713 @section Floating-point numbers
714 @cindex floating-point number
716 Not all real numbers can be represented exactly. (There is an easy mathematical
717 proof for this: Only a countable set of numbers can be stored exactly in
718 a computer, even if one assumes that it has unlimited storage. But there
719 are uncountably many real numbers.) So some approximation is needed.
720 CLN implements ordinary floating-point numbers, with mantissa and exponent.
722 @cindex rounding error
723 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
724 only return approximate results. For example, the value of the expression
725 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
726 @samp{0.7}. Rounding errors like this one are inevitable when computing
727 with floating-point numbers.
729 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
730 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
731 rule: It first computes the exact mathematical result and then returns the
732 floating-point number which is nearest to this. If two floating-point numbers
733 are equally distant from the ideal result, the one with a @code{0} in its least
734 significant mantissa bit is chosen.
736 Similarly, testing floating point numbers for equality @samp{x == y}
737 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
738 for some well-chosen @code{epsilon}.
740 Floating point numbers come in four flavors:
745 Short floats, type @code{cl_SF}.
746 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
747 and 17 mantissa bits (including the ``hidden'' bit).
748 They don't consume heap allocation.
752 Single floats, type @code{cl_FF}.
753 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
754 and 24 mantissa bits (including the ``hidden'' bit).
755 In CLN, they are represented as IEEE single-precision floating point numbers.
756 This corresponds closely to the C/C++ type @samp{float}.
760 Double floats, type @code{cl_DF}.
761 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
762 and 53 mantissa bits (including the ``hidden'' bit).
763 In CLN, they are represented as IEEE double-precision floating point numbers.
764 This corresponds closely to the C/C++ type @samp{double}.
768 Long floats, type @code{cl_LF}.
769 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
770 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
771 The precision of a long float is unlimited, but once created, a long float
772 has a fixed precision. (No ``lazy recomputation''.)
775 Of course, computations with long floats are more expensive than those
776 with smaller floating-point formats.
778 CLN does not implement features like NaNs, denormalized numbers and
779 gradual underflow. If the exponent range of some floating-point type
780 is too limited for your application, choose another floating-point type
781 with larger exponent range.
784 As a user of CLN, you can forget about the differences between the
785 four floating-point types and just declare all your floating-point
786 variables as being of type @code{cl_F}. This has the advantage that
787 when you change the precision of some computation (say, from @code{cl_DF}
788 to @code{cl_LF}), you don't have to change the code, only the precision
789 of the initial values. Also, many transcendental functions have been
790 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
791 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
792 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
793 the floating point contagion rule happened to change in the future.)
796 @node Complex numbers
797 @section Complex numbers
798 @cindex complex number
800 Complex numbers, as implemented by the class @code{cl_N}, have a real
801 part and an imaginary part, both real numbers. A complex number whose
802 imaginary part is the exact number @code{0} is automatically converted
805 Complex numbers can arise from real numbers alone, for example
806 through application of @code{sqrt} or transcendental functions.
813 Conversions from any class to any its superclasses (``base classes'' in
814 C++ terminology) is done automatically.
816 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
817 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
818 @code{cl_N} and @code{cl_number}.
820 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
821 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
822 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
823 efficiency. On 32-bit systems, their range is therefore limited:
827 The conversion from @samp{int} works only if the argument is < 2^29 and >= -2^29.
829 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
832 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
833 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
834 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
835 in error on 32-bit machines.
836 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
837 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
838 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
839 @samp{cl_I}, first convert it to an @samp{unsigned long}. On 64-bit machines
840 there is no such restriction. There, conversions from arbitrary 32-bit @samp{int}
841 values always works correctly.
843 Conversions from the C built-in type @samp{float} are provided for the classes
844 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
846 Conversions from the C built-in type @samp{double} are provided for the classes
847 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
849 Conversions from @samp{const char *} are provided for the classes
850 @code{cl_I}, @code{cl_RA},
851 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
852 @code{cl_R}, @code{cl_N}.
853 The easiest way to specify a value which is outside of the range of the
854 C++ built-in types is therefore to specify it as a string, like this:
857 cl_I order_of_rubiks_cube_group = "43252003274489856000";
859 Note that this conversion is done at runtime, not at compile-time.
861 Conversions from @code{cl_I} to the C built-in types @samp{int},
862 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
866 @item int cl_I_to_int (const cl_I& x)
867 @cindex @code{cl_I_to_int ()}
868 @itemx unsigned int cl_I_to_uint (const cl_I& x)
869 @cindex @code{cl_I_to_uint ()}
870 @itemx long cl_I_to_long (const cl_I& x)
871 @cindex @code{cl_I_to_long ()}
872 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
873 @cindex @code{cl_I_to_ulong ()}
874 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
875 representable in the range of @var{ctype}, a runtime error occurs.
878 Conversions from the classes @code{cl_I}, @code{cl_RA},
879 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
881 to the C built-in types @samp{float} and @samp{double} are provided through
885 @item float float_approx (const @var{type}& x)
886 @cindex @code{float_approx ()}
887 @itemx double double_approx (const @var{type}& x)
888 @cindex @code{double_approx ()}
889 Returns an approximation of @code{x} of C type @var{ctype}.
890 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
891 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
894 Conversions from any class to any of its subclasses (``derived classes'' in
895 C++ terminology) are not provided. Instead, you can assert and check
896 that a value belongs to a certain subclass, and return it as element of that
897 class, using the @samp{As} and @samp{The} macros.
899 @cindex @code{As()()}
900 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
901 @var{type} and returns it as such.
902 @cindex @code{The()()}
903 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
904 @var{type} and returns it as such. It is your responsibility to ensure
905 that this assumption is valid. Since macros and namespaces don't go
906 together well, there is an equivalent to @samp{The}: the template
914 if (!(x >= 0)) abort();
915 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
916 // In general, it would be a rational number.
917 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
922 @node Functions on numbers
923 @chapter Functions on numbers
925 Each of the number classes declares its mathematical operations in the
926 corresponding include file. For example, if your code operates with
927 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
931 * Constructing numbers::
932 * Elementary functions::
933 * Elementary rational functions::
934 * Elementary complex functions::
936 * Rounding functions::
938 * Transcendental functions::
939 * Functions on integers::
940 * Functions on floating-point numbers::
941 * Conversion functions::
942 * Random number generators::
943 * Modifying operators::
946 @node Constructing numbers
947 @section Constructing numbers
949 Here is how to create number objects ``from nothing''.
953 * Constructing integers::
954 * Constructing rational numbers::
955 * Constructing floating-point numbers::
956 * Constructing complex numbers::
959 @node Constructing integers
960 @subsection Constructing integers
962 @code{cl_I} objects are most easily constructed from C integers and from
963 strings. See @ref{Conversions}.
966 @node Constructing rational numbers
967 @subsection Constructing rational numbers
969 @code{cl_RA} objects can be constructed from strings. The syntax
970 for rational numbers is described in @ref{Internal and printed representation}.
971 Another standard way to produce a rational number is through application
972 of @samp{operator /} or @samp{recip} on integers.
975 @node Constructing floating-point numbers
976 @subsection Constructing floating-point numbers
978 @code{cl_F} objects with low precision are most easily constructed from
979 C @samp{float} and @samp{double}. See @ref{Conversions}.
981 To construct a @code{cl_F} with high precision, you can use the conversion
982 from @samp{const char *}, but you have to specify the desired precision
983 within the string. (See @ref{Internal and printed representation}.)
986 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
988 will set @samp{e} to the given value, with a precision of 40 decimal digits.
990 The programmatic way to construct a @code{cl_F} with high precision is
991 through the @code{cl_float} conversion function, see
992 @ref{Conversion to floating-point numbers}. For example, to compute
993 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
994 and then apply the exponential function:
996 float_format_t precision = float_format(40);
997 cl_F e = exp(cl_float(1,precision));
1001 @node Constructing complex numbers
1002 @subsection Constructing complex numbers
1004 Non-real @code{cl_N} objects are normally constructed through the function
1006 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
1008 See @ref{Elementary complex functions}.
1011 @node Elementary functions
1012 @section Elementary functions
1014 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1015 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1016 defines the following operations:
1019 @item @var{type} operator + (const @var{type}&, const @var{type}&)
1020 @cindex @code{operator + ()}
1023 @item @var{type} operator - (const @var{type}&, const @var{type}&)
1024 @cindex @code{operator - ()}
1027 @item @var{type} operator - (const @var{type}&)
1028 Returns the negative of the argument.
1030 @item @var{type} plus1 (const @var{type}& x)
1031 @cindex @code{plus1 ()}
1032 Returns @code{x + 1}.
1034 @item @var{type} minus1 (const @var{type}& x)
1035 @cindex @code{minus1 ()}
1036 Returns @code{x - 1}.
1038 @item @var{type} operator * (const @var{type}&, const @var{type}&)
1039 @cindex @code{operator * ()}
1042 @item @var{type} square (const @var{type}& x)
1043 @cindex @code{square ()}
1044 Returns @code{x * x}.
1047 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
1048 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1049 defines the following operations:
1052 @item @var{type} operator / (const @var{type}&, const @var{type}&)
1053 @cindex @code{operator / ()}
1056 @item @var{type} recip (const @var{type}&)
1057 @cindex @code{recip ()}
1058 Returns the reciprocal of the argument.
1061 The class @code{cl_I} doesn't define a @samp{/} operation because
1062 in the C/C++ language this operator, applied to integral types,
1063 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
1064 is implementation dependent). (@xref{Rounding functions}.)
1065 Instead, @code{cl_I} defines an ``exact quotient'' function:
1068 @item cl_I exquo (const cl_I& x, const cl_I& y)
1069 @cindex @code{exquo ()}
1070 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
1073 The following exponentiation functions are defined:
1076 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
1077 @cindex @code{expt_pos ()}
1078 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
1079 @code{y} must be > 0. Returns @code{x^y}.
1081 @item cl_RA expt (const cl_RA& x, const cl_I& y)
1082 @cindex @code{expt ()}
1083 @itemx cl_R expt (const cl_R& x, const cl_I& y)
1084 @itemx cl_N expt (const cl_N& x, const cl_I& y)
1088 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1089 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1090 defines the following operation:
1093 @item @var{type} abs (const @var{type}& x)
1094 @cindex @code{abs ()}
1095 Returns the absolute value of @code{x}.
1096 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
1099 The class @code{cl_N} implements this as follows:
1102 @item cl_R abs (const cl_N x)
1103 Returns the absolute value of @code{x}.
1106 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1107 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1108 defines the following operation:
1111 @item @var{type} signum (const @var{type}& x)
1112 @cindex @code{signum ()}
1113 Returns the sign of @code{x}, in the same number format as @code{x}.
1114 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
1115 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
1120 @node Elementary rational functions
1121 @section Elementary rational functions
1123 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
1126 @item cl_I numerator (const @var{type}& x)
1127 @cindex @code{numerator ()}
1128 Returns the numerator of @code{x}.
1130 @item cl_I denominator (const @var{type}& x)
1131 @cindex @code{denominator ()}
1132 Returns the denominator of @code{x}.
1135 The numerator and denominator of a rational number are normalized in such
1136 a way that they have no factor in common and the denominator is positive.
1139 @node Elementary complex functions
1140 @section Elementary complex functions
1142 The class @code{cl_N} defines the following operation:
1145 @item cl_N complex (const cl_R& a, const cl_R& b)
1146 @cindex @code{complex ()}
1147 Returns the complex number @code{a+bi}, that is, the complex number with
1148 real part @code{a} and imaginary part @code{b}.
1151 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1154 @item cl_R realpart (const @var{type}& x)
1155 @cindex @code{realpart ()}
1156 Returns the real part of @code{x}.
1158 @item cl_R imagpart (const @var{type}& x)
1159 @cindex @code{imagpart ()}
1160 Returns the imaginary part of @code{x}.
1162 @item @var{type} conjugate (const @var{type}& x)
1163 @cindex @code{conjugate ()}
1164 Returns the complex conjugate of @code{x}.
1167 We have the relations
1171 @code{x = complex(realpart(x), imagpart(x))}
1173 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1178 @section Comparisons
1181 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1182 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1183 defines the following operations:
1186 @item bool operator == (const @var{type}&, const @var{type}&)
1187 @cindex @code{operator == ()}
1188 @itemx bool operator != (const @var{type}&, const @var{type}&)
1189 @cindex @code{operator != ()}
1190 Comparison, as in C and C++.
1192 @item uint32 equal_hashcode (const @var{type}&)
1193 @cindex @code{equal_hashcode ()}
1194 Returns a 32-bit hash code that is the same for any two numbers which are
1195 the same according to @code{==}. This hash code depends on the number's value,
1196 not its type or precision.
1198 @item bool zerop (const @var{type}& x)
1199 @cindex @code{zerop ()}
1200 Compare against zero: @code{x == 0}
1203 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1204 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1205 defines the following operations:
1208 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1209 @cindex @code{compare ()}
1210 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1211 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1213 @item bool operator <= (const @var{type}&, const @var{type}&)
1214 @cindex @code{operator <= ()}
1215 @itemx bool operator < (const @var{type}&, const @var{type}&)
1216 @cindex @code{operator < ()}
1217 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1218 @cindex @code{operator >= ()}
1219 @itemx bool operator > (const @var{type}&, const @var{type}&)
1220 @cindex @code{operator > ()}
1221 Comparison, as in C and C++.
1223 @item bool minusp (const @var{type}& x)
1224 @cindex @code{minusp ()}
1225 Compare against zero: @code{x < 0}
1227 @item bool plusp (const @var{type}& x)
1228 @cindex @code{plusp ()}
1229 Compare against zero: @code{x > 0}
1231 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1232 @cindex @code{max ()}
1233 Return the maximum of @code{x} and @code{y}.
1235 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1236 @cindex @code{min ()}
1237 Return the minimum of @code{x} and @code{y}.
1240 When a floating point number and a rational number are compared, the float
1241 is first converted to a rational number using the function @code{rational}.
1242 Since a floating point number actually represents an interval of real numbers,
1243 the result might be surprising.
1244 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1245 there is no floating point number whose value is exactly @code{1/3}.
1248 @node Rounding functions
1249 @section Rounding functions
1252 When a real number is to be converted to an integer, there is no ``best''
1253 rounding. The desired rounding function depends on the application.
1254 The Common Lisp and ISO Lisp standards offer four rounding functions:
1258 This is the largest integer <=@code{x}.
1261 This is the smallest integer >=@code{x}.
1264 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1267 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1268 integers, choose the even one.
1271 These functions have different advantages:
1273 @code{floor} and @code{ceiling} are translation invariant:
1274 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1275 for every @code{x} and every integer @code{n}.
1277 On the other hand, @code{truncate} and @code{round} are symmetric:
1278 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1279 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1280 down exactly as often as it rounds up.
1282 The functions are related like this:
1286 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1287 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1289 @code{truncate(x) = sign(x) * floor(abs(x))}
1292 Each of the classes @code{cl_R}, @code{cl_RA},
1293 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1294 defines the following operations:
1297 @item cl_I floor1 (const @var{type}& x)
1298 @cindex @code{floor1 ()}
1299 Returns @code{floor(x)}.
1300 @item cl_I ceiling1 (const @var{type}& x)
1301 @cindex @code{ceiling1 ()}
1302 Returns @code{ceiling(x)}.
1303 @item cl_I truncate1 (const @var{type}& x)
1304 @cindex @code{truncate1 ()}
1305 Returns @code{truncate(x)}.
1306 @item cl_I round1 (const @var{type}& x)
1307 @cindex @code{round1 ()}
1308 Returns @code{round(x)}.
1311 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1312 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1313 defines the following operations:
1316 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1317 Returns @code{floor(x/y)}.
1318 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1319 Returns @code{ceiling(x/y)}.
1320 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1321 Returns @code{truncate(x/y)}.
1322 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1323 Returns @code{round(x/y)}.
1326 These functions are called @samp{floor1}, @dots{} here instead of
1327 @samp{floor}, @dots{}, because on some systems, system dependent include
1328 files define @samp{floor} and @samp{ceiling} as macros.
1330 In many cases, one needs both the quotient and the remainder of a division.
1331 It is more efficient to compute both at the same time than to perform
1332 two divisions, one for quotient and the next one for the remainder.
1333 The following functions therefore return a structure containing both
1334 the quotient and the remainder. The suffix @samp{2} indicates the number
1335 of ``return values''. The remainder is defined as follows:
1339 for the computation of @code{quotient = floor(x)},
1340 @code{remainder = x - quotient},
1342 for the computation of @code{quotient = floor(x,y)},
1343 @code{remainder = x - quotient*y},
1346 and similarly for the other three operations.
1348 Each of the classes @code{cl_R}, @code{cl_RA},
1349 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1350 defines the following operations:
1353 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1354 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1355 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1356 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1357 @itemx @var{type}_div_t round2 (const @var{type}& x)
1360 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1361 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1362 defines the following operations:
1365 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1366 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1367 @cindex @code{floor2 ()}
1368 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1369 @cindex @code{ceiling2 ()}
1370 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1371 @cindex @code{truncate2 ()}
1372 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1373 @cindex @code{round2 ()}
1376 Sometimes, one wants the quotient as a floating-point number (of the
1377 same format as the argument, if the argument is a float) instead of as
1378 an integer. The prefix @samp{f} indicates this.
1381 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1382 defines the following operations:
1385 @item @var{type} ffloor (const @var{type}& x)
1386 @cindex @code{ffloor ()}
1387 @itemx @var{type} fceiling (const @var{type}& x)
1388 @cindex @code{fceiling ()}
1389 @itemx @var{type} ftruncate (const @var{type}& x)
1390 @cindex @code{ftruncate ()}
1391 @itemx @var{type} fround (const @var{type}& x)
1392 @cindex @code{fround ()}
1395 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1397 The class @code{cl_R} defines the following operations:
1400 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1401 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1402 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1403 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1406 These functions also exist in versions which return both the quotient
1407 and the remainder. The suffix @samp{2} indicates this.
1410 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1411 defines the following operations:
1412 @cindex @code{cl_F_fdiv_t}
1413 @cindex @code{cl_SF_fdiv_t}
1414 @cindex @code{cl_FF_fdiv_t}
1415 @cindex @code{cl_DF_fdiv_t}
1416 @cindex @code{cl_LF_fdiv_t}
1419 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1420 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1421 @cindex @code{ffloor2 ()}
1422 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1423 @cindex @code{fceiling2 ()}
1424 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1425 @cindex @code{ftruncate2 ()}
1426 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1427 @cindex @code{fround2 ()}
1429 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1430 @cindex @code{cl_R_fdiv_t}
1432 The class @code{cl_R} defines the following operations:
1435 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1436 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1437 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1438 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1439 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1442 Other applications need only the remainder of a division.
1443 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1444 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1445 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1449 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1451 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1454 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1455 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1456 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1458 The classes @code{cl_R}, @code{cl_I} define the following operations:
1461 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1462 @cindex @code{mod ()}
1463 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1464 @cindex @code{rem ()}
1471 Each of the classes @code{cl_R},
1472 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1473 defines the following operation:
1476 @item @var{type} sqrt (const @var{type}& x)
1477 @cindex @code{sqrt ()}
1478 @code{x} must be >= 0. This function returns the square root of @code{x},
1479 normalized to be >= 0. If @code{x} is the square of a rational number,
1480 @code{sqrt(x)} will be a rational number, else it will return a
1481 floating-point approximation.
1484 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1487 @item bool sqrtp (const @var{type}& x, @var{type}* root)
1488 @cindex @code{sqrtp ()}
1489 This tests whether @code{x} is a perfect square. If so, it returns true
1490 and the exact square root in @code{*root}, else it returns false.
1493 Furthermore, for integers, similarly:
1496 @item bool isqrt (const @var{type}& x, @var{type}* root)
1497 @cindex @code{isqrt ()}
1498 @code{x} should be >= 0. This function sets @code{*root} to
1499 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1500 the boolean value @code{(expt(*root,2) == x)}.
1503 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1504 define the following operation:
1507 @item bool rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1508 @cindex @code{rootp ()}
1509 @code{x} must be >= 0. @code{n} must be > 0.
1510 This tests whether @code{x} is an @code{n}th power of a rational number.
1511 If so, it returns true and the exact root in @code{*root}, else it returns
1515 The only square root function which accepts negative numbers is the one
1516 for class @code{cl_N}:
1519 @item cl_N sqrt (const cl_N& z)
1520 @cindex @code{sqrt ()}
1521 Returns the square root of @code{z}, as defined by the formula
1522 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1523 or to a complex number are done if necessary. The range of the result is the
1524 right half plane @code{realpart(sqrt(z)) >= 0}
1525 including the positive imaginary axis and 0, but excluding
1526 the negative imaginary axis.
1527 The result is an exact number only if @code{z} is an exact number.
1531 @node Transcendental functions
1532 @section Transcendental functions
1533 @cindex transcendental functions
1535 The transcendental functions return an exact result if the argument
1536 is exact and the result is exact as well. Otherwise they must return
1537 inexact numbers even if the argument is exact.
1538 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1542 * Exponential and logarithmic functions::
1543 * Trigonometric functions::
1544 * Hyperbolic functions::
1549 @node Exponential and logarithmic functions
1550 @subsection Exponential and logarithmic functions
1553 @item cl_R exp (const cl_R& x)
1554 @cindex @code{exp ()}
1555 @itemx cl_N exp (const cl_N& x)
1556 Returns the exponential function of @code{x}. This is @code{e^x} where
1557 @code{e} is the base of the natural logarithms. The range of the result
1558 is the entire complex plane excluding 0.
1560 @item cl_R ln (const cl_R& x)
1561 @cindex @code{ln ()}
1562 @code{x} must be > 0. Returns the (natural) logarithm of x.
1564 @item cl_N log (const cl_N& x)
1565 @cindex @code{log ()}
1566 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1567 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1568 The range of the result is the strip in the complex plane
1569 @code{-pi < imagpart(log(x)) <= pi}.
1571 @item cl_R phase (const cl_N& x)
1572 @cindex @code{phase ()}
1573 Returns the angle part of @code{x} in its polar representation as a
1574 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1575 This is also the imaginary part of @code{log(x)}.
1576 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1577 The result will be an exact number only if @code{zerop(x)} or
1578 if @code{x} is real and positive.
1580 @item cl_R log (const cl_R& a, const cl_R& b)
1581 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1582 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1583 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1586 @item cl_N log (const cl_N& a, const cl_N& b)
1587 Returns the logarithm of @code{a} with respect to base @code{b}.
1588 @code{log(a,b) = log(a)/log(b)}.
1590 @item cl_N expt (const cl_N& x, const cl_N& y)
1591 @cindex @code{expt ()}
1592 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1595 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1598 @item cl_F exp1 (float_format_t f)
1599 @cindex @code{exp1 ()}
1600 Returns e as a float of format @code{f}.
1602 @item cl_F exp1 (const cl_F& y)
1603 Returns e in the float format of @code{y}.
1605 @item cl_F exp1 (void)
1606 Returns e as a float of format @code{default_float_format}.
1610 @node Trigonometric functions
1611 @subsection Trigonometric functions
1614 @item cl_R sin (const cl_R& x)
1615 @cindex @code{sin ()}
1616 Returns @code{sin(x)}. The range of the result is the interval
1617 @code{-1 <= sin(x) <= 1}.
1619 @item cl_N sin (const cl_N& z)
1620 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1622 @item cl_R cos (const cl_R& x)
1623 @cindex @code{cos ()}
1624 Returns @code{cos(x)}. The range of the result is the interval
1625 @code{-1 <= cos(x) <= 1}.
1627 @item cl_N cos (const cl_N& x)
1628 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1630 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1631 @cindex @code{cos_sin_t}
1632 @itemx cos_sin_t cos_sin (const cl_R& x)
1633 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1634 @cindex @code{cos_sin ()}
1635 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1636 hold only approximately.
1638 @item cl_R tan (const cl_R& x)
1639 @cindex @code{tan ()}
1640 @itemx cl_N tan (const cl_N& x)
1641 Returns @code{tan(x) = sin(x)/cos(x)}.
1643 @item cl_N cis (const cl_R& x)
1644 @cindex @code{cis ()}
1645 @itemx cl_N cis (const cl_N& x)
1646 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1647 @code{e^(i*x) = cos(x) + i*sin(x)}.
1650 @cindex @code{asin ()}
1651 @item cl_N asin (const cl_N& z)
1652 Returns @code{arcsin(z)}. This is defined as
1653 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1654 @code{arcsin(-z) = -arcsin(z)}.
1655 The range of the result is the strip in the complex domain
1656 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1657 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1658 with @code{realpart = pi/2} and @code{imagpart > 0}.
1660 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1664 @item cl_N acos (const cl_N& z)
1665 @cindex @code{acos ()}
1666 Returns @code{arccos(z)}. This is defined as
1667 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1670 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1672 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1673 The range of the result is the strip in the complex domain
1674 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1675 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1676 with @code{realpart = pi} and @code{imagpart > 0}.
1678 Proof: This follows from the results about arcsin.
1682 @cindex @code{atan ()}
1683 @item cl_R atan (const cl_R& x, const cl_R& y)
1684 Returns the angle of the polar representation of the complex number
1685 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1686 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1687 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1688 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1689 with reversed order of arguments.
1691 @item cl_R atan (const cl_R& x)
1692 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1693 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1694 will be an exact number only if @code{x} is the exact @code{0}.
1696 @item cl_N atan (const cl_N& z)
1697 Returns @code{arctan(z)}. This is defined as
1698 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1699 @code{arctan(-z) = -arctan(z)}. The range of the result is
1700 the strip in the complex domain
1701 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1702 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1703 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1705 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1711 @cindex Archimedes' constant
1712 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1715 @item cl_F pi (float_format_t f)
1716 @cindex @code{pi ()}
1717 Returns pi as a float of format @code{f}.
1719 @item cl_F pi (const cl_F& y)
1720 Returns pi in the float format of @code{y}.
1722 @item cl_F pi (void)
1723 Returns pi as a float of format @code{default_float_format}.
1727 @node Hyperbolic functions
1728 @subsection Hyperbolic functions
1731 @item cl_R sinh (const cl_R& x)
1732 @cindex @code{sinh ()}
1733 Returns @code{sinh(x)}.
1735 @item cl_N sinh (const cl_N& z)
1736 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1738 @item cl_R cosh (const cl_R& x)
1739 @cindex @code{cosh ()}
1740 Returns @code{cosh(x)}. The range of the result is the interval
1741 @code{cosh(x) >= 1}.
1743 @item cl_N cosh (const cl_N& z)
1744 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1746 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1747 @cindex @code{cosh_sinh_t}
1748 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1749 @cindex @code{cosh_sinh ()}
1750 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1751 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1752 hold only approximately.
1754 @item cl_R tanh (const cl_R& x)
1755 @cindex @code{tanh ()}
1756 @itemx cl_N tanh (const cl_N& x)
1757 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1759 @item cl_N asinh (const cl_N& z)
1760 @cindex @code{asinh ()}
1761 Returns @code{arsinh(z)}. This is defined as
1762 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1763 @code{arsinh(-z) = -arsinh(z)}.
1765 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1766 Actually, z+sqrt(1+z^2) can never be real and <0, so
1767 -pi < imagpart(arsinh(z)) < pi.
1768 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1769 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1771 The range of the result is the strip in the complex domain
1772 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1773 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1774 with @code{imagpart = pi/2} and @code{realpart < 0}.
1776 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1777 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1778 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1779 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1780 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1781 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1782 If y >= 1, the imagpart is pi/2 and the realpart is
1783 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1786 Moreover, if z is in Range(sqrt),
1787 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1788 (for a proof, see file src/cl_C_asinh.cc).
1791 @item cl_N acosh (const cl_N& z)
1792 @cindex @code{acosh ()}
1793 Returns @code{arcosh(z)}. This is defined as
1794 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1795 The range of the result is the half-strip in the complex domain
1796 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1797 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1799 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1800 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1801 If z is in Range(sqrt), we have
1802 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1803 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1805 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1806 and since the imagpart of both expressions is > -pi, <= pi
1807 ==> arcosh(z) = log(z+sqrt(z^2-1))
1808 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1809 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1810 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1811 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1812 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1814 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1815 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1816 = x^2 + y^2 + sqrt(u^2+v^2)
1821 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1822 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1823 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1824 Otherwise, -z is in Range(sqrt).
1825 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1826 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1827 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1828 and this has realpart > 0.
1829 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1830 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1831 has realpart = 0 and imagpart > 0.
1832 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1833 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1834 This has realpart >= 0 and imagpart = pi.
1837 @item cl_N atanh (const cl_N& z)
1838 @cindex @code{atanh ()}
1839 Returns @code{artanh(z)}. This is defined as
1840 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1841 @code{artanh(-z) = -artanh(z)}. The range of the result is
1842 the strip in the complex domain
1843 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1844 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1845 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1847 Proof: Write z = x+iy. Examine
1848 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1850 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1851 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1852 |x| < 1 ==> imagpart = 0
1855 = (atan(1+x,y) - atan(1-x,-y))/2
1856 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1857 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1858 > (pi - pi/2 - pi/2 )/2 = 0
1859 and (1+x)/y > (1-x)/y
1860 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1861 ==> imagpart < pi/2.
1862 Hence 0 < imagpart < pi/2.
1864 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1870 @subsection Euler gamma
1871 @cindex Euler's constant
1873 Euler's constant C = 0.577@dots{} is returned by the following functions:
1876 @item cl_F eulerconst (float_format_t f)
1877 @cindex @code{eulerconst ()}
1878 Returns Euler's constant as a float of format @code{f}.
1880 @item cl_F eulerconst (const cl_F& y)
1881 Returns Euler's constant in the float format of @code{y}.
1883 @item cl_F eulerconst (void)
1884 Returns Euler's constant as a float of format @code{default_float_format}.
1887 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1888 @cindex Catalan's constant
1891 @item cl_F catalanconst (float_format_t f)
1892 @cindex @code{catalanconst ()}
1893 Returns Catalan's constant as a float of format @code{f}.
1895 @item cl_F catalanconst (const cl_F& y)
1896 Returns Catalan's constant in the float format of @code{y}.
1898 @item cl_F catalanconst (void)
1899 Returns Catalan's constant as a float of format @code{default_float_format}.
1904 @subsection Riemann zeta
1905 @cindex Riemann's zeta
1907 Riemann's zeta function at an integral point @code{s>1} is returned by the
1908 following functions:
1911 @item cl_F zeta (int s, float_format_t f)
1912 @cindex @code{zeta ()}
1913 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1915 @item cl_F zeta (int s, const cl_F& y)
1916 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1918 @item cl_F zeta (int s)
1919 Returns Riemann's zeta function at @code{s} as a float of format
1920 @code{default_float_format}.
1924 @node Functions on integers
1925 @section Functions on integers
1928 * Logical functions::
1929 * Number theoretic functions::
1930 * Combinatorial functions::
1933 @node Logical functions
1934 @subsection Logical functions
1936 Integers, when viewed as in two's complement notation, can be thought as
1937 infinite bit strings where the bits' values eventually are constant.
1944 The logical operations view integers as such bit strings and operate
1945 on each of the bit positions in parallel.
1948 @item cl_I lognot (const cl_I& x)
1949 @cindex @code{lognot ()}
1950 @itemx cl_I operator ~ (const cl_I& x)
1951 @cindex @code{operator ~ ()}
1952 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1954 @item cl_I logand (const cl_I& x, const cl_I& y)
1955 @cindex @code{logand ()}
1956 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1957 @cindex @code{operator & ()}
1958 Logical and, like @code{x & y} in C.
1960 @item cl_I logior (const cl_I& x, const cl_I& y)
1961 @cindex @code{logior ()}
1962 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1963 @cindex @code{operator | ()}
1964 Logical (inclusive) or, like @code{x | y} in C.
1966 @item cl_I logxor (const cl_I& x, const cl_I& y)
1967 @cindex @code{logxor ()}
1968 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1969 @cindex @code{operator ^ ()}
1970 Exclusive or, like @code{x ^ y} in C.
1972 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1973 @cindex @code{logeqv ()}
1974 Bitwise equivalence, like @code{~(x ^ y)} in C.
1976 @item cl_I lognand (const cl_I& x, const cl_I& y)
1977 @cindex @code{lognand ()}
1978 Bitwise not and, like @code{~(x & y)} in C.
1980 @item cl_I lognor (const cl_I& x, const cl_I& y)
1981 @cindex @code{lognor ()}
1982 Bitwise not or, like @code{~(x | y)} in C.
1984 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1985 @cindex @code{logandc1 ()}
1986 Logical and, complementing the first argument, like @code{~x & y} in C.
1988 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1989 @cindex @code{logandc2 ()}
1990 Logical and, complementing the second argument, like @code{x & ~y} in C.
1992 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1993 @cindex @code{logorc1 ()}
1994 Logical or, complementing the first argument, like @code{~x | y} in C.
1996 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1997 @cindex @code{logorc2 ()}
1998 Logical or, complementing the second argument, like @code{x | ~y} in C.
2001 These operations are all available though the function
2003 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
2004 @cindex @code{boole ()}
2006 where @code{op} must have one of the 16 values (each one stands for a function
2007 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
2008 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
2009 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
2010 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
2011 @code{boole_orc1}, @code{boole_orc2}.
2012 @cindex @code{boole_clr}
2013 @cindex @code{boole_set}
2014 @cindex @code{boole_1}
2015 @cindex @code{boole_2}
2016 @cindex @code{boole_c1}
2017 @cindex @code{boole_c2}
2018 @cindex @code{boole_and}
2019 @cindex @code{boole_xor}
2020 @cindex @code{boole_eqv}
2021 @cindex @code{boole_nand}
2022 @cindex @code{boole_nor}
2023 @cindex @code{boole_andc1}
2024 @cindex @code{boole_andc2}
2025 @cindex @code{boole_orc1}
2026 @cindex @code{boole_orc2}
2029 Other functions that view integers as bit strings:
2032 @item bool logtest (const cl_I& x, const cl_I& y)
2033 @cindex @code{logtest ()}
2034 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
2035 @code{logand(x,y) != 0}.
2037 @item bool logbitp (const cl_I& n, const cl_I& x)
2038 @cindex @code{logbitp ()}
2039 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
2040 Bit 0 is the least significant bit.
2042 @item uintC logcount (const cl_I& x)
2043 @cindex @code{logcount ()}
2044 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
2045 the number of zero bits in @code{x}, if @code{x} < 0.
2048 The following functions operate on intervals of bits in integers.
2051 struct cl_byte @{ uintC size; uintC position; @};
2053 @cindex @code{cl_byte}
2054 represents the bit interval containing the bits
2055 @code{position}@dots{}@code{position+size-1} of an integer.
2056 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
2059 @item cl_I ldb (const cl_I& n, const cl_byte& b)
2060 @cindex @code{ldb ()}
2061 extracts the bits of @code{n} described by the bit interval @code{b}
2062 and returns them as a nonnegative integer with @code{b.size} bits.
2064 @item bool ldb_test (const cl_I& n, const cl_byte& b)
2065 @cindex @code{ldb_test ()}
2066 Returns true if some bit described by the bit interval @code{b} is set in
2069 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2070 @cindex @code{dpb ()}
2071 Returns @code{n}, with the bits described by the bit interval @code{b}
2072 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
2073 @code{newbyte} are relevant.
2076 The functions @code{ldb} and @code{dpb} implicitly shift. The following
2077 functions are their counterparts without shifting:
2080 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
2081 @cindex @code{mask_field ()}
2082 returns an integer with the bits described by the bit interval @code{b}
2083 copied from the corresponding bits in @code{n}, the other bits zero.
2085 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2086 @cindex @code{deposit_field ()}
2087 returns an integer where the bits described by the bit interval @code{b}
2088 come from @code{newbyte} and the other bits come from @code{n}.
2091 The following relations hold:
2095 @code{ldb (n, b) = mask_field(n, b) >> b.position},
2097 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
2099 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
2102 The following operations on integers as bit strings are efficient shortcuts
2103 for common arithmetic operations:
2106 @item bool oddp (const cl_I& x)
2107 @cindex @code{oddp ()}
2108 Returns true if the least significant bit of @code{x} is 1. Equivalent to
2109 @code{mod(x,2) != 0}.
2111 @item bool evenp (const cl_I& x)
2112 @cindex @code{evenp ()}
2113 Returns true if the least significant bit of @code{x} is 0. Equivalent to
2114 @code{mod(x,2) == 0}.
2116 @item cl_I operator << (const cl_I& x, const cl_I& n)
2117 @cindex @code{operator << ()}
2118 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
2119 Equivalent to @code{x * expt(2,n)}.
2121 @item cl_I operator >> (const cl_I& x, const cl_I& n)
2122 @cindex @code{operator >> ()}
2123 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
2124 Bits shifted out to the right are thrown away.
2125 Equivalent to @code{floor(x / expt(2,n))}.
2127 @item cl_I ash (const cl_I& x, const cl_I& y)
2128 @cindex @code{ash ()}
2129 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
2130 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
2131 returns @code{floor(x * expt(2,y))}.
2133 @item uintC integer_length (const cl_I& x)
2134 @cindex @code{integer_length ()}
2135 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
2136 in two's complement notation. This is the smallest n >= 0 such that
2137 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
2140 @item uintC ord2 (const cl_I& x)
2141 @cindex @code{ord2 ()}
2142 @code{x} must be non-zero. This function returns the number of 0 bits at the
2143 right of @code{x} in two's complement notation. This is the largest n >= 0
2144 such that 2^n divides @code{x}.
2146 @item uintC power2p (const cl_I& x)
2147 @cindex @code{power2p ()}
2148 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
2149 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
2150 (See also the function @code{logp}.)
2154 @node Number theoretic functions
2155 @subsection Number theoretic functions
2158 @item uint32 gcd (unsigned long a, unsigned long b)
2159 @cindex @code{gcd ()}
2160 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
2161 This function returns the greatest common divisor of @code{a} and @code{b},
2162 normalized to be >= 0.
2164 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
2165 @cindex @code{xgcd ()}
2166 This function (``extended gcd'') returns the greatest common divisor @code{g} of
2167 @code{a} and @code{b} and at the same time the representation of @code{g}
2168 as an integral linear combination of @code{a} and @code{b}:
2169 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
2170 @code{u} and @code{v} will be normalized to be of smallest possible absolute
2171 value, in the following sense: If @code{a} and @code{b} are non-zero, and
2172 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
2173 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
2175 @item cl_I lcm (const cl_I& a, const cl_I& b)
2176 @cindex @code{lcm ()}
2177 This function returns the least common multiple of @code{a} and @code{b},
2178 normalized to be >= 0.
2180 @item bool logp (const cl_I& a, const cl_I& b, cl_RA* l)
2181 @cindex @code{logp ()}
2182 @itemx bool logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2183 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2184 rational number, this function returns true and sets *l = log(a,b), else
2187 @item int jacobi (signed long a, signed long b)
2188 @cindex @code{jacobi()}
2189 @itemx int jacobi (const cl_I& a, const cl_I& b)
2190 Returns the Jacobi symbol
2192 $\left({a\over b}\right)$,
2197 @code{a,b} must be integers, @code{b>0} and odd. The result is 0
2200 @item bool isprobprime (const cl_I& n)
2202 @cindex @code{isprobprime()}
2203 Returns true if @code{n} is a small prime or passes the Miller-Rabin
2204 primality test. The probability of a false positive is 1:10^30.
2206 @item cl_I nextprobprime (const cl_R& x)
2207 @cindex @code{nextprobprime()}
2208 Returns the smallest probable prime >=@code{x}.
2212 @node Combinatorial functions
2213 @subsection Combinatorial functions
2216 @item cl_I factorial (uintL n)
2217 @cindex @code{factorial ()}
2218 @code{n} must be a small integer >= 0. This function returns the factorial
2219 @code{n}! = @code{1*2*@dots{}*n}.
2221 @item cl_I doublefactorial (uintL n)
2222 @cindex @code{doublefactorial ()}
2223 @code{n} must be a small integer >= 0. This function returns the
2224 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2225 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2227 @item cl_I binomial (uintL n, uintL k)
2228 @cindex @code{binomial ()}
2229 @code{n} and @code{k} must be small integers >= 0. This function returns the
2230 binomial coefficient
2232 ${n \choose k} = {n! \over n! (n-k)!}$
2235 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2237 for 0 <= k <= n, 0 else.
2241 @node Functions on floating-point numbers
2242 @section Functions on floating-point numbers
2244 Recall that a floating-point number consists of a sign @code{s}, an
2245 exponent @code{e} and a mantissa @code{m}. The value of the number is
2246 @code{(-1)^s * 2^e * m}.
2249 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2250 defines the following operations.
2253 @item @var{type} scale_float (const @var{type}& x, sintC delta)
2254 @cindex @code{scale_float ()}
2255 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2256 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2257 because it copies @code{x} and modifies the exponent.
2260 The following functions provide an abstract interface to the underlying
2261 representation of floating-point numbers.
2264 @item sintE float_exponent (const @var{type}& x)
2265 @cindex @code{float_exponent ()}
2266 Returns the exponent @code{e} of @code{x}.
2267 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2268 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2270 @item sintL float_radix (const @var{type}& x)
2271 @cindex @code{float_radix ()}
2272 Returns the base of the floating-point representation. This is always @code{2}.
2274 @item @var{type} float_sign (const @var{type}& x)
2275 @cindex @code{float_sign ()}
2276 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2277 @code{x} >= 0, -1 for @code{x} < 0.
2279 @item uintC float_digits (const @var{type}& x)
2280 @cindex @code{float_digits ()}
2281 Returns the number of mantissa bits in the floating-point representation
2282 of @code{x}, including the hidden bit. The value only depends on the type
2283 of @code{x}, not on its value.
2285 @item uintC float_precision (const @var{type}& x)
2286 @cindex @code{float_precision ()}
2287 Returns the number of significant mantissa bits in the floating-point
2288 representation of @code{x}. Since denormalized numbers are not supported,
2289 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2293 The complete internal representation of a float is encoded in the type
2294 @cindex @code{decoded_float}
2295 @cindex @code{decoded_sfloat}
2296 @cindex @code{decoded_ffloat}
2297 @cindex @code{decoded_dfloat}
2298 @cindex @code{decoded_lfloat}
2299 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2300 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2302 struct decoded_@var{type}float @{
2303 @var{type} mantissa; cl_I exponent; @var{type} sign;
2307 and returned by the function
2310 @item decoded_@var{type}float decode_float (const @var{type}& x)
2311 @cindex @code{decode_float ()}
2312 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2313 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2314 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2315 @code{e} is the same as returned by the function @code{float_exponent}.
2318 A complete decoding in terms of integers is provided as type
2319 @cindex @code{cl_idecoded_float}
2321 struct cl_idecoded_float @{
2322 cl_I mantissa; cl_I exponent; cl_I sign;
2325 by the following function:
2328 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2329 @cindex @code{integer_decode_float ()}
2330 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2331 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2332 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2333 WARNING: The exponent @code{e} is not the same as the one returned by
2334 the functions @code{decode_float} and @code{float_exponent}.
2337 Some other function, implemented only for class @code{cl_F}:
2340 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2341 @cindex @code{float_sign ()}
2342 This returns a floating point number whose precision and absolute value
2343 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2344 zero, it is treated as positive. Same for @code{y}.
2348 @node Conversion functions
2349 @section Conversion functions
2353 * Conversion to floating-point numbers::
2354 * Conversion to rational numbers::
2357 @node Conversion to floating-point numbers
2358 @subsection Conversion to floating-point numbers
2360 The type @code{float_format_t} describes a floating-point format.
2361 @cindex @code{float_format_t}
2364 @item float_format_t float_format (uintE n)
2365 @cindex @code{float_format ()}
2366 Returns the smallest float format which guarantees at least @code{n}
2367 decimal digits in the mantissa (after the decimal point).
2369 @item float_format_t float_format (const cl_F& x)
2370 Returns the floating point format of @code{x}.
2372 @item float_format_t default_float_format
2373 @cindex @code{default_float_format}
2374 Global variable: the default float format used when converting rational numbers
2378 To convert a real number to a float, each of the types
2379 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2380 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2381 defines the following operations:
2384 @item cl_F cl_float (const @var{type}&x, float_format_t f)
2385 @cindex @code{cl_float ()}
2386 Returns @code{x} as a float of format @code{f}.
2387 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2388 Returns @code{x} in the float format of @code{y}.
2389 @item cl_F cl_float (const @var{type}&x)
2390 Returns @code{x} as a float of format @code{default_float_format} if
2391 it is an exact number, or @code{x} itself if it is already a float.
2394 Of course, converting a number to a float can lose precision.
2396 Every floating-point format has some characteristic numbers:
2399 @item cl_F most_positive_float (float_format_t f)
2400 @cindex @code{most_positive_float ()}
2401 Returns the largest (most positive) floating point number in float format @code{f}.
2403 @item cl_F most_negative_float (float_format_t f)
2404 @cindex @code{most_negative_float ()}
2405 Returns the smallest (most negative) floating point number in float format @code{f}.
2407 @item cl_F least_positive_float (float_format_t f)
2408 @cindex @code{least_positive_float ()}
2409 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2410 in float format @code{f}.
2412 @item cl_F least_negative_float (float_format_t f)
2413 @cindex @code{least_negative_float ()}
2414 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2415 in float format @code{f}.
2417 @item cl_F float_epsilon (float_format_t f)
2418 @cindex @code{float_epsilon ()}
2419 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2421 @item cl_F float_negative_epsilon (float_format_t f)
2422 @cindex @code{float_negative_epsilon ()}
2423 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2427 @node Conversion to rational numbers
2428 @subsection Conversion to rational numbers
2430 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2431 defines the following operation:
2434 @item cl_RA rational (const @var{type}& x)
2435 @cindex @code{rational ()}
2436 Returns the value of @code{x} as an exact number. If @code{x} is already
2437 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2438 the value is a rational number whose denominator is a power of 2.
2441 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2445 @item cl_RA rationalize (const cl_R& x)
2446 @cindex @code{rationalize ()}
2447 If @code{x} is a floating-point number, it actually represents an interval
2448 of real numbers, and this function returns the rational number with
2449 smallest denominator (and smallest numerator, in magnitude)
2450 which lies in this interval.
2451 If @code{x} is already an exact number, this function returns @code{x}.
2454 If @code{x} is any float, one has
2458 @code{cl_float(rational(x),x) = x}
2460 @code{cl_float(rationalize(x),x) = x}
2464 @node Random number generators
2465 @section Random number generators
2468 A random generator is a machine which produces (pseudo-)random numbers.
2469 The include file @code{<cln/random.h>} defines a class @code{random_state}
2470 which contains the state of a random generator. If you make a copy
2471 of the random number generator, the original one and the copy will produce
2472 the same sequence of random numbers.
2474 The following functions return (pseudo-)random numbers in different formats.
2475 Calling one of these modifies the state of the random number generator in
2476 a complicated but deterministic way.
2479 @cindex @code{random_state}
2480 @cindex @code{default_random_state}
2482 random_state default_random_state
2484 contains a default random number generator. It is used when the functions
2485 below are called without @code{random_state} argument.
2488 @item uint32 random32 (random_state& randomstate)
2489 @itemx uint32 random32 ()
2490 @cindex @code{random32 ()}
2491 Returns a random unsigned 32-bit number. All bits are equally random.
2493 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2494 @itemx cl_I random_I (const cl_I& n)
2495 @cindex @code{random_I ()}
2496 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2497 in the range @code{0 <= x < n}.
2499 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2500 @itemx cl_F random_F (const cl_F& n)
2501 @cindex @code{random_F ()}
2502 @code{n} must be a float > 0. This function returns a random floating-point
2503 number of the same format as @code{n} in the range @code{0 <= x < n}.
2505 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2506 @itemx cl_R random_R (const cl_R& n)
2507 @cindex @code{random_R ()}
2508 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2509 if @code{n} is a float.
2513 @node Modifying operators
2514 @section Modifying operators
2515 @cindex modifying operators
2517 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2518 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2521 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2522 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2525 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2526 @cindex @code{operator += ()}
2527 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2528 @cindex @code{operator -= ()}
2529 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2530 @cindex @code{operator *= ()}
2531 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2532 @cindex @code{operator /= ()}
2535 For the class @code{cl_I}:
2538 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2539 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2540 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2541 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2542 @cindex @code{operator &= ()}
2543 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2544 @cindex @code{operator |= ()}
2545 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2546 @cindex @code{operator ^= ()}
2547 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2548 @cindex @code{operator <<= ()}
2549 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2550 @cindex @code{operator >>= ()}
2553 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2554 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2557 @item @var{type}& operator ++ (@var{type}& x)
2558 @cindex @code{operator ++ ()}
2559 The prefix operator @code{++x}.
2561 @item void operator ++ (@var{type}& x, int)
2562 The postfix operator @code{x++}.
2564 @item @var{type}& operator -- (@var{type}& x)
2565 @cindex @code{operator -- ()}
2566 The prefix operator @code{--x}.
2568 @item void operator -- (@var{type}& x, int)
2569 The postfix operator @code{x--}.
2572 Note that by using these modifying operators, you don't gain efficiency:
2573 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2578 @chapter Input/Output
2579 @cindex Input/Output
2582 * Internal and printed representation::
2584 * Output functions::
2587 @node Internal and printed representation
2588 @section Internal and printed representation
2589 @cindex representation
2591 All computations deal with the internal representations of the numbers.
2593 Every number has an external representation as a sequence of ASCII characters.
2594 Several external representations may denote the same number, for example,
2595 "20.0" and "20.000".
2597 Converting an internal to an external representation is called ``printing'',
2599 converting an external to an internal representation is called ``reading''.
2601 In CLN, it is always true that conversion of an internal to an external
2602 representation and then back to an internal representation will yield the
2603 same internal representation. Symbolically: @code{read(print(x)) == x}.
2604 This is called ``print-read consistency''.
2606 Different types of numbers have different external representations (case
2611 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2612 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2613 for decimal integers
2614 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2616 @item Rational numbers
2617 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2618 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2621 @item Floating-point numbers
2622 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2623 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2624 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2625 of the form _@var{prec} may be appended. There must be at least
2626 one digit in the non-exponent part. The exponent has the syntax
2627 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2628 The exponent marker is
2632 @samp{s} for short-floats,
2634 @samp{f} for single-floats,
2636 @samp{d} for double-floats,
2638 @samp{L} for long-floats,
2641 or @samp{e}, which denotes a default float format. The precision specifying
2642 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2643 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2644 function @samp{float_format}.
2646 @item Complex numbers
2647 External representation:
2650 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2651 if @var{imagpart} is negative, its printed representation begins with
2652 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2653 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2654 is rational and the rational number's base is >18, because the @samp{i}
2655 is then read as a digit.
2657 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2662 @node Input functions
2663 @section Input functions
2665 Including @code{<cln/io.h>} defines a number of simple input functions
2666 that read from @code{std::istream&}:
2669 @item int freadchar (std::istream& stream)
2670 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2671 if the end of stream was encountered or an error occurred.
2673 @item int funreadchar (std::istream& stream, int c)
2674 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2675 last @code{freadchar} operation on @code{stream}.
2678 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2679 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2680 defines, in @code{<cln/@var{type}_io.h>}, the following input function:
2683 @item std::istream& operator>> (std::istream& stream, @var{type}& result)
2684 Reads a number from @code{stream} and stores it in the @code{result}.
2687 The most flexible input functions, defined in @code{<cln/@var{type}_io.h>},
2691 @item cl_N read_complex (std::istream& stream, const cl_read_flags& flags)
2692 @itemx cl_R read_real (std::istream& stream, const cl_read_flags& flags)
2693 @itemx cl_F read_float (std::istream& stream, const cl_read_flags& flags)
2694 @itemx cl_RA read_rational (std::istream& stream, const cl_read_flags& flags)
2695 @itemx cl_I read_integer (std::istream& stream, const cl_read_flags& flags)
2696 Reads a number from @code{stream}. The @code{flags} are parameters which
2697 affect the input syntax. Whitespace before the number is silently skipped.
2699 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2700 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2701 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2702 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2703 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2704 Reads a number from a string in memory. The @code{flags} are parameters which
2705 affect the input syntax. The string starts at @code{string} and ends at
2706 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2707 @code{NULL}, denoting the entire string, i.e. equivalent to
2708 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2709 @code{NULL}, the string in memory must contain exactly one number and nothing
2710 more, else an exception will be thrown. If @code{end_of_parse}
2711 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2712 the last parsed character (i.e. @code{string_limit} if nothing came after
2713 the number). Whitespace is not allowed.
2716 The structure @code{cl_read_flags} contains the following fields:
2719 @item cl_read_syntax_t syntax
2720 The possible results of the read operation. Possible values are
2721 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2722 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2723 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2725 @item cl_read_lsyntax_t lsyntax
2726 Specifies the language-dependent syntax variant for the read operation.
2730 @item lsyntax_standard
2731 accept standard algebraic notation only, no complex numbers,
2732 @item lsyntax_algebraic
2733 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2734 @item lsyntax_commonlisp
2735 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2736 hexadecimal numbers,
2737 @code{#@var{base}R} for rational numbers in a given base,
2738 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2740 accept all of these extensions.
2743 @item unsigned int rational_base
2744 The base in which rational numbers are read.
2746 @item float_format_t float_flags.default_float_format
2747 The float format used when reading floats with exponent marker @samp{e}.
2749 @item float_format_t float_flags.default_lfloat_format
2750 The float format used when reading floats with exponent marker @samp{l}.
2752 @item bool float_flags.mantissa_dependent_float_format
2753 When this flag is true, floats specified with more digits than corresponding
2754 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2755 precision corresponding to their number of significant digits.
2759 @node Output functions
2760 @section Output functions
2762 Including @code{<cln/io.h>} defines a number of simple output functions
2763 that write to @code{std::ostream&}:
2766 @item void fprintchar (std::ostream& stream, char c)
2767 Prints the character @code{x} literally on the @code{stream}.
2769 @item void fprint (std::ostream& stream, const char * string)
2770 Prints the @code{string} literally on the @code{stream}.
2772 @item void fprintdecimal (std::ostream& stream, int x)
2773 @itemx void fprintdecimal (std::ostream& stream, const cl_I& x)
2774 Prints the integer @code{x} in decimal on the @code{stream}.
2776 @item void fprintbinary (std::ostream& stream, const cl_I& x)
2777 Prints the integer @code{x} in binary (base 2, without prefix)
2778 on the @code{stream}.
2780 @item void fprintoctal (std::ostream& stream, const cl_I& x)
2781 Prints the integer @code{x} in octal (base 8, without prefix)
2782 on the @code{stream}.
2784 @item void fprinthexadecimal (std::ostream& stream, const cl_I& x)
2785 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2786 on the @code{stream}.
2789 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2790 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2791 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2794 @item void fprint (std::ostream& stream, const @var{type}& x)
2795 @itemx std::ostream& operator<< (std::ostream& stream, const @var{type}& x)
2796 Prints the number @code{x} on the @code{stream}. The output may depend
2797 on the global printer settings in the variable @code{default_print_flags}.
2798 The @code{ostream} flags and settings (flags, width and locale) are
2802 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2805 void print_complex (std::ostream& stream, const cl_print_flags& flags,
2807 void print_real (std::ostream& stream, const cl_print_flags& flags,
2809 void print_float (std::ostream& stream, const cl_print_flags& flags,
2811 void print_rational (std::ostream& stream, const cl_print_flags& flags,
2813 void print_integer (std::ostream& stream, const cl_print_flags& flags,
2816 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2817 parameters which affect the output.
2819 The structure type @code{cl_print_flags} contains the following fields:
2822 @item unsigned int rational_base
2823 The base in which rational numbers are printed. Default is @code{10}.
2825 @item bool rational_readably
2826 If this flag is true, rational numbers are printed with radix specifiers in
2827 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2828 prefixes, trailing dot). Default is false.
2830 @item bool float_readably
2831 If this flag is true, type specific exponent markers have precedence over 'E'.
2834 @item float_format_t default_float_format
2835 Floating point numbers of this format will be printed using the 'E' exponent
2836 marker. Default is @code{float_format_ffloat}.
2838 @item bool complex_readably
2839 If this flag is true, complex numbers will be printed using the Common Lisp
2840 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2842 @item cl_string univpoly_varname
2843 Univariate polynomials with no explicit indeterminate name will be printed
2844 using this variable name. Default is @code{"x"}.
2847 The global variable @code{default_print_flags} contains the default values,
2848 used by the function @code{fprint}.
2854 CLN has a class of abstract rings.
2862 Rings can be compared for equality:
2865 @item bool operator== (const cl_ring&, const cl_ring&)
2866 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2867 These compare two rings for equality.
2870 Given a ring @code{R}, the following members can be used.
2873 @item void R->fprint (std::ostream& stream, const cl_ring_element& x)
2874 @cindex @code{fprint ()}
2875 @itemx bool R->equal (const cl_ring_element& x, const cl_ring_element& y)
2876 @cindex @code{equal ()}
2877 @itemx cl_ring_element R->zero ()
2878 @cindex @code{zero ()}
2879 @itemx bool R->zerop (const cl_ring_element& x)
2880 @cindex @code{zerop ()}
2881 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2882 @cindex @code{plus ()}
2883 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2884 @cindex @code{minus ()}
2885 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2886 @cindex @code{uminus ()}
2887 @itemx cl_ring_element R->one ()
2888 @cindex @code{one ()}
2889 @itemx cl_ring_element R->canonhom (const cl_I& x)
2890 @cindex @code{canonhom ()}
2891 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2892 @cindex @code{mul ()}
2893 @itemx cl_ring_element R->square (const cl_ring_element& x)
2894 @cindex @code{square ()}
2895 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2896 @cindex @code{expt_pos ()}
2899 The following rings are built-in.
2902 @item cl_null_ring cl_0_ring
2903 The null ring, containing only zero.
2905 @item cl_complex_ring cl_C_ring
2906 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2908 @item cl_real_ring cl_R_ring
2909 The ring of real numbers. This corresponds to the type @code{cl_R}.
2911 @item cl_rational_ring cl_RA_ring
2912 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2914 @item cl_integer_ring cl_I_ring
2915 The ring of integers. This corresponds to the type @code{cl_I}.
2918 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2919 @code{cl_RA_ring}, @code{cl_I_ring}:
2922 @item bool instanceof (const cl_number& x, const cl_number_ring& R)
2923 @cindex @code{instanceof ()}
2924 Tests whether the given number is an element of the number ring R.
2928 @node Modular integers
2929 @chapter Modular integers
2930 @cindex modular integer
2933 * Modular integer rings::
2934 * Functions on modular integers::
2937 @node Modular integer rings
2938 @section Modular integer rings
2941 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2942 The modulus is explicitly part of every modular integer. CLN doesn't
2943 allow you to (accidentally) mix elements of different modular rings,
2944 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2945 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2946 doesn't have generic types. So one has to live with runtime checks.)
2948 The class of modular integer rings is
2956 Modular integer ring
2960 @cindex @code{cl_modint_ring}
2962 and the class of all modular integers (elements of modular integer rings) is
2970 Modular integer rings are constructed using the function
2973 @item cl_modint_ring find_modint_ring (const cl_I& N)
2974 @cindex @code{find_modint_ring ()}
2975 This function returns the modular ring @samp{Z/NZ}. It takes care
2976 of finding out about special cases of @code{N}, like powers of two
2977 and odd numbers for which Montgomery multiplication will be a win,
2978 @cindex Montgomery multiplication
2979 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2980 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2981 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2985 Modular integer rings can be compared for equality:
2988 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2989 @cindex @code{operator == ()}
2990 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2991 @cindex @code{operator != ()}
2992 These compare two modular integer rings for equality. Two different calls
2993 to @code{find_modint_ring} with the same argument necessarily return the
2994 same ring because it is memoized in the cache table.
2997 @node Functions on modular integers
2998 @section Functions on modular integers
3000 Given a modular integer ring @code{R}, the following members can be used.
3003 @item cl_I R->modulus
3004 @cindex @code{modulus}
3005 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
3007 @item cl_MI R->zero()
3008 @cindex @code{zero ()}
3009 This returns @code{0 mod N}.
3011 @item cl_MI R->one()
3012 @cindex @code{one ()}
3013 This returns @code{1 mod N}.
3015 @item cl_MI R->canonhom (const cl_I& x)
3016 @cindex @code{canonhom ()}
3017 This returns @code{x mod N}.
3019 @item cl_I R->retract (const cl_MI& x)
3020 @cindex @code{retract ()}
3021 This is a partial inverse function to @code{R->canonhom}. It returns the
3022 standard representative (@code{>=0}, @code{<N}) of @code{x}.
3024 @item cl_MI R->random(random_state& randomstate)
3025 @itemx cl_MI R->random()
3026 @cindex @code{random ()}
3027 This returns a random integer modulo @code{N}.
3030 The following operations are defined on modular integers.
3033 @item cl_modint_ring x.ring ()
3034 @cindex @code{ring ()}
3035 Returns the ring to which the modular integer @code{x} belongs.
3037 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
3038 @cindex @code{operator + ()}
3039 Returns the sum of two modular integers. One of the arguments may also
3042 @item cl_MI operator- (const cl_MI&, const cl_MI&)
3043 @cindex @code{operator - ()}
3044 Returns the difference of two modular integers. One of the arguments may also
3047 @item cl_MI operator- (const cl_MI&)
3048 Returns the negative of a modular integer.
3050 @item cl_MI operator* (const cl_MI&, const cl_MI&)
3051 @cindex @code{operator * ()}
3052 Returns the product of two modular integers. One of the arguments may also
3055 @item cl_MI square (const cl_MI&)
3056 @cindex @code{square ()}
3057 Returns the square of a modular integer.
3059 @item cl_MI recip (const cl_MI& x)
3060 @cindex @code{recip ()}
3061 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
3062 must be coprime to the modulus, otherwise an error message is issued.
3064 @item cl_MI div (const cl_MI& x, const cl_MI& y)
3065 @cindex @code{div ()}
3066 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
3067 @code{y} must be coprime to the modulus, otherwise an error message is issued.
3069 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
3070 @cindex @code{expt_pos ()}
3071 @code{y} must be > 0. Returns @code{x^y}.
3073 @item cl_MI expt (const cl_MI& x, const cl_I& y)
3074 @cindex @code{expt ()}
3075 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
3076 modulus, else an error message is issued.
3078 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
3079 @cindex @code{operator << ()}
3080 Returns @code{x*2^y}.
3082 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
3083 @cindex @code{operator >> ()}
3084 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
3085 or an error message is issued.
3087 @item bool operator== (const cl_MI&, const cl_MI&)
3088 @cindex @code{operator == ()}
3089 @itemx bool operator!= (const cl_MI&, const cl_MI&)
3090 @cindex @code{operator != ()}
3091 Compares two modular integers, belonging to the same modular integer ring,
3094 @item bool zerop (const cl_MI& x)
3095 @cindex @code{zerop ()}
3096 Returns true if @code{x} is @code{0 mod N}.
3099 The following output functions are defined (see also the chapter on
3103 @item void fprint (std::ostream& stream, const cl_MI& x)
3104 @cindex @code{fprint ()}
3105 @itemx std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
3106 @cindex @code{operator << ()}
3107 Prints the modular integer @code{x} on the @code{stream}. The output may depend
3108 on the global printer settings in the variable @code{default_print_flags}.
3112 @node Symbolic data types
3113 @chapter Symbolic data types
3114 @cindex symbolic type
3116 CLN implements two symbolic (non-numeric) data types: strings and symbols.
3126 @cindex @code{cl_string}
3136 implements immutable strings.
3138 Strings are constructed through the following constructors:
3141 @item cl_string (const char * s)
3142 Returns an immutable copy of the (zero-terminated) C string @code{s}.
3144 @item cl_string (const char * ptr, unsigned long len)
3145 Returns an immutable copy of the @code{len} characters at
3146 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
3149 The following functions are available on strings:
3153 Assignment from @code{cl_string} and @code{const char *}.
3156 @cindex @code{length ()}
3158 @cindex @code{strlen ()}
3159 Returns the length of the string @code{s}.
3162 @cindex @code{operator [] ()}
3163 Returns the @code{i}th character of the string @code{s}.
3164 @code{i} must be in the range @code{0 <= i < s.length()}.
3166 @item bool equal (const cl_string& s1, const cl_string& s2)
3167 @cindex @code{equal ()}
3168 Compares two strings for equality. One of the arguments may also be a
3169 plain @code{const char *}.
3175 @cindex @code{cl_symbol}
3177 Symbols are uniquified strings: all symbols with the same name are shared.
3178 This means that comparison of two symbols is fast (effectively just a pointer
3179 comparison), whereas comparison of two strings must in the worst case walk
3180 both strings until their end.
3181 Symbols are used, for example, as tags for properties, as names of variables
3182 in polynomial rings, etc.
3184 Symbols are constructed through the following constructor:
3187 @item cl_symbol (const cl_string& s)
3188 Looks up or creates a new symbol with a given name.
3191 The following operations are available on symbols:
3194 @item cl_string (const cl_symbol& sym)
3195 Conversion to @code{cl_string}: Returns the string which names the symbol
3198 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
3199 @cindex @code{equal ()}
3200 Compares two symbols for equality. This is very fast.
3204 @node Univariate polynomials
3205 @chapter Univariate polynomials
3207 @cindex univariate polynomial
3210 * Univariate polynomial rings::
3211 * Functions on univariate polynomials::
3212 * Special polynomials::
3215 @node Univariate polynomial rings
3216 @section Univariate polynomial rings
3218 CLN implements univariate polynomials (polynomials in one variable) over an
3219 arbitrary ring. The indeterminate variable may be either unnamed (and will be
3220 printed according to @code{default_print_flags.univpoly_varname}, which
3221 defaults to @samp{x}) or carry a given name. The base ring and the
3222 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
3223 (accidentally) mix elements of different polynomial rings, e.g.
3224 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
3225 return a multivariate polynomial, but they are not yet implemented in CLN.)
3227 The classes of univariate polynomial rings are
3235 Univariate polynomial ring
3239 +----------------+-------------------+
3241 Complex polynomial ring | Modular integer polynomial ring
3242 cl_univpoly_complex_ring | cl_univpoly_modint_ring
3243 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3247 Real polynomial ring |
3248 cl_univpoly_real_ring |
3249 <cln/univpoly_real.h> |
3253 Rational polynomial ring |
3254 cl_univpoly_rational_ring |
3255 <cln/univpoly_rational.h> |
3259 Integer polynomial ring
3260 cl_univpoly_integer_ring
3261 <cln/univpoly_integer.h>
3264 and the corresponding classes of univariate polynomials are
3267 Univariate polynomial
3271 +----------------+-------------------+
3273 Complex polynomial | Modular integer polynomial
3275 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3281 <cln/univpoly_real.h> |
3285 Rational polynomial |
3287 <cln/univpoly_rational.h> |
3293 <cln/univpoly_integer.h>
3296 Univariate polynomial rings are constructed using the functions
3299 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3300 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3301 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3302 @code{R} may be an arbitrary ring. This function takes care of finding out
3303 about special cases of @code{R}, such as the rings of complex numbers,
3304 real numbers, rational numbers, integers, or modular integer rings.
3305 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3306 This ensures that two calls of this function with the same arguments will
3307 return the same polynomial ring.
3309 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3310 @cindex @code{find_univpoly_ring ()}
3311 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3312 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3313 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3314 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3315 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3316 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3317 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3318 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3319 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3320 These functions are equivalent to the general @code{find_univpoly_ring},
3321 only the return type is more specific, according to the base ring's type.
3324 @node Functions on univariate polynomials
3325 @section Functions on univariate polynomials
3327 Given a univariate polynomial ring @code{R}, the following members can be used.
3330 @item cl_ring R->basering()
3331 @cindex @code{basering ()}
3332 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3334 @item cl_UP R->zero()
3335 @cindex @code{zero ()}
3336 This returns @code{0 in R}, a polynomial of degree -1.
3338 @item cl_UP R->one()
3339 @cindex @code{one ()}
3340 This returns @code{1 in R}, a polynomial of degree == 0.
3342 @item cl_UP R->canonhom (const cl_I& x)
3343 @cindex @code{canonhom ()}
3344 This returns @code{x in R}, a polynomial of degree <= 0.
3346 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3347 @cindex @code{monomial ()}
3348 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3351 @item cl_UP R->create (sintL degree)
3352 @cindex @code{create ()}
3353 Creates a new polynomial with a given degree. The zero polynomial has degree
3354 @code{-1}. After creating the polynomial, you should put in the coefficients,
3355 using the @code{set_coeff} member function, and then call the @code{finalize}
3359 The following are the only destructive operations on univariate polynomials.
3362 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3363 @cindex @code{set_coeff ()}
3364 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3365 After changing a polynomial and before applying any "normal" operation on it,
3366 you should call its @code{finalize} member function.
3368 @item void finalize (cl_UP& x)
3369 @cindex @code{finalize ()}
3370 This function marks the endpoint of destructive modifications of a polynomial.
3371 It normalizes the internal representation so that subsequent computations have
3372 less overhead. Doing normal computations on unnormalized polynomials may
3373 produce wrong results or crash the program.
3376 The following operations are defined on univariate polynomials.
3379 @item cl_univpoly_ring x.ring ()
3380 @cindex @code{ring ()}
3381 Returns the ring to which the univariate polynomial @code{x} belongs.
3383 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3384 @cindex @code{operator + ()}
3385 Returns the sum of two univariate polynomials.
3387 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3388 @cindex @code{operator - ()}
3389 Returns the difference of two univariate polynomials.
3391 @item cl_UP operator- (const cl_UP&)
3392 Returns the negative of a univariate polynomial.
3394 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3395 @cindex @code{operator * ()}
3396 Returns the product of two univariate polynomials. One of the arguments may
3397 also be a plain integer or an element of the base ring.
3399 @item cl_UP square (const cl_UP&)
3400 @cindex @code{square ()}
3401 Returns the square of a univariate polynomial.
3403 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3404 @cindex @code{expt_pos ()}
3405 @code{y} must be > 0. Returns @code{x^y}.
3407 @item bool operator== (const cl_UP&, const cl_UP&)
3408 @cindex @code{operator == ()}
3409 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3410 @cindex @code{operator != ()}
3411 Compares two univariate polynomials, belonging to the same univariate
3412 polynomial ring, for equality.
3414 @item bool zerop (const cl_UP& x)
3415 @cindex @code{zerop ()}
3416 Returns true if @code{x} is @code{0 in R}.
3418 @item sintL degree (const cl_UP& x)
3419 @cindex @code{degree ()}
3420 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3422 @item sintL ldegree (const cl_UP& x)
3423 @cindex @code{degree ()}
3424 Returns the low degree of the polynomial. This is the degree of the first
3425 non-vanishing polynomial coefficient. The zero polynomial has ldegree @code{-1}.
3427 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3428 @cindex @code{coeff ()}
3429 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3431 @item cl_ring_element x (const cl_ring_element& y)
3432 @cindex @code{operator () ()}
3433 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3434 then @samp{x(y)} returns the value of the substitution of @code{y} into
3437 @item cl_UP deriv (const cl_UP& x)
3438 @cindex @code{deriv ()}
3439 Returns the derivative of the polynomial @code{x} with respect to the
3440 indeterminate @code{X}.
3443 The following output functions are defined (see also the chapter on
3447 @item void fprint (std::ostream& stream, const cl_UP& x)
3448 @cindex @code{fprint ()}
3449 @itemx std::ostream& operator<< (std::ostream& stream, const cl_UP& x)
3450 @cindex @code{operator << ()}
3451 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3452 depend on the global printer settings in the variable
3453 @code{default_print_flags}.
3456 @node Special polynomials
3457 @section Special polynomials
3459 The following functions return special polynomials.
3462 @item cl_UP_I tschebychev (sintL n)
3463 @cindex @code{tschebychev ()}
3464 @cindex Chebyshev polynomial
3465 Returns the n-th Chebyshev polynomial (n >= 0).
3467 @item cl_UP_I hermite (sintL n)
3468 @cindex @code{hermite ()}
3469 @cindex Hermite polynomial
3470 Returns the n-th Hermite polynomial (n >= 0).
3472 @item cl_UP_RA legendre (sintL n)
3473 @cindex @code{legendre ()}
3474 @cindex Legende polynomial
3475 Returns the n-th Legendre polynomial (n >= 0).
3477 @item cl_UP_I laguerre (sintL n)
3478 @cindex @code{laguerre ()}
3479 @cindex Laguerre polynomial
3480 Returns the n-th Laguerre polynomial (n >= 0).
3483 Information how to derive the differential equation satisfied by each
3484 of these polynomials from their definition can be found in the
3485 @code{doc/polynomial/} directory.
3493 * Memory efficiency::
3494 * Speed efficiency::
3495 * Garbage collection::
3502 Using C++ as an implementation language provides
3506 Efficiency: It compiles to machine code.
3510 Portability: It runs on all platforms supporting a C++ compiler. Because
3511 of the availability of GNU C++, this includes all currently used 32-bit and
3512 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3515 Type safety: The C++ compilers knows about the number types and complains if,
3516 for example, you try to assign a float to an integer variable. However,
3517 a drawback is that C++ doesn't know about generic types, hence a restriction
3518 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3519 arguments belong to the same modular ring cannot be expressed as a compile-time
3523 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3524 @code{=}, @code{==}, ... can be used in infix notation, which is more
3525 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3528 With these language features, there is no need for two separate languages,
3529 one for the implementation of the library and one in which the library's users
3530 can program. This means that a prototype implementation of an algorithm
3531 can be integrated into the library immediately after it has been tested and
3532 debugged. No need to rewrite it in a low-level language after having prototyped
3533 in a high-level language.
3536 @node Memory efficiency
3537 @section Memory efficiency
3539 In order to save memory allocations, CLN implements:
3543 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3546 @cindex garbage collection
3547 @cindex reference counting
3548 Garbage collection: A reference counting mechanism makes sure that any
3549 number object's storage is freed immediately when the last reference to the
3552 @cindex immediate numbers
3553 Small integers are represented as immediate values instead of pointers
3554 to heap allocated storage. This means that integers @code{>= -2^29},
3555 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3560 @node Speed efficiency
3561 @section Speed efficiency
3563 Speed efficiency is obtained by the combination of the following tricks
3568 Small integers, being represented as immediate values, don't require
3569 memory access, just a couple of instructions for each elementary operation.
3571 The kernel of CLN has been written in assembly language for some CPUs
3572 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3574 On all CPUs, CLN may be configured to use the superefficient low-level
3575 routines from GNU GMP version 3.
3577 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3578 algorithm, the Karatsuba multiplication, which is an
3589 For very large numbers (more than 12000 decimal digits), CLN uses
3591 Sch{@"o}nhage-Strassen
3592 @cindex Sch{@"o}nhage-Strassen multiplication
3596 @cindex Schoenhage-Strassen multiplication
3598 multiplication, which is an asymptotically optimal multiplication
3601 These fast multiplication algorithms also give improvements in the speed
3602 of division and radix conversion.
3606 @node Garbage collection
3607 @section Garbage collection
3608 @cindex garbage collection
3610 All the number classes are reference count classes: They only contain a pointer
3611 to an object in the heap. Upon construction, assignment and destruction of
3612 number objects, only the objects' reference count are manipulated.
3614 Memory occupied by number objects are automatically reclaimed as soon as
3615 their reference count drops to zero.
3617 For number rings, another strategy is implemented: There is a cache of,
3618 for example, the modular integer rings. A modular integer ring is destroyed
3619 only if its reference count dropped to zero and the cache is about to be
3620 resized. The effect of this strategy is that recently used rings remain
3621 cached, whereas undue memory consumption through cached rings is avoided.
3624 @node Using the library
3625 @chapter Using the library
3627 For the following discussion, we will assume that you have installed
3628 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3629 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3630 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3631 environment variables, or directly substitute the appropriate values.
3635 * Compiler options::
3638 * Debugging support::
3639 * Reporting Problems::
3642 @node Compiler options
3643 @section Compiler options
3644 @cindex compiler options
3646 Until you have installed CLN in a public place, the following options are
3649 When you compile CLN application code, add the flags
3651 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3653 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3654 When you link CLN application code to form an executable, add the flags
3656 $CLN_TARGETDIR/src/libcln.a
3658 to the C/C++ compiler's command line (@code{make} variable LIBS).
3660 If you did a @code{make install}, the include files are installed in a
3661 public directory (normally @code{/usr/local/include}), hence you don't
3662 need special flags for compiling. The library has been installed to a
3663 public directory as well (normally @code{/usr/local/lib}), hence when
3664 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3666 @cindex @code{pkg-config}
3667 To make the creation of software packages that use CLN easier, the
3668 @code{pkg-config} utility can be used. CLN provides all the necessary
3669 metainformation in a file called @code{cln.pc} (installed in
3670 @code{/usr/local/lib/pkgconfig} by default). A program using CLN can
3671 be compiled and linked using @footnote{If you installed CLN to
3672 non-standard location @var{prefix}, you need to set the
3673 @env{PKG_CONFIG_PATH} environment variable to @var{prefix}/lib/pkgconfig
3676 g++ `pkg-config --libs cln` `pkg-config --cflags cln` prog.cc -o prog
3679 Software using GNU autoconf can check for CLN with the
3680 @code{PKG_CHECK_MODULES} macro supplied with @code{pkg-config}.
3682 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}])
3684 This will check for CLN version at least @var{MIN-VERSION}. If the
3685 required version was found, the variables @var{CLN_CFLAGS} and
3686 @var{CLN_LIBS} are set. Otherwise the configure script aborts. If this
3687 is not the desired behaviour, use the following code instead
3688 @footnote{See the @code{pkg-config} documentation for more details.}
3690 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}], [],
3691 [AC_MSG_WARNING([No suitable version of CLN can be found])])
3696 @section Include files
3697 @cindex include files
3698 @cindex header files
3700 Here is a summary of the include files and their contents.
3703 @item <cln/object.h>
3704 General definitions, reference counting, garbage collection.
3705 @item <cln/number.h>
3706 The class cl_number.
3707 @item <cln/complex.h>
3708 Functions for class cl_N, the complex numbers.
3710 Functions for class cl_R, the real numbers.
3712 Functions for class cl_F, the floats.
3713 @item <cln/sfloat.h>
3714 Functions for class cl_SF, the short-floats.
3715 @item <cln/ffloat.h>
3716 Functions for class cl_FF, the single-floats.
3717 @item <cln/dfloat.h>
3718 Functions for class cl_DF, the double-floats.
3719 @item <cln/lfloat.h>
3720 Functions for class cl_LF, the long-floats.
3721 @item <cln/rational.h>
3722 Functions for class cl_RA, the rational numbers.
3723 @item <cln/integer.h>
3724 Functions for class cl_I, the integers.
3727 @item <cln/complex_io.h>
3728 Input/Output for class cl_N, the complex numbers.
3729 @item <cln/real_io.h>
3730 Input/Output for class cl_R, the real numbers.
3731 @item <cln/float_io.h>
3732 Input/Output for class cl_F, the floats.
3733 @item <cln/sfloat_io.h>
3734 Input/Output for class cl_SF, the short-floats.
3735 @item <cln/ffloat_io.h>
3736 Input/Output for class cl_FF, the single-floats.
3737 @item <cln/dfloat_io.h>
3738 Input/Output for class cl_DF, the double-floats.
3739 @item <cln/lfloat_io.h>
3740 Input/Output for class cl_LF, the long-floats.
3741 @item <cln/rational_io.h>
3742 Input/Output for class cl_RA, the rational numbers.
3743 @item <cln/integer_io.h>
3744 Input/Output for class cl_I, the integers.
3746 Flags for customizing input operations.
3747 @item <cln/output.h>
3748 Flags for customizing output operations.
3749 @item <cln/malloc.h>
3750 @code{malloc_hook}, @code{free_hook}.
3751 @item <cln/exception.h>
3752 Exception base class.
3753 @item <cln/condition.h>
3755 @item <cln/string.h>
3757 @item <cln/symbol.h>
3759 @item <cln/proplist.h>
3763 @item <cln/null_ring.h>
3765 @item <cln/complex_ring.h>
3766 The ring of complex numbers.
3767 @item <cln/real_ring.h>
3768 The ring of real numbers.
3769 @item <cln/rational_ring.h>
3770 The ring of rational numbers.
3771 @item <cln/integer_ring.h>
3772 The ring of integers.
3773 @item <cln/numtheory.h>
3774 Number threory functions.
3775 @item <cln/modinteger.h>
3781 @item <cln/GV_number.h>
3782 General vectors over cl_number.
3783 @item <cln/GV_complex.h>
3784 General vectors over cl_N.
3785 @item <cln/GV_real.h>
3786 General vectors over cl_R.
3787 @item <cln/GV_rational.h>
3788 General vectors over cl_RA.
3789 @item <cln/GV_integer.h>
3790 General vectors over cl_I.
3791 @item <cln/GV_modinteger.h>
3792 General vectors of modular integers.
3795 @item <cln/SV_number.h>
3796 Simple vectors over cl_number.
3797 @item <cln/SV_complex.h>
3798 Simple vectors over cl_N.
3799 @item <cln/SV_real.h>
3800 Simple vectors over cl_R.
3801 @item <cln/SV_rational.h>
3802 Simple vectors over cl_RA.
3803 @item <cln/SV_integer.h>
3804 Simple vectors over cl_I.
3805 @item <cln/SV_ringelt.h>
3806 Simple vectors of general ring elements.
3807 @item <cln/univpoly.h>
3808 Univariate polynomials.
3809 @item <cln/univpoly_integer.h>
3810 Univariate polynomials over the integers.
3811 @item <cln/univpoly_rational.h>
3812 Univariate polynomials over the rational numbers.
3813 @item <cln/univpoly_real.h>
3814 Univariate polynomials over the real numbers.
3815 @item <cln/univpoly_complex.h>
3816 Univariate polynomials over the complex numbers.
3817 @item <cln/univpoly_modint.h>
3818 Univariate polynomials over modular integer rings.
3819 @item <cln/timing.h>
3822 Includes all of the above.
3829 A function which computes the nth Fibonacci number can be written as follows.
3830 @cindex Fibonacci number
3833 #include <cln/integer.h>
3834 #include <cln/real.h>
3835 using namespace cln;
3837 // Returns F_n, computed as the nearest integer to
3838 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3839 const cl_I fibonacci (int n)
3841 // Need a precision of ((1+sqrt(5))/2)^-n.
3842 float_format_t prec = float_format((int)(0.208987641*n+5));
3843 cl_R sqrt5 = sqrt(cl_float(5,prec));
3844 cl_R phi = (1+sqrt5)/2;
3845 return round1( expt(phi,n)/sqrt5 );
3849 Let's explain what is going on in detail.
3851 The include file @code{<cln/integer.h>} is necessary because the type
3852 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3853 is needed for the type @code{cl_R} and the floating point number functions.
3854 The order of the include files does not matter. In order not to write
3855 out @code{cln::}@var{foo} in this simple example we can safely import
3856 the whole namespace @code{cln}.
3858 Then comes the function declaration. The argument is an @code{int}, the
3859 result an integer. The return type is defined as @samp{const cl_I}, not
3860 simply @samp{cl_I}, because that allows the compiler to detect typos like
3861 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3862 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3863 number). We use the most specialized possible return type because functions
3864 which call @samp{fibonacci} will be able to profit from the compiler's type
3865 analysis: Adding two integers is slightly more efficient than adding the
3866 same objects declared as complex numbers, because it needs less type
3867 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3868 the size of the resulting executable program.
3870 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3871 integer. In order to get a correct result, the absolute error should be less
3872 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3873 To this end, the first line computes a floating point precision for sqrt(5)
3876 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3877 number and than taking the square root. The converse, first taking the square
3878 root of 5, and then converting to the desired precision, would not work in
3879 CLN: The square root would be computed to a default precision (normally
3880 single-float precision), and the following conversion could not help about
3881 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3882 system and does not represent sqrt(5) in a non-numeric way.
3884 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3885 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3886 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3887 @code{cl_N} because a @samp{round1} does not exist for general complex
3890 When the function returns, all the local variables in the function are
3891 automatically reclaimed (garbage collected). Only the result survives and
3892 gets passed to the caller.
3894 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3895 contains this implementation together with an even faster algorithm.
3897 @node Debugging support
3898 @section Debugging support
3901 When debugging a CLN application with GNU @code{gdb}, two facilities are
3902 available from the library:
3905 @item The library does type checks, range checks, consistency checks at
3906 many places. When one of these fails, an exception of a type derived from
3907 @code{runtime_exception} is thrown. When an exception is cought, the stack
3908 has already been unwound, so it is may not be possible to tell at which
3909 point the exception was thrown. For debugging, it is best to set up a
3910 catchpoint at the event of throwning a C++ exception:
3914 When this catchpoint is hit, look at the stack's backtrace:
3918 When control over the type of exception is required, it may be possible
3919 to set a breakpoint at the @code{g++} runtime library function
3920 @code{__raise_exception}. Refer to the documentation of GNU @code{gdb}
3923 @item The debugger's normal @code{print} command doesn't know about
3924 CLN's types and therefore prints mostly useless hexadecimal addresses.
3925 CLN offers a function @code{cl_print}, callable from the debugger,
3926 for printing number objects. In order to get this function, you have
3927 to define the macro @samp{CL_DEBUG} and then include all the header files
3928 for which you want @code{cl_print} debugging support. For example:
3929 @cindex @code{CL_DEBUG}
3932 #include <cln/string.h>
3934 Now, if you have in your program a variable @code{cl_string s}, and
3935 inspect it under @code{gdb}, the output may look like this:
3938 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3939 word = 134568800@}@}, @}
3940 (gdb) call cl_print(s)
3944 Note that the output of @code{cl_print} goes to the program's error output,
3945 not to gdb's standard output.
3947 Note, however, that the above facility does not work with all CLN types,
3948 only with number objects and similar. Therefore CLN offers a member function
3949 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3950 is needed for this member function to be implemented. Under @code{gdb},
3951 you call it like this:
3952 @cindex @code{debug_print ()}
3955 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3956 word = 134568800@}@}, @}
3957 (gdb) call s.debug_print()
3960 >call ($1).debug_print()
3965 Unfortunately, this feature does not seem to work under all circumstances.
3968 @node Reporting Problems
3969 @section Reporting Problems
3971 @cindex mailing list
3973 If you encounter any problem, please don't hesitate to send a detailed
3974 bugreport to the @code{cln-list@@ginac.de} mailing list. Please think
3975 about your bug: consider including a short description of your operating
3976 system and compilation environment with corresponding version numbers. A
3977 description of your configuration options may also be helpful. Also, a
3978 short test program together with the output you get and the output you
3979 expect will help us to reproduce it quickly. Finally, do not forget to
3980 report the version number of CLN.
3984 @chapter Customizing
3989 * Floating-point underflow::
3991 * Customizing the memory allocator::
3994 @node Error handling
3995 @section Error handling
3997 @cindex error handling
3999 @cindex @code{runtime_exception}
4000 CLN signals abnormal situations by throwning exceptions. All exceptions
4001 thrown by the library are of type @code{runtime_exception} or of a
4002 derived type. Class @code{cln::runtime_exception} in turn is derived
4003 from the C++ standard library class @code{std::runtime_error} and
4004 inherits the @code{.what()} member function that can be used to query
4005 details about the cause of error.
4007 The most important classes thrown by the library are
4009 @cindex @code{floating_point_exception}
4010 @cindex @code{read_number_exception}
4012 Exception base class
4016 +----------------+----------------+
4018 Malformed number input Floating-point error
4019 read_number_exception floating_poing_exception
4020 <cln/number_io.h> <cln/float.h>
4023 CLN has many more exception classes that allow for more fine-grained
4024 control but I refrain from documenting them all here. They are all
4025 declared in the public header files and they are all subclasses of the
4026 above exceptions, so catching those you are always on the safe side.
4029 @node Floating-point underflow
4030 @section Floating-point underflow
4033 @cindex @code{floating_point_underflow_exception}
4034 Floating point underflow denotes the situation when a floating-point
4035 number is to be created which is so close to @code{0} that its exponent
4036 is too low to be represented internally. By default, this causes the
4037 exception @code{floating_point_underflow_exception} (subclass of
4038 @code{floating_point_exception}) to be thrown. If you set the global
4041 bool cl_inhibit_floating_point_underflow
4043 to @code{true}, the exception will be inhibited, and a floating-point
4044 zero will be generated instead. The default value of
4045 @code{cl_inhibit_floating_point_underflow} is @code{false}.
4048 @node Customizing I/O
4049 @section Customizing I/O
4051 The output of the function @code{fprint} may be customized by changing the
4052 value of the global variable @code{default_print_flags}.
4053 @cindex @code{default_print_flags}
4056 @node Customizing the memory allocator
4057 @section Customizing the memory allocator
4059 Every memory allocation of CLN is done through the function pointer
4060 @code{malloc_hook}. Freeing of this memory is done through the function
4061 pointer @code{free_hook}. The default versions of these functions,
4062 provided in the library, call @code{malloc} and @code{free} and check
4063 the @code{malloc} result against @code{NULL}.
4064 If you want to provide another memory allocator, you need to define
4065 the variables @code{malloc_hook} and @code{free_hook} yourself,
4068 #include <cln/malloc.h>
4070 void* (*malloc_hook) (size_t size) = @dots{};
4071 void (*free_hook) (void* ptr) = @dots{};
4074 @cindex @code{malloc_hook ()}
4075 @cindex @code{free_hook ()}
4076 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
4078 It is not possible to change the memory allocator at runtime, because
4079 it is already called at program startup by the constructors of some
4087 @node Index, , Customizing, Top