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, 2010, 2011.
40 Copyright (C) Alexei Sheplyakov 2008, 2010.
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, 2010, 2011.
77 Copyright @copyright{} Alexei Sheplyakov 2008, 2010.
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 GNU @code{g++ 4.0.0} or newer is recommended.
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.
418 @subsection Sed utility
421 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
422 This is because the libtool script, which creates the CLN library, relies
423 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
427 @node Building the library
428 @section Building the library
430 As with any autoconfiguring GNU software, installation is as easy as this:
438 If on your system, @samp{make} is not GNU @code{make}, you have to use
439 @samp{gmake} instead of @samp{make} above.
441 The @code{configure} command checks out some features of your system and
442 C++ compiler and builds the @code{Makefile}s. The @code{make} command
443 builds the library. This step may take about half an hour on an average
444 workstation. The @code{make check} runs some test to check that no
445 important subroutine has been miscompiled.
447 The @code{configure} command accepts options. To get a summary of them, try
453 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
455 You can specify the C compiler, the C++ compiler and their options through
456 the following environment variables when running @code{configure}:
460 Specifies the C compiler.
463 Flags to be given to the C compiler when compiling programs (not when linking).
466 Specifies the C++ compiler.
469 Flags to be given to the C++ compiler when compiling programs (not when linking).
472 Flags to be given to the C/C++ preprocessor.
475 Flags to be given to the linker.
481 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
484 $ CC="gcc -V 3.2.3" CFLAGS="-O2 -finline-limit=1000" \
485 CXX="g++ -V 3.2.3" CXXFLAGS="-O2 -finline-limit=1000" \
486 CPPFLAGS="-DNO_ASM" ./configure
489 $ CC="gcc-4.2" CFLAGS="-O2" CXX="g++-4.2" CXXFLAGS="-O2" ./configure
492 Note that for these environment variables to take effect, you have to set
493 them (assuming a Bourne-compatible shell) on the same line as the
494 @code{configure} command. If you made the settings in earlier shell
495 commands, you have to @code{export} the environment variables before
496 calling @code{configure}. In a @code{csh} shell, you have to use the
497 @samp{setenv} command for setting each of the environment variables.
499 Currently CLN works only with the GNU @code{g++} compiler, and only in
500 optimizing mode. So you should specify at least @code{-O} in the
501 CXXFLAGS, or no CXXFLAGS at all. If CXXFLAGS is not set, CLN will be
502 compiled with @code{-O}.
504 The assembler language kernel can be turned off by specifying
505 @code{-DNO_ASM} in the CPPFLAGS. If @code{make check} reports any
506 problems, you may try to clean up (see @ref{Cleaning up}) and configure
507 and compile again, this time with @code{-DNO_ASM}.
509 If you use @code{g++} 3.2.x or earlier, I recommend adding
510 @samp{-finline-limit=1000} to the CXXFLAGS. This is essential for good
513 If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
514 @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
515 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
516 routines. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
519 Also, please do not compile CLN with @code{g++} using the @code{-O3}
520 optimization level. This leads to inferior code quality.
522 Some newer versions of @code{g++} require quite an amount of memory.
523 You might need some swap space if your machine doesn't have 512 MB of
526 By default, both a shared and a static library are built. You can build
527 CLN as a static (or shared) library only, by calling @code{configure}
528 with the option @samp{--disable-shared} (or @samp{--disable-static}).
529 While shared libraries are usually more convenient to use, they may not
530 work on all architectures. Try disabling them if you run into linker
531 problems. Also, they are generally slightly slower than static
532 libraries so runtime-critical applications should be linked statically.
536 * Using the GNU MP Library::
539 @node Using the GNU MP Library
540 @subsection Using the GNU MP Library
543 CLN may be configured to make use of a preinstalled @code{gmp} library
544 for some low-level routines. Please make sure that you have at least
545 @code{gmp} version 3.0 installed since earlier versions are unsupported
546 and likely not to work. Using @code{gmp} is known to be quite a boost
547 for CLN's performance.
549 By default, CLN will autodetect @code{gmp} and use it. If you do not
550 want CLN to make use of a preinstalled @code{gmp} library, then you can
551 explicitly specify so by calling @code{configure} with the option
552 @samp{--without-gmp}.
554 If you have installed the @code{gmp} library and its header files in
555 some place where the compiler cannot find it by default, you must help
556 @code{configure} and specify the prefix that was used when @code{gmp}
557 was configured. Here is an example:
560 $ ./configure --with-gmp=/opt/gmp-4.2.2
563 This assumes that the @code{gmp} header files have been installed in
564 @file{/opt/gmp-4.2.2/include/} and the library in
565 @file{/opt/gmp-4.2.2/lib/}. More uncommon GMP installations can be
566 handled by setting CPPFLAGS and LDFLAGS appropriately prior to running
570 @node Installing the library
571 @section Installing the library
574 As with any autoconfiguring GNU software, installation is as easy as this:
580 The @samp{make install} command installs the library and the include files
581 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
582 if you haven't specified a @code{--prefix} option to @code{configure}).
583 This step may require superuser privileges.
585 If you have already built the library and wish to install it, but didn't
586 specify @code{--prefix=@dots{}} at configure time, just re-run
587 @code{configure}, giving it the same options as the first time, plus
588 the @code{--prefix=@dots{}} option.
594 You can remove system-dependent files generated by @code{make} through
600 You can remove all files generated by @code{make}, thus reverting to a
601 virgin distribution of CLN, through
608 @node Ordinary number types
609 @chapter Ordinary number types
611 CLN implements the following class hierarchy:
619 Real or complex number
628 +-------------------+-------------------+
630 Rational number Floating-point number
632 <cln/rational.h> <cln/float.h>
634 | +--------------+--------------+--------------+
636 cl_I Short-Float Single-Float Double-Float Long-Float
637 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
638 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
641 @cindex @code{cl_number}
642 @cindex abstract class
643 The base class @code{cl_number} is an abstract base class.
644 It is not useful to declare a variable of this type except if you want
645 to completely disable compile-time type checking and use run-time type
650 @cindex complex number
651 The class @code{cl_N} comprises real and complex numbers. There is
652 no special class for complex numbers since complex numbers with imaginary
653 part @code{0} are automatically converted to real numbers.
656 The class @code{cl_R} comprises real numbers of different kinds. It is an
660 @cindex rational number
662 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
663 integers. There is no special class for non-integral rational numbers
664 since rational numbers with denominator @code{1} are automatically converted
668 The class @code{cl_F} implements floating-point approximations to real numbers.
669 It is an abstract class.
674 * Floating-point numbers::
680 @section Exact numbers
683 Some numbers are represented as exact numbers: there is no loss of information
684 when such a number is converted from its mathematical value to its internal
685 representation. On exact numbers, the elementary operations (@code{+},
686 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
689 In CLN, the exact numbers are:
693 rational numbers (including integers),
695 complex numbers whose real and imaginary parts are both rational numbers.
698 Rational numbers are always normalized to the form
699 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
700 are coprime integers and the denominator is positive. If the resulting
701 denominator is @code{1}, the rational number is converted to an integer.
703 @cindex immediate numbers
704 Small integers (typically in the range @code{-2^29}@dots{}@code{2^29-1},
705 for 32-bit machines) are especially efficient, because they consume no heap
706 allocation. Otherwise the distinction between these immediate integers
707 (called ``fixnums'') and heap allocated integers (called ``bignums'')
708 is completely transparent.
711 @node Floating-point numbers
712 @section Floating-point numbers
713 @cindex floating-point number
715 Not all real numbers can be represented exactly. (There is an easy mathematical
716 proof for this: Only a countable set of numbers can be stored exactly in
717 a computer, even if one assumes that it has unlimited storage. But there
718 are uncountably many real numbers.) So some approximation is needed.
719 CLN implements ordinary floating-point numbers, with mantissa and exponent.
721 @cindex rounding error
722 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
723 only return approximate results. For example, the value of the expression
724 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
725 @samp{0.7}. Rounding errors like this one are inevitable when computing
726 with floating-point numbers.
728 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
729 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
730 rule: It first computes the exact mathematical result and then returns the
731 floating-point number which is nearest to this. If two floating-point numbers
732 are equally distant from the ideal result, the one with a @code{0} in its least
733 significant mantissa bit is chosen.
735 Similarly, testing floating point numbers for equality @samp{x == y}
736 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
737 for some well-chosen @code{epsilon}.
739 Floating point numbers come in four flavors:
744 Short floats, type @code{cl_SF}.
745 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
746 and 17 mantissa bits (including the ``hidden'' bit).
747 They don't consume heap allocation.
751 Single floats, type @code{cl_FF}.
752 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
753 and 24 mantissa bits (including the ``hidden'' bit).
754 In CLN, they are represented as IEEE single-precision floating point numbers.
755 This corresponds closely to the C/C++ type @samp{float}.
759 Double floats, type @code{cl_DF}.
760 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
761 and 53 mantissa bits (including the ``hidden'' bit).
762 In CLN, they are represented as IEEE double-precision floating point numbers.
763 This corresponds closely to the C/C++ type @samp{double}.
767 Long floats, type @code{cl_LF}.
768 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
769 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
770 The precision of a long float is unlimited, but once created, a long float
771 has a fixed precision. (No ``lazy recomputation''.)
774 Of course, computations with long floats are more expensive than those
775 with smaller floating-point formats.
777 CLN does not implement features like NaNs, denormalized numbers and
778 gradual underflow. If the exponent range of some floating-point type
779 is too limited for your application, choose another floating-point type
780 with larger exponent range.
783 As a user of CLN, you can forget about the differences between the
784 four floating-point types and just declare all your floating-point
785 variables as being of type @code{cl_F}. This has the advantage that
786 when you change the precision of some computation (say, from @code{cl_DF}
787 to @code{cl_LF}), you don't have to change the code, only the precision
788 of the initial values. Also, many transcendental functions have been
789 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
790 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
791 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
792 the floating point contagion rule happened to change in the future.)
795 @node Complex numbers
796 @section Complex numbers
797 @cindex complex number
799 Complex numbers, as implemented by the class @code{cl_N}, have a real
800 part and an imaginary part, both real numbers. A complex number whose
801 imaginary part is the exact number @code{0} is automatically converted
804 Complex numbers can arise from real numbers alone, for example
805 through application of @code{sqrt} or transcendental functions.
812 Conversions from any class to any its superclasses (``base classes'' in
813 C++ terminology) is done automatically.
815 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
816 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
817 @code{cl_N} and @code{cl_number}.
819 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
820 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
821 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
822 efficiency. On 32-bit systems, their range is therefore limited:
826 The conversion from @samp{int} works only if the argument is < 2^29 and >= -2^29.
828 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
831 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
832 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
833 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
834 in error on 32-bit machines.
835 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
836 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
837 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
838 @samp{cl_I}, first convert it to an @samp{unsigned long}. On 64-bit machines
839 there is no such restriction. There, conversions from arbitrary 32-bit @samp{int}
840 values always works correctly.
842 Conversions from the C built-in type @samp{float} are provided for the classes
843 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
845 Conversions from the C built-in type @samp{double} are provided for the classes
846 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
848 Conversions from @samp{const char *} are provided for the classes
849 @code{cl_I}, @code{cl_RA},
850 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
851 @code{cl_R}, @code{cl_N}.
852 The easiest way to specify a value which is outside of the range of the
853 C++ built-in types is therefore to specify it as a string, like this:
856 cl_I order_of_rubiks_cube_group = "43252003274489856000";
858 Note that this conversion is done at runtime, not at compile-time.
860 Conversions from @code{cl_I} to the C built-in types @samp{int},
861 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
865 @item int cl_I_to_int (const cl_I& x)
866 @cindex @code{cl_I_to_int ()}
867 @itemx unsigned int cl_I_to_uint (const cl_I& x)
868 @cindex @code{cl_I_to_uint ()}
869 @itemx long cl_I_to_long (const cl_I& x)
870 @cindex @code{cl_I_to_long ()}
871 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
872 @cindex @code{cl_I_to_ulong ()}
873 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
874 representable in the range of @var{ctype}, a runtime error occurs.
877 Conversions from the classes @code{cl_I}, @code{cl_RA},
878 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
880 to the C built-in types @samp{float} and @samp{double} are provided through
884 @item float float_approx (const @var{type}& x)
885 @cindex @code{float_approx ()}
886 @itemx double double_approx (const @var{type}& x)
887 @cindex @code{double_approx ()}
888 Returns an approximation of @code{x} of C type @var{ctype}.
889 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
890 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
893 Conversions from any class to any of its subclasses (``derived classes'' in
894 C++ terminology) are not provided. Instead, you can assert and check
895 that a value belongs to a certain subclass, and return it as element of that
896 class, using the @samp{As} and @samp{The} macros.
898 @cindex @code{As()()}
899 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
900 @var{type} and returns it as such.
901 @cindex @code{The()()}
902 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
903 @var{type} and returns it as such. It is your responsibility to ensure
904 that this assumption is valid. Since macros and namespaces don't go
905 together well, there is an equivalent to @samp{The}: the template
913 if (!(x >= 0)) abort();
914 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
915 // In general, it would be a rational number.
916 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
921 @node Functions on numbers
922 @chapter Functions on numbers
924 Each of the number classes declares its mathematical operations in the
925 corresponding include file. For example, if your code operates with
926 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
930 * Constructing numbers::
931 * Elementary functions::
932 * Elementary rational functions::
933 * Elementary complex functions::
935 * Rounding functions::
937 * Transcendental functions::
938 * Functions on integers::
939 * Functions on floating-point numbers::
940 * Conversion functions::
941 * Random number generators::
942 * Modifying operators::
945 @node Constructing numbers
946 @section Constructing numbers
948 Here is how to create number objects ``from nothing''.
952 * Constructing integers::
953 * Constructing rational numbers::
954 * Constructing floating-point numbers::
955 * Constructing complex numbers::
958 @node Constructing integers
959 @subsection Constructing integers
961 @code{cl_I} objects are most easily constructed from C integers and from
962 strings. See @ref{Conversions}.
965 @node Constructing rational numbers
966 @subsection Constructing rational numbers
968 @code{cl_RA} objects can be constructed from strings. The syntax
969 for rational numbers is described in @ref{Internal and printed representation}.
970 Another standard way to produce a rational number is through application
971 of @samp{operator /} or @samp{recip} on integers.
974 @node Constructing floating-point numbers
975 @subsection Constructing floating-point numbers
977 @code{cl_F} objects with low precision are most easily constructed from
978 C @samp{float} and @samp{double}. See @ref{Conversions}.
980 To construct a @code{cl_F} with high precision, you can use the conversion
981 from @samp{const char *}, but you have to specify the desired precision
982 within the string. (See @ref{Internal and printed representation}.)
985 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
987 will set @samp{e} to the given value, with a precision of 40 decimal digits.
989 The programmatic way to construct a @code{cl_F} with high precision is
990 through the @code{cl_float} conversion function, see
991 @ref{Conversion to floating-point numbers}. For example, to compute
992 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
993 and then apply the exponential function:
995 float_format_t precision = float_format(40);
996 cl_F e = exp(cl_float(1,precision));
1000 @node Constructing complex numbers
1001 @subsection Constructing complex numbers
1003 Non-real @code{cl_N} objects are normally constructed through the function
1005 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
1007 See @ref{Elementary complex functions}.
1010 @node Elementary functions
1011 @section Elementary functions
1013 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1014 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1015 defines the following operations:
1018 @item @var{type} operator + (const @var{type}&, const @var{type}&)
1019 @cindex @code{operator + ()}
1022 @item @var{type} operator - (const @var{type}&, const @var{type}&)
1023 @cindex @code{operator - ()}
1026 @item @var{type} operator - (const @var{type}&)
1027 Returns the negative of the argument.
1029 @item @var{type} plus1 (const @var{type}& x)
1030 @cindex @code{plus1 ()}
1031 Returns @code{x + 1}.
1033 @item @var{type} minus1 (const @var{type}& x)
1034 @cindex @code{minus1 ()}
1035 Returns @code{x - 1}.
1037 @item @var{type} operator * (const @var{type}&, const @var{type}&)
1038 @cindex @code{operator * ()}
1041 @item @var{type} square (const @var{type}& x)
1042 @cindex @code{square ()}
1043 Returns @code{x * x}.
1046 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
1047 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1048 defines the following operations:
1051 @item @var{type} operator / (const @var{type}&, const @var{type}&)
1052 @cindex @code{operator / ()}
1055 @item @var{type} recip (const @var{type}&)
1056 @cindex @code{recip ()}
1057 Returns the reciprocal of the argument.
1060 The class @code{cl_I} doesn't define a @samp{/} operation because
1061 in the C/C++ language this operator, applied to integral types,
1062 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
1063 is implementation dependent). (@xref{Rounding functions}.)
1064 Instead, @code{cl_I} defines an ``exact quotient'' function:
1067 @item cl_I exquo (const cl_I& x, const cl_I& y)
1068 @cindex @code{exquo ()}
1069 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
1072 The following exponentiation functions are defined:
1075 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
1076 @cindex @code{expt_pos ()}
1077 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
1078 @code{y} must be > 0. Returns @code{x^y}.
1080 @item cl_RA expt (const cl_RA& x, const cl_I& y)
1081 @cindex @code{expt ()}
1082 @itemx cl_R expt (const cl_R& x, const cl_I& y)
1083 @itemx cl_N expt (const cl_N& x, const cl_I& y)
1087 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1088 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1089 defines the following operation:
1092 @item @var{type} abs (const @var{type}& x)
1093 @cindex @code{abs ()}
1094 Returns the absolute value of @code{x}.
1095 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
1098 The class @code{cl_N} implements this as follows:
1101 @item cl_R abs (const cl_N x)
1102 Returns the absolute value of @code{x}.
1105 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1106 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1107 defines the following operation:
1110 @item @var{type} signum (const @var{type}& x)
1111 @cindex @code{signum ()}
1112 Returns the sign of @code{x}, in the same number format as @code{x}.
1113 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
1114 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
1119 @node Elementary rational functions
1120 @section Elementary rational functions
1122 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
1125 @item cl_I numerator (const @var{type}& x)
1126 @cindex @code{numerator ()}
1127 Returns the numerator of @code{x}.
1129 @item cl_I denominator (const @var{type}& x)
1130 @cindex @code{denominator ()}
1131 Returns the denominator of @code{x}.
1134 The numerator and denominator of a rational number are normalized in such
1135 a way that they have no factor in common and the denominator is positive.
1138 @node Elementary complex functions
1139 @section Elementary complex functions
1141 The class @code{cl_N} defines the following operation:
1144 @item cl_N complex (const cl_R& a, const cl_R& b)
1145 @cindex @code{complex ()}
1146 Returns the complex number @code{a+bi}, that is, the complex number with
1147 real part @code{a} and imaginary part @code{b}.
1150 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1153 @item cl_R realpart (const @var{type}& x)
1154 @cindex @code{realpart ()}
1155 Returns the real part of @code{x}.
1157 @item cl_R imagpart (const @var{type}& x)
1158 @cindex @code{imagpart ()}
1159 Returns the imaginary part of @code{x}.
1161 @item @var{type} conjugate (const @var{type}& x)
1162 @cindex @code{conjugate ()}
1163 Returns the complex conjugate of @code{x}.
1166 We have the relations
1170 @code{x = complex(realpart(x), imagpart(x))}
1172 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1177 @section Comparisons
1180 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1181 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1182 defines the following operations:
1185 @item bool operator == (const @var{type}&, const @var{type}&)
1186 @cindex @code{operator == ()}
1187 @itemx bool operator != (const @var{type}&, const @var{type}&)
1188 @cindex @code{operator != ()}
1189 Comparison, as in C and C++.
1191 @item uint32 equal_hashcode (const @var{type}&)
1192 @cindex @code{equal_hashcode ()}
1193 Returns a 32-bit hash code that is the same for any two numbers which are
1194 the same according to @code{==}. This hash code depends on the number's value,
1195 not its type or precision.
1197 @item bool zerop (const @var{type}& x)
1198 @cindex @code{zerop ()}
1199 Compare against zero: @code{x == 0}
1202 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1203 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1204 defines the following operations:
1207 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1208 @cindex @code{compare ()}
1209 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1210 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1212 @item bool operator <= (const @var{type}&, const @var{type}&)
1213 @cindex @code{operator <= ()}
1214 @itemx 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 Comparison, as in C and C++.
1222 @item bool minusp (const @var{type}& x)
1223 @cindex @code{minusp ()}
1224 Compare against zero: @code{x < 0}
1226 @item bool plusp (const @var{type}& x)
1227 @cindex @code{plusp ()}
1228 Compare against zero: @code{x > 0}
1230 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1231 @cindex @code{max ()}
1232 Return the maximum of @code{x} and @code{y}.
1234 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1235 @cindex @code{min ()}
1236 Return the minimum of @code{x} and @code{y}.
1239 When a floating point number and a rational number are compared, the float
1240 is first converted to a rational number using the function @code{rational}.
1241 Since a floating point number actually represents an interval of real numbers,
1242 the result might be surprising.
1243 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1244 there is no floating point number whose value is exactly @code{1/3}.
1247 @node Rounding functions
1248 @section Rounding functions
1251 When a real number is to be converted to an integer, there is no ``best''
1252 rounding. The desired rounding function depends on the application.
1253 The Common Lisp and ISO Lisp standards offer four rounding functions:
1257 This is the largest integer <=@code{x}.
1260 This is the smallest integer >=@code{x}.
1263 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1266 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1267 integers, choose the even one.
1270 These functions have different advantages:
1272 @code{floor} and @code{ceiling} are translation invariant:
1273 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1274 for every @code{x} and every integer @code{n}.
1276 On the other hand, @code{truncate} and @code{round} are symmetric:
1277 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1278 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1279 down exactly as often as it rounds up.
1281 The functions are related like this:
1285 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1286 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1288 @code{truncate(x) = sign(x) * floor(abs(x))}
1291 Each of the classes @code{cl_R}, @code{cl_RA},
1292 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1293 defines the following operations:
1296 @item cl_I floor1 (const @var{type}& x)
1297 @cindex @code{floor1 ()}
1298 Returns @code{floor(x)}.
1299 @item cl_I ceiling1 (const @var{type}& x)
1300 @cindex @code{ceiling1 ()}
1301 Returns @code{ceiling(x)}.
1302 @item cl_I truncate1 (const @var{type}& x)
1303 @cindex @code{truncate1 ()}
1304 Returns @code{truncate(x)}.
1305 @item cl_I round1 (const @var{type}& x)
1306 @cindex @code{round1 ()}
1307 Returns @code{round(x)}.
1310 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1311 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1312 defines the following operations:
1315 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1316 Returns @code{floor(x/y)}.
1317 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1318 Returns @code{ceiling(x/y)}.
1319 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1320 Returns @code{truncate(x/y)}.
1321 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1322 Returns @code{round(x/y)}.
1325 These functions are called @samp{floor1}, @dots{} here instead of
1326 @samp{floor}, @dots{}, because on some systems, system dependent include
1327 files define @samp{floor} and @samp{ceiling} as macros.
1329 In many cases, one needs both the quotient and the remainder of a division.
1330 It is more efficient to compute both at the same time than to perform
1331 two divisions, one for quotient and the next one for the remainder.
1332 The following functions therefore return a structure containing both
1333 the quotient and the remainder. The suffix @samp{2} indicates the number
1334 of ``return values''. The remainder is defined as follows:
1338 for the computation of @code{quotient = floor(x)},
1339 @code{remainder = x - quotient},
1341 for the computation of @code{quotient = floor(x,y)},
1342 @code{remainder = x - quotient*y},
1345 and similarly for the other three operations.
1347 Each of the classes @code{cl_R}, @code{cl_RA},
1348 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1349 defines the following operations:
1352 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1353 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1354 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1355 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1356 @itemx @var{type}_div_t round2 (const @var{type}& x)
1359 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1360 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1361 defines the following operations:
1364 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1365 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1366 @cindex @code{floor2 ()}
1367 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1368 @cindex @code{ceiling2 ()}
1369 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1370 @cindex @code{truncate2 ()}
1371 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1372 @cindex @code{round2 ()}
1375 Sometimes, one wants the quotient as a floating-point number (of the
1376 same format as the argument, if the argument is a float) instead of as
1377 an integer. The prefix @samp{f} indicates this.
1380 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1381 defines the following operations:
1384 @item @var{type} ffloor (const @var{type}& x)
1385 @cindex @code{ffloor ()}
1386 @itemx @var{type} fceiling (const @var{type}& x)
1387 @cindex @code{fceiling ()}
1388 @itemx @var{type} ftruncate (const @var{type}& x)
1389 @cindex @code{ftruncate ()}
1390 @itemx @var{type} fround (const @var{type}& x)
1391 @cindex @code{fround ()}
1394 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1396 The class @code{cl_R} defines the following operations:
1399 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1400 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1401 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1402 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1405 These functions also exist in versions which return both the quotient
1406 and the remainder. The suffix @samp{2} indicates this.
1409 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1410 defines the following operations:
1411 @cindex @code{cl_F_fdiv_t}
1412 @cindex @code{cl_SF_fdiv_t}
1413 @cindex @code{cl_FF_fdiv_t}
1414 @cindex @code{cl_DF_fdiv_t}
1415 @cindex @code{cl_LF_fdiv_t}
1418 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1419 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1420 @cindex @code{ffloor2 ()}
1421 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1422 @cindex @code{fceiling2 ()}
1423 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1424 @cindex @code{ftruncate2 ()}
1425 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1426 @cindex @code{fround2 ()}
1428 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1429 @cindex @code{cl_R_fdiv_t}
1431 The class @code{cl_R} defines the following operations:
1434 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1435 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1436 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1437 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1438 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1441 Other applications need only the remainder of a division.
1442 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1443 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1444 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1448 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1450 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1453 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1454 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1455 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1457 The classes @code{cl_R}, @code{cl_I} define the following operations:
1460 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1461 @cindex @code{mod ()}
1462 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1463 @cindex @code{rem ()}
1470 Each of the classes @code{cl_R},
1471 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1472 defines the following operation:
1475 @item @var{type} sqrt (const @var{type}& x)
1476 @cindex @code{sqrt ()}
1477 @code{x} must be >= 0. This function returns the square root of @code{x},
1478 normalized to be >= 0. If @code{x} is the square of a rational number,
1479 @code{sqrt(x)} will be a rational number, else it will return a
1480 floating-point approximation.
1483 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1486 @item bool sqrtp (const @var{type}& x, @var{type}* root)
1487 @cindex @code{sqrtp ()}
1488 This tests whether @code{x} is a perfect square. If so, it returns true
1489 and the exact square root in @code{*root}, else it returns false.
1492 Furthermore, for integers, similarly:
1495 @item bool isqrt (const @var{type}& x, @var{type}* root)
1496 @cindex @code{isqrt ()}
1497 @code{x} should be >= 0. This function sets @code{*root} to
1498 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1499 the boolean value @code{(expt(*root,2) == x)}.
1502 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1503 define the following operation:
1506 @item bool rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1507 @cindex @code{rootp ()}
1508 @code{x} must be >= 0. @code{n} must be > 0.
1509 This tests whether @code{x} is an @code{n}th power of a rational number.
1510 If so, it returns true and the exact root in @code{*root}, else it returns
1514 The only square root function which accepts negative numbers is the one
1515 for class @code{cl_N}:
1518 @item cl_N sqrt (const cl_N& z)
1519 @cindex @code{sqrt ()}
1520 Returns the square root of @code{z}, as defined by the formula
1521 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1522 or to a complex number are done if necessary. The range of the result is the
1523 right half plane @code{realpart(sqrt(z)) >= 0}
1524 including the positive imaginary axis and 0, but excluding
1525 the negative imaginary axis.
1526 The result is an exact number only if @code{z} is an exact number.
1530 @node Transcendental functions
1531 @section Transcendental functions
1532 @cindex transcendental functions
1534 The transcendental functions return an exact result if the argument
1535 is exact and the result is exact as well. Otherwise they must return
1536 inexact numbers even if the argument is exact.
1537 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1541 * Exponential and logarithmic functions::
1542 * Trigonometric functions::
1543 * Hyperbolic functions::
1548 @node Exponential and logarithmic functions
1549 @subsection Exponential and logarithmic functions
1552 @item cl_R exp (const cl_R& x)
1553 @cindex @code{exp ()}
1554 @itemx cl_N exp (const cl_N& x)
1555 Returns the exponential function of @code{x}. This is @code{e^x} where
1556 @code{e} is the base of the natural logarithms. The range of the result
1557 is the entire complex plane excluding 0.
1559 @item cl_R ln (const cl_R& x)
1560 @cindex @code{ln ()}
1561 @code{x} must be > 0. Returns the (natural) logarithm of x.
1563 @item cl_N log (const cl_N& x)
1564 @cindex @code{log ()}
1565 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1566 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1567 The range of the result is the strip in the complex plane
1568 @code{-pi < imagpart(log(x)) <= pi}.
1570 @item cl_R phase (const cl_N& x)
1571 @cindex @code{phase ()}
1572 Returns the angle part of @code{x} in its polar representation as a
1573 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1574 This is also the imaginary part of @code{log(x)}.
1575 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1576 The result will be an exact number only if @code{zerop(x)} or
1577 if @code{x} is real and positive.
1579 @item cl_R log (const cl_R& a, const cl_R& b)
1580 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1581 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1582 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1585 @item cl_N log (const cl_N& a, const cl_N& b)
1586 Returns the logarithm of @code{a} with respect to base @code{b}.
1587 @code{log(a,b) = log(a)/log(b)}.
1589 @item cl_N expt (const cl_N& x, const cl_N& y)
1590 @cindex @code{expt ()}
1591 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1594 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1597 @item cl_F exp1 (float_format_t f)
1598 @cindex @code{exp1 ()}
1599 Returns e as a float of format @code{f}.
1601 @item cl_F exp1 (const cl_F& y)
1602 Returns e in the float format of @code{y}.
1604 @item cl_F exp1 (void)
1605 Returns e as a float of format @code{default_float_format}.
1609 @node Trigonometric functions
1610 @subsection Trigonometric functions
1613 @item cl_R sin (const cl_R& x)
1614 @cindex @code{sin ()}
1615 Returns @code{sin(x)}. The range of the result is the interval
1616 @code{-1 <= sin(x) <= 1}.
1618 @item cl_N sin (const cl_N& z)
1619 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1621 @item cl_R cos (const cl_R& x)
1622 @cindex @code{cos ()}
1623 Returns @code{cos(x)}. The range of the result is the interval
1624 @code{-1 <= cos(x) <= 1}.
1626 @item cl_N cos (const cl_N& x)
1627 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1629 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1630 @cindex @code{cos_sin_t}
1631 @itemx cos_sin_t cos_sin (const cl_R& x)
1632 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1633 @cindex @code{cos_sin ()}
1634 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1635 hold only approximately.
1637 @item cl_R tan (const cl_R& x)
1638 @cindex @code{tan ()}
1639 @itemx cl_N tan (const cl_N& x)
1640 Returns @code{tan(x) = sin(x)/cos(x)}.
1642 @item cl_N cis (const cl_R& x)
1643 @cindex @code{cis ()}
1644 @itemx cl_N cis (const cl_N& x)
1645 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1646 @code{e^(i*x) = cos(x) + i*sin(x)}.
1649 @cindex @code{asin ()}
1650 @item cl_N asin (const cl_N& z)
1651 Returns @code{arcsin(z)}. This is defined as
1652 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1653 @code{arcsin(-z) = -arcsin(z)}.
1654 The range of the result is the strip in the complex domain
1655 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1656 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1657 with @code{realpart = pi/2} and @code{imagpart > 0}.
1659 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1663 @item cl_N acos (const cl_N& z)
1664 @cindex @code{acos ()}
1665 Returns @code{arccos(z)}. This is defined as
1666 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1669 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1671 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1672 The range of the result is the strip in the complex domain
1673 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1674 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1675 with @code{realpart = pi} and @code{imagpart > 0}.
1677 Proof: This follows from the results about arcsin.
1681 @cindex @code{atan ()}
1682 @item cl_R atan (const cl_R& x, const cl_R& y)
1683 Returns the angle of the polar representation of the complex number
1684 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1685 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1686 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1687 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1688 with reversed order of arguments.
1690 @item cl_R atan (const cl_R& x)
1691 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1692 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1693 will be an exact number only if @code{x} is the exact @code{0}.
1695 @item cl_N atan (const cl_N& z)
1696 Returns @code{arctan(z)}. This is defined as
1697 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1698 @code{arctan(-z) = -arctan(z)}. The range of the result is
1699 the strip in the complex domain
1700 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1701 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1702 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1704 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1710 @cindex Archimedes' constant
1711 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1714 @item cl_F pi (float_format_t f)
1715 @cindex @code{pi ()}
1716 Returns pi as a float of format @code{f}.
1718 @item cl_F pi (const cl_F& y)
1719 Returns pi in the float format of @code{y}.
1721 @item cl_F pi (void)
1722 Returns pi as a float of format @code{default_float_format}.
1726 @node Hyperbolic functions
1727 @subsection Hyperbolic functions
1730 @item cl_R sinh (const cl_R& x)
1731 @cindex @code{sinh ()}
1732 Returns @code{sinh(x)}.
1734 @item cl_N sinh (const cl_N& z)
1735 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1737 @item cl_R cosh (const cl_R& x)
1738 @cindex @code{cosh ()}
1739 Returns @code{cosh(x)}. The range of the result is the interval
1740 @code{cosh(x) >= 1}.
1742 @item cl_N cosh (const cl_N& z)
1743 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1745 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1746 @cindex @code{cosh_sinh_t}
1747 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1748 @cindex @code{cosh_sinh ()}
1749 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1750 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1751 hold only approximately.
1753 @item cl_R tanh (const cl_R& x)
1754 @cindex @code{tanh ()}
1755 @itemx cl_N tanh (const cl_N& x)
1756 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1758 @item cl_N asinh (const cl_N& z)
1759 @cindex @code{asinh ()}
1760 Returns @code{arsinh(z)}. This is defined as
1761 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1762 @code{arsinh(-z) = -arsinh(z)}.
1764 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1765 Actually, z+sqrt(1+z^2) can never be real and <0, so
1766 -pi < imagpart(arsinh(z)) < pi.
1767 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1768 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1770 The range of the result is the strip in the complex domain
1771 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1772 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1773 with @code{imagpart = pi/2} and @code{realpart < 0}.
1775 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1776 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1777 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1778 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1779 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1780 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1781 If y >= 1, the imagpart is pi/2 and the realpart is
1782 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1785 Moreover, if z is in Range(sqrt),
1786 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1787 (for a proof, see file src/cl_C_asinh.cc).
1790 @item cl_N acosh (const cl_N& z)
1791 @cindex @code{acosh ()}
1792 Returns @code{arcosh(z)}. This is defined as
1793 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1794 The range of the result is the half-strip in the complex domain
1795 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1796 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1798 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1799 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1800 If z is in Range(sqrt), we have
1801 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1802 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1804 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1805 and since the imagpart of both expressions is > -pi, <= pi
1806 ==> arcosh(z) = log(z+sqrt(z^2-1))
1807 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1808 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1809 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1810 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1811 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1813 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1814 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1815 = x^2 + y^2 + sqrt(u^2+v^2)
1820 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1821 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1822 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1823 Otherwise, -z is in Range(sqrt).
1824 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1825 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1826 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1827 and this has realpart > 0.
1828 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1829 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1830 has realpart = 0 and imagpart > 0.
1831 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1832 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1833 This has realpart >= 0 and imagpart = pi.
1836 @item cl_N atanh (const cl_N& z)
1837 @cindex @code{atanh ()}
1838 Returns @code{artanh(z)}. This is defined as
1839 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1840 @code{artanh(-z) = -artanh(z)}. The range of the result is
1841 the strip in the complex domain
1842 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1843 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1844 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1846 Proof: Write z = x+iy. Examine
1847 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1849 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1850 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1851 |x| < 1 ==> imagpart = 0
1854 = (atan(1+x,y) - atan(1-x,-y))/2
1855 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1856 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1857 > (pi - pi/2 - pi/2 )/2 = 0
1858 and (1+x)/y > (1-x)/y
1859 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1860 ==> imagpart < pi/2.
1861 Hence 0 < imagpart < pi/2.
1863 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1869 @subsection Euler gamma
1870 @cindex Euler's constant
1872 Euler's constant C = 0.577@dots{} is returned by the following functions:
1875 @item cl_F eulerconst (float_format_t f)
1876 @cindex @code{eulerconst ()}
1877 Returns Euler's constant as a float of format @code{f}.
1879 @item cl_F eulerconst (const cl_F& y)
1880 Returns Euler's constant in the float format of @code{y}.
1882 @item cl_F eulerconst (void)
1883 Returns Euler's constant as a float of format @code{default_float_format}.
1886 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1887 @cindex Catalan's constant
1890 @item cl_F catalanconst (float_format_t f)
1891 @cindex @code{catalanconst ()}
1892 Returns Catalan's constant as a float of format @code{f}.
1894 @item cl_F catalanconst (const cl_F& y)
1895 Returns Catalan's constant in the float format of @code{y}.
1897 @item cl_F catalanconst (void)
1898 Returns Catalan's constant as a float of format @code{default_float_format}.
1903 @subsection Riemann zeta
1904 @cindex Riemann's zeta
1906 Riemann's zeta function at an integral point @code{s>1} is returned by the
1907 following functions:
1910 @item cl_F zeta (int s, float_format_t f)
1911 @cindex @code{zeta ()}
1912 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1914 @item cl_F zeta (int s, const cl_F& y)
1915 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1917 @item cl_F zeta (int s)
1918 Returns Riemann's zeta function at @code{s} as a float of format
1919 @code{default_float_format}.
1923 @node Functions on integers
1924 @section Functions on integers
1927 * Logical functions::
1928 * Number theoretic functions::
1929 * Combinatorial functions::
1932 @node Logical functions
1933 @subsection Logical functions
1935 Integers, when viewed as in two's complement notation, can be thought as
1936 infinite bit strings where the bits' values eventually are constant.
1943 The logical operations view integers as such bit strings and operate
1944 on each of the bit positions in parallel.
1947 @item cl_I lognot (const cl_I& x)
1948 @cindex @code{lognot ()}
1949 @itemx cl_I operator ~ (const cl_I& x)
1950 @cindex @code{operator ~ ()}
1951 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1953 @item cl_I logand (const cl_I& x, const cl_I& y)
1954 @cindex @code{logand ()}
1955 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1956 @cindex @code{operator & ()}
1957 Logical and, like @code{x & y} in C.
1959 @item cl_I logior (const cl_I& x, const cl_I& y)
1960 @cindex @code{logior ()}
1961 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1962 @cindex @code{operator | ()}
1963 Logical (inclusive) or, like @code{x | y} in C.
1965 @item cl_I logxor (const cl_I& x, const cl_I& y)
1966 @cindex @code{logxor ()}
1967 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1968 @cindex @code{operator ^ ()}
1969 Exclusive or, like @code{x ^ y} in C.
1971 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1972 @cindex @code{logeqv ()}
1973 Bitwise equivalence, like @code{~(x ^ y)} in C.
1975 @item cl_I lognand (const cl_I& x, const cl_I& y)
1976 @cindex @code{lognand ()}
1977 Bitwise not and, like @code{~(x & y)} in C.
1979 @item cl_I lognor (const cl_I& x, const cl_I& y)
1980 @cindex @code{lognor ()}
1981 Bitwise not or, like @code{~(x | y)} in C.
1983 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1984 @cindex @code{logandc1 ()}
1985 Logical and, complementing the first argument, like @code{~x & y} in C.
1987 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1988 @cindex @code{logandc2 ()}
1989 Logical and, complementing the second argument, like @code{x & ~y} in C.
1991 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1992 @cindex @code{logorc1 ()}
1993 Logical or, complementing the first argument, like @code{~x | y} in C.
1995 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1996 @cindex @code{logorc2 ()}
1997 Logical or, complementing the second argument, like @code{x | ~y} in C.
2000 These operations are all available though the function
2002 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
2003 @cindex @code{boole ()}
2005 where @code{op} must have one of the 16 values (each one stands for a function
2006 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
2007 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
2008 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
2009 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
2010 @code{boole_orc1}, @code{boole_orc2}.
2011 @cindex @code{boole_clr}
2012 @cindex @code{boole_set}
2013 @cindex @code{boole_1}
2014 @cindex @code{boole_2}
2015 @cindex @code{boole_c1}
2016 @cindex @code{boole_c2}
2017 @cindex @code{boole_and}
2018 @cindex @code{boole_xor}
2019 @cindex @code{boole_eqv}
2020 @cindex @code{boole_nand}
2021 @cindex @code{boole_nor}
2022 @cindex @code{boole_andc1}
2023 @cindex @code{boole_andc2}
2024 @cindex @code{boole_orc1}
2025 @cindex @code{boole_orc2}
2028 Other functions that view integers as bit strings:
2031 @item bool logtest (const cl_I& x, const cl_I& y)
2032 @cindex @code{logtest ()}
2033 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
2034 @code{logand(x,y) != 0}.
2036 @item bool logbitp (const cl_I& n, const cl_I& x)
2037 @cindex @code{logbitp ()}
2038 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
2039 Bit 0 is the least significant bit.
2041 @item uintC logcount (const cl_I& x)
2042 @cindex @code{logcount ()}
2043 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
2044 the number of zero bits in @code{x}, if @code{x} < 0.
2047 The following functions operate on intervals of bits in integers.
2050 struct cl_byte @{ uintC size; uintC position; @};
2052 @cindex @code{cl_byte}
2053 represents the bit interval containing the bits
2054 @code{position}@dots{}@code{position+size-1} of an integer.
2055 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
2058 @item cl_I ldb (const cl_I& n, const cl_byte& b)
2059 @cindex @code{ldb ()}
2060 extracts the bits of @code{n} described by the bit interval @code{b}
2061 and returns them as a nonnegative integer with @code{b.size} bits.
2063 @item bool ldb_test (const cl_I& n, const cl_byte& b)
2064 @cindex @code{ldb_test ()}
2065 Returns true if some bit described by the bit interval @code{b} is set in
2068 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2069 @cindex @code{dpb ()}
2070 Returns @code{n}, with the bits described by the bit interval @code{b}
2071 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
2072 @code{newbyte} are relevant.
2075 The functions @code{ldb} and @code{dpb} implicitly shift. The following
2076 functions are their counterparts without shifting:
2079 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
2080 @cindex @code{mask_field ()}
2081 returns an integer with the bits described by the bit interval @code{b}
2082 copied from the corresponding bits in @code{n}, the other bits zero.
2084 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2085 @cindex @code{deposit_field ()}
2086 returns an integer where the bits described by the bit interval @code{b}
2087 come from @code{newbyte} and the other bits come from @code{n}.
2090 The following relations hold:
2094 @code{ldb (n, b) = mask_field(n, b) >> b.position},
2096 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
2098 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
2101 The following operations on integers as bit strings are efficient shortcuts
2102 for common arithmetic operations:
2105 @item bool oddp (const cl_I& x)
2106 @cindex @code{oddp ()}
2107 Returns true if the least significant bit of @code{x} is 1. Equivalent to
2108 @code{mod(x,2) != 0}.
2110 @item bool evenp (const cl_I& x)
2111 @cindex @code{evenp ()}
2112 Returns true if the least significant bit of @code{x} is 0. Equivalent to
2113 @code{mod(x,2) == 0}.
2115 @item cl_I operator << (const cl_I& x, const cl_I& n)
2116 @cindex @code{operator << ()}
2117 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
2118 Equivalent to @code{x * expt(2,n)}.
2120 @item cl_I operator >> (const cl_I& x, const cl_I& n)
2121 @cindex @code{operator >> ()}
2122 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
2123 Bits shifted out to the right are thrown away.
2124 Equivalent to @code{floor(x / expt(2,n))}.
2126 @item cl_I ash (const cl_I& x, const cl_I& y)
2127 @cindex @code{ash ()}
2128 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
2129 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
2130 returns @code{floor(x * expt(2,y))}.
2132 @item uintC integer_length (const cl_I& x)
2133 @cindex @code{integer_length ()}
2134 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
2135 in two's complement notation. This is the smallest n >= 0 such that
2136 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
2139 @item uintC ord2 (const cl_I& x)
2140 @cindex @code{ord2 ()}
2141 @code{x} must be non-zero. This function returns the number of 0 bits at the
2142 right of @code{x} in two's complement notation. This is the largest n >= 0
2143 such that 2^n divides @code{x}.
2145 @item uintC power2p (const cl_I& x)
2146 @cindex @code{power2p ()}
2147 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
2148 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
2149 (See also the function @code{logp}.)
2153 @node Number theoretic functions
2154 @subsection Number theoretic functions
2157 @item uint32 gcd (unsigned long a, unsigned long b)
2158 @cindex @code{gcd ()}
2159 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
2160 This function returns the greatest common divisor of @code{a} and @code{b},
2161 normalized to be >= 0.
2163 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
2164 @cindex @code{xgcd ()}
2165 This function (``extended gcd'') returns the greatest common divisor @code{g} of
2166 @code{a} and @code{b} and at the same time the representation of @code{g}
2167 as an integral linear combination of @code{a} and @code{b}:
2168 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
2169 @code{u} and @code{v} will be normalized to be of smallest possible absolute
2170 value, in the following sense: If @code{a} and @code{b} are non-zero, and
2171 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
2172 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
2174 @item cl_I lcm (const cl_I& a, const cl_I& b)
2175 @cindex @code{lcm ()}
2176 This function returns the least common multiple of @code{a} and @code{b},
2177 normalized to be >= 0.
2179 @item bool logp (const cl_I& a, const cl_I& b, cl_RA* l)
2180 @cindex @code{logp ()}
2181 @itemx bool logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2182 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2183 rational number, this function returns true and sets *l = log(a,b), else
2186 @item int jacobi (signed long a, signed long b)
2187 @cindex @code{jacobi()}
2188 @itemx int jacobi (const cl_I& a, const cl_I& b)
2189 Returns the Jacobi symbol
2191 $\left({a\over b}\right)$,
2196 @code{a,b} must be integers, @code{b>0} and odd. The result is 0
2199 @item bool isprobprime (const cl_I& n)
2201 @cindex @code{isprobprime()}
2202 Returns true if @code{n} is a small prime or passes the Miller-Rabin
2203 primality test. The probability of a false positive is 1:10^30.
2205 @item cl_I nextprobprime (const cl_R& x)
2206 @cindex @code{nextprobprime()}
2207 Returns the smallest probable prime >=@code{x}.
2211 @node Combinatorial functions
2212 @subsection Combinatorial functions
2215 @item cl_I factorial (uintL n)
2216 @cindex @code{factorial ()}
2217 @code{n} must be a small integer >= 0. This function returns the factorial
2218 @code{n}! = @code{1*2*@dots{}*n}.
2220 @item cl_I doublefactorial (uintL n)
2221 @cindex @code{doublefactorial ()}
2222 @code{n} must be a small integer >= 0. This function returns the
2223 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2224 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2226 @item cl_I binomial (uintL n, uintL k)
2227 @cindex @code{binomial ()}
2228 @code{n} and @code{k} must be small integers >= 0. This function returns the
2229 binomial coefficient
2231 ${n \choose k} = {n! \over k! (n-k)!}$
2234 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2236 for 0 <= k <= n, 0 else.
2240 @node Functions on floating-point numbers
2241 @section Functions on floating-point numbers
2243 Recall that a floating-point number consists of a sign @code{s}, an
2244 exponent @code{e} and a mantissa @code{m}. The value of the number is
2245 @code{(-1)^s * 2^e * m}.
2248 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2249 defines the following operations.
2252 @item @var{type} scale_float (const @var{type}& x, sintC delta)
2253 @cindex @code{scale_float ()}
2254 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2255 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2256 because it copies @code{x} and modifies the exponent.
2259 The following functions provide an abstract interface to the underlying
2260 representation of floating-point numbers.
2263 @item sintE float_exponent (const @var{type}& x)
2264 @cindex @code{float_exponent ()}
2265 Returns the exponent @code{e} of @code{x}.
2266 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2267 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2269 @item sintL float_radix (const @var{type}& x)
2270 @cindex @code{float_radix ()}
2271 Returns the base of the floating-point representation. This is always @code{2}.
2273 @item @var{type} float_sign (const @var{type}& x)
2274 @cindex @code{float_sign ()}
2275 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2276 @code{x} >= 0, -1 for @code{x} < 0.
2278 @item uintC float_digits (const @var{type}& x)
2279 @cindex @code{float_digits ()}
2280 Returns the number of mantissa bits in the floating-point representation
2281 of @code{x}, including the hidden bit. The value only depends on the type
2282 of @code{x}, not on its value.
2284 @item uintC float_precision (const @var{type}& x)
2285 @cindex @code{float_precision ()}
2286 Returns the number of significant mantissa bits in the floating-point
2287 representation of @code{x}. Since denormalized numbers are not supported,
2288 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2292 The complete internal representation of a float is encoded in the type
2293 @cindex @code{decoded_float}
2294 @cindex @code{decoded_sfloat}
2295 @cindex @code{decoded_ffloat}
2296 @cindex @code{decoded_dfloat}
2297 @cindex @code{decoded_lfloat}
2298 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2299 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2301 struct decoded_@var{type}float @{
2302 @var{type} mantissa; cl_I exponent; @var{type} sign;
2306 and returned by the function
2309 @item decoded_@var{type}float decode_float (const @var{type}& x)
2310 @cindex @code{decode_float ()}
2311 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2312 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2313 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2314 @code{e} is the same as returned by the function @code{float_exponent}.
2317 A complete decoding in terms of integers is provided as type
2318 @cindex @code{cl_idecoded_float}
2320 struct cl_idecoded_float @{
2321 cl_I mantissa; cl_I exponent; cl_I sign;
2324 by the following function:
2327 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2328 @cindex @code{integer_decode_float ()}
2329 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2330 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2331 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2332 WARNING: The exponent @code{e} is not the same as the one returned by
2333 the functions @code{decode_float} and @code{float_exponent}.
2336 Some other function, implemented only for class @code{cl_F}:
2339 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2340 @cindex @code{float_sign ()}
2341 This returns a floating point number whose precision and absolute value
2342 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2343 zero, it is treated as positive. Same for @code{y}.
2347 @node Conversion functions
2348 @section Conversion functions
2352 * Conversion to floating-point numbers::
2353 * Conversion to rational numbers::
2356 @node Conversion to floating-point numbers
2357 @subsection Conversion to floating-point numbers
2359 The type @code{float_format_t} describes a floating-point format.
2360 @cindex @code{float_format_t}
2363 @item float_format_t float_format (uintE n)
2364 @cindex @code{float_format ()}
2365 Returns the smallest float format which guarantees at least @code{n}
2366 decimal digits in the mantissa (after the decimal point).
2368 @item float_format_t float_format (const cl_F& x)
2369 Returns the floating point format of @code{x}.
2371 @item float_format_t default_float_format
2372 @cindex @code{default_float_format}
2373 Global variable: the default float format used when converting rational numbers
2377 To convert a real number to a float, each of the types
2378 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2379 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2380 defines the following operations:
2383 @item cl_F cl_float (const @var{type}&x, float_format_t f)
2384 @cindex @code{cl_float ()}
2385 Returns @code{x} as a float of format @code{f}.
2386 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2387 Returns @code{x} in the float format of @code{y}.
2388 @item cl_F cl_float (const @var{type}&x)
2389 Returns @code{x} as a float of format @code{default_float_format} if
2390 it is an exact number, or @code{x} itself if it is already a float.
2393 Of course, converting a number to a float can lose precision.
2395 Every floating-point format has some characteristic numbers:
2398 @item cl_F most_positive_float (float_format_t f)
2399 @cindex @code{most_positive_float ()}
2400 Returns the largest (most positive) floating point number in float format @code{f}.
2402 @item cl_F most_negative_float (float_format_t f)
2403 @cindex @code{most_negative_float ()}
2404 Returns the smallest (most negative) floating point number in float format @code{f}.
2406 @item cl_F least_positive_float (float_format_t f)
2407 @cindex @code{least_positive_float ()}
2408 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2409 in float format @code{f}.
2411 @item cl_F least_negative_float (float_format_t f)
2412 @cindex @code{least_negative_float ()}
2413 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2414 in float format @code{f}.
2416 @item cl_F float_epsilon (float_format_t f)
2417 @cindex @code{float_epsilon ()}
2418 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2420 @item cl_F float_negative_epsilon (float_format_t f)
2421 @cindex @code{float_negative_epsilon ()}
2422 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2426 @node Conversion to rational numbers
2427 @subsection Conversion to rational numbers
2429 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2430 defines the following operation:
2433 @item cl_RA rational (const @var{type}& x)
2434 @cindex @code{rational ()}
2435 Returns the value of @code{x} as an exact number. If @code{x} is already
2436 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2437 the value is a rational number whose denominator is a power of 2.
2440 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2444 @item cl_RA rationalize (const cl_R& x)
2445 @cindex @code{rationalize ()}
2446 If @code{x} is a floating-point number, it actually represents an interval
2447 of real numbers, and this function returns the rational number with
2448 smallest denominator (and smallest numerator, in magnitude)
2449 which lies in this interval.
2450 If @code{x} is already an exact number, this function returns @code{x}.
2453 If @code{x} is any float, one has
2457 @code{cl_float(rational(x),x) = x}
2459 @code{cl_float(rationalize(x),x) = x}
2463 @node Random number generators
2464 @section Random number generators
2467 A random generator is a machine which produces (pseudo-)random numbers.
2468 The include file @code{<cln/random.h>} defines a class @code{random_state}
2469 which contains the state of a random generator. If you make a copy
2470 of the random number generator, the original one and the copy will produce
2471 the same sequence of random numbers.
2473 The following functions return (pseudo-)random numbers in different formats.
2474 Calling one of these modifies the state of the random number generator in
2475 a complicated but deterministic way.
2478 @cindex @code{random_state}
2479 @cindex @code{default_random_state}
2481 random_state default_random_state
2483 contains a default random number generator. It is used when the functions
2484 below are called without @code{random_state} argument.
2487 @item uint32 random32 (random_state& randomstate)
2488 @itemx uint32 random32 ()
2489 @cindex @code{random32 ()}
2490 Returns a random unsigned 32-bit number. All bits are equally random.
2492 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2493 @itemx cl_I random_I (const cl_I& n)
2494 @cindex @code{random_I ()}
2495 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2496 in the range @code{0 <= x < n}.
2498 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2499 @itemx cl_F random_F (const cl_F& n)
2500 @cindex @code{random_F ()}
2501 @code{n} must be a float > 0. This function returns a random floating-point
2502 number of the same format as @code{n} in the range @code{0 <= x < n}.
2504 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2505 @itemx cl_R random_R (const cl_R& n)
2506 @cindex @code{random_R ()}
2507 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2508 if @code{n} is a float.
2512 @node Modifying operators
2513 @section Modifying operators
2514 @cindex modifying operators
2516 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2517 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2520 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2521 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2524 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2525 @cindex @code{operator += ()}
2526 @itemx @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 /= ()}
2534 For the class @code{cl_I}:
2537 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2538 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2539 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2540 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2541 @cindex @code{operator &= ()}
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 >>= ()}
2552 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2553 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2556 @item @var{type}& operator ++ (@var{type}& x)
2557 @cindex @code{operator ++ ()}
2558 The prefix operator @code{++x}.
2560 @item void operator ++ (@var{type}& x, int)
2561 The postfix operator @code{x++}.
2563 @item @var{type}& operator -- (@var{type}& x)
2564 @cindex @code{operator -- ()}
2565 The prefix operator @code{--x}.
2567 @item void operator -- (@var{type}& x, int)
2568 The postfix operator @code{x--}.
2571 Note that by using these modifying operators, you don't gain efficiency:
2572 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2577 @chapter Input/Output
2578 @cindex Input/Output
2581 * Internal and printed representation::
2583 * Output functions::
2586 @node Internal and printed representation
2587 @section Internal and printed representation
2588 @cindex representation
2590 All computations deal with the internal representations of the numbers.
2592 Every number has an external representation as a sequence of ASCII characters.
2593 Several external representations may denote the same number, for example,
2594 "20.0" and "20.000".
2596 Converting an internal to an external representation is called ``printing'',
2598 converting an external to an internal representation is called ``reading''.
2600 In CLN, it is always true that conversion of an internal to an external
2601 representation and then back to an internal representation will yield the
2602 same internal representation. Symbolically: @code{read(print(x)) == x}.
2603 This is called ``print-read consistency''.
2605 Different types of numbers have different external representations (case
2610 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2611 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2612 for decimal integers
2613 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2615 @item Rational numbers
2616 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2617 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2620 @item Floating-point numbers
2621 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2622 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2623 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2624 of the form _@var{prec} may be appended. There must be at least
2625 one digit in the non-exponent part. The exponent has the syntax
2626 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2627 The exponent marker is
2631 @samp{s} for short-floats,
2633 @samp{f} for single-floats,
2635 @samp{d} for double-floats,
2637 @samp{L} for long-floats,
2640 or @samp{e}, which denotes a default float format. The precision specifying
2641 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2642 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2643 function @samp{float_format}.
2645 @item Complex numbers
2646 External representation:
2649 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2650 if @var{imagpart} is negative, its printed representation begins with
2651 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2652 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2653 is rational and the rational number's base is >18, because the @samp{i}
2654 is then read as a digit.
2656 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2661 @node Input functions
2662 @section Input functions
2664 Including @code{<cln/io.h>} defines flexible input functions:
2667 @item cl_N read_complex (std::istream& stream, const cl_read_flags& flags)
2668 @itemx cl_R read_real (std::istream& stream, const cl_read_flags& flags)
2669 @itemx cl_F read_float (std::istream& stream, const cl_read_flags& flags)
2670 @itemx cl_RA read_rational (std::istream& stream, const cl_read_flags& flags)
2671 @itemx cl_I read_integer (std::istream& stream, const cl_read_flags& flags)
2672 Reads a number from @code{stream}. The @code{flags} are parameters which
2673 affect the input syntax. Whitespace before the number is silently skipped.
2675 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2676 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2677 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2678 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2679 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2680 Reads a number from a string in memory. The @code{flags} are parameters which
2681 affect the input syntax. The string starts at @code{string} and ends at
2682 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2683 @code{NULL}, denoting the entire string, i.e. equivalent to
2684 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2685 @code{NULL}, the string in memory must contain exactly one number and nothing
2686 more, else an exception will be thrown. If @code{end_of_parse}
2687 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2688 the last parsed character (i.e. @code{string_limit} if nothing came after
2689 the number). Whitespace is not allowed.
2692 The structure @code{cl_read_flags} contains the following fields:
2695 @item cl_read_syntax_t syntax
2696 The possible results of the read operation. Possible values are
2697 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2698 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2699 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2701 @item cl_read_lsyntax_t lsyntax
2702 Specifies the language-dependent syntax variant for the read operation.
2706 @item lsyntax_standard
2707 accept standard algebraic notation only, no complex numbers,
2708 @item lsyntax_algebraic
2709 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2710 @item lsyntax_commonlisp
2711 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2712 hexadecimal numbers,
2713 @code{#@var{base}R} for rational numbers in a given base,
2714 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2716 accept all of these extensions.
2719 @item unsigned int rational_base
2720 The base in which rational numbers are read.
2722 @item float_format_t float_flags.default_float_format
2723 The float format used when reading floats with exponent marker @samp{e}.
2725 @item float_format_t float_flags.default_lfloat_format
2726 The float format used when reading floats with exponent marker @samp{l}.
2728 @item bool float_flags.mantissa_dependent_float_format
2729 When this flag is true, floats specified with more digits than corresponding
2730 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2731 precision corresponding to their number of significant digits.
2735 @node Output functions
2736 @section Output functions
2738 Including @code{<cln/io.h>} defines a number of simple output functions
2739 that write to @code{std::ostream&}:
2742 @item void fprintchar (std::ostream& stream, char c)
2743 Prints the character @code{x} literally on the @code{stream}.
2745 @item void fprint (std::ostream& stream, const char * string)
2746 Prints the @code{string} literally on the @code{stream}.
2748 @item void fprintdecimal (std::ostream& stream, int x)
2749 @itemx void fprintdecimal (std::ostream& stream, const cl_I& x)
2750 Prints the integer @code{x} in decimal on the @code{stream}.
2752 @item void fprintbinary (std::ostream& stream, const cl_I& x)
2753 Prints the integer @code{x} in binary (base 2, without prefix)
2754 on the @code{stream}.
2756 @item void fprintoctal (std::ostream& stream, const cl_I& x)
2757 Prints the integer @code{x} in octal (base 8, without prefix)
2758 on the @code{stream}.
2760 @item void fprinthexadecimal (std::ostream& stream, const cl_I& x)
2761 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2762 on the @code{stream}.
2765 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2766 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2767 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2770 @item void fprint (std::ostream& stream, const @var{type}& x)
2771 @itemx std::ostream& operator<< (std::ostream& stream, const @var{type}& x)
2772 Prints the number @code{x} on the @code{stream}. The output may depend
2773 on the global printer settings in the variable @code{default_print_flags}.
2774 The @code{ostream} flags and settings (flags, width and locale) are
2778 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2781 void print_complex (std::ostream& stream, const cl_print_flags& flags,
2783 void print_real (std::ostream& stream, const cl_print_flags& flags,
2785 void print_float (std::ostream& stream, const cl_print_flags& flags,
2787 void print_rational (std::ostream& stream, const cl_print_flags& flags,
2789 void print_integer (std::ostream& stream, const cl_print_flags& flags,
2792 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2793 parameters which affect the output.
2795 The structure type @code{cl_print_flags} contains the following fields:
2798 @item unsigned int rational_base
2799 The base in which rational numbers are printed. Default is @code{10}.
2801 @item bool rational_readably
2802 If this flag is true, rational numbers are printed with radix specifiers in
2803 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2804 prefixes, trailing dot). Default is false.
2806 @item bool float_readably
2807 If this flag is true, type specific exponent markers have precedence over 'E'.
2810 @item float_format_t default_float_format
2811 Floating point numbers of this format will be printed using the 'E' exponent
2812 marker. Default is @code{float_format_ffloat}.
2814 @item bool complex_readably
2815 If this flag is true, complex numbers will be printed using the Common Lisp
2816 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2818 @item cl_string univpoly_varname
2819 Univariate polynomials with no explicit indeterminate name will be printed
2820 using this variable name. Default is @code{"x"}.
2823 The global variable @code{default_print_flags} contains the default values,
2824 used by the function @code{fprint}.
2830 CLN has a class of abstract rings.
2838 Rings can be compared for equality:
2841 @item bool operator== (const cl_ring&, const cl_ring&)
2842 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2843 These compare two rings for equality.
2846 Given a ring @code{R}, the following members can be used.
2849 @item void R->fprint (std::ostream& stream, const cl_ring_element& x)
2850 @cindex @code{fprint ()}
2851 @itemx bool R->equal (const cl_ring_element& x, const cl_ring_element& y)
2852 @cindex @code{equal ()}
2853 @itemx cl_ring_element R->zero ()
2854 @cindex @code{zero ()}
2855 @itemx bool R->zerop (const cl_ring_element& x)
2856 @cindex @code{zerop ()}
2857 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2858 @cindex @code{plus ()}
2859 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2860 @cindex @code{minus ()}
2861 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2862 @cindex @code{uminus ()}
2863 @itemx cl_ring_element R->one ()
2864 @cindex @code{one ()}
2865 @itemx cl_ring_element R->canonhom (const cl_I& x)
2866 @cindex @code{canonhom ()}
2867 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2868 @cindex @code{mul ()}
2869 @itemx cl_ring_element R->square (const cl_ring_element& x)
2870 @cindex @code{square ()}
2871 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2872 @cindex @code{expt_pos ()}
2875 The following rings are built-in.
2878 @item cl_null_ring cl_0_ring
2879 The null ring, containing only zero.
2881 @item cl_complex_ring cl_C_ring
2882 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2884 @item cl_real_ring cl_R_ring
2885 The ring of real numbers. This corresponds to the type @code{cl_R}.
2887 @item cl_rational_ring cl_RA_ring
2888 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2890 @item cl_integer_ring cl_I_ring
2891 The ring of integers. This corresponds to the type @code{cl_I}.
2894 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2895 @code{cl_RA_ring}, @code{cl_I_ring}:
2898 @item bool instanceof (const cl_number& x, const cl_number_ring& R)
2899 @cindex @code{instanceof ()}
2900 Tests whether the given number is an element of the number ring R.
2904 @node Modular integers
2905 @chapter Modular integers
2906 @cindex modular integer
2909 * Modular integer rings::
2910 * Functions on modular integers::
2913 @node Modular integer rings
2914 @section Modular integer rings
2917 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2918 The modulus is explicitly part of every modular integer. CLN doesn't
2919 allow you to (accidentally) mix elements of different modular rings,
2920 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2921 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2922 doesn't have generic types. So one has to live with runtime checks.)
2924 The class of modular integer rings is
2932 Modular integer ring
2936 @cindex @code{cl_modint_ring}
2938 and the class of all modular integers (elements of modular integer rings) is
2946 Modular integer rings are constructed using the function
2949 @item cl_modint_ring find_modint_ring (const cl_I& N)
2950 @cindex @code{find_modint_ring ()}
2951 This function returns the modular ring @samp{Z/NZ}. It takes care
2952 of finding out about special cases of @code{N}, like powers of two
2953 and odd numbers for which Montgomery multiplication will be a win,
2954 @cindex Montgomery multiplication
2955 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2956 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2957 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2961 Modular integer rings can be compared for equality:
2964 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2965 @cindex @code{operator == ()}
2966 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2967 @cindex @code{operator != ()}
2968 These compare two modular integer rings for equality. Two different calls
2969 to @code{find_modint_ring} with the same argument necessarily return the
2970 same ring because it is memoized in the cache table.
2973 @node Functions on modular integers
2974 @section Functions on modular integers
2976 Given a modular integer ring @code{R}, the following members can be used.
2979 @item cl_I R->modulus
2980 @cindex @code{modulus}
2981 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2983 @item cl_MI R->zero()
2984 @cindex @code{zero ()}
2985 This returns @code{0 mod N}.
2987 @item cl_MI R->one()
2988 @cindex @code{one ()}
2989 This returns @code{1 mod N}.
2991 @item cl_MI R->canonhom (const cl_I& x)
2992 @cindex @code{canonhom ()}
2993 This returns @code{x mod N}.
2995 @item cl_I R->retract (const cl_MI& x)
2996 @cindex @code{retract ()}
2997 This is a partial inverse function to @code{R->canonhom}. It returns the
2998 standard representative (@code{>=0}, @code{<N}) of @code{x}.
3000 @item cl_MI R->random(random_state& randomstate)
3001 @itemx cl_MI R->random()
3002 @cindex @code{random ()}
3003 This returns a random integer modulo @code{N}.
3006 The following operations are defined on modular integers.
3009 @item cl_modint_ring x.ring ()
3010 @cindex @code{ring ()}
3011 Returns the ring to which the modular integer @code{x} belongs.
3013 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
3014 @cindex @code{operator + ()}
3015 Returns the sum of two modular integers. One of the arguments may also
3018 @item cl_MI operator- (const cl_MI&, const cl_MI&)
3019 @cindex @code{operator - ()}
3020 Returns the difference of two modular integers. One of the arguments may also
3023 @item cl_MI operator- (const cl_MI&)
3024 Returns the negative of a modular integer.
3026 @item cl_MI operator* (const cl_MI&, const cl_MI&)
3027 @cindex @code{operator * ()}
3028 Returns the product of two modular integers. One of the arguments may also
3031 @item cl_MI square (const cl_MI&)
3032 @cindex @code{square ()}
3033 Returns the square of a modular integer.
3035 @item cl_MI recip (const cl_MI& x)
3036 @cindex @code{recip ()}
3037 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
3038 must be coprime to the modulus, otherwise an error message is issued.
3040 @item cl_MI div (const cl_MI& x, const cl_MI& y)
3041 @cindex @code{div ()}
3042 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
3043 @code{y} must be coprime to the modulus, otherwise an error message is issued.
3045 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
3046 @cindex @code{expt_pos ()}
3047 @code{y} must be > 0. Returns @code{x^y}.
3049 @item cl_MI expt (const cl_MI& x, const cl_I& y)
3050 @cindex @code{expt ()}
3051 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
3052 modulus, else an error message is issued.
3054 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
3055 @cindex @code{operator << ()}
3056 Returns @code{x*2^y}.
3058 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
3059 @cindex @code{operator >> ()}
3060 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
3061 or an error message is issued.
3063 @item bool operator== (const cl_MI&, const cl_MI&)
3064 @cindex @code{operator == ()}
3065 @itemx bool operator!= (const cl_MI&, const cl_MI&)
3066 @cindex @code{operator != ()}
3067 Compares two modular integers, belonging to the same modular integer ring,
3070 @item bool zerop (const cl_MI& x)
3071 @cindex @code{zerop ()}
3072 Returns true if @code{x} is @code{0 mod N}.
3075 The following output functions are defined (see also the chapter on
3079 @item void fprint (std::ostream& stream, const cl_MI& x)
3080 @cindex @code{fprint ()}
3081 @itemx std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
3082 @cindex @code{operator << ()}
3083 Prints the modular integer @code{x} on the @code{stream}. The output may depend
3084 on the global printer settings in the variable @code{default_print_flags}.
3088 @node Symbolic data types
3089 @chapter Symbolic data types
3090 @cindex symbolic type
3092 CLN implements two symbolic (non-numeric) data types: strings and symbols.
3102 @cindex @code{cl_string}
3112 implements immutable strings.
3114 Strings are constructed through the following constructors:
3117 @item cl_string (const char * s)
3118 Returns an immutable copy of the (zero-terminated) C string @code{s}.
3120 @item cl_string (const char * ptr, unsigned long len)
3121 Returns an immutable copy of the @code{len} characters at
3122 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
3125 The following functions are available on strings:
3129 Assignment from @code{cl_string} and @code{const char *}.
3132 @cindex @code{size()}
3134 @cindex @code{strlen ()}
3135 Returns the length of the string @code{s}.
3138 @cindex @code{operator [] ()}
3139 Returns the @code{i}th character of the string @code{s}.
3140 @code{i} must be in the range @code{0 <= i < s.size()}.
3142 @item bool equal (const cl_string& s1, const cl_string& s2)
3143 @cindex @code{equal ()}
3144 Compares two strings for equality. One of the arguments may also be a
3145 plain @code{const char *}.
3151 @cindex @code{cl_symbol}
3153 Symbols are uniquified strings: all symbols with the same name are shared.
3154 This means that comparison of two symbols is fast (effectively just a pointer
3155 comparison), whereas comparison of two strings must in the worst case walk
3156 both strings until their end.
3157 Symbols are used, for example, as tags for properties, as names of variables
3158 in polynomial rings, etc.
3160 Symbols are constructed through the following constructor:
3163 @item cl_symbol (const cl_string& s)
3164 Looks up or creates a new symbol with a given name.
3167 The following operations are available on symbols:
3170 @item cl_string (const cl_symbol& sym)
3171 Conversion to @code{cl_string}: Returns the string which names the symbol
3174 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
3175 @cindex @code{equal ()}
3176 Compares two symbols for equality. This is very fast.
3180 @node Univariate polynomials
3181 @chapter Univariate polynomials
3183 @cindex univariate polynomial
3186 * Univariate polynomial rings::
3187 * Functions on univariate polynomials::
3188 * Special polynomials::
3191 @node Univariate polynomial rings
3192 @section Univariate polynomial rings
3194 CLN implements univariate polynomials (polynomials in one variable) over an
3195 arbitrary ring. The indeterminate variable may be either unnamed (and will be
3196 printed according to @code{default_print_flags.univpoly_varname}, which
3197 defaults to @samp{x}) or carry a given name. The base ring and the
3198 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
3199 (accidentally) mix elements of different polynomial rings, e.g.
3200 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
3201 return a multivariate polynomial, but they are not yet implemented in CLN.)
3203 The classes of univariate polynomial rings are
3211 Univariate polynomial ring
3215 +----------------+-------------------+
3217 Complex polynomial ring | Modular integer polynomial ring
3218 cl_univpoly_complex_ring | cl_univpoly_modint_ring
3219 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3223 Real polynomial ring |
3224 cl_univpoly_real_ring |
3225 <cln/univpoly_real.h> |
3229 Rational polynomial ring |
3230 cl_univpoly_rational_ring |
3231 <cln/univpoly_rational.h> |
3235 Integer polynomial ring
3236 cl_univpoly_integer_ring
3237 <cln/univpoly_integer.h>
3240 and the corresponding classes of univariate polynomials are
3243 Univariate polynomial
3247 +----------------+-------------------+
3249 Complex polynomial | Modular integer polynomial
3251 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3257 <cln/univpoly_real.h> |
3261 Rational polynomial |
3263 <cln/univpoly_rational.h> |
3269 <cln/univpoly_integer.h>
3272 Univariate polynomial rings are constructed using the functions
3275 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3276 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3277 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3278 @code{R} may be an arbitrary ring. This function takes care of finding out
3279 about special cases of @code{R}, such as the rings of complex numbers,
3280 real numbers, rational numbers, integers, or modular integer rings.
3281 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3282 This ensures that two calls of this function with the same arguments will
3283 return the same polynomial ring.
3285 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3286 @cindex @code{find_univpoly_ring ()}
3287 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3288 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3289 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3290 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3291 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3292 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3293 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3294 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3295 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3296 These functions are equivalent to the general @code{find_univpoly_ring},
3297 only the return type is more specific, according to the base ring's type.
3300 @node Functions on univariate polynomials
3301 @section Functions on univariate polynomials
3303 Given a univariate polynomial ring @code{R}, the following members can be used.
3306 @item cl_ring R->basering()
3307 @cindex @code{basering ()}
3308 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3310 @item cl_UP R->zero()
3311 @cindex @code{zero ()}
3312 This returns @code{0 in R}, a polynomial of degree -1.
3314 @item cl_UP R->one()
3315 @cindex @code{one ()}
3316 This returns @code{1 in R}, a polynomial of degree == 0.
3318 @item cl_UP R->canonhom (const cl_I& x)
3319 @cindex @code{canonhom ()}
3320 This returns @code{x in R}, a polynomial of degree <= 0.
3322 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3323 @cindex @code{monomial ()}
3324 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3327 @item cl_UP R->create (sintL degree)
3328 @cindex @code{create ()}
3329 Creates a new polynomial with a given degree. The zero polynomial has degree
3330 @code{-1}. After creating the polynomial, you should put in the coefficients,
3331 using the @code{set_coeff} member function, and then call the @code{finalize}
3335 The following are the only destructive operations on univariate polynomials.
3338 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3339 @cindex @code{set_coeff ()}
3340 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3341 After changing a polynomial and before applying any "normal" operation on it,
3342 you should call its @code{finalize} member function.
3344 @item void finalize (cl_UP& x)
3345 @cindex @code{finalize ()}
3346 This function marks the endpoint of destructive modifications of a polynomial.
3347 It normalizes the internal representation so that subsequent computations have
3348 less overhead. Doing normal computations on unnormalized polynomials may
3349 produce wrong results or crash the program.
3352 The following operations are defined on univariate polynomials.
3355 @item cl_univpoly_ring x.ring ()
3356 @cindex @code{ring ()}
3357 Returns the ring to which the univariate polynomial @code{x} belongs.
3359 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3360 @cindex @code{operator + ()}
3361 Returns the sum of two univariate polynomials.
3363 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3364 @cindex @code{operator - ()}
3365 Returns the difference of two univariate polynomials.
3367 @item cl_UP operator- (const cl_UP&)
3368 Returns the negative of a univariate polynomial.
3370 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3371 @cindex @code{operator * ()}
3372 Returns the product of two univariate polynomials. One of the arguments may
3373 also be a plain integer or an element of the base ring.
3375 @item cl_UP square (const cl_UP&)
3376 @cindex @code{square ()}
3377 Returns the square of a univariate polynomial.
3379 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3380 @cindex @code{expt_pos ()}
3381 @code{y} must be > 0. Returns @code{x^y}.
3383 @item bool operator== (const cl_UP&, const cl_UP&)
3384 @cindex @code{operator == ()}
3385 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3386 @cindex @code{operator != ()}
3387 Compares two univariate polynomials, belonging to the same univariate
3388 polynomial ring, for equality.
3390 @item bool zerop (const cl_UP& x)
3391 @cindex @code{zerop ()}
3392 Returns true if @code{x} is @code{0 in R}.
3394 @item sintL degree (const cl_UP& x)
3395 @cindex @code{degree ()}
3396 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3398 @item sintL ldegree (const cl_UP& x)
3399 @cindex @code{degree ()}
3400 Returns the low degree of the polynomial. This is the degree of the first
3401 non-vanishing polynomial coefficient. The zero polynomial has ldegree @code{-1}.
3403 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3404 @cindex @code{coeff ()}
3405 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3407 @item cl_ring_element x (const cl_ring_element& y)
3408 @cindex @code{operator () ()}
3409 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3410 then @samp{x(y)} returns the value of the substitution of @code{y} into
3413 @item cl_UP deriv (const cl_UP& x)
3414 @cindex @code{deriv ()}
3415 Returns the derivative of the polynomial @code{x} with respect to the
3416 indeterminate @code{X}.
3419 The following output functions are defined (see also the chapter on
3423 @item void fprint (std::ostream& stream, const cl_UP& x)
3424 @cindex @code{fprint ()}
3425 @itemx std::ostream& operator<< (std::ostream& stream, const cl_UP& x)
3426 @cindex @code{operator << ()}
3427 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3428 depend on the global printer settings in the variable
3429 @code{default_print_flags}.
3432 @node Special polynomials
3433 @section Special polynomials
3435 The following functions return special polynomials.
3438 @item cl_UP_I tschebychev (sintL n)
3439 @cindex @code{tschebychev ()}
3440 @cindex Chebyshev polynomial
3441 Returns the n-th Chebyshev polynomial (n >= 0).
3443 @item cl_UP_I hermite (sintL n)
3444 @cindex @code{hermite ()}
3445 @cindex Hermite polynomial
3446 Returns the n-th Hermite polynomial (n >= 0).
3448 @item cl_UP_RA legendre (sintL n)
3449 @cindex @code{legendre ()}
3450 @cindex Legende polynomial
3451 Returns the n-th Legendre polynomial (n >= 0).
3453 @item cl_UP_I laguerre (sintL n)
3454 @cindex @code{laguerre ()}
3455 @cindex Laguerre polynomial
3456 Returns the n-th Laguerre polynomial (n >= 0).
3459 Information how to derive the differential equation satisfied by each
3460 of these polynomials from their definition can be found in the
3461 @code{doc/polynomial/} directory.
3469 * Memory efficiency::
3470 * Speed efficiency::
3471 * Garbage collection::
3478 Using C++ as an implementation language provides
3482 Efficiency: It compiles to machine code.
3486 Portability: It runs on all platforms supporting a C++ compiler. Because
3487 of the availability of GNU C++, this includes all currently used 32-bit and
3488 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3491 Type safety: The C++ compilers knows about the number types and complains if,
3492 for example, you try to assign a float to an integer variable. However,
3493 a drawback is that C++ doesn't know about generic types, hence a restriction
3494 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3495 arguments belong to the same modular ring cannot be expressed as a compile-time
3499 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3500 @code{=}, @code{==}, ... can be used in infix notation, which is more
3501 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3504 With these language features, there is no need for two separate languages,
3505 one for the implementation of the library and one in which the library's users
3506 can program. This means that a prototype implementation of an algorithm
3507 can be integrated into the library immediately after it has been tested and
3508 debugged. No need to rewrite it in a low-level language after having prototyped
3509 in a high-level language.
3512 @node Memory efficiency
3513 @section Memory efficiency
3515 In order to save memory allocations, CLN implements:
3519 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3522 @cindex garbage collection
3523 @cindex reference counting
3524 Garbage collection: A reference counting mechanism makes sure that any
3525 number object's storage is freed immediately when the last reference to the
3528 @cindex immediate numbers
3529 Small integers are represented as immediate values instead of pointers
3530 to heap allocated storage. This means that integers @code{>= -2^29},
3531 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3536 @node Speed efficiency
3537 @section Speed efficiency
3539 Speed efficiency is obtained by the combination of the following tricks
3544 Small integers, being represented as immediate values, don't require
3545 memory access, just a couple of instructions for each elementary operation.
3547 The kernel of CLN has been written in assembly language for some CPUs
3548 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3550 On all CPUs, CLN may be configured to use the superefficient low-level
3551 routines from GNU GMP version 3.
3553 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3554 algorithm, the Karatsuba multiplication, which is an
3565 For very large numbers (more than 12000 decimal digits), CLN uses
3567 Sch{@"o}nhage-Strassen
3568 @cindex Sch{@"o}nhage-Strassen multiplication
3572 @cindex Schoenhage-Strassen multiplication
3574 multiplication, which is an asymptotically optimal multiplication
3577 These fast multiplication algorithms also give improvements in the speed
3578 of division and radix conversion.
3582 @node Garbage collection
3583 @section Garbage collection
3584 @cindex garbage collection
3586 All the number classes are reference count classes: They only contain a pointer
3587 to an object in the heap. Upon construction, assignment and destruction of
3588 number objects, only the objects' reference count are manipulated.
3590 Memory occupied by number objects are automatically reclaimed as soon as
3591 their reference count drops to zero.
3593 For number rings, another strategy is implemented: There is a cache of,
3594 for example, the modular integer rings. A modular integer ring is destroyed
3595 only if its reference count dropped to zero and the cache is about to be
3596 resized. The effect of this strategy is that recently used rings remain
3597 cached, whereas undue memory consumption through cached rings is avoided.
3600 @node Using the library
3601 @chapter Using the library
3603 For the following discussion, we will assume that you have installed
3604 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3605 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3606 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3607 environment variables, or directly substitute the appropriate values.
3611 * Compiler options::
3614 * Debugging support::
3615 * Reporting Problems::
3618 @node Compiler options
3619 @section Compiler options
3620 @cindex compiler options
3622 Until you have installed CLN in a public place, the following options are
3625 When you compile CLN application code, add the flags
3627 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3629 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3630 When you link CLN application code to form an executable, add the flags
3632 $CLN_TARGETDIR/src/libcln.a
3634 to the C/C++ compiler's command line (@code{make} variable LIBS).
3636 If you did a @code{make install}, the include files are installed in a
3637 public directory (normally @code{/usr/local/include}), hence you don't
3638 need special flags for compiling. The library has been installed to a
3639 public directory as well (normally @code{/usr/local/lib}), hence when
3640 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3642 @cindex @code{pkg-config}
3643 To make the creation of software packages that use CLN easier, the
3644 @code{pkg-config} utility can be used. CLN provides all the necessary
3645 metainformation in a file called @code{cln.pc} (installed in
3646 @code{/usr/local/lib/pkgconfig} by default). A program using CLN can
3647 be compiled and linked using @footnote{If you installed CLN to
3648 non-standard location @var{prefix}, you need to set the
3649 @env{PKG_CONFIG_PATH} environment variable to @var{prefix}/lib/pkgconfig
3652 g++ `pkg-config --libs cln` `pkg-config --cflags cln` prog.cc -o prog
3655 Software using GNU autoconf can check for CLN with the
3656 @code{PKG_CHECK_MODULES} macro supplied with @code{pkg-config}.
3658 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}])
3660 This will check for CLN version at least @var{MIN-VERSION}. If the
3661 required version was found, the variables @var{CLN_CFLAGS} and
3662 @var{CLN_LIBS} are set. Otherwise the configure script aborts. If this
3663 is not the desired behaviour, use the following code instead
3664 @footnote{See the @code{pkg-config} documentation for more details.}
3666 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}], [],
3667 [AC_MSG_WARNING([No suitable version of CLN can be found])])
3672 @section Include files
3673 @cindex include files
3674 @cindex header files
3676 Here is a summary of the include files and their contents.
3679 @item <cln/object.h>
3680 General definitions, reference counting, garbage collection.
3681 @item <cln/number.h>
3682 The class cl_number.
3683 @item <cln/complex.h>
3684 Functions for class cl_N, the complex numbers.
3686 Functions for class cl_R, the real numbers.
3688 Functions for class cl_F, the floats.
3689 @item <cln/sfloat.h>
3690 Functions for class cl_SF, the short-floats.
3691 @item <cln/ffloat.h>
3692 Functions for class cl_FF, the single-floats.
3693 @item <cln/dfloat.h>
3694 Functions for class cl_DF, the double-floats.
3695 @item <cln/lfloat.h>
3696 Functions for class cl_LF, the long-floats.
3697 @item <cln/rational.h>
3698 Functions for class cl_RA, the rational numbers.
3699 @item <cln/integer.h>
3700 Functions for class cl_I, the integers.
3703 @item <cln/complex_io.h>
3704 Input/Output for class cl_N, the complex numbers.
3705 @item <cln/real_io.h>
3706 Input/Output for class cl_R, the real numbers.
3707 @item <cln/float_io.h>
3708 Input/Output for class cl_F, the floats.
3709 @item <cln/sfloat_io.h>
3710 Input/Output for class cl_SF, the short-floats.
3711 @item <cln/ffloat_io.h>
3712 Input/Output for class cl_FF, the single-floats.
3713 @item <cln/dfloat_io.h>
3714 Input/Output for class cl_DF, the double-floats.
3715 @item <cln/lfloat_io.h>
3716 Input/Output for class cl_LF, the long-floats.
3717 @item <cln/rational_io.h>
3718 Input/Output for class cl_RA, the rational numbers.
3719 @item <cln/integer_io.h>
3720 Input/Output for class cl_I, the integers.
3722 Flags for customizing input operations.
3723 @item <cln/output.h>
3724 Flags for customizing output operations.
3725 @item <cln/malloc.h>
3726 @code{malloc_hook}, @code{free_hook}.
3727 @item <cln/exception.h>
3728 Exception base class.
3729 @item <cln/condition.h>
3731 @item <cln/string.h>
3733 @item <cln/symbol.h>
3735 @item <cln/proplist.h>
3739 @item <cln/null_ring.h>
3741 @item <cln/complex_ring.h>
3742 The ring of complex numbers.
3743 @item <cln/real_ring.h>
3744 The ring of real numbers.
3745 @item <cln/rational_ring.h>
3746 The ring of rational numbers.
3747 @item <cln/integer_ring.h>
3748 The ring of integers.
3749 @item <cln/numtheory.h>
3750 Number threory functions.
3751 @item <cln/modinteger.h>
3757 @item <cln/GV_number.h>
3758 General vectors over cl_number.
3759 @item <cln/GV_complex.h>
3760 General vectors over cl_N.
3761 @item <cln/GV_real.h>
3762 General vectors over cl_R.
3763 @item <cln/GV_rational.h>
3764 General vectors over cl_RA.
3765 @item <cln/GV_integer.h>
3766 General vectors over cl_I.
3767 @item <cln/GV_modinteger.h>
3768 General vectors of modular integers.
3771 @item <cln/SV_number.h>
3772 Simple vectors over cl_number.
3773 @item <cln/SV_complex.h>
3774 Simple vectors over cl_N.
3775 @item <cln/SV_real.h>
3776 Simple vectors over cl_R.
3777 @item <cln/SV_rational.h>
3778 Simple vectors over cl_RA.
3779 @item <cln/SV_integer.h>
3780 Simple vectors over cl_I.
3781 @item <cln/SV_ringelt.h>
3782 Simple vectors of general ring elements.
3783 @item <cln/univpoly.h>
3784 Univariate polynomials.
3785 @item <cln/univpoly_integer.h>
3786 Univariate polynomials over the integers.
3787 @item <cln/univpoly_rational.h>
3788 Univariate polynomials over the rational numbers.
3789 @item <cln/univpoly_real.h>
3790 Univariate polynomials over the real numbers.
3791 @item <cln/univpoly_complex.h>
3792 Univariate polynomials over the complex numbers.
3793 @item <cln/univpoly_modint.h>
3794 Univariate polynomials over modular integer rings.
3795 @item <cln/timing.h>
3798 Includes all of the above.
3805 A function which computes the nth Fibonacci number can be written as follows.
3806 @cindex Fibonacci number
3809 #include <cln/integer.h>
3810 #include <cln/real.h>
3811 using namespace cln;
3813 // Returns F_n, computed as the nearest integer to
3814 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3815 const cl_I fibonacci (int n)
3817 // Need a precision of ((1+sqrt(5))/2)^-n.
3818 float_format_t prec = float_format((int)(0.208987641*n+5));
3819 cl_R sqrt5 = sqrt(cl_float(5,prec));
3820 cl_R phi = (1+sqrt5)/2;
3821 return round1( expt(phi,n)/sqrt5 );
3825 Let's explain what is going on in detail.
3827 The include file @code{<cln/integer.h>} is necessary because the type
3828 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3829 is needed for the type @code{cl_R} and the floating point number functions.
3830 The order of the include files does not matter. In order not to write
3831 out @code{cln::}@var{foo} in this simple example we can safely import
3832 the whole namespace @code{cln}.
3834 Then comes the function declaration. The argument is an @code{int}, the
3835 result an integer. The return type is defined as @samp{const cl_I}, not
3836 simply @samp{cl_I}, because that allows the compiler to detect typos like
3837 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3838 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3839 number). We use the most specialized possible return type because functions
3840 which call @samp{fibonacci} will be able to profit from the compiler's type
3841 analysis: Adding two integers is slightly more efficient than adding the
3842 same objects declared as complex numbers, because it needs less type
3843 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3844 the size of the resulting executable program.
3846 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3847 integer. In order to get a correct result, the absolute error should be less
3848 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3849 To this end, the first line computes a floating point precision for sqrt(5)
3852 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3853 number and than taking the square root. The converse, first taking the square
3854 root of 5, and then converting to the desired precision, would not work in
3855 CLN: The square root would be computed to a default precision (normally
3856 single-float precision), and the following conversion could not help about
3857 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3858 system and does not represent sqrt(5) in a non-numeric way.
3860 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3861 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3862 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3863 @code{cl_N} because a @samp{round1} does not exist for general complex
3866 When the function returns, all the local variables in the function are
3867 automatically reclaimed (garbage collected). Only the result survives and
3868 gets passed to the caller.
3870 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3871 contains this implementation together with an even faster algorithm.
3873 @node Debugging support
3874 @section Debugging support
3877 When debugging a CLN application with GNU @code{gdb}, two facilities are
3878 available from the library:
3881 @item The library does type checks, range checks, consistency checks at
3882 many places. When one of these fails, an exception of a type derived from
3883 @code{runtime_exception} is thrown. When an exception is cought, the stack
3884 has already been unwound, so it is may not be possible to tell at which
3885 point the exception was thrown. For debugging, it is best to set up a
3886 catchpoint at the event of throwning a C++ exception:
3890 When this catchpoint is hit, look at the stack's backtrace:
3894 When control over the type of exception is required, it may be possible
3895 to set a breakpoint at the @code{g++} runtime library function
3896 @code{__raise_exception}. Refer to the documentation of GNU @code{gdb}
3899 @item The debugger's normal @code{print} command doesn't know about
3900 CLN's types and therefore prints mostly useless hexadecimal addresses.
3901 CLN offers a function @code{cl_print}, callable from the debugger,
3902 for printing number objects. In order to get this function, you have
3903 to define the macro @samp{CL_DEBUG} and then include all the header files
3904 for which you want @code{cl_print} debugging support. For example:
3905 @cindex @code{CL_DEBUG}
3908 #include <cln/string.h>
3910 Now, if you have in your program a variable @code{cl_string s}, and
3911 inspect it under @code{gdb}, the output may look like this:
3914 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3915 word = 134568800@}@}, @}
3916 (gdb) call cl_print(s)
3920 Note that the output of @code{cl_print} goes to the program's error output,
3921 not to gdb's standard output.
3923 Note, however, that the above facility does not work with all CLN types,
3924 only with number objects and similar. Therefore CLN offers a member function
3925 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3926 is needed for this member function to be implemented. Under @code{gdb},
3927 you call it like this:
3928 @cindex @code{debug_print ()}
3931 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3932 word = 134568800@}@}, @}
3933 (gdb) call s.debug_print()
3936 >call ($1).debug_print()
3941 Unfortunately, this feature does not seem to work under all circumstances.
3944 @node Reporting Problems
3945 @section Reporting Problems
3947 @cindex mailing list
3949 If you encounter any problem, please don't hesitate to send a detailed
3950 bugreport to the @code{cln-list@@ginac.de} mailing list. Please think
3951 about your bug: consider including a short description of your operating
3952 system and compilation environment with corresponding version numbers. A
3953 description of your configuration options may also be helpful. Also, a
3954 short test program together with the output you get and the output you
3955 expect will help us to reproduce it quickly. Finally, do not forget to
3956 report the version number of CLN.
3960 @chapter Customizing
3965 * Floating-point underflow::
3967 * Customizing the memory allocator::
3970 @node Error handling
3971 @section Error handling
3973 @cindex error handling
3975 @cindex @code{runtime_exception}
3976 CLN signals abnormal situations by throwning exceptions. All exceptions
3977 thrown by the library are of type @code{runtime_exception} or of a
3978 derived type. Class @code{cln::runtime_exception} in turn is derived
3979 from the C++ standard library class @code{std::runtime_error} and
3980 inherits the @code{.what()} member function that can be used to query
3981 details about the cause of error.
3983 The most important classes thrown by the library are
3985 @cindex @code{floating_point_exception}
3986 @cindex @code{read_number_exception}
3988 Exception base class
3992 +----------------+----------------+
3994 Malformed number input Floating-point error
3995 read_number_exception floating_poing_exception
3996 <cln/number_io.h> <cln/float.h>
3999 CLN has many more exception classes that allow for more fine-grained
4000 control but I refrain from documenting them all here. They are all
4001 declared in the public header files and they are all subclasses of the
4002 above exceptions, so catching those you are always on the safe side.
4005 @node Floating-point underflow
4006 @section Floating-point underflow
4009 @cindex @code{floating_point_underflow_exception}
4010 Floating point underflow denotes the situation when a floating-point
4011 number is to be created which is so close to @code{0} that its exponent
4012 is too low to be represented internally. By default, this causes the
4013 exception @code{floating_point_underflow_exception} (subclass of
4014 @code{floating_point_exception}) to be thrown. If you set the global
4017 bool cl_inhibit_floating_point_underflow
4019 to @code{true}, the exception will be inhibited, and a floating-point
4020 zero will be generated instead. The default value of
4021 @code{cl_inhibit_floating_point_underflow} is @code{false}.
4024 @node Customizing I/O
4025 @section Customizing I/O
4027 The output of the function @code{fprint} may be customized by changing the
4028 value of the global variable @code{default_print_flags}.
4029 @cindex @code{default_print_flags}
4032 @node Customizing the memory allocator
4033 @section Customizing the memory allocator
4035 Every memory allocation of CLN is done through the function pointer
4036 @code{malloc_hook}. Freeing of this memory is done through the function
4037 pointer @code{free_hook}. The default versions of these functions,
4038 provided in the library, call @code{malloc} and @code{free} and check
4039 the @code{malloc} result against @code{NULL}.
4040 If you want to provide another memory allocator, you need to define
4041 the variables @code{malloc_hook} and @code{free_hook} yourself,
4044 #include <cln/malloc.h>
4046 void* (*malloc_hook) (size_t size) = @dots{};
4047 void (*free_hook) (void* ptr) = @dots{};
4050 @cindex @code{malloc_hook ()}
4051 @cindex @code{free_hook ()}
4052 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
4054 It is not possible to change the memory allocator at runtime, because
4055 it is already called at program startup by the constructors of some
4063 @node Index, , Customizing, Top