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.
33 This manual documents @sc{cln}, a Class Library for Numbers.
35 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
36 Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
38 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008.
39 Copyright (C) Richard B. Kreckel 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009.
40 Copyright (C) Alexei Sheplyakov 2008.
42 Permission is granted to make and distribute verbatim copies of
43 this manual provided the copyright notice and this permission notice
44 are preserved on all copies.
47 Permission is granted to process this file through TeX and print the
48 results, provided the printed document carries copying permission
49 notice identical to this one except for the removal of this paragraph
50 (this paragraph not being relevant to the printed manual).
53 Permission is granted to copy and distribute modified versions of this
54 manual under the conditions for verbatim copying, provided that the entire
55 resulting derived work is distributed under the terms of a permission
56 notice identical to this one.
58 Permission is granted to copy and distribute translations of this manual
59 into another language, under the above conditions for modified versions,
60 except that this permission notice may be stated in a translation approved
66 @c prevent ugly black rectangles on overfull hbox lines:
69 @title CLN, a Class Library for Numbers
71 @author @uref{http://www.ginac.de/CLN}
73 @vskip 0pt plus 1filll
74 Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008.
76 Copyright @copyright{} Richard B. Kreckel 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009.
77 Copyright @copyright{} Alexei Sheplyakov 2008.
80 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
81 Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
83 Permission is granted to make and distribute verbatim copies of
84 this manual provided the copyright notice and this permission notice
85 are preserved on all copies.
87 Permission is granted to copy and distribute modified versions of this
88 manual under the conditions for verbatim copying, provided that the entire
89 resulting derived work is distributed under the terms of a permission
90 notice identical to this one.
92 Permission is granted to copy and distribute translations of this manual
93 into another language, under the above conditions for modified versions,
94 except that this permission notice may be stated in a translation approved
109 * Ordinary number types::
110 * Functions on numbers::
114 * Symbolic data types::
115 * Univariate polynomials::
117 * Using the library::
121 --- The Detailed Node Listing ---
126 * Building the library::
127 * Installing the library::
138 * Using the GNU MP Library::
140 Ordinary number types
143 * Floating-point numbers::
149 * Constructing numbers::
150 * Elementary functions::
151 * Elementary rational functions::
152 * Elementary complex functions::
154 * Rounding functions::
156 * Transcendental functions::
157 * Functions on integers::
158 * Functions on floating-point numbers::
159 * Conversion functions::
160 * Random number generators::
161 * Modifying operators::
165 * Constructing integers::
166 * Constructing rational numbers::
167 * Constructing floating-point numbers::
168 * Constructing complex numbers::
170 Transcendental functions
172 * Exponential and logarithmic functions::
173 * Trigonometric functions::
174 * Hyperbolic functions::
178 Functions on integers
180 * Logical functions::
181 * Number theoretic functions::
182 * Combinatorial functions::
186 * Conversion to floating-point numbers::
187 * Conversion to rational numbers::
191 * Internal and printed representation::
197 * Modular integer rings::
198 * Functions on modular integers::
205 Univariate polynomials
207 * Univariate polynomial rings::
208 * Functions on univariate polynomials::
209 * Special polynomials::
214 * Memory efficiency::
216 * Garbage collection::
223 * Debugging support::
224 * Reporting Problems::
229 * Floating-point underflow::
231 * Customizing the memory allocator::
236 @chapter Introduction
239 CLN is a library for computations with all kinds of numbers.
240 It has a rich set of number classes:
244 Integers (with unlimited precision),
250 Floating-point numbers:
260 Long float (with unlimited precision),
267 Modular integers (integers modulo a fixed integer),
270 Univariate polynomials.
274 The subtypes of the complex numbers among these are exactly the
275 types of numbers known to the Common Lisp language. Therefore
276 @code{CLN} can be used for Common Lisp implementations, giving
277 @samp{CLN} another meaning: it becomes an abbreviation of
278 ``Common Lisp Numbers''.
281 The CLN package implements
285 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
286 comparisons, @dots{}),
289 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
292 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
293 functions and their inverse functions).
297 CLN is a C++ library. Using C++ as an implementation language provides
301 efficiency: it compiles to machine code,
303 type safety: the C++ compiler knows about the number types and complains
304 if, for example, you try to assign a float to an integer variable.
306 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
307 @code{==}, @dots{} operators as in C or C++.
311 CLN is memory efficient:
315 Small integers and short floats are immediate, not heap allocated.
317 Heap-allocated memory is reclaimed through an automatic, non-interruptive
322 CLN is speed efficient:
326 The kernel of CLN has been written in assembly language for some CPUs
327 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
330 On all CPUs, CLN may be configured to use the superefficient low-level
331 routines from GNU GMP version 3.
333 It uses Karatsuba multiplication, which is significantly faster
334 for large numbers than the standard multiplication algorithm.
336 For very large numbers (more than 12000 decimal digits), it uses
338 Sch{@"o}nhage-Strassen
339 @cindex Sch{@"o}nhage-Strassen multiplication
343 @cindex Schoenhage-Strassen multiplication
345 multiplication, which is an asymptotically optimal multiplication
346 algorithm, for multiplication, division and radix conversion.
348 @cindex binary splitting
349 It uses binary splitting for fast evaluation of series of rational
350 numbers as they occur in the evaluation of elementary functions and some
355 CLN aims at being easily integrated into larger software packages:
359 The garbage collection imposes no burden on the main application.
361 The library provides hooks for memory allocation and throws exceptions
365 All non-macro identifiers are hidden in namespace @code{cln} in
366 order to avoid name clashes.
371 @chapter Installation
373 This section describes how to install the CLN package on your system.
378 * Building the library::
379 * Installing the library::
383 @node Prerequisites, Building the library, Installation, Installation
384 @section Prerequisites
393 @subsection C++ compiler
395 To build CLN, you need a C++ compiler.
396 Actually, you need GNU @code{g++ 3.0.0} or newer.
398 The following C++ features are used:
399 classes, member functions, overloading of functions and operators,
400 constructors and destructors, inline, const, multiple inheritance,
401 templates and namespaces.
403 The following C++ features are not used:
404 @code{new}, @code{delete}, virtual inheritance.
406 CLN relies on semi-automatic ordering of initializations of static and
407 global variables, a feature which I could implement for GNU g++
408 only. Also, it is not known whether this semi-automatic ordering works
409 on all platforms when a non-GNU assembler is being used.
412 @subsection Make utility
415 To build CLN, you also need to have GNU @code{make} installed.
417 Only GNU @code{make} 3.77 is unusable for CLN; other versions work fine.
420 @subsection Sed utility
423 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
424 This is because the libtool script, which creates the CLN library, relies
425 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
429 @node Building the library
430 @section Building the library
432 As with any autoconfiguring GNU software, installation is as easy as this:
440 If on your system, @samp{make} is not GNU @code{make}, you have to use
441 @samp{gmake} instead of @samp{make} above.
443 The @code{configure} command checks out some features of your system and
444 C++ compiler and builds the @code{Makefile}s. The @code{make} command
445 builds the library. This step may take about half an hour on an average
446 workstation. The @code{make check} runs some test to check that no
447 important subroutine has been miscompiled.
449 The @code{configure} command accepts options. To get a summary of them, try
455 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
457 You can specify the C compiler, the C++ compiler and their options through
458 the following environment variables when running @code{configure}:
462 Specifies the C compiler.
465 Flags to be given to the C compiler when compiling programs (not when linking).
468 Specifies the C++ compiler.
471 Flags to be given to the C++ compiler when compiling programs (not when linking).
474 Flags to be given to the C/C++ preprocessor.
477 Flags to be given to the linker.
483 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
486 $ CC="gcc -V 3.2.3" CFLAGS="-O2 -finline-limit=1000" \
487 CXX="g++ -V 3.2.3" CXXFLAGS="-O2 -finline-limit=1000" \
488 CPPFLAGS="-DNO_ASM" ./configure
491 $ CC="gcc-4.2" CFLAGS="-O2" CXX="g++-4.2" CXXFLAGS="-O2" ./configure
494 Note that for these environment variables to take effect, you have to set
495 them (assuming a Bourne-compatible shell) on the same line as the
496 @code{configure} command. If you made the settings in earlier shell
497 commands, you have to @code{export} the environment variables before
498 calling @code{configure}. In a @code{csh} shell, you have to use the
499 @samp{setenv} command for setting each of the environment variables.
501 Currently CLN works only with the GNU @code{g++} compiler, and only in
502 optimizing mode. So you should specify at least @code{-O} in the
503 CXXFLAGS, or no CXXFLAGS at all. If CXXFLAGS is not set, CLN will be
504 compiled with @code{-O}.
506 The assembler language kernel can be turned off by specifying
507 @code{-DNO_ASM} in the CPPFLAGS. If @code{make check} reports any
508 problems, you may try to clean up (see @ref{Cleaning up}) and configure
509 and compile again, this time with @code{-DNO_ASM}.
511 If you use @code{g++} 3.2.x or earlier, I recommend adding
512 @samp{-finline-limit=1000} to the CXXFLAGS. This is essential for good
515 If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
516 @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
517 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
518 routines. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
521 Also, please do not compile CLN with @code{g++} using the @code{-O3}
522 optimization level. This leads to inferior code quality.
524 Some newer versions of @code{g++} require quite an amount of memory.
525 You might need some swap space if your machine doesn't have 512 MB of
528 By default, both a shared and a static library are built. You can build
529 CLN as a static (or shared) library only, by calling @code{configure}
530 with the option @samp{--disable-shared} (or @samp{--disable-static}).
531 While shared libraries are usually more convenient to use, they may not
532 work on all architectures. Try disabling them if you run into linker
533 problems. Also, they are generally slightly slower than static
534 libraries so runtime-critical applications should be linked statically.
538 * Using the GNU MP Library::
541 @node Using the GNU MP Library
542 @subsection Using the GNU MP Library
545 CLN may be configured to make use of a preinstalled @code{gmp} library
546 for some low-level routines. Please make sure that you have at least
547 @code{gmp} version 3.0 installed since earlier versions are unsupported
548 and likely not to work. Using @code{gmp} is known to be quite a boost
549 for CLN's performance.
551 By default, CLN will autodetect @code{gmp} and use it. If you do not
552 want CLN to make use of a preinstalled @code{gmp} library, then you can
553 explicitly specify so by calling @code{configure} with the option
554 @samp{--without-gmp}.
556 If you have installed the @code{gmp} library and its header files in
557 some place where the compiler cannot find it by default, you must help
558 @code{configure} and specify the prefix that was used when @code{gmp}
559 was configured. Here is an example:
562 $ ./configure --with-gmp=/opt/gmp-4.2.2
565 This assumes that the @code{gmp} header files have been installed in
566 @file{/opt/gmp-4.2.2/include/} and the library in
567 @file{/opt/gmp-4.2.2/lib/}. More uncommon GMP installations can be
568 handled by setting CPPFLAGS and LDFLAGS appropriately prior to running
572 @node Installing the library
573 @section Installing the library
576 As with any autoconfiguring GNU software, installation is as easy as this:
582 The @samp{make install} command installs the library and the include files
583 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
584 if you haven't specified a @code{--prefix} option to @code{configure}).
585 This step may require superuser privileges.
587 If you have already built the library and wish to install it, but didn't
588 specify @code{--prefix=@dots{}} at configure time, just re-run
589 @code{configure}, giving it the same options as the first time, plus
590 the @code{--prefix=@dots{}} option.
596 You can remove system-dependent files generated by @code{make} through
602 You can remove all files generated by @code{make}, thus reverting to a
603 virgin distribution of CLN, through
610 @node Ordinary number types
611 @chapter Ordinary number types
613 CLN implements the following class hierarchy:
621 Real or complex number
630 +-------------------+-------------------+
632 Rational number Floating-point number
634 <cln/rational.h> <cln/float.h>
636 | +--------------+--------------+--------------+
638 cl_I Short-Float Single-Float Double-Float Long-Float
639 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
640 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
643 @cindex @code{cl_number}
644 @cindex abstract class
645 The base class @code{cl_number} is an abstract base class.
646 It is not useful to declare a variable of this type except if you want
647 to completely disable compile-time type checking and use run-time type
652 @cindex complex number
653 The class @code{cl_N} comprises real and complex numbers. There is
654 no special class for complex numbers since complex numbers with imaginary
655 part @code{0} are automatically converted to real numbers.
658 The class @code{cl_R} comprises real numbers of different kinds. It is an
662 @cindex rational number
664 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
665 integers. There is no special class for non-integral rational numbers
666 since rational numbers with denominator @code{1} are automatically converted
670 The class @code{cl_F} implements floating-point approximations to real numbers.
671 It is an abstract class.
676 * Floating-point numbers::
682 @section Exact numbers
685 Some numbers are represented as exact numbers: there is no loss of information
686 when such a number is converted from its mathematical value to its internal
687 representation. On exact numbers, the elementary operations (@code{+},
688 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
691 In CLN, the exact numbers are:
695 rational numbers (including integers),
697 complex numbers whose real and imaginary parts are both rational numbers.
700 Rational numbers are always normalized to the form
701 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
702 are coprime integers and the denominator is positive. If the resulting
703 denominator is @code{1}, the rational number is converted to an integer.
705 @cindex immediate numbers
706 Small integers (typically in the range @code{-2^29}@dots{}@code{2^29-1},
707 for 32-bit machines) are especially efficient, because they consume no heap
708 allocation. Otherwise the distinction between these immediate integers
709 (called ``fixnums'') and heap allocated integers (called ``bignums'')
710 is completely transparent.
713 @node Floating-point numbers
714 @section Floating-point numbers
715 @cindex floating-point number
717 Not all real numbers can be represented exactly. (There is an easy mathematical
718 proof for this: Only a countable set of numbers can be stored exactly in
719 a computer, even if one assumes that it has unlimited storage. But there
720 are uncountably many real numbers.) So some approximation is needed.
721 CLN implements ordinary floating-point numbers, with mantissa and exponent.
723 @cindex rounding error
724 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
725 only return approximate results. For example, the value of the expression
726 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
727 @samp{0.7}. Rounding errors like this one are inevitable when computing
728 with floating-point numbers.
730 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
731 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
732 rule: It first computes the exact mathematical result and then returns the
733 floating-point number which is nearest to this. If two floating-point numbers
734 are equally distant from the ideal result, the one with a @code{0} in its least
735 significant mantissa bit is chosen.
737 Similarly, testing floating point numbers for equality @samp{x == y}
738 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
739 for some well-chosen @code{epsilon}.
741 Floating point numbers come in four flavors:
746 Short floats, type @code{cl_SF}.
747 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
748 and 17 mantissa bits (including the ``hidden'' bit).
749 They don't consume heap allocation.
753 Single floats, type @code{cl_FF}.
754 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
755 and 24 mantissa bits (including the ``hidden'' bit).
756 In CLN, they are represented as IEEE single-precision floating point numbers.
757 This corresponds closely to the C/C++ type @samp{float}.
761 Double floats, type @code{cl_DF}.
762 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
763 and 53 mantissa bits (including the ``hidden'' bit).
764 In CLN, they are represented as IEEE double-precision floating point numbers.
765 This corresponds closely to the C/C++ type @samp{double}.
769 Long floats, type @code{cl_LF}.
770 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
771 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
772 The precision of a long float is unlimited, but once created, a long float
773 has a fixed precision. (No ``lazy recomputation''.)
776 Of course, computations with long floats are more expensive than those
777 with smaller floating-point formats.
779 CLN does not implement features like NaNs, denormalized numbers and
780 gradual underflow. If the exponent range of some floating-point type
781 is too limited for your application, choose another floating-point type
782 with larger exponent range.
785 As a user of CLN, you can forget about the differences between the
786 four floating-point types and just declare all your floating-point
787 variables as being of type @code{cl_F}. This has the advantage that
788 when you change the precision of some computation (say, from @code{cl_DF}
789 to @code{cl_LF}), you don't have to change the code, only the precision
790 of the initial values. Also, many transcendental functions have been
791 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
792 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
793 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
794 the floating point contagion rule happened to change in the future.)
797 @node Complex numbers
798 @section Complex numbers
799 @cindex complex number
801 Complex numbers, as implemented by the class @code{cl_N}, have a real
802 part and an imaginary part, both real numbers. A complex number whose
803 imaginary part is the exact number @code{0} is automatically converted
806 Complex numbers can arise from real numbers alone, for example
807 through application of @code{sqrt} or transcendental functions.
814 Conversions from any class to any its superclasses (``base classes'' in
815 C++ terminology) is done automatically.
817 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
818 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
819 @code{cl_N} and @code{cl_number}.
821 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
822 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
823 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
824 efficiency. On 32-bit systems, their range is therefore limited:
828 The conversion from @samp{int} works only if the argument is < 2^29 and >= -2^29.
830 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
833 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
834 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
835 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
836 in error on 32-bit machines.
837 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
838 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
839 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
840 @samp{cl_I}, first convert it to an @samp{unsigned long}. On 64-bit machines
841 there is no such restriction. There, conversions from arbitrary 32-bit @samp{int}
842 values always works correctly.
844 Conversions from the C built-in type @samp{float} are provided for the classes
845 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
847 Conversions from the C built-in type @samp{double} are provided for the classes
848 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
850 Conversions from @samp{const char *} are provided for the classes
851 @code{cl_I}, @code{cl_RA},
852 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
853 @code{cl_R}, @code{cl_N}.
854 The easiest way to specify a value which is outside of the range of the
855 C++ built-in types is therefore to specify it as a string, like this:
858 cl_I order_of_rubiks_cube_group = "43252003274489856000";
860 Note that this conversion is done at runtime, not at compile-time.
862 Conversions from @code{cl_I} to the C built-in types @samp{int},
863 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
867 @item int cl_I_to_int (const cl_I& x)
868 @cindex @code{cl_I_to_int ()}
869 @itemx unsigned int cl_I_to_uint (const cl_I& x)
870 @cindex @code{cl_I_to_uint ()}
871 @itemx long cl_I_to_long (const cl_I& x)
872 @cindex @code{cl_I_to_long ()}
873 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
874 @cindex @code{cl_I_to_ulong ()}
875 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
876 representable in the range of @var{ctype}, a runtime error occurs.
879 Conversions from the classes @code{cl_I}, @code{cl_RA},
880 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
882 to the C built-in types @samp{float} and @samp{double} are provided through
886 @item float float_approx (const @var{type}& x)
887 @cindex @code{float_approx ()}
888 @itemx double double_approx (const @var{type}& x)
889 @cindex @code{double_approx ()}
890 Returns an approximation of @code{x} of C type @var{ctype}.
891 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
892 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
895 Conversions from any class to any of its subclasses (``derived classes'' in
896 C++ terminology) are not provided. Instead, you can assert and check
897 that a value belongs to a certain subclass, and return it as element of that
898 class, using the @samp{As} and @samp{The} macros.
900 @cindex @code{As()()}
901 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
902 @var{type} and returns it as such.
903 @cindex @code{The()()}
904 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
905 @var{type} and returns it as such. It is your responsibility to ensure
906 that this assumption is valid. Since macros and namespaces don't go
907 together well, there is an equivalent to @samp{The}: the template
915 if (!(x >= 0)) abort();
916 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
917 // In general, it would be a rational number.
918 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
923 @node Functions on numbers
924 @chapter Functions on numbers
926 Each of the number classes declares its mathematical operations in the
927 corresponding include file. For example, if your code operates with
928 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
932 * Constructing numbers::
933 * Elementary functions::
934 * Elementary rational functions::
935 * Elementary complex functions::
937 * Rounding functions::
939 * Transcendental functions::
940 * Functions on integers::
941 * Functions on floating-point numbers::
942 * Conversion functions::
943 * Random number generators::
944 * Modifying operators::
947 @node Constructing numbers
948 @section Constructing numbers
950 Here is how to create number objects ``from nothing''.
954 * Constructing integers::
955 * Constructing rational numbers::
956 * Constructing floating-point numbers::
957 * Constructing complex numbers::
960 @node Constructing integers
961 @subsection Constructing integers
963 @code{cl_I} objects are most easily constructed from C integers and from
964 strings. See @ref{Conversions}.
967 @node Constructing rational numbers
968 @subsection Constructing rational numbers
970 @code{cl_RA} objects can be constructed from strings. The syntax
971 for rational numbers is described in @ref{Internal and printed representation}.
972 Another standard way to produce a rational number is through application
973 of @samp{operator /} or @samp{recip} on integers.
976 @node Constructing floating-point numbers
977 @subsection Constructing floating-point numbers
979 @code{cl_F} objects with low precision are most easily constructed from
980 C @samp{float} and @samp{double}. See @ref{Conversions}.
982 To construct a @code{cl_F} with high precision, you can use the conversion
983 from @samp{const char *}, but you have to specify the desired precision
984 within the string. (See @ref{Internal and printed representation}.)
987 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
989 will set @samp{e} to the given value, with a precision of 40 decimal digits.
991 The programmatic way to construct a @code{cl_F} with high precision is
992 through the @code{cl_float} conversion function, see
993 @ref{Conversion to floating-point numbers}. For example, to compute
994 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
995 and then apply the exponential function:
997 float_format_t precision = float_format(40);
998 cl_F e = exp(cl_float(1,precision));
1002 @node Constructing complex numbers
1003 @subsection Constructing complex numbers
1005 Non-real @code{cl_N} objects are normally constructed through the function
1007 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
1009 See @ref{Elementary complex functions}.
1012 @node Elementary functions
1013 @section Elementary functions
1015 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1016 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1017 defines the following operations:
1020 @item @var{type} operator + (const @var{type}&, const @var{type}&)
1021 @cindex @code{operator + ()}
1024 @item @var{type} operator - (const @var{type}&, const @var{type}&)
1025 @cindex @code{operator - ()}
1028 @item @var{type} operator - (const @var{type}&)
1029 Returns the negative of the argument.
1031 @item @var{type} plus1 (const @var{type}& x)
1032 @cindex @code{plus1 ()}
1033 Returns @code{x + 1}.
1035 @item @var{type} minus1 (const @var{type}& x)
1036 @cindex @code{minus1 ()}
1037 Returns @code{x - 1}.
1039 @item @var{type} operator * (const @var{type}&, const @var{type}&)
1040 @cindex @code{operator * ()}
1043 @item @var{type} square (const @var{type}& x)
1044 @cindex @code{square ()}
1045 Returns @code{x * x}.
1048 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
1049 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1050 defines the following operations:
1053 @item @var{type} operator / (const @var{type}&, const @var{type}&)
1054 @cindex @code{operator / ()}
1057 @item @var{type} recip (const @var{type}&)
1058 @cindex @code{recip ()}
1059 Returns the reciprocal of the argument.
1062 The class @code{cl_I} doesn't define a @samp{/} operation because
1063 in the C/C++ language this operator, applied to integral types,
1064 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
1065 is implementation dependent). (@xref{Rounding functions}.)
1066 Instead, @code{cl_I} defines an ``exact quotient'' function:
1069 @item cl_I exquo (const cl_I& x, const cl_I& y)
1070 @cindex @code{exquo ()}
1071 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
1074 The following exponentiation functions are defined:
1077 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
1078 @cindex @code{expt_pos ()}
1079 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
1080 @code{y} must be > 0. Returns @code{x^y}.
1082 @item cl_RA expt (const cl_RA& x, const cl_I& y)
1083 @cindex @code{expt ()}
1084 @itemx cl_R expt (const cl_R& x, const cl_I& y)
1085 @itemx cl_N expt (const cl_N& x, const cl_I& y)
1089 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1090 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1091 defines the following operation:
1094 @item @var{type} abs (const @var{type}& x)
1095 @cindex @code{abs ()}
1096 Returns the absolute value of @code{x}.
1097 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
1100 The class @code{cl_N} implements this as follows:
1103 @item cl_R abs (const cl_N x)
1104 Returns the absolute value of @code{x}.
1107 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1108 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1109 defines the following operation:
1112 @item @var{type} signum (const @var{type}& x)
1113 @cindex @code{signum ()}
1114 Returns the sign of @code{x}, in the same number format as @code{x}.
1115 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
1116 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
1121 @node Elementary rational functions
1122 @section Elementary rational functions
1124 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
1127 @item cl_I numerator (const @var{type}& x)
1128 @cindex @code{numerator ()}
1129 Returns the numerator of @code{x}.
1131 @item cl_I denominator (const @var{type}& x)
1132 @cindex @code{denominator ()}
1133 Returns the denominator of @code{x}.
1136 The numerator and denominator of a rational number are normalized in such
1137 a way that they have no factor in common and the denominator is positive.
1140 @node Elementary complex functions
1141 @section Elementary complex functions
1143 The class @code{cl_N} defines the following operation:
1146 @item cl_N complex (const cl_R& a, const cl_R& b)
1147 @cindex @code{complex ()}
1148 Returns the complex number @code{a+bi}, that is, the complex number with
1149 real part @code{a} and imaginary part @code{b}.
1152 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1155 @item cl_R realpart (const @var{type}& x)
1156 @cindex @code{realpart ()}
1157 Returns the real part of @code{x}.
1159 @item cl_R imagpart (const @var{type}& x)
1160 @cindex @code{imagpart ()}
1161 Returns the imaginary part of @code{x}.
1163 @item @var{type} conjugate (const @var{type}& x)
1164 @cindex @code{conjugate ()}
1165 Returns the complex conjugate of @code{x}.
1168 We have the relations
1172 @code{x = complex(realpart(x), imagpart(x))}
1174 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1179 @section Comparisons
1182 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1183 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1184 defines the following operations:
1187 @item bool operator == (const @var{type}&, const @var{type}&)
1188 @cindex @code{operator == ()}
1189 @itemx bool operator != (const @var{type}&, const @var{type}&)
1190 @cindex @code{operator != ()}
1191 Comparison, as in C and C++.
1193 @item uint32 equal_hashcode (const @var{type}&)
1194 @cindex @code{equal_hashcode ()}
1195 Returns a 32-bit hash code that is the same for any two numbers which are
1196 the same according to @code{==}. This hash code depends on the number's value,
1197 not its type or precision.
1199 @item bool zerop (const @var{type}& x)
1200 @cindex @code{zerop ()}
1201 Compare against zero: @code{x == 0}
1204 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1205 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1206 defines the following operations:
1209 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1210 @cindex @code{compare ()}
1211 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1212 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1214 @item bool operator <= (const @var{type}&, const @var{type}&)
1215 @cindex @code{operator <= ()}
1216 @itemx bool operator < (const @var{type}&, const @var{type}&)
1217 @cindex @code{operator < ()}
1218 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1219 @cindex @code{operator >= ()}
1220 @itemx bool operator > (const @var{type}&, const @var{type}&)
1221 @cindex @code{operator > ()}
1222 Comparison, as in C and C++.
1224 @item bool minusp (const @var{type}& x)
1225 @cindex @code{minusp ()}
1226 Compare against zero: @code{x < 0}
1228 @item bool plusp (const @var{type}& x)
1229 @cindex @code{plusp ()}
1230 Compare against zero: @code{x > 0}
1232 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1233 @cindex @code{max ()}
1234 Return the maximum of @code{x} and @code{y}.
1236 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1237 @cindex @code{min ()}
1238 Return the minimum of @code{x} and @code{y}.
1241 When a floating point number and a rational number are compared, the float
1242 is first converted to a rational number using the function @code{rational}.
1243 Since a floating point number actually represents an interval of real numbers,
1244 the result might be surprising.
1245 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1246 there is no floating point number whose value is exactly @code{1/3}.
1249 @node Rounding functions
1250 @section Rounding functions
1253 When a real number is to be converted to an integer, there is no ``best''
1254 rounding. The desired rounding function depends on the application.
1255 The Common Lisp and ISO Lisp standards offer four rounding functions:
1259 This is the largest integer <=@code{x}.
1262 This is the smallest integer >=@code{x}.
1265 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1268 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1269 integers, choose the even one.
1272 These functions have different advantages:
1274 @code{floor} and @code{ceiling} are translation invariant:
1275 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1276 for every @code{x} and every integer @code{n}.
1278 On the other hand, @code{truncate} and @code{round} are symmetric:
1279 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1280 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1281 down exactly as often as it rounds up.
1283 The functions are related like this:
1287 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1288 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1290 @code{truncate(x) = sign(x) * floor(abs(x))}
1293 Each of the classes @code{cl_R}, @code{cl_RA},
1294 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1295 defines the following operations:
1298 @item cl_I floor1 (const @var{type}& x)
1299 @cindex @code{floor1 ()}
1300 Returns @code{floor(x)}.
1301 @item cl_I ceiling1 (const @var{type}& x)
1302 @cindex @code{ceiling1 ()}
1303 Returns @code{ceiling(x)}.
1304 @item cl_I truncate1 (const @var{type}& x)
1305 @cindex @code{truncate1 ()}
1306 Returns @code{truncate(x)}.
1307 @item cl_I round1 (const @var{type}& x)
1308 @cindex @code{round1 ()}
1309 Returns @code{round(x)}.
1312 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1313 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1314 defines the following operations:
1317 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1318 Returns @code{floor(x/y)}.
1319 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1320 Returns @code{ceiling(x/y)}.
1321 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1322 Returns @code{truncate(x/y)}.
1323 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1324 Returns @code{round(x/y)}.
1327 These functions are called @samp{floor1}, @dots{} here instead of
1328 @samp{floor}, @dots{}, because on some systems, system dependent include
1329 files define @samp{floor} and @samp{ceiling} as macros.
1331 In many cases, one needs both the quotient and the remainder of a division.
1332 It is more efficient to compute both at the same time than to perform
1333 two divisions, one for quotient and the next one for the remainder.
1334 The following functions therefore return a structure containing both
1335 the quotient and the remainder. The suffix @samp{2} indicates the number
1336 of ``return values''. The remainder is defined as follows:
1340 for the computation of @code{quotient = floor(x)},
1341 @code{remainder = x - quotient},
1343 for the computation of @code{quotient = floor(x,y)},
1344 @code{remainder = x - quotient*y},
1347 and similarly for the other three operations.
1349 Each of the classes @code{cl_R}, @code{cl_RA},
1350 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1351 defines the following operations:
1354 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1355 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1356 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1357 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1358 @itemx @var{type}_div_t round2 (const @var{type}& x)
1361 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1362 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1363 defines the following operations:
1366 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1367 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1368 @cindex @code{floor2 ()}
1369 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1370 @cindex @code{ceiling2 ()}
1371 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1372 @cindex @code{truncate2 ()}
1373 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1374 @cindex @code{round2 ()}
1377 Sometimes, one wants the quotient as a floating-point number (of the
1378 same format as the argument, if the argument is a float) instead of as
1379 an integer. The prefix @samp{f} indicates this.
1382 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1383 defines the following operations:
1386 @item @var{type} ffloor (const @var{type}& x)
1387 @cindex @code{ffloor ()}
1388 @itemx @var{type} fceiling (const @var{type}& x)
1389 @cindex @code{fceiling ()}
1390 @itemx @var{type} ftruncate (const @var{type}& x)
1391 @cindex @code{ftruncate ()}
1392 @itemx @var{type} fround (const @var{type}& x)
1393 @cindex @code{fround ()}
1396 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1398 The class @code{cl_R} defines the following operations:
1401 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1402 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1403 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1404 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1407 These functions also exist in versions which return both the quotient
1408 and the remainder. The suffix @samp{2} indicates this.
1411 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1412 defines the following operations:
1413 @cindex @code{cl_F_fdiv_t}
1414 @cindex @code{cl_SF_fdiv_t}
1415 @cindex @code{cl_FF_fdiv_t}
1416 @cindex @code{cl_DF_fdiv_t}
1417 @cindex @code{cl_LF_fdiv_t}
1420 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1421 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1422 @cindex @code{ffloor2 ()}
1423 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1424 @cindex @code{fceiling2 ()}
1425 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1426 @cindex @code{ftruncate2 ()}
1427 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1428 @cindex @code{fround2 ()}
1430 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1431 @cindex @code{cl_R_fdiv_t}
1433 The class @code{cl_R} defines the following operations:
1436 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1437 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1438 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1439 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1440 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1443 Other applications need only the remainder of a division.
1444 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1445 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1446 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1450 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1452 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1455 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1456 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1457 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1459 The classes @code{cl_R}, @code{cl_I} define the following operations:
1462 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1463 @cindex @code{mod ()}
1464 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1465 @cindex @code{rem ()}
1472 Each of the classes @code{cl_R},
1473 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1474 defines the following operation:
1477 @item @var{type} sqrt (const @var{type}& x)
1478 @cindex @code{sqrt ()}
1479 @code{x} must be >= 0. This function returns the square root of @code{x},
1480 normalized to be >= 0. If @code{x} is the square of a rational number,
1481 @code{sqrt(x)} will be a rational number, else it will return a
1482 floating-point approximation.
1485 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1488 @item bool sqrtp (const @var{type}& x, @var{type}* root)
1489 @cindex @code{sqrtp ()}
1490 This tests whether @code{x} is a perfect square. If so, it returns true
1491 and the exact square root in @code{*root}, else it returns false.
1494 Furthermore, for integers, similarly:
1497 @item bool isqrt (const @var{type}& x, @var{type}* root)
1498 @cindex @code{isqrt ()}
1499 @code{x} should be >= 0. This function sets @code{*root} to
1500 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1501 the boolean value @code{(expt(*root,2) == x)}.
1504 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1505 define the following operation:
1508 @item bool rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1509 @cindex @code{rootp ()}
1510 @code{x} must be >= 0. @code{n} must be > 0.
1511 This tests whether @code{x} is an @code{n}th power of a rational number.
1512 If so, it returns true and the exact root in @code{*root}, else it returns
1516 The only square root function which accepts negative numbers is the one
1517 for class @code{cl_N}:
1520 @item cl_N sqrt (const cl_N& z)
1521 @cindex @code{sqrt ()}
1522 Returns the square root of @code{z}, as defined by the formula
1523 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1524 or to a complex number are done if necessary. The range of the result is the
1525 right half plane @code{realpart(sqrt(z)) >= 0}
1526 including the positive imaginary axis and 0, but excluding
1527 the negative imaginary axis.
1528 The result is an exact number only if @code{z} is an exact number.
1532 @node Transcendental functions
1533 @section Transcendental functions
1534 @cindex transcendental functions
1536 The transcendental functions return an exact result if the argument
1537 is exact and the result is exact as well. Otherwise they must return
1538 inexact numbers even if the argument is exact.
1539 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1543 * Exponential and logarithmic functions::
1544 * Trigonometric functions::
1545 * Hyperbolic functions::
1550 @node Exponential and logarithmic functions
1551 @subsection Exponential and logarithmic functions
1554 @item cl_R exp (const cl_R& x)
1555 @cindex @code{exp ()}
1556 @itemx cl_N exp (const cl_N& x)
1557 Returns the exponential function of @code{x}. This is @code{e^x} where
1558 @code{e} is the base of the natural logarithms. The range of the result
1559 is the entire complex plane excluding 0.
1561 @item cl_R ln (const cl_R& x)
1562 @cindex @code{ln ()}
1563 @code{x} must be > 0. Returns the (natural) logarithm of x.
1565 @item cl_N log (const cl_N& x)
1566 @cindex @code{log ()}
1567 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1568 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1569 The range of the result is the strip in the complex plane
1570 @code{-pi < imagpart(log(x)) <= pi}.
1572 @item cl_R phase (const cl_N& x)
1573 @cindex @code{phase ()}
1574 Returns the angle part of @code{x} in its polar representation as a
1575 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1576 This is also the imaginary part of @code{log(x)}.
1577 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1578 The result will be an exact number only if @code{zerop(x)} or
1579 if @code{x} is real and positive.
1581 @item cl_R log (const cl_R& a, const cl_R& b)
1582 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1583 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1584 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1587 @item cl_N log (const cl_N& a, const cl_N& b)
1588 Returns the logarithm of @code{a} with respect to base @code{b}.
1589 @code{log(a,b) = log(a)/log(b)}.
1591 @item cl_N expt (const cl_N& x, const cl_N& y)
1592 @cindex @code{expt ()}
1593 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1596 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1599 @item cl_F exp1 (float_format_t f)
1600 @cindex @code{exp1 ()}
1601 Returns e as a float of format @code{f}.
1603 @item cl_F exp1 (const cl_F& y)
1604 Returns e in the float format of @code{y}.
1606 @item cl_F exp1 (void)
1607 Returns e as a float of format @code{default_float_format}.
1611 @node Trigonometric functions
1612 @subsection Trigonometric functions
1615 @item cl_R sin (const cl_R& x)
1616 @cindex @code{sin ()}
1617 Returns @code{sin(x)}. The range of the result is the interval
1618 @code{-1 <= sin(x) <= 1}.
1620 @item cl_N sin (const cl_N& z)
1621 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1623 @item cl_R cos (const cl_R& x)
1624 @cindex @code{cos ()}
1625 Returns @code{cos(x)}. The range of the result is the interval
1626 @code{-1 <= cos(x) <= 1}.
1628 @item cl_N cos (const cl_N& x)
1629 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1631 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1632 @cindex @code{cos_sin_t}
1633 @itemx cos_sin_t cos_sin (const cl_R& x)
1634 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1635 @cindex @code{cos_sin ()}
1636 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1637 hold only approximately.
1639 @item cl_R tan (const cl_R& x)
1640 @cindex @code{tan ()}
1641 @itemx cl_N tan (const cl_N& x)
1642 Returns @code{tan(x) = sin(x)/cos(x)}.
1644 @item cl_N cis (const cl_R& x)
1645 @cindex @code{cis ()}
1646 @itemx cl_N cis (const cl_N& x)
1647 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1648 @code{e^(i*x) = cos(x) + i*sin(x)}.
1651 @cindex @code{asin ()}
1652 @item cl_N asin (const cl_N& z)
1653 Returns @code{arcsin(z)}. This is defined as
1654 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1655 @code{arcsin(-z) = -arcsin(z)}.
1656 The range of the result is the strip in the complex domain
1657 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1658 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1659 with @code{realpart = pi/2} and @code{imagpart > 0}.
1661 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1665 @item cl_N acos (const cl_N& z)
1666 @cindex @code{acos ()}
1667 Returns @code{arccos(z)}. This is defined as
1668 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1671 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1673 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1674 The range of the result is the strip in the complex domain
1675 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1676 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1677 with @code{realpart = pi} and @code{imagpart > 0}.
1679 Proof: This follows from the results about arcsin.
1683 @cindex @code{atan ()}
1684 @item cl_R atan (const cl_R& x, const cl_R& y)
1685 Returns the angle of the polar representation of the complex number
1686 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1687 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1688 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1689 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1690 with reversed order of arguments.
1692 @item cl_R atan (const cl_R& x)
1693 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1694 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1695 will be an exact number only if @code{x} is the exact @code{0}.
1697 @item cl_N atan (const cl_N& z)
1698 Returns @code{arctan(z)}. This is defined as
1699 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1700 @code{arctan(-z) = -arctan(z)}. The range of the result is
1701 the strip in the complex domain
1702 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1703 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1704 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1706 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1712 @cindex Archimedes' constant
1713 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1716 @item cl_F pi (float_format_t f)
1717 @cindex @code{pi ()}
1718 Returns pi as a float of format @code{f}.
1720 @item cl_F pi (const cl_F& y)
1721 Returns pi in the float format of @code{y}.
1723 @item cl_F pi (void)
1724 Returns pi as a float of format @code{default_float_format}.
1728 @node Hyperbolic functions
1729 @subsection Hyperbolic functions
1732 @item cl_R sinh (const cl_R& x)
1733 @cindex @code{sinh ()}
1734 Returns @code{sinh(x)}.
1736 @item cl_N sinh (const cl_N& z)
1737 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1739 @item cl_R cosh (const cl_R& x)
1740 @cindex @code{cosh ()}
1741 Returns @code{cosh(x)}. The range of the result is the interval
1742 @code{cosh(x) >= 1}.
1744 @item cl_N cosh (const cl_N& z)
1745 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1747 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1748 @cindex @code{cosh_sinh_t}
1749 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1750 @cindex @code{cosh_sinh ()}
1751 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1752 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1753 hold only approximately.
1755 @item cl_R tanh (const cl_R& x)
1756 @cindex @code{tanh ()}
1757 @itemx cl_N tanh (const cl_N& x)
1758 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1760 @item cl_N asinh (const cl_N& z)
1761 @cindex @code{asinh ()}
1762 Returns @code{arsinh(z)}. This is defined as
1763 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1764 @code{arsinh(-z) = -arsinh(z)}.
1766 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1767 Actually, z+sqrt(1+z^2) can never be real and <0, so
1768 -pi < imagpart(arsinh(z)) < pi.
1769 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1770 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1772 The range of the result is the strip in the complex domain
1773 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1774 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1775 with @code{imagpart = pi/2} and @code{realpart < 0}.
1777 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1778 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1779 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1780 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1781 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1782 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1783 If y >= 1, the imagpart is pi/2 and the realpart is
1784 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1787 Moreover, if z is in Range(sqrt),
1788 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1789 (for a proof, see file src/cl_C_asinh.cc).
1792 @item cl_N acosh (const cl_N& z)
1793 @cindex @code{acosh ()}
1794 Returns @code{arcosh(z)}. This is defined as
1795 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1796 The range of the result is the half-strip in the complex domain
1797 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1798 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1800 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1801 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1802 If z is in Range(sqrt), we have
1803 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1804 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1806 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1807 and since the imagpart of both expressions is > -pi, <= pi
1808 ==> arcosh(z) = log(z+sqrt(z^2-1))
1809 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1810 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1811 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1812 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1813 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1815 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1816 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1817 = x^2 + y^2 + sqrt(u^2+v^2)
1822 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1823 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1824 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1825 Otherwise, -z is in Range(sqrt).
1826 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1827 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1828 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1829 and this has realpart > 0.
1830 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1831 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1832 has realpart = 0 and imagpart > 0.
1833 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1834 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1835 This has realpart >= 0 and imagpart = pi.
1838 @item cl_N atanh (const cl_N& z)
1839 @cindex @code{atanh ()}
1840 Returns @code{artanh(z)}. This is defined as
1841 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1842 @code{artanh(-z) = -artanh(z)}. The range of the result is
1843 the strip in the complex domain
1844 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1845 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1846 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1848 Proof: Write z = x+iy. Examine
1849 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1851 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1852 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1853 |x| < 1 ==> imagpart = 0
1856 = (atan(1+x,y) - atan(1-x,-y))/2
1857 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1858 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1859 > (pi - pi/2 - pi/2 )/2 = 0
1860 and (1+x)/y > (1-x)/y
1861 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1862 ==> imagpart < pi/2.
1863 Hence 0 < imagpart < pi/2.
1865 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1871 @subsection Euler gamma
1872 @cindex Euler's constant
1874 Euler's constant C = 0.577@dots{} is returned by the following functions:
1877 @item cl_F eulerconst (float_format_t f)
1878 @cindex @code{eulerconst ()}
1879 Returns Euler's constant as a float of format @code{f}.
1881 @item cl_F eulerconst (const cl_F& y)
1882 Returns Euler's constant in the float format of @code{y}.
1884 @item cl_F eulerconst (void)
1885 Returns Euler's constant as a float of format @code{default_float_format}.
1888 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1889 @cindex Catalan's constant
1892 @item cl_F catalanconst (float_format_t f)
1893 @cindex @code{catalanconst ()}
1894 Returns Catalan's constant as a float of format @code{f}.
1896 @item cl_F catalanconst (const cl_F& y)
1897 Returns Catalan's constant in the float format of @code{y}.
1899 @item cl_F catalanconst (void)
1900 Returns Catalan's constant as a float of format @code{default_float_format}.
1905 @subsection Riemann zeta
1906 @cindex Riemann's zeta
1908 Riemann's zeta function at an integral point @code{s>1} is returned by the
1909 following functions:
1912 @item cl_F zeta (int s, float_format_t f)
1913 @cindex @code{zeta ()}
1914 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1916 @item cl_F zeta (int s, const cl_F& y)
1917 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1919 @item cl_F zeta (int s)
1920 Returns Riemann's zeta function at @code{s} as a float of format
1921 @code{default_float_format}.
1925 @node Functions on integers
1926 @section Functions on integers
1929 * Logical functions::
1930 * Number theoretic functions::
1931 * Combinatorial functions::
1934 @node Logical functions
1935 @subsection Logical functions
1937 Integers, when viewed as in two's complement notation, can be thought as
1938 infinite bit strings where the bits' values eventually are constant.
1945 The logical operations view integers as such bit strings and operate
1946 on each of the bit positions in parallel.
1949 @item cl_I lognot (const cl_I& x)
1950 @cindex @code{lognot ()}
1951 @itemx cl_I operator ~ (const cl_I& x)
1952 @cindex @code{operator ~ ()}
1953 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1955 @item cl_I logand (const cl_I& x, const cl_I& y)
1956 @cindex @code{logand ()}
1957 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1958 @cindex @code{operator & ()}
1959 Logical and, like @code{x & y} in C.
1961 @item cl_I logior (const cl_I& x, const cl_I& y)
1962 @cindex @code{logior ()}
1963 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1964 @cindex @code{operator | ()}
1965 Logical (inclusive) or, like @code{x | y} in C.
1967 @item cl_I logxor (const cl_I& x, const cl_I& y)
1968 @cindex @code{logxor ()}
1969 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1970 @cindex @code{operator ^ ()}
1971 Exclusive or, like @code{x ^ y} in C.
1973 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1974 @cindex @code{logeqv ()}
1975 Bitwise equivalence, like @code{~(x ^ y)} in C.
1977 @item cl_I lognand (const cl_I& x, const cl_I& y)
1978 @cindex @code{lognand ()}
1979 Bitwise not and, like @code{~(x & y)} in C.
1981 @item cl_I lognor (const cl_I& x, const cl_I& y)
1982 @cindex @code{lognor ()}
1983 Bitwise not or, like @code{~(x | y)} in C.
1985 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1986 @cindex @code{logandc1 ()}
1987 Logical and, complementing the first argument, like @code{~x & y} in C.
1989 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1990 @cindex @code{logandc2 ()}
1991 Logical and, complementing the second argument, like @code{x & ~y} in C.
1993 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1994 @cindex @code{logorc1 ()}
1995 Logical or, complementing the first argument, like @code{~x | y} in C.
1997 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1998 @cindex @code{logorc2 ()}
1999 Logical or, complementing the second argument, like @code{x | ~y} in C.
2002 These operations are all available though the function
2004 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
2005 @cindex @code{boole ()}
2007 where @code{op} must have one of the 16 values (each one stands for a function
2008 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
2009 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
2010 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
2011 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
2012 @code{boole_orc1}, @code{boole_orc2}.
2013 @cindex @code{boole_clr}
2014 @cindex @code{boole_set}
2015 @cindex @code{boole_1}
2016 @cindex @code{boole_2}
2017 @cindex @code{boole_c1}
2018 @cindex @code{boole_c2}
2019 @cindex @code{boole_and}
2020 @cindex @code{boole_xor}
2021 @cindex @code{boole_eqv}
2022 @cindex @code{boole_nand}
2023 @cindex @code{boole_nor}
2024 @cindex @code{boole_andc1}
2025 @cindex @code{boole_andc2}
2026 @cindex @code{boole_orc1}
2027 @cindex @code{boole_orc2}
2030 Other functions that view integers as bit strings:
2033 @item bool logtest (const cl_I& x, const cl_I& y)
2034 @cindex @code{logtest ()}
2035 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
2036 @code{logand(x,y) != 0}.
2038 @item bool logbitp (const cl_I& n, const cl_I& x)
2039 @cindex @code{logbitp ()}
2040 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
2041 Bit 0 is the least significant bit.
2043 @item uintC logcount (const cl_I& x)
2044 @cindex @code{logcount ()}
2045 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
2046 the number of zero bits in @code{x}, if @code{x} < 0.
2049 The following functions operate on intervals of bits in integers.
2052 struct cl_byte @{ uintC size; uintC position; @};
2054 @cindex @code{cl_byte}
2055 represents the bit interval containing the bits
2056 @code{position}@dots{}@code{position+size-1} of an integer.
2057 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
2060 @item cl_I ldb (const cl_I& n, const cl_byte& b)
2061 @cindex @code{ldb ()}
2062 extracts the bits of @code{n} described by the bit interval @code{b}
2063 and returns them as a nonnegative integer with @code{b.size} bits.
2065 @item bool ldb_test (const cl_I& n, const cl_byte& b)
2066 @cindex @code{ldb_test ()}
2067 Returns true if some bit described by the bit interval @code{b} is set in
2070 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2071 @cindex @code{dpb ()}
2072 Returns @code{n}, with the bits described by the bit interval @code{b}
2073 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
2074 @code{newbyte} are relevant.
2077 The functions @code{ldb} and @code{dpb} implicitly shift. The following
2078 functions are their counterparts without shifting:
2081 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
2082 @cindex @code{mask_field ()}
2083 returns an integer with the bits described by the bit interval @code{b}
2084 copied from the corresponding bits in @code{n}, the other bits zero.
2086 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2087 @cindex @code{deposit_field ()}
2088 returns an integer where the bits described by the bit interval @code{b}
2089 come from @code{newbyte} and the other bits come from @code{n}.
2092 The following relations hold:
2096 @code{ldb (n, b) = mask_field(n, b) >> b.position},
2098 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
2100 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
2103 The following operations on integers as bit strings are efficient shortcuts
2104 for common arithmetic operations:
2107 @item bool oddp (const cl_I& x)
2108 @cindex @code{oddp ()}
2109 Returns true if the least significant bit of @code{x} is 1. Equivalent to
2110 @code{mod(x,2) != 0}.
2112 @item bool evenp (const cl_I& x)
2113 @cindex @code{evenp ()}
2114 Returns true if the least significant bit of @code{x} is 0. Equivalent to
2115 @code{mod(x,2) == 0}.
2117 @item cl_I operator << (const cl_I& x, const cl_I& n)
2118 @cindex @code{operator << ()}
2119 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
2120 Equivalent to @code{x * expt(2,n)}.
2122 @item cl_I operator >> (const cl_I& x, const cl_I& n)
2123 @cindex @code{operator >> ()}
2124 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
2125 Bits shifted out to the right are thrown away.
2126 Equivalent to @code{floor(x / expt(2,n))}.
2128 @item cl_I ash (const cl_I& x, const cl_I& y)
2129 @cindex @code{ash ()}
2130 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
2131 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
2132 returns @code{floor(x * expt(2,y))}.
2134 @item uintC integer_length (const cl_I& x)
2135 @cindex @code{integer_length ()}
2136 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
2137 in two's complement notation. This is the smallest n >= 0 such that
2138 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
2141 @item uintC ord2 (const cl_I& x)
2142 @cindex @code{ord2 ()}
2143 @code{x} must be non-zero. This function returns the number of 0 bits at the
2144 right of @code{x} in two's complement notation. This is the largest n >= 0
2145 such that 2^n divides @code{x}.
2147 @item uintC power2p (const cl_I& x)
2148 @cindex @code{power2p ()}
2149 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
2150 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
2151 (See also the function @code{logp}.)
2155 @node Number theoretic functions
2156 @subsection Number theoretic functions
2159 @item uint32 gcd (unsigned long a, unsigned long b)
2160 @cindex @code{gcd ()}
2161 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
2162 This function returns the greatest common divisor of @code{a} and @code{b},
2163 normalized to be >= 0.
2165 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
2166 @cindex @code{xgcd ()}
2167 This function (``extended gcd'') returns the greatest common divisor @code{g} of
2168 @code{a} and @code{b} and at the same time the representation of @code{g}
2169 as an integral linear combination of @code{a} and @code{b}:
2170 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
2171 @code{u} and @code{v} will be normalized to be of smallest possible absolute
2172 value, in the following sense: If @code{a} and @code{b} are non-zero, and
2173 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
2174 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
2176 @item cl_I lcm (const cl_I& a, const cl_I& b)
2177 @cindex @code{lcm ()}
2178 This function returns the least common multiple of @code{a} and @code{b},
2179 normalized to be >= 0.
2181 @item bool logp (const cl_I& a, const cl_I& b, cl_RA* l)
2182 @cindex @code{logp ()}
2183 @itemx bool logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2184 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2185 rational number, this function returns true and sets *l = log(a,b), else
2188 @item int jacobi (signed long a, signed long b)
2189 @cindex @code{jacobi()}
2190 @itemx int jacobi (const cl_I& a, const cl_I& b)
2191 Returns the Jacobi symbol
2193 $\left({a\over b}\right)$,
2198 @code{a,b} must be integers, @code{b>0} and odd. The result is 0
2201 @item bool isprobprime (const cl_I& n)
2203 @cindex @code{isprobprime()}
2204 Returns true if @code{n} is a small prime or passes the Miller-Rabin
2205 primality test. The probability of a false positive is 1:10^30.
2207 @item cl_I nextprobprime (const cl_R& x)
2208 @cindex @code{nextprobprime()}
2209 Returns the smallest probable prime >=@code{x}.
2213 @node Combinatorial functions
2214 @subsection Combinatorial functions
2217 @item cl_I factorial (uintL n)
2218 @cindex @code{factorial ()}
2219 @code{n} must be a small integer >= 0. This function returns the factorial
2220 @code{n}! = @code{1*2*@dots{}*n}.
2222 @item cl_I doublefactorial (uintL n)
2223 @cindex @code{doublefactorial ()}
2224 @code{n} must be a small integer >= 0. This function returns the
2225 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2226 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2228 @item cl_I binomial (uintL n, uintL k)
2229 @cindex @code{binomial ()}
2230 @code{n} and @code{k} must be small integers >= 0. This function returns the
2231 binomial coefficient
2233 ${n \choose k} = {n! \over k! (n-k)!}$
2236 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2238 for 0 <= k <= n, 0 else.
2242 @node Functions on floating-point numbers
2243 @section Functions on floating-point numbers
2245 Recall that a floating-point number consists of a sign @code{s}, an
2246 exponent @code{e} and a mantissa @code{m}. The value of the number is
2247 @code{(-1)^s * 2^e * m}.
2250 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2251 defines the following operations.
2254 @item @var{type} scale_float (const @var{type}& x, sintC delta)
2255 @cindex @code{scale_float ()}
2256 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2257 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2258 because it copies @code{x} and modifies the exponent.
2261 The following functions provide an abstract interface to the underlying
2262 representation of floating-point numbers.
2265 @item sintE float_exponent (const @var{type}& x)
2266 @cindex @code{float_exponent ()}
2267 Returns the exponent @code{e} of @code{x}.
2268 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2269 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2271 @item sintL float_radix (const @var{type}& x)
2272 @cindex @code{float_radix ()}
2273 Returns the base of the floating-point representation. This is always @code{2}.
2275 @item @var{type} float_sign (const @var{type}& x)
2276 @cindex @code{float_sign ()}
2277 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2278 @code{x} >= 0, -1 for @code{x} < 0.
2280 @item uintC float_digits (const @var{type}& x)
2281 @cindex @code{float_digits ()}
2282 Returns the number of mantissa bits in the floating-point representation
2283 of @code{x}, including the hidden bit. The value only depends on the type
2284 of @code{x}, not on its value.
2286 @item uintC float_precision (const @var{type}& x)
2287 @cindex @code{float_precision ()}
2288 Returns the number of significant mantissa bits in the floating-point
2289 representation of @code{x}. Since denormalized numbers are not supported,
2290 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2294 The complete internal representation of a float is encoded in the type
2295 @cindex @code{decoded_float}
2296 @cindex @code{decoded_sfloat}
2297 @cindex @code{decoded_ffloat}
2298 @cindex @code{decoded_dfloat}
2299 @cindex @code{decoded_lfloat}
2300 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2301 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2303 struct decoded_@var{type}float @{
2304 @var{type} mantissa; cl_I exponent; @var{type} sign;
2308 and returned by the function
2311 @item decoded_@var{type}float decode_float (const @var{type}& x)
2312 @cindex @code{decode_float ()}
2313 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2314 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2315 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2316 @code{e} is the same as returned by the function @code{float_exponent}.
2319 A complete decoding in terms of integers is provided as type
2320 @cindex @code{cl_idecoded_float}
2322 struct cl_idecoded_float @{
2323 cl_I mantissa; cl_I exponent; cl_I sign;
2326 by the following function:
2329 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2330 @cindex @code{integer_decode_float ()}
2331 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2332 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2333 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2334 WARNING: The exponent @code{e} is not the same as the one returned by
2335 the functions @code{decode_float} and @code{float_exponent}.
2338 Some other function, implemented only for class @code{cl_F}:
2341 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2342 @cindex @code{float_sign ()}
2343 This returns a floating point number whose precision and absolute value
2344 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2345 zero, it is treated as positive. Same for @code{y}.
2349 @node Conversion functions
2350 @section Conversion functions
2354 * Conversion to floating-point numbers::
2355 * Conversion to rational numbers::
2358 @node Conversion to floating-point numbers
2359 @subsection Conversion to floating-point numbers
2361 The type @code{float_format_t} describes a floating-point format.
2362 @cindex @code{float_format_t}
2365 @item float_format_t float_format (uintE n)
2366 @cindex @code{float_format ()}
2367 Returns the smallest float format which guarantees at least @code{n}
2368 decimal digits in the mantissa (after the decimal point).
2370 @item float_format_t float_format (const cl_F& x)
2371 Returns the floating point format of @code{x}.
2373 @item float_format_t default_float_format
2374 @cindex @code{default_float_format}
2375 Global variable: the default float format used when converting rational numbers
2379 To convert a real number to a float, each of the types
2380 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2381 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2382 defines the following operations:
2385 @item cl_F cl_float (const @var{type}&x, float_format_t f)
2386 @cindex @code{cl_float ()}
2387 Returns @code{x} as a float of format @code{f}.
2388 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2389 Returns @code{x} in the float format of @code{y}.
2390 @item cl_F cl_float (const @var{type}&x)
2391 Returns @code{x} as a float of format @code{default_float_format} if
2392 it is an exact number, or @code{x} itself if it is already a float.
2395 Of course, converting a number to a float can lose precision.
2397 Every floating-point format has some characteristic numbers:
2400 @item cl_F most_positive_float (float_format_t f)
2401 @cindex @code{most_positive_float ()}
2402 Returns the largest (most positive) floating point number in float format @code{f}.
2404 @item cl_F most_negative_float (float_format_t f)
2405 @cindex @code{most_negative_float ()}
2406 Returns the smallest (most negative) floating point number in float format @code{f}.
2408 @item cl_F least_positive_float (float_format_t f)
2409 @cindex @code{least_positive_float ()}
2410 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2411 in float format @code{f}.
2413 @item cl_F least_negative_float (float_format_t f)
2414 @cindex @code{least_negative_float ()}
2415 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2416 in float format @code{f}.
2418 @item cl_F float_epsilon (float_format_t f)
2419 @cindex @code{float_epsilon ()}
2420 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2422 @item cl_F float_negative_epsilon (float_format_t f)
2423 @cindex @code{float_negative_epsilon ()}
2424 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2428 @node Conversion to rational numbers
2429 @subsection Conversion to rational numbers
2431 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2432 defines the following operation:
2435 @item cl_RA rational (const @var{type}& x)
2436 @cindex @code{rational ()}
2437 Returns the value of @code{x} as an exact number. If @code{x} is already
2438 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2439 the value is a rational number whose denominator is a power of 2.
2442 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2446 @item cl_RA rationalize (const cl_R& x)
2447 @cindex @code{rationalize ()}
2448 If @code{x} is a floating-point number, it actually represents an interval
2449 of real numbers, and this function returns the rational number with
2450 smallest denominator (and smallest numerator, in magnitude)
2451 which lies in this interval.
2452 If @code{x} is already an exact number, this function returns @code{x}.
2455 If @code{x} is any float, one has
2459 @code{cl_float(rational(x),x) = x}
2461 @code{cl_float(rationalize(x),x) = x}
2465 @node Random number generators
2466 @section Random number generators
2469 A random generator is a machine which produces (pseudo-)random numbers.
2470 The include file @code{<cln/random.h>} defines a class @code{random_state}
2471 which contains the state of a random generator. If you make a copy
2472 of the random number generator, the original one and the copy will produce
2473 the same sequence of random numbers.
2475 The following functions return (pseudo-)random numbers in different formats.
2476 Calling one of these modifies the state of the random number generator in
2477 a complicated but deterministic way.
2480 @cindex @code{random_state}
2481 @cindex @code{default_random_state}
2483 random_state default_random_state
2485 contains a default random number generator. It is used when the functions
2486 below are called without @code{random_state} argument.
2489 @item uint32 random32 (random_state& randomstate)
2490 @itemx uint32 random32 ()
2491 @cindex @code{random32 ()}
2492 Returns a random unsigned 32-bit number. All bits are equally random.
2494 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2495 @itemx cl_I random_I (const cl_I& n)
2496 @cindex @code{random_I ()}
2497 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2498 in the range @code{0 <= x < n}.
2500 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2501 @itemx cl_F random_F (const cl_F& n)
2502 @cindex @code{random_F ()}
2503 @code{n} must be a float > 0. This function returns a random floating-point
2504 number of the same format as @code{n} in the range @code{0 <= x < n}.
2506 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2507 @itemx cl_R random_R (const cl_R& n)
2508 @cindex @code{random_R ()}
2509 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2510 if @code{n} is a float.
2514 @node Modifying operators
2515 @section Modifying operators
2516 @cindex modifying operators
2518 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2519 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2522 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2523 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2526 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2527 @cindex @code{operator += ()}
2528 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2529 @cindex @code{operator -= ()}
2530 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2531 @cindex @code{operator *= ()}
2532 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2533 @cindex @code{operator /= ()}
2536 For the class @code{cl_I}:
2539 @item @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 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2543 @cindex @code{operator &= ()}
2544 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2545 @cindex @code{operator |= ()}
2546 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2547 @cindex @code{operator ^= ()}
2548 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2549 @cindex @code{operator <<= ()}
2550 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2551 @cindex @code{operator >>= ()}
2554 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2555 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2558 @item @var{type}& operator ++ (@var{type}& x)
2559 @cindex @code{operator ++ ()}
2560 The prefix operator @code{++x}.
2562 @item void operator ++ (@var{type}& x, int)
2563 The postfix operator @code{x++}.
2565 @item @var{type}& operator -- (@var{type}& x)
2566 @cindex @code{operator -- ()}
2567 The prefix operator @code{--x}.
2569 @item void operator -- (@var{type}& x, int)
2570 The postfix operator @code{x--}.
2573 Note that by using these modifying operators, you don't gain efficiency:
2574 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2579 @chapter Input/Output
2580 @cindex Input/Output
2583 * Internal and printed representation::
2585 * Output functions::
2588 @node Internal and printed representation
2589 @section Internal and printed representation
2590 @cindex representation
2592 All computations deal with the internal representations of the numbers.
2594 Every number has an external representation as a sequence of ASCII characters.
2595 Several external representations may denote the same number, for example,
2596 "20.0" and "20.000".
2598 Converting an internal to an external representation is called ``printing'',
2600 converting an external to an internal representation is called ``reading''.
2602 In CLN, it is always true that conversion of an internal to an external
2603 representation and then back to an internal representation will yield the
2604 same internal representation. Symbolically: @code{read(print(x)) == x}.
2605 This is called ``print-read consistency''.
2607 Different types of numbers have different external representations (case
2612 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2613 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2614 for decimal integers
2615 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2617 @item Rational numbers
2618 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2619 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2622 @item Floating-point numbers
2623 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2624 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2625 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2626 of the form _@var{prec} may be appended. There must be at least
2627 one digit in the non-exponent part. The exponent has the syntax
2628 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2629 The exponent marker is
2633 @samp{s} for short-floats,
2635 @samp{f} for single-floats,
2637 @samp{d} for double-floats,
2639 @samp{L} for long-floats,
2642 or @samp{e}, which denotes a default float format. The precision specifying
2643 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2644 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2645 function @samp{float_format}.
2647 @item Complex numbers
2648 External representation:
2651 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2652 if @var{imagpart} is negative, its printed representation begins with
2653 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2654 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2655 is rational and the rational number's base is >18, because the @samp{i}
2656 is then read as a digit.
2658 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2663 @node Input functions
2664 @section Input functions
2666 Including @code{<cln/io.h>} defines flexible input functions:
2669 @item cl_N read_complex (std::istream& stream, const cl_read_flags& flags)
2670 @itemx cl_R read_real (std::istream& stream, const cl_read_flags& flags)
2671 @itemx cl_F read_float (std::istream& stream, const cl_read_flags& flags)
2672 @itemx cl_RA read_rational (std::istream& stream, const cl_read_flags& flags)
2673 @itemx cl_I read_integer (std::istream& stream, const cl_read_flags& flags)
2674 Reads a number from @code{stream}. The @code{flags} are parameters which
2675 affect the input syntax. Whitespace before the number is silently skipped.
2677 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2678 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2679 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2680 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2681 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2682 Reads a number from a string in memory. The @code{flags} are parameters which
2683 affect the input syntax. The string starts at @code{string} and ends at
2684 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2685 @code{NULL}, denoting the entire string, i.e. equivalent to
2686 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2687 @code{NULL}, the string in memory must contain exactly one number and nothing
2688 more, else an exception will be thrown. If @code{end_of_parse}
2689 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2690 the last parsed character (i.e. @code{string_limit} if nothing came after
2691 the number). Whitespace is not allowed.
2694 The structure @code{cl_read_flags} contains the following fields:
2697 @item cl_read_syntax_t syntax
2698 The possible results of the read operation. Possible values are
2699 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2700 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2701 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2703 @item cl_read_lsyntax_t lsyntax
2704 Specifies the language-dependent syntax variant for the read operation.
2708 @item lsyntax_standard
2709 accept standard algebraic notation only, no complex numbers,
2710 @item lsyntax_algebraic
2711 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2712 @item lsyntax_commonlisp
2713 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2714 hexadecimal numbers,
2715 @code{#@var{base}R} for rational numbers in a given base,
2716 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2718 accept all of these extensions.
2721 @item unsigned int rational_base
2722 The base in which rational numbers are read.
2724 @item float_format_t float_flags.default_float_format
2725 The float format used when reading floats with exponent marker @samp{e}.
2727 @item float_format_t float_flags.default_lfloat_format
2728 The float format used when reading floats with exponent marker @samp{l}.
2730 @item bool float_flags.mantissa_dependent_float_format
2731 When this flag is true, floats specified with more digits than corresponding
2732 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2733 precision corresponding to their number of significant digits.
2737 @node Output functions
2738 @section Output functions
2740 Including @code{<cln/io.h>} defines a number of simple output functions
2741 that write to @code{std::ostream&}:
2744 @item void fprintchar (std::ostream& stream, char c)
2745 Prints the character @code{x} literally on the @code{stream}.
2747 @item void fprint (std::ostream& stream, const char * string)
2748 Prints the @code{string} literally on the @code{stream}.
2750 @item void fprintdecimal (std::ostream& stream, int x)
2751 @itemx void fprintdecimal (std::ostream& stream, const cl_I& x)
2752 Prints the integer @code{x} in decimal on the @code{stream}.
2754 @item void fprintbinary (std::ostream& stream, const cl_I& x)
2755 Prints the integer @code{x} in binary (base 2, without prefix)
2756 on the @code{stream}.
2758 @item void fprintoctal (std::ostream& stream, const cl_I& x)
2759 Prints the integer @code{x} in octal (base 8, without prefix)
2760 on the @code{stream}.
2762 @item void fprinthexadecimal (std::ostream& stream, const cl_I& x)
2763 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2764 on the @code{stream}.
2767 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2768 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2769 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2772 @item void fprint (std::ostream& stream, const @var{type}& x)
2773 @itemx std::ostream& operator<< (std::ostream& stream, const @var{type}& x)
2774 Prints the number @code{x} on the @code{stream}. The output may depend
2775 on the global printer settings in the variable @code{default_print_flags}.
2776 The @code{ostream} flags and settings (flags, width and locale) are
2780 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2783 void print_complex (std::ostream& stream, const cl_print_flags& flags,
2785 void print_real (std::ostream& stream, const cl_print_flags& flags,
2787 void print_float (std::ostream& stream, const cl_print_flags& flags,
2789 void print_rational (std::ostream& stream, const cl_print_flags& flags,
2791 void print_integer (std::ostream& stream, const cl_print_flags& flags,
2794 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2795 parameters which affect the output.
2797 The structure type @code{cl_print_flags} contains the following fields:
2800 @item unsigned int rational_base
2801 The base in which rational numbers are printed. Default is @code{10}.
2803 @item bool rational_readably
2804 If this flag is true, rational numbers are printed with radix specifiers in
2805 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2806 prefixes, trailing dot). Default is false.
2808 @item bool float_readably
2809 If this flag is true, type specific exponent markers have precedence over 'E'.
2812 @item float_format_t default_float_format
2813 Floating point numbers of this format will be printed using the 'E' exponent
2814 marker. Default is @code{float_format_ffloat}.
2816 @item bool complex_readably
2817 If this flag is true, complex numbers will be printed using the Common Lisp
2818 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2820 @item cl_string univpoly_varname
2821 Univariate polynomials with no explicit indeterminate name will be printed
2822 using this variable name. Default is @code{"x"}.
2825 The global variable @code{default_print_flags} contains the default values,
2826 used by the function @code{fprint}.
2832 CLN has a class of abstract rings.
2840 Rings can be compared for equality:
2843 @item bool operator== (const cl_ring&, const cl_ring&)
2844 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2845 These compare two rings for equality.
2848 Given a ring @code{R}, the following members can be used.
2851 @item void R->fprint (std::ostream& stream, const cl_ring_element& x)
2852 @cindex @code{fprint ()}
2853 @itemx bool R->equal (const cl_ring_element& x, const cl_ring_element& y)
2854 @cindex @code{equal ()}
2855 @itemx cl_ring_element R->zero ()
2856 @cindex @code{zero ()}
2857 @itemx bool R->zerop (const cl_ring_element& x)
2858 @cindex @code{zerop ()}
2859 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2860 @cindex @code{plus ()}
2861 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2862 @cindex @code{minus ()}
2863 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2864 @cindex @code{uminus ()}
2865 @itemx cl_ring_element R->one ()
2866 @cindex @code{one ()}
2867 @itemx cl_ring_element R->canonhom (const cl_I& x)
2868 @cindex @code{canonhom ()}
2869 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2870 @cindex @code{mul ()}
2871 @itemx cl_ring_element R->square (const cl_ring_element& x)
2872 @cindex @code{square ()}
2873 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2874 @cindex @code{expt_pos ()}
2877 The following rings are built-in.
2880 @item cl_null_ring cl_0_ring
2881 The null ring, containing only zero.
2883 @item cl_complex_ring cl_C_ring
2884 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2886 @item cl_real_ring cl_R_ring
2887 The ring of real numbers. This corresponds to the type @code{cl_R}.
2889 @item cl_rational_ring cl_RA_ring
2890 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2892 @item cl_integer_ring cl_I_ring
2893 The ring of integers. This corresponds to the type @code{cl_I}.
2896 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2897 @code{cl_RA_ring}, @code{cl_I_ring}:
2900 @item bool instanceof (const cl_number& x, const cl_number_ring& R)
2901 @cindex @code{instanceof ()}
2902 Tests whether the given number is an element of the number ring R.
2906 @node Modular integers
2907 @chapter Modular integers
2908 @cindex modular integer
2911 * Modular integer rings::
2912 * Functions on modular integers::
2915 @node Modular integer rings
2916 @section Modular integer rings
2919 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2920 The modulus is explicitly part of every modular integer. CLN doesn't
2921 allow you to (accidentally) mix elements of different modular rings,
2922 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2923 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2924 doesn't have generic types. So one has to live with runtime checks.)
2926 The class of modular integer rings is
2934 Modular integer ring
2938 @cindex @code{cl_modint_ring}
2940 and the class of all modular integers (elements of modular integer rings) is
2948 Modular integer rings are constructed using the function
2951 @item cl_modint_ring find_modint_ring (const cl_I& N)
2952 @cindex @code{find_modint_ring ()}
2953 This function returns the modular ring @samp{Z/NZ}. It takes care
2954 of finding out about special cases of @code{N}, like powers of two
2955 and odd numbers for which Montgomery multiplication will be a win,
2956 @cindex Montgomery multiplication
2957 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2958 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2959 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2963 Modular integer rings can be compared for equality:
2966 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2967 @cindex @code{operator == ()}
2968 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2969 @cindex @code{operator != ()}
2970 These compare two modular integer rings for equality. Two different calls
2971 to @code{find_modint_ring} with the same argument necessarily return the
2972 same ring because it is memoized in the cache table.
2975 @node Functions on modular integers
2976 @section Functions on modular integers
2978 Given a modular integer ring @code{R}, the following members can be used.
2981 @item cl_I R->modulus
2982 @cindex @code{modulus}
2983 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2985 @item cl_MI R->zero()
2986 @cindex @code{zero ()}
2987 This returns @code{0 mod N}.
2989 @item cl_MI R->one()
2990 @cindex @code{one ()}
2991 This returns @code{1 mod N}.
2993 @item cl_MI R->canonhom (const cl_I& x)
2994 @cindex @code{canonhom ()}
2995 This returns @code{x mod N}.
2997 @item cl_I R->retract (const cl_MI& x)
2998 @cindex @code{retract ()}
2999 This is a partial inverse function to @code{R->canonhom}. It returns the
3000 standard representative (@code{>=0}, @code{<N}) of @code{x}.
3002 @item cl_MI R->random(random_state& randomstate)
3003 @itemx cl_MI R->random()
3004 @cindex @code{random ()}
3005 This returns a random integer modulo @code{N}.
3008 The following operations are defined on modular integers.
3011 @item cl_modint_ring x.ring ()
3012 @cindex @code{ring ()}
3013 Returns the ring to which the modular integer @code{x} belongs.
3015 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
3016 @cindex @code{operator + ()}
3017 Returns the sum of two modular integers. One of the arguments may also
3020 @item cl_MI operator- (const cl_MI&, const cl_MI&)
3021 @cindex @code{operator - ()}
3022 Returns the difference of two modular integers. One of the arguments may also
3025 @item cl_MI operator- (const cl_MI&)
3026 Returns the negative of a modular integer.
3028 @item cl_MI operator* (const cl_MI&, const cl_MI&)
3029 @cindex @code{operator * ()}
3030 Returns the product of two modular integers. One of the arguments may also
3033 @item cl_MI square (const cl_MI&)
3034 @cindex @code{square ()}
3035 Returns the square of a modular integer.
3037 @item cl_MI recip (const cl_MI& x)
3038 @cindex @code{recip ()}
3039 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
3040 must be coprime to the modulus, otherwise an error message is issued.
3042 @item cl_MI div (const cl_MI& x, const cl_MI& y)
3043 @cindex @code{div ()}
3044 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
3045 @code{y} must be coprime to the modulus, otherwise an error message is issued.
3047 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
3048 @cindex @code{expt_pos ()}
3049 @code{y} must be > 0. Returns @code{x^y}.
3051 @item cl_MI expt (const cl_MI& x, const cl_I& y)
3052 @cindex @code{expt ()}
3053 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
3054 modulus, else an error message is issued.
3056 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
3057 @cindex @code{operator << ()}
3058 Returns @code{x*2^y}.
3060 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
3061 @cindex @code{operator >> ()}
3062 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
3063 or an error message is issued.
3065 @item bool operator== (const cl_MI&, const cl_MI&)
3066 @cindex @code{operator == ()}
3067 @itemx bool operator!= (const cl_MI&, const cl_MI&)
3068 @cindex @code{operator != ()}
3069 Compares two modular integers, belonging to the same modular integer ring,
3072 @item bool zerop (const cl_MI& x)
3073 @cindex @code{zerop ()}
3074 Returns true if @code{x} is @code{0 mod N}.
3077 The following output functions are defined (see also the chapter on
3081 @item void fprint (std::ostream& stream, const cl_MI& x)
3082 @cindex @code{fprint ()}
3083 @itemx std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
3084 @cindex @code{operator << ()}
3085 Prints the modular integer @code{x} on the @code{stream}. The output may depend
3086 on the global printer settings in the variable @code{default_print_flags}.
3090 @node Symbolic data types
3091 @chapter Symbolic data types
3092 @cindex symbolic type
3094 CLN implements two symbolic (non-numeric) data types: strings and symbols.
3104 @cindex @code{cl_string}
3114 implements immutable strings.
3116 Strings are constructed through the following constructors:
3119 @item cl_string (const char * s)
3120 Returns an immutable copy of the (zero-terminated) C string @code{s}.
3122 @item cl_string (const char * ptr, unsigned long len)
3123 Returns an immutable copy of the @code{len} characters at
3124 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
3127 The following functions are available on strings:
3131 Assignment from @code{cl_string} and @code{const char *}.
3134 @cindex @code{size()}
3136 @cindex @code{strlen ()}
3137 Returns the length of the string @code{s}.
3140 @cindex @code{operator [] ()}
3141 Returns the @code{i}th character of the string @code{s}.
3142 @code{i} must be in the range @code{0 <= i < s.size()}.
3144 @item bool equal (const cl_string& s1, const cl_string& s2)
3145 @cindex @code{equal ()}
3146 Compares two strings for equality. One of the arguments may also be a
3147 plain @code{const char *}.
3153 @cindex @code{cl_symbol}
3155 Symbols are uniquified strings: all symbols with the same name are shared.
3156 This means that comparison of two symbols is fast (effectively just a pointer
3157 comparison), whereas comparison of two strings must in the worst case walk
3158 both strings until their end.
3159 Symbols are used, for example, as tags for properties, as names of variables
3160 in polynomial rings, etc.
3162 Symbols are constructed through the following constructor:
3165 @item cl_symbol (const cl_string& s)
3166 Looks up or creates a new symbol with a given name.
3169 The following operations are available on symbols:
3172 @item cl_string (const cl_symbol& sym)
3173 Conversion to @code{cl_string}: Returns the string which names the symbol
3176 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
3177 @cindex @code{equal ()}
3178 Compares two symbols for equality. This is very fast.
3182 @node Univariate polynomials
3183 @chapter Univariate polynomials
3185 @cindex univariate polynomial
3188 * Univariate polynomial rings::
3189 * Functions on univariate polynomials::
3190 * Special polynomials::
3193 @node Univariate polynomial rings
3194 @section Univariate polynomial rings
3196 CLN implements univariate polynomials (polynomials in one variable) over an
3197 arbitrary ring. The indeterminate variable may be either unnamed (and will be
3198 printed according to @code{default_print_flags.univpoly_varname}, which
3199 defaults to @samp{x}) or carry a given name. The base ring and the
3200 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
3201 (accidentally) mix elements of different polynomial rings, e.g.
3202 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
3203 return a multivariate polynomial, but they are not yet implemented in CLN.)
3205 The classes of univariate polynomial rings are
3213 Univariate polynomial ring
3217 +----------------+-------------------+
3219 Complex polynomial ring | Modular integer polynomial ring
3220 cl_univpoly_complex_ring | cl_univpoly_modint_ring
3221 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3225 Real polynomial ring |
3226 cl_univpoly_real_ring |
3227 <cln/univpoly_real.h> |
3231 Rational polynomial ring |
3232 cl_univpoly_rational_ring |
3233 <cln/univpoly_rational.h> |
3237 Integer polynomial ring
3238 cl_univpoly_integer_ring
3239 <cln/univpoly_integer.h>
3242 and the corresponding classes of univariate polynomials are
3245 Univariate polynomial
3249 +----------------+-------------------+
3251 Complex polynomial | Modular integer polynomial
3253 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3259 <cln/univpoly_real.h> |
3263 Rational polynomial |
3265 <cln/univpoly_rational.h> |
3271 <cln/univpoly_integer.h>
3274 Univariate polynomial rings are constructed using the functions
3277 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3278 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3279 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3280 @code{R} may be an arbitrary ring. This function takes care of finding out
3281 about special cases of @code{R}, such as the rings of complex numbers,
3282 real numbers, rational numbers, integers, or modular integer rings.
3283 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3284 This ensures that two calls of this function with the same arguments will
3285 return the same polynomial ring.
3287 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3288 @cindex @code{find_univpoly_ring ()}
3289 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3290 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3291 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3292 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3293 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3294 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3295 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3296 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3297 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3298 These functions are equivalent to the general @code{find_univpoly_ring},
3299 only the return type is more specific, according to the base ring's type.
3302 @node Functions on univariate polynomials
3303 @section Functions on univariate polynomials
3305 Given a univariate polynomial ring @code{R}, the following members can be used.
3308 @item cl_ring R->basering()
3309 @cindex @code{basering ()}
3310 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3312 @item cl_UP R->zero()
3313 @cindex @code{zero ()}
3314 This returns @code{0 in R}, a polynomial of degree -1.
3316 @item cl_UP R->one()
3317 @cindex @code{one ()}
3318 This returns @code{1 in R}, a polynomial of degree == 0.
3320 @item cl_UP R->canonhom (const cl_I& x)
3321 @cindex @code{canonhom ()}
3322 This returns @code{x in R}, a polynomial of degree <= 0.
3324 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3325 @cindex @code{monomial ()}
3326 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3329 @item cl_UP R->create (sintL degree)
3330 @cindex @code{create ()}
3331 Creates a new polynomial with a given degree. The zero polynomial has degree
3332 @code{-1}. After creating the polynomial, you should put in the coefficients,
3333 using the @code{set_coeff} member function, and then call the @code{finalize}
3337 The following are the only destructive operations on univariate polynomials.
3340 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3341 @cindex @code{set_coeff ()}
3342 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3343 After changing a polynomial and before applying any "normal" operation on it,
3344 you should call its @code{finalize} member function.
3346 @item void finalize (cl_UP& x)
3347 @cindex @code{finalize ()}
3348 This function marks the endpoint of destructive modifications of a polynomial.
3349 It normalizes the internal representation so that subsequent computations have
3350 less overhead. Doing normal computations on unnormalized polynomials may
3351 produce wrong results or crash the program.
3354 The following operations are defined on univariate polynomials.
3357 @item cl_univpoly_ring x.ring ()
3358 @cindex @code{ring ()}
3359 Returns the ring to which the univariate polynomial @code{x} belongs.
3361 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3362 @cindex @code{operator + ()}
3363 Returns the sum of two univariate polynomials.
3365 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3366 @cindex @code{operator - ()}
3367 Returns the difference of two univariate polynomials.
3369 @item cl_UP operator- (const cl_UP&)
3370 Returns the negative of a univariate polynomial.
3372 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3373 @cindex @code{operator * ()}
3374 Returns the product of two univariate polynomials. One of the arguments may
3375 also be a plain integer or an element of the base ring.
3377 @item cl_UP square (const cl_UP&)
3378 @cindex @code{square ()}
3379 Returns the square of a univariate polynomial.
3381 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3382 @cindex @code{expt_pos ()}
3383 @code{y} must be > 0. Returns @code{x^y}.
3385 @item bool operator== (const cl_UP&, const cl_UP&)
3386 @cindex @code{operator == ()}
3387 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3388 @cindex @code{operator != ()}
3389 Compares two univariate polynomials, belonging to the same univariate
3390 polynomial ring, for equality.
3392 @item bool zerop (const cl_UP& x)
3393 @cindex @code{zerop ()}
3394 Returns true if @code{x} is @code{0 in R}.
3396 @item sintL degree (const cl_UP& x)
3397 @cindex @code{degree ()}
3398 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3400 @item sintL ldegree (const cl_UP& x)
3401 @cindex @code{degree ()}
3402 Returns the low degree of the polynomial. This is the degree of the first
3403 non-vanishing polynomial coefficient. The zero polynomial has ldegree @code{-1}.
3405 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3406 @cindex @code{coeff ()}
3407 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3409 @item cl_ring_element x (const cl_ring_element& y)
3410 @cindex @code{operator () ()}
3411 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3412 then @samp{x(y)} returns the value of the substitution of @code{y} into
3415 @item cl_UP deriv (const cl_UP& x)
3416 @cindex @code{deriv ()}
3417 Returns the derivative of the polynomial @code{x} with respect to the
3418 indeterminate @code{X}.
3421 The following output functions are defined (see also the chapter on
3425 @item void fprint (std::ostream& stream, const cl_UP& x)
3426 @cindex @code{fprint ()}
3427 @itemx std::ostream& operator<< (std::ostream& stream, const cl_UP& x)
3428 @cindex @code{operator << ()}
3429 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3430 depend on the global printer settings in the variable
3431 @code{default_print_flags}.
3434 @node Special polynomials
3435 @section Special polynomials
3437 The following functions return special polynomials.
3440 @item cl_UP_I tschebychev (sintL n)
3441 @cindex @code{tschebychev ()}
3442 @cindex Chebyshev polynomial
3443 Returns the n-th Chebyshev polynomial (n >= 0).
3445 @item cl_UP_I hermite (sintL n)
3446 @cindex @code{hermite ()}
3447 @cindex Hermite polynomial
3448 Returns the n-th Hermite polynomial (n >= 0).
3450 @item cl_UP_RA legendre (sintL n)
3451 @cindex @code{legendre ()}
3452 @cindex Legende polynomial
3453 Returns the n-th Legendre polynomial (n >= 0).
3455 @item cl_UP_I laguerre (sintL n)
3456 @cindex @code{laguerre ()}
3457 @cindex Laguerre polynomial
3458 Returns the n-th Laguerre polynomial (n >= 0).
3461 Information how to derive the differential equation satisfied by each
3462 of these polynomials from their definition can be found in the
3463 @code{doc/polynomial/} directory.
3471 * Memory efficiency::
3472 * Speed efficiency::
3473 * Garbage collection::
3480 Using C++ as an implementation language provides
3484 Efficiency: It compiles to machine code.
3488 Portability: It runs on all platforms supporting a C++ compiler. Because
3489 of the availability of GNU C++, this includes all currently used 32-bit and
3490 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3493 Type safety: The C++ compilers knows about the number types and complains if,
3494 for example, you try to assign a float to an integer variable. However,
3495 a drawback is that C++ doesn't know about generic types, hence a restriction
3496 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3497 arguments belong to the same modular ring cannot be expressed as a compile-time
3501 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3502 @code{=}, @code{==}, ... can be used in infix notation, which is more
3503 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3506 With these language features, there is no need for two separate languages,
3507 one for the implementation of the library and one in which the library's users
3508 can program. This means that a prototype implementation of an algorithm
3509 can be integrated into the library immediately after it has been tested and
3510 debugged. No need to rewrite it in a low-level language after having prototyped
3511 in a high-level language.
3514 @node Memory efficiency
3515 @section Memory efficiency
3517 In order to save memory allocations, CLN implements:
3521 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3524 @cindex garbage collection
3525 @cindex reference counting
3526 Garbage collection: A reference counting mechanism makes sure that any
3527 number object's storage is freed immediately when the last reference to the
3530 @cindex immediate numbers
3531 Small integers are represented as immediate values instead of pointers
3532 to heap allocated storage. This means that integers @code{>= -2^29},
3533 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3538 @node Speed efficiency
3539 @section Speed efficiency
3541 Speed efficiency is obtained by the combination of the following tricks
3546 Small integers, being represented as immediate values, don't require
3547 memory access, just a couple of instructions for each elementary operation.
3549 The kernel of CLN has been written in assembly language for some CPUs
3550 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3552 On all CPUs, CLN may be configured to use the superefficient low-level
3553 routines from GNU GMP version 3.
3555 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3556 algorithm, the Karatsuba multiplication, which is an
3567 For very large numbers (more than 12000 decimal digits), CLN uses
3569 Sch{@"o}nhage-Strassen
3570 @cindex Sch{@"o}nhage-Strassen multiplication
3574 @cindex Schoenhage-Strassen multiplication
3576 multiplication, which is an asymptotically optimal multiplication
3579 These fast multiplication algorithms also give improvements in the speed
3580 of division and radix conversion.
3584 @node Garbage collection
3585 @section Garbage collection
3586 @cindex garbage collection
3588 All the number classes are reference count classes: They only contain a pointer
3589 to an object in the heap. Upon construction, assignment and destruction of
3590 number objects, only the objects' reference count are manipulated.
3592 Memory occupied by number objects are automatically reclaimed as soon as
3593 their reference count drops to zero.
3595 For number rings, another strategy is implemented: There is a cache of,
3596 for example, the modular integer rings. A modular integer ring is destroyed
3597 only if its reference count dropped to zero and the cache is about to be
3598 resized. The effect of this strategy is that recently used rings remain
3599 cached, whereas undue memory consumption through cached rings is avoided.
3602 @node Using the library
3603 @chapter Using the library
3605 For the following discussion, we will assume that you have installed
3606 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3607 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3608 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3609 environment variables, or directly substitute the appropriate values.
3613 * Compiler options::
3616 * Debugging support::
3617 * Reporting Problems::
3620 @node Compiler options
3621 @section Compiler options
3622 @cindex compiler options
3624 Until you have installed CLN in a public place, the following options are
3627 When you compile CLN application code, add the flags
3629 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3631 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3632 When you link CLN application code to form an executable, add the flags
3634 $CLN_TARGETDIR/src/libcln.a
3636 to the C/C++ compiler's command line (@code{make} variable LIBS).
3638 If you did a @code{make install}, the include files are installed in a
3639 public directory (normally @code{/usr/local/include}), hence you don't
3640 need special flags for compiling. The library has been installed to a
3641 public directory as well (normally @code{/usr/local/lib}), hence when
3642 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3644 @cindex @code{pkg-config}
3645 To make the creation of software packages that use CLN easier, the
3646 @code{pkg-config} utility can be used. CLN provides all the necessary
3647 metainformation in a file called @code{cln.pc} (installed in
3648 @code{/usr/local/lib/pkgconfig} by default). A program using CLN can
3649 be compiled and linked using @footnote{If you installed CLN to
3650 non-standard location @var{prefix}, you need to set the
3651 @env{PKG_CONFIG_PATH} environment variable to @var{prefix}/lib/pkgconfig
3654 g++ `pkg-config --libs cln` `pkg-config --cflags cln` prog.cc -o prog
3657 Software using GNU autoconf can check for CLN with the
3658 @code{PKG_CHECK_MODULES} macro supplied with @code{pkg-config}.
3660 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}])
3662 This will check for CLN version at least @var{MIN-VERSION}. If the
3663 required version was found, the variables @var{CLN_CFLAGS} and
3664 @var{CLN_LIBS} are set. Otherwise the configure script aborts. If this
3665 is not the desired behaviour, use the following code instead
3666 @footnote{See the @code{pkg-config} documentation for more details.}
3668 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}], [],
3669 [AC_MSG_WARNING([No suitable version of CLN can be found])])
3674 @section Include files
3675 @cindex include files
3676 @cindex header files
3678 Here is a summary of the include files and their contents.
3681 @item <cln/object.h>
3682 General definitions, reference counting, garbage collection.
3683 @item <cln/number.h>
3684 The class cl_number.
3685 @item <cln/complex.h>
3686 Functions for class cl_N, the complex numbers.
3688 Functions for class cl_R, the real numbers.
3690 Functions for class cl_F, the floats.
3691 @item <cln/sfloat.h>
3692 Functions for class cl_SF, the short-floats.
3693 @item <cln/ffloat.h>
3694 Functions for class cl_FF, the single-floats.
3695 @item <cln/dfloat.h>
3696 Functions for class cl_DF, the double-floats.
3697 @item <cln/lfloat.h>
3698 Functions for class cl_LF, the long-floats.
3699 @item <cln/rational.h>
3700 Functions for class cl_RA, the rational numbers.
3701 @item <cln/integer.h>
3702 Functions for class cl_I, the integers.
3705 @item <cln/complex_io.h>
3706 Input/Output for class cl_N, the complex numbers.
3707 @item <cln/real_io.h>
3708 Input/Output for class cl_R, the real numbers.
3709 @item <cln/float_io.h>
3710 Input/Output for class cl_F, the floats.
3711 @item <cln/sfloat_io.h>
3712 Input/Output for class cl_SF, the short-floats.
3713 @item <cln/ffloat_io.h>
3714 Input/Output for class cl_FF, the single-floats.
3715 @item <cln/dfloat_io.h>
3716 Input/Output for class cl_DF, the double-floats.
3717 @item <cln/lfloat_io.h>
3718 Input/Output for class cl_LF, the long-floats.
3719 @item <cln/rational_io.h>
3720 Input/Output for class cl_RA, the rational numbers.
3721 @item <cln/integer_io.h>
3722 Input/Output for class cl_I, the integers.
3724 Flags for customizing input operations.
3725 @item <cln/output.h>
3726 Flags for customizing output operations.
3727 @item <cln/malloc.h>
3728 @code{malloc_hook}, @code{free_hook}.
3729 @item <cln/exception.h>
3730 Exception base class.
3731 @item <cln/condition.h>
3733 @item <cln/string.h>
3735 @item <cln/symbol.h>
3737 @item <cln/proplist.h>
3741 @item <cln/null_ring.h>
3743 @item <cln/complex_ring.h>
3744 The ring of complex numbers.
3745 @item <cln/real_ring.h>
3746 The ring of real numbers.
3747 @item <cln/rational_ring.h>
3748 The ring of rational numbers.
3749 @item <cln/integer_ring.h>
3750 The ring of integers.
3751 @item <cln/numtheory.h>
3752 Number threory functions.
3753 @item <cln/modinteger.h>
3759 @item <cln/GV_number.h>
3760 General vectors over cl_number.
3761 @item <cln/GV_complex.h>
3762 General vectors over cl_N.
3763 @item <cln/GV_real.h>
3764 General vectors over cl_R.
3765 @item <cln/GV_rational.h>
3766 General vectors over cl_RA.
3767 @item <cln/GV_integer.h>
3768 General vectors over cl_I.
3769 @item <cln/GV_modinteger.h>
3770 General vectors of modular integers.
3773 @item <cln/SV_number.h>
3774 Simple vectors over cl_number.
3775 @item <cln/SV_complex.h>
3776 Simple vectors over cl_N.
3777 @item <cln/SV_real.h>
3778 Simple vectors over cl_R.
3779 @item <cln/SV_rational.h>
3780 Simple vectors over cl_RA.
3781 @item <cln/SV_integer.h>
3782 Simple vectors over cl_I.
3783 @item <cln/SV_ringelt.h>
3784 Simple vectors of general ring elements.
3785 @item <cln/univpoly.h>
3786 Univariate polynomials.
3787 @item <cln/univpoly_integer.h>
3788 Univariate polynomials over the integers.
3789 @item <cln/univpoly_rational.h>
3790 Univariate polynomials over the rational numbers.
3791 @item <cln/univpoly_real.h>
3792 Univariate polynomials over the real numbers.
3793 @item <cln/univpoly_complex.h>
3794 Univariate polynomials over the complex numbers.
3795 @item <cln/univpoly_modint.h>
3796 Univariate polynomials over modular integer rings.
3797 @item <cln/timing.h>
3800 Includes all of the above.
3807 A function which computes the nth Fibonacci number can be written as follows.
3808 @cindex Fibonacci number
3811 #include <cln/integer.h>
3812 #include <cln/real.h>
3813 using namespace cln;
3815 // Returns F_n, computed as the nearest integer to
3816 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3817 const cl_I fibonacci (int n)
3819 // Need a precision of ((1+sqrt(5))/2)^-n.
3820 float_format_t prec = float_format((int)(0.208987641*n+5));
3821 cl_R sqrt5 = sqrt(cl_float(5,prec));
3822 cl_R phi = (1+sqrt5)/2;
3823 return round1( expt(phi,n)/sqrt5 );
3827 Let's explain what is going on in detail.
3829 The include file @code{<cln/integer.h>} is necessary because the type
3830 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3831 is needed for the type @code{cl_R} and the floating point number functions.
3832 The order of the include files does not matter. In order not to write
3833 out @code{cln::}@var{foo} in this simple example we can safely import
3834 the whole namespace @code{cln}.
3836 Then comes the function declaration. The argument is an @code{int}, the
3837 result an integer. The return type is defined as @samp{const cl_I}, not
3838 simply @samp{cl_I}, because that allows the compiler to detect typos like
3839 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3840 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3841 number). We use the most specialized possible return type because functions
3842 which call @samp{fibonacci} will be able to profit from the compiler's type
3843 analysis: Adding two integers is slightly more efficient than adding the
3844 same objects declared as complex numbers, because it needs less type
3845 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3846 the size of the resulting executable program.
3848 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3849 integer. In order to get a correct result, the absolute error should be less
3850 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3851 To this end, the first line computes a floating point precision for sqrt(5)
3854 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3855 number and than taking the square root. The converse, first taking the square
3856 root of 5, and then converting to the desired precision, would not work in
3857 CLN: The square root would be computed to a default precision (normally
3858 single-float precision), and the following conversion could not help about
3859 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3860 system and does not represent sqrt(5) in a non-numeric way.
3862 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3863 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3864 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3865 @code{cl_N} because a @samp{round1} does not exist for general complex
3868 When the function returns, all the local variables in the function are
3869 automatically reclaimed (garbage collected). Only the result survives and
3870 gets passed to the caller.
3872 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3873 contains this implementation together with an even faster algorithm.
3875 @node Debugging support
3876 @section Debugging support
3879 When debugging a CLN application with GNU @code{gdb}, two facilities are
3880 available from the library:
3883 @item The library does type checks, range checks, consistency checks at
3884 many places. When one of these fails, an exception of a type derived from
3885 @code{runtime_exception} is thrown. When an exception is cought, the stack
3886 has already been unwound, so it is may not be possible to tell at which
3887 point the exception was thrown. For debugging, it is best to set up a
3888 catchpoint at the event of throwning a C++ exception:
3892 When this catchpoint is hit, look at the stack's backtrace:
3896 When control over the type of exception is required, it may be possible
3897 to set a breakpoint at the @code{g++} runtime library function
3898 @code{__raise_exception}. Refer to the documentation of GNU @code{gdb}
3901 @item The debugger's normal @code{print} command doesn't know about
3902 CLN's types and therefore prints mostly useless hexadecimal addresses.
3903 CLN offers a function @code{cl_print}, callable from the debugger,
3904 for printing number objects. In order to get this function, you have
3905 to define the macro @samp{CL_DEBUG} and then include all the header files
3906 for which you want @code{cl_print} debugging support. For example:
3907 @cindex @code{CL_DEBUG}
3910 #include <cln/string.h>
3912 Now, if you have in your program a variable @code{cl_string s}, and
3913 inspect it under @code{gdb}, the output may look like this:
3916 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3917 word = 134568800@}@}, @}
3918 (gdb) call cl_print(s)
3922 Note that the output of @code{cl_print} goes to the program's error output,
3923 not to gdb's standard output.
3925 Note, however, that the above facility does not work with all CLN types,
3926 only with number objects and similar. Therefore CLN offers a member function
3927 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3928 is needed for this member function to be implemented. Under @code{gdb},
3929 you call it like this:
3930 @cindex @code{debug_print ()}
3933 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3934 word = 134568800@}@}, @}
3935 (gdb) call s.debug_print()
3938 >call ($1).debug_print()
3943 Unfortunately, this feature does not seem to work under all circumstances.
3946 @node Reporting Problems
3947 @section Reporting Problems
3949 @cindex mailing list
3951 If you encounter any problem, please don't hesitate to send a detailed
3952 bugreport to the @code{cln-list@@ginac.de} mailing list. Please think
3953 about your bug: consider including a short description of your operating
3954 system and compilation environment with corresponding version numbers. A
3955 description of your configuration options may also be helpful. Also, a
3956 short test program together with the output you get and the output you
3957 expect will help us to reproduce it quickly. Finally, do not forget to
3958 report the version number of CLN.
3962 @chapter Customizing
3967 * Floating-point underflow::
3969 * Customizing the memory allocator::
3972 @node Error handling
3973 @section Error handling
3975 @cindex error handling
3977 @cindex @code{runtime_exception}
3978 CLN signals abnormal situations by throwning exceptions. All exceptions
3979 thrown by the library are of type @code{runtime_exception} or of a
3980 derived type. Class @code{cln::runtime_exception} in turn is derived
3981 from the C++ standard library class @code{std::runtime_error} and
3982 inherits the @code{.what()} member function that can be used to query
3983 details about the cause of error.
3985 The most important classes thrown by the library are
3987 @cindex @code{floating_point_exception}
3988 @cindex @code{read_number_exception}
3990 Exception base class
3994 +----------------+----------------+
3996 Malformed number input Floating-point error
3997 read_number_exception floating_poing_exception
3998 <cln/number_io.h> <cln/float.h>
4001 CLN has many more exception classes that allow for more fine-grained
4002 control but I refrain from documenting them all here. They are all
4003 declared in the public header files and they are all subclasses of the
4004 above exceptions, so catching those you are always on the safe side.
4007 @node Floating-point underflow
4008 @section Floating-point underflow
4011 @cindex @code{floating_point_underflow_exception}
4012 Floating point underflow denotes the situation when a floating-point
4013 number is to be created which is so close to @code{0} that its exponent
4014 is too low to be represented internally. By default, this causes the
4015 exception @code{floating_point_underflow_exception} (subclass of
4016 @code{floating_point_exception}) to be thrown. If you set the global
4019 bool cl_inhibit_floating_point_underflow
4021 to @code{true}, the exception will be inhibited, and a floating-point
4022 zero will be generated instead. The default value of
4023 @code{cl_inhibit_floating_point_underflow} is @code{false}.
4026 @node Customizing I/O
4027 @section Customizing I/O
4029 The output of the function @code{fprint} may be customized by changing the
4030 value of the global variable @code{default_print_flags}.
4031 @cindex @code{default_print_flags}
4034 @node Customizing the memory allocator
4035 @section Customizing the memory allocator
4037 Every memory allocation of CLN is done through the function pointer
4038 @code{malloc_hook}. Freeing of this memory is done through the function
4039 pointer @code{free_hook}. The default versions of these functions,
4040 provided in the library, call @code{malloc} and @code{free} and check
4041 the @code{malloc} result against @code{NULL}.
4042 If you want to provide another memory allocator, you need to define
4043 the variables @code{malloc_hook} and @code{free_hook} yourself,
4046 #include <cln/malloc.h>
4048 void* (*malloc_hook) (size_t size) = @dots{};
4049 void (*free_hook) (void* ptr) = @dots{};
4052 @cindex @code{malloc_hook ()}
4053 @cindex @code{free_hook ()}
4054 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
4056 It is not possible to change the memory allocator at runtime, because
4057 it is already called at program startup by the constructors of some
4065 @node Index, , Customizing, Top