1 \input texinfo @c -*-texinfo-*-
4 @settitle CLN, a Class Library for Numbers
5 @c @setchapternewpage off
10 @c I hate putting "@noindent" in front of every paragraph.
18 @c Don't need the other types of indices.
29 This file documents @sc{cln}, a Class Library for Numbers.
31 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
32 Richard Kreckel, @code{<kreckel@@ginac.de>}.
34 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
36 Permission is granted to make and distribute verbatim copies of
37 this manual provided the copyright notice and this permission notice
38 are preserved on all copies.
41 Permission is granted to process this file through TeX and print the
42 results, provided the printed document carries copying permission
43 notice identical to this one except for the removal of this paragraph
44 (this paragraph not being relevant to the printed manual).
47 Permission is granted to copy and distribute modified versions of this
48 manual under the conditions for verbatim copying, provided that the entire
49 resulting derived work is distributed under the terms of a permission
50 notice identical to this one.
52 Permission is granted to copy and distribute translations of this manual
53 into another language, under the above conditions for modified versions,
54 except that this permission notice may be stated in a translation approved
60 @c prevent ugly black rectangles on overfull hbox lines:
63 @title CLN, a Class Library for Numbers
65 @author by Bruno Haible
67 @vskip 0pt plus 1filll
68 Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
71 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
72 Richard Kreckel, @code{<kreckel@@ginac.de>}.
74 Permission is granted to make and distribute verbatim copies of
75 this manual provided the copyright notice and this permission notice
76 are preserved on all copies.
78 Permission is granted to copy and distribute modified versions of this
79 manual under the conditions for verbatim copying, provided that the entire
80 resulting derived work is distributed under the terms of a permission
81 notice identical to this one.
83 Permission is granted to copy and distribute translations of this manual
84 into another language, under the above conditions for modified versions,
85 except that this permission notice may be stated in a translation approved
92 @node Top, Introduction, (dir), (dir)
95 @c * Introduction:: Introduction
101 * Ordinary number types::
102 * Functions on numbers::
106 * Symbolic data types::
107 * Univariate polynomials::
109 * Using the library::
114 --- The Detailed Node Listing ---
119 * Building the library::
120 * Installing the library::
131 * Using the GNU MP Library::
133 Ordinary number types
136 * Floating-point numbers::
142 * Constructing numbers::
143 * Elementary functions::
144 * Elementary rational functions::
145 * Elementary complex functions::
147 * Rounding functions::
149 * Transcendental functions::
150 * Functions on integers::
151 * Functions on floating-point numbers::
152 * Conversion functions::
153 * Random number generators::
154 * Obfuscating operators::
158 * Constructing integers::
159 * Constructing rational numbers::
160 * Constructing floating-point numbers::
161 * Constructing complex numbers::
163 Transcendental functions
165 * Exponential and logarithmic functions::
166 * Trigonometric functions::
167 * Hyperbolic functions::
171 Functions on integers
173 * Logical functions::
174 * Number theoretic functions::
175 * Combinatorial functions::
179 * Conversion to floating-point numbers::
180 * Conversion to rational numbers::
184 * Internal and printed representation::
190 * Modular integer rings::
191 * Functions on modular integers::
198 Univariate polynomials
200 * Univariate polynomial rings::
201 * Functions on univariate polynomials::
202 * Special polynomials::
207 * Memory efficiency::
209 * Garbage collection::
214 * Compatibility to old CLN versions::
217 * Debugging support::
222 * Floating-point underflow::
224 * Customizing the memory allocator::
229 @node Introduction, Installation, Top, Top
230 @comment node-name, next, previous, up
231 @chapter Introduction
234 CLN is a library for computations with all kinds of numbers.
235 It has a rich set of number classes:
239 Integers (with unlimited precision),
245 Floating-point numbers:
255 Long float (with unlimited precision),
262 Modular integers (integers modulo a fixed integer),
265 Univariate polynomials.
269 The subtypes of the complex numbers among these are exactly the
270 types of numbers known to the Common Lisp language. Therefore
271 @code{CLN} can be used for Common Lisp implementations, giving
272 @samp{CLN} another meaning: it becomes an abbreviation of
273 ``Common Lisp Numbers''.
276 The CLN package implements
280 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
281 comparisons, @dots{}),
284 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
287 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
288 functions and their inverse functions).
292 CLN is a C++ library. Using C++ as an implementation language provides
296 efficiency: it compiles to machine code,
298 type safety: the C++ compiler knows about the number types and complains
299 if, for example, you try to assign a float to an integer variable.
301 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
302 @code{==}, @dots{} operators as in C or C++.
306 CLN is memory efficient:
310 Small integers and short floats are immediate, not heap allocated.
312 Heap-allocated memory is reclaimed through an automatic, non-interruptive
317 CLN is speed efficient:
321 The kernel of CLN has been written in assembly language for some CPUs
322 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
325 On all CPUs, CLN may be configured to use the superefficient low-level
326 routines from GNU GMP version 3.
328 It uses Karatsuba multiplication, which is significantly faster
329 for large numbers than the standard multiplication algorithm.
331 For very large numbers (more than 12000 decimal digits), it uses
333 Sch{@"o}nhage-Strassen
334 @cindex Sch{@"o}nhage-Strassen multiplication
338 @cindex Schönhage-Strassen multiplication
340 multiplication, which is an asymptotically optimal multiplication
341 algorithm, for multiplication, division and radix conversion.
345 CLN aims at being easily integrated into larger software packages:
349 The garbage collection imposes no burden on the main application.
351 The library provides hooks for memory allocation and exceptions.
354 All non-macro identifiers are hidden in namespace @code{cln} in
355 order to avoid name clashes.
359 @node Installation, Ordinary number types, Introduction, Top
360 @chapter Installation
362 This section describes how to install the CLN package on your system.
367 * Building the library::
368 * Installing the library::
372 @node Prerequisites, Building the library, Installation, Installation
373 @section Prerequisites
381 @node C++ compiler, Make utility, Prerequisites, Prerequisites
382 @subsection C++ compiler
384 To build CLN, you need a C++ compiler.
385 Actually, you need GNU @code{g++ 2.90} or newer, the EGCS compilers will
387 I recommend GNU @code{g++ 2.95} or newer.
389 The following C++ features are used:
390 classes, member functions, overloading of functions and operators,
391 constructors and destructors, inline, const, multiple inheritance,
392 templates and namespaces.
394 The following C++ features are not used:
395 @code{new}, @code{delete}, virtual inheritance, exceptions.
397 CLN relies on semi-automatic ordering of initializations
398 of static and global variables, a feature which I could
399 implement for GNU g++ only.
402 @comment cl_modules.h requires g++
403 Therefore nearly any C++ compiler will do.
405 The following C++ compilers are known to compile CLN:
408 GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
413 The following C++ compilers are known to be unusable for CLN:
416 On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
417 in lines containing @code{#if} or @code{#elif} preprocessor commands.
419 On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
420 in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
421 to have default constructors, and because it probably miscompiles the
422 integer multiplication routines.
424 On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
425 @code{short}s to @code{int}s by zero-extend.
429 On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
430 initializations will not work.
434 @node Make utility, Sed utility, C++ compiler, Prerequisites
435 @subsection Make utility
438 To build CLN, you also need to have GNU @code{make} installed.
440 @node Sed utility, , Make utility, Prerequisites
441 @subsection Sed utility
444 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
445 This is because the libtool script, which creates the CLN library, relies
446 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
450 @node Building the library, Installing the library, Prerequisites, Installation
451 @section Building the library
453 As with any autoconfiguring GNU software, installation is as easy as this:
461 If on your system, @samp{make} is not GNU @code{make}, you have to use
462 @samp{gmake} instead of @samp{make} above.
464 The @code{configure} command checks out some features of your system and
465 C++ compiler and builds the @code{Makefile}s. The @code{make} command
466 builds the library. This step may take 4 hours on an average workstation.
467 The @code{make check} runs some test to check that no important subroutine
468 has been miscompiled.
470 The @code{configure} command accepts options. To get a summary of them, try
476 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
478 You can specify the C compiler, the C++ compiler and their options through
479 the following environment variables when running @code{configure}:
483 Specifies the C compiler.
486 Flags to be given to the C compiler when compiling programs (not when linking).
489 Specifies the C++ compiler.
492 Flags to be given to the C++ compiler when compiling programs (not when linking).
498 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
499 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O -g" \
500 CXX="g++ -V egcs-2.91.60" CXXFLAGS="-O -g" ./configure
501 $ CC="gcc -V 2.95.2" CFLAGS="-O2 -fno-exceptions" \
502 CXX="g++ -V 2.95.2" CFLAGS="-O2 -fno-exceptions" ./configure
505 @comment cl_modules.h requires g++
506 You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
507 compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
510 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
511 $ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
514 On SGI Irix 5, if you wish not to use @code{g++}:
517 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
520 On SGI Irix 6, if you wish not to use @code{g++}:
523 $ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
524 ./configure --without-gmp
525 $ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
526 -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
527 ./configure --without-gmp
531 Note that for these environment variables to take effect, you have to set
532 them (assuming a Bourne-compatible shell) on the same line as the
533 @code{configure} command. If you made the settings in earlier shell
534 commands, you have to @code{export} the environment variables before
535 calling @code{configure}. In a @code{csh} shell, you have to use the
536 @samp{setenv} command for setting each of the environment variables.
538 Currently CLN works only with the GNU @code{g++} compiler, and only in
539 optimizing mode. So you should specify at least @code{-O} in the CXXFLAGS,
540 or no CXXFLAGS at all. (If CXXFLAGS is not set, CLN will use @code{-O}.)
542 If you use @code{g++} version 2.8.x or egcs-2.91.x (a.k.a. egcs-1.1) or
543 gcc-2.95.x, I recommend adding @samp{-fno-exceptions} to the CXXFLAGS.
544 This will likely generate better code.
546 If you use @code{g++} version egcs-2.91.x (egcs-1.1) or gcc-2.95.x on Sparc,
547 add either @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
548 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division routines.
549 Also, if you have @code{g++} version egcs-1.1.1 or older on Sparc, you must
550 specify @samp{--disable-shared} because @code{g++} would miscompile parts of
553 By default, both a shared and a static library are built. You can build
554 CLN as a static (or shared) library only, by calling @code{configure} with
555 the option @samp{--disable-shared} (or @samp{--disable-static}). While
556 shared libraries are usually more convenient to use, they may not work
557 on all architectures. Try disabling them if you run into linker
558 problems. Also, they are generally somewhat slower than static
559 libraries so runtime-critical applications should be linked statically.
563 * Using the GNU MP Library::
566 @node Using the GNU MP Library, , Building the library, Building the library
567 @subsection Using the GNU MP Library
570 Starting with version 1.1, CLN may be configured to make use of a
571 preinstalled @code{gmp} library. Please make sure that you have at
572 least @code{gmp} version 3.0 installed since earlier versions are
573 unsupported and likely not to work. Enabling this feature by calling
574 @code{configure} with the option @samp{--with-gmp} is known to be quite
575 a boost for CLN's performance.
577 If you have installed the @code{gmp} library and its header file in
578 some place where your compiler cannot find it by default, you must help
579 @code{configure} by setting @code{CPPFLAGS} and @code{LDFLAGS}. Here is
583 $ CC="gcc" CFLAGS="-O2" CXX="g++" CXXFLAGS="-O2 -fno-exceptions" \
584 CPPFLAGS="-I/opt/gmp/include" LDFLAGS="-L/opt/gmp/lib" ./configure --with-gmp
588 @node Installing the library, Cleaning up, Building the library, Installation
589 @section Installing the library
592 As with any autoconfiguring GNU software, installation is as easy as this:
598 The @samp{make install} command installs the library and the include files
599 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
600 if you haven't specified a @code{--prefix} option to @code{configure}).
601 This step may require superuser privileges.
603 If you have already built the library and wish to install it, but didn't
604 specify @code{--prefix=@dots{}} at configure time, just re-run
605 @code{configure}, giving it the same options as the first time, plus
606 the @code{--prefix=@dots{}} option.
609 @node Cleaning up, , Installing the library, Installation
612 You can remove system-dependent files generated by @code{make} through
618 You can remove all files generated by @code{make}, thus reverting to a
619 virgin distribution of CLN, through
626 @node Ordinary number types, Functions on numbers, Installation, Top
627 @chapter Ordinary number types
629 CLN implements the following class hierarchy:
637 Real or complex number
646 +-------------------+-------------------+
648 Rational number Floating-point number
650 <cln/rational.h> <cln/float.h>
652 | +--------------+--------------+--------------+
654 cl_I Short-Float Single-Float Double-Float Long-Float
655 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
656 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
659 @cindex @code{cl_number}
660 @cindex abstract class
661 The base class @code{cl_number} is an abstract base class.
662 It is not useful to declare a variable of this type except if you want
663 to completely disable compile-time type checking and use run-time type
668 @cindex complex number
669 The class @code{cl_N} comprises real and complex numbers. There is
670 no special class for complex numbers since complex numbers with imaginary
671 part @code{0} are automatically converted to real numbers.
674 The class @code{cl_R} comprises real numbers of different kinds. It is an
678 @cindex rational number
680 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
681 integers. There is no special class for non-integral rational numbers
682 since rational numbers with denominator @code{1} are automatically converted
686 The class @code{cl_F} implements floating-point approximations to real numbers.
687 It is an abstract class.
692 * Floating-point numbers::
697 @node Exact numbers, Floating-point numbers, Ordinary number types, Ordinary number types
698 @section Exact numbers
701 Some numbers are represented as exact numbers: there is no loss of information
702 when such a number is converted from its mathematical value to its internal
703 representation. On exact numbers, the elementary operations (@code{+},
704 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
707 In CLN, the exact numbers are:
711 rational numbers (including integers),
713 complex numbers whose real and imaginary parts are both rational numbers.
716 Rational numbers are always normalized to the form
717 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
718 are coprime integers and the denominator is positive. If the resulting
719 denominator is @code{1}, the rational number is converted to an integer.
721 Small integers (typically in the range @code{-2^30}@dots{}@code{2^30-1},
722 for 32-bit machines) are especially efficient, because they consume no heap
723 allocation. Otherwise the distinction between these immediate integers
724 (called ``fixnums'') and heap allocated integers (called ``bignums'')
725 is completely transparent.
728 @node Floating-point numbers, Complex numbers, Exact numbers, Ordinary number types
729 @section Floating-point numbers
730 @cindex floating-point number
732 Not all real numbers can be represented exactly. (There is an easy mathematical
733 proof for this: Only a countable set of numbers can be stored exactly in
734 a computer, even if one assumes that it has unlimited storage. But there
735 are uncountably many real numbers.) So some approximation is needed.
736 CLN implements ordinary floating-point numbers, with mantissa and exponent.
738 @cindex rounding error
739 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
740 only return approximate results. For example, the value of the expression
741 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
742 @samp{0.7}. Rounding errors like this one are inevitable when computing
743 with floating-point numbers.
745 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
746 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
747 rule: It first computes the exact mathematical result and then returns the
748 floating-point number which is nearest to this. If two floating-point numbers
749 are equally distant from the ideal result, the one with a @code{0} in its least
750 significant mantissa bit is chosen.
752 Similarly, testing floating point numbers for equality @samp{x == y}
753 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
754 for some well-chosen @code{epsilon}.
756 Floating point numbers come in four flavors:
761 Short floats, type @code{cl_SF}.
762 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
763 and 17 mantissa bits (including the ``hidden'' bit).
764 They don't consume heap allocation.
768 Single floats, type @code{cl_FF}.
769 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
770 and 24 mantissa bits (including the ``hidden'' bit).
771 In CLN, they are represented as IEEE single-precision floating point numbers.
772 This corresponds closely to the C/C++ type @samp{float}.
776 Double floats, type @code{cl_DF}.
777 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
778 and 53 mantissa bits (including the ``hidden'' bit).
779 In CLN, they are represented as IEEE double-precision floating point numbers.
780 This corresponds closely to the C/C++ type @samp{double}.
784 Long floats, type @code{cl_LF}.
785 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
786 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
787 The precision of a long float is unlimited, but once created, a long float
788 has a fixed precision. (No ``lazy recomputation''.)
791 Of course, computations with long floats are more expensive than those
792 with smaller floating-point formats.
794 CLN does not implement features like NaNs, denormalized numbers and
795 gradual underflow. If the exponent range of some floating-point type
796 is too limited for your application, choose another floating-point type
797 with larger exponent range.
800 As a user of CLN, you can forget about the differences between the
801 four floating-point types and just declare all your floating-point
802 variables as being of type @code{cl_F}. This has the advantage that
803 when you change the precision of some computation (say, from @code{cl_DF}
804 to @code{cl_LF}), you don't have to change the code, only the precision
805 of the initial values. Also, many transcendental functions have been
806 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
807 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
808 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
809 the floating point contagion rule happened to change in the future.)
812 @node Complex numbers, Conversions, Floating-point numbers, Ordinary number types
813 @section Complex numbers
814 @cindex complex number
816 Complex numbers, as implemented by the class @code{cl_N}, have a real
817 part and an imaginary part, both real numbers. A complex number whose
818 imaginary part is the exact number @code{0} is automatically converted
821 Complex numbers can arise from real numbers alone, for example
822 through application of @code{sqrt} or transcendental functions.
825 @node Conversions, , Complex numbers, Ordinary number types
829 Conversions from any class to any its superclasses (``base classes'' in
830 C++ terminology) is done automatically.
832 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
833 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
834 @code{cl_N} and @code{cl_number}.
836 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
837 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
838 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
839 efficiency. Their range is therefore limited:
843 The conversion from @samp{int} works only if the argument is < 2^29 and > -2^29.
845 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
848 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
849 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
850 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
852 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
853 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
854 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
855 @samp{cl_I}, first convert it to an @samp{unsigned long}.
857 Conversions from the C built-in type @samp{float} are provided for the classes
858 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
860 Conversions from the C built-in type @samp{double} are provided for the classes
861 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
863 Conversions from @samp{const char *} are provided for the classes
864 @code{cl_I}, @code{cl_RA},
865 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
866 @code{cl_R}, @code{cl_N}.
867 The easiest way to specify a value which is outside of the range of the
868 C++ built-in types is therefore to specify it as a string, like this:
871 cl_I order_of_rubiks_cube_group = "43252003274489856000";
873 Note that this conversion is done at runtime, not at compile-time.
875 Conversions from @code{cl_I} to the C built-in types @samp{int},
876 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
880 @item int cl_I_to_int (const cl_I& x)
881 @cindex @code{cl_I_to_int ()}
882 @itemx unsigned int cl_I_to_uint (const cl_I& x)
883 @cindex @code{cl_I_to_uint ()}
884 @itemx long cl_I_to_long (const cl_I& x)
885 @cindex @code{cl_I_to_long ()}
886 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
887 @cindex @code{cl_I_to_ulong ()}
888 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
889 representable in the range of @var{ctype}, a runtime error occurs.
892 Conversions from the classes @code{cl_I}, @code{cl_RA},
893 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
895 to the C built-in types @samp{float} and @samp{double} are provided through
899 @item float float_approx (const @var{type}& x)
900 @cindex @code{float_approx ()}
901 @itemx double double_approx (const @var{type}& x)
902 @cindex @code{double_approx ()}
903 Returns an approximation of @code{x} of C type @var{ctype}.
904 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
905 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
908 Conversions from any class to any of its subclasses (``derived classes'' in
909 C++ terminology) are not provided. Instead, you can assert and check
910 that a value belongs to a certain subclass, and return it as element of that
911 class, using the @samp{As} and @samp{The} macros.
912 @cindex @code{As()()}
913 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
914 @var{type} and returns it as such.
915 @cindex @code{The()()}
916 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
917 @var{type} and returns it as such. It is your responsibility to ensure
918 that this assumption is valid.
924 if (!(x >= 0)) abort();
925 cl_I ten_x = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
926 // In general, it would be a rational number.
931 @node Functions on numbers, Input/Output, Ordinary number types, Top
932 @chapter Functions on numbers
934 Each of the number classes declares its mathematical operations in the
935 corresponding include file. For example, if your code operates with
936 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
940 * Constructing numbers::
941 * Elementary functions::
942 * Elementary rational functions::
943 * Elementary complex functions::
945 * Rounding functions::
947 * Transcendental functions::
948 * Functions on integers::
949 * Functions on floating-point numbers::
950 * Conversion functions::
951 * Random number generators::
952 * Obfuscating operators::
955 @node Constructing numbers, Elementary functions, Functions on numbers, Functions on numbers
956 @section Constructing numbers
958 Here is how to create number objects ``from nothing''.
962 * Constructing integers::
963 * Constructing rational numbers::
964 * Constructing floating-point numbers::
965 * Constructing complex numbers::
968 @node Constructing integers, Constructing rational numbers, Constructing numbers, Constructing numbers
969 @subsection Constructing integers
971 @code{cl_I} objects are most easily constructed from C integers and from
972 strings. See @ref{Conversions}.
975 @node Constructing rational numbers, Constructing floating-point numbers, Constructing integers, Constructing numbers
976 @subsection Constructing rational numbers
978 @code{cl_RA} objects can be constructed from strings. The syntax
979 for rational numbers is described in @ref{Internal and printed representation}.
980 Another standard way to produce a rational number is through application
981 of @samp{operator /} or @samp{recip} on integers.
984 @node Constructing floating-point numbers, Constructing complex numbers, Constructing rational numbers, Constructing numbers
985 @subsection Constructing floating-point numbers
987 @code{cl_F} objects with low precision are most easily constructed from
988 C @samp{float} and @samp{double}. See @ref{Conversions}.
990 To construct a @code{cl_F} with high precision, you can use the conversion
991 from @samp{const char *}, but you have to specify the desired precision
992 within the string. (See @ref{Internal and printed representation}.)
995 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
997 will set @samp{e} to the given value, with a precision of 40 decimal digits.
999 The programmatic way to construct a @code{cl_F} with high precision is
1000 through the @code{cl_float} conversion function, see
1001 @ref{Conversion to floating-point numbers}. For example, to compute
1002 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
1003 and then apply the exponential function:
1005 cl_float_format_t precision = cl_float_format(40);
1006 cl_F e = exp(cl_float(1,precision));
1010 @node Constructing complex numbers, , Constructing floating-point numbers, Constructing numbers
1011 @subsection Constructing complex numbers
1013 Non-real @code{cl_N} objects are normally constructed through the function
1015 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
1017 See @ref{Elementary complex functions}.
1020 @node Elementary functions, Elementary rational functions, Constructing numbers, Functions on numbers
1021 @section Elementary functions
1023 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1024 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1025 defines the following operations:
1028 @item @var{type} operator + (const @var{type}&, const @var{type}&)
1029 @cindex @code{operator + ()}
1032 @item @var{type} operator - (const @var{type}&, const @var{type}&)
1033 @cindex @code{operator - ()}
1036 @item @var{type} operator - (const @var{type}&)
1037 Returns the negative of the argument.
1039 @item @var{type} plus1 (const @var{type}& x)
1040 @cindex @code{plus1 ()}
1041 Returns @code{x + 1}.
1043 @item @var{type} minus1 (const @var{type}& x)
1044 @cindex @code{minus1 ()}
1045 Returns @code{x - 1}.
1047 @item @var{type} operator * (const @var{type}&, const @var{type}&)
1048 @cindex @code{operator * ()}
1051 @item @var{type} square (const @var{type}& x)
1052 @cindex @code{square ()}
1053 Returns @code{x * x}.
1056 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
1057 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1058 defines the following operations:
1061 @item @var{type} operator / (const @var{type}&, const @var{type}&)
1062 @cindex @code{operator / ()}
1065 @item @var{type} recip (const @var{type}&)
1066 @cindex @code{recip ()}
1067 Returns the reciprocal of the argument.
1070 The class @code{cl_I} doesn't define a @samp{/} operation because
1071 in the C/C++ language this operator, applied to integral types,
1072 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
1073 is implementation dependent). (@xref{Rounding functions}.)
1074 Instead, @code{cl_I} defines an ``exact quotient'' function:
1077 @item cl_I exquo (const cl_I& x, const cl_I& y)
1078 @cindex @code{exquo ()}
1079 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
1082 The following exponentiation functions are defined:
1085 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
1086 @cindex @code{expt_pos ()}
1087 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
1088 @code{y} must be > 0. Returns @code{x^y}.
1090 @item cl_RA expt (const cl_RA& x, const cl_I& y)
1091 @cindex @code{expt ()}
1092 @itemx cl_R expt (const cl_R& x, const cl_I& y)
1093 @itemx cl_N expt (const cl_N& x, const cl_I& y)
1097 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1098 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1099 defines the following operation:
1102 @item @var{type} abs (const @var{type}& x)
1103 @cindex @code{abs ()}
1104 Returns the absolute value of @code{x}.
1105 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
1108 The class @code{cl_N} implements this as follows:
1111 @item cl_R abs (const cl_N x)
1112 Returns the absolute value of @code{x}.
1115 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1116 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1117 defines the following operation:
1120 @item @var{type} signum (const @var{type}& x)
1121 @cindex @code{signum ()}
1122 Returns the sign of @code{x}, in the same number format as @code{x}.
1123 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
1124 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
1129 @node Elementary rational functions, Elementary complex functions, Elementary functions, Functions on numbers
1130 @section Elementary rational functions
1132 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
1135 @item cl_I numerator (const @var{type}& x)
1136 @cindex @code{numerator ()}
1137 Returns the numerator of @code{x}.
1139 @item cl_I denominator (const @var{type}& x)
1140 @cindex @code{denominator ()}
1141 Returns the denominator of @code{x}.
1144 The numerator and denominator of a rational number are normalized in such
1145 a way that they have no factor in common and the denominator is positive.
1148 @node Elementary complex functions, Comparisons, Elementary rational functions, Functions on numbers
1149 @section Elementary complex functions
1151 The class @code{cl_N} defines the following operation:
1154 @item cl_N complex (const cl_R& a, const cl_R& b)
1155 @cindex @code{complex ()}
1156 Returns the complex number @code{a+bi}, that is, the complex number with
1157 real part @code{a} and imaginary part @code{b}.
1160 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1163 @item cl_R realpart (const @var{type}& x)
1164 @cindex @code{realpart ()}
1165 Returns the real part of @code{x}.
1167 @item cl_R imagpart (const @var{type}& x)
1168 @cindex @code{imagpart ()}
1169 Returns the imaginary part of @code{x}.
1171 @item @var{type} conjugate (const @var{type}& x)
1172 @cindex @code{conjugate ()}
1173 Returns the complex conjugate of @code{x}.
1176 We have the relations
1180 @code{x = complex(realpart(x), imagpart(x))}
1182 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1186 @node Comparisons, Rounding functions, Elementary complex functions, Functions on numbers
1187 @section Comparisons
1190 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1191 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1192 defines the following operations:
1195 @item bool operator == (const @var{type}&, const @var{type}&)
1196 @cindex @code{operator == ()}
1197 @itemx bool operator != (const @var{type}&, const @var{type}&)
1198 @cindex @code{operator != ()}
1199 Comparison, as in C and C++.
1201 @item uint32 equal_hashcode (const @var{type}&)
1202 @cindex @code{equal_hashcode ()}
1203 Returns a 32-bit hash code that is the same for any two numbers which are
1204 the same according to @code{==}. This hash code depends on the number's value,
1205 not its type or precision.
1207 @item cl_boolean zerop (const @var{type}& x)
1208 @cindex @code{zerop ()}
1209 Compare against zero: @code{x == 0}
1212 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1213 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1214 defines the following operations:
1217 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1218 @cindex @code{compare ()}
1219 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1220 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1222 @item bool operator <= (const @var{type}&, const @var{type}&)
1223 @cindex @code{operator <= ()}
1224 @itemx bool operator < (const @var{type}&, const @var{type}&)
1225 @cindex @code{operator < ()}
1226 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1227 @cindex @code{operator >= ()}
1228 @itemx bool operator > (const @var{type}&, const @var{type}&)
1229 @cindex @code{operator > ()}
1230 Comparison, as in C and C++.
1232 @item cl_boolean minusp (const @var{type}& x)
1233 @cindex @code{minusp ()}
1234 Compare against zero: @code{x < 0}
1236 @item cl_boolean plusp (const @var{type}& x)
1237 @cindex @code{plusp ()}
1238 Compare against zero: @code{x > 0}
1240 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1241 @cindex @code{max ()}
1242 Return the maximum of @code{x} and @code{y}.
1244 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1245 @cindex @code{min ()}
1246 Return the minimum of @code{x} and @code{y}.
1249 When a floating point number and a rational number are compared, the float
1250 is first converted to a rational number using the function @code{rational}.
1251 Since a floating point number actually represents an interval of real numbers,
1252 the result might be surprising.
1253 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1254 there is no floating point number whose value is exactly @code{1/3}.
1257 @node Rounding functions, Roots, Comparisons, Functions on numbers
1258 @section Rounding functions
1261 When a real number is to be converted to an integer, there is no ``best''
1262 rounding. The desired rounding function depends on the application.
1263 The Common Lisp and ISO Lisp standards offer four rounding functions:
1267 This is the largest integer <=@code{x}.
1270 This is the smallest integer >=@code{x}.
1273 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1276 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1277 integers, choose the even one.
1280 These functions have different advantages:
1282 @code{floor} and @code{ceiling} are translation invariant:
1283 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1284 for every @code{x} and every integer @code{n}.
1286 On the other hand, @code{truncate} and @code{round} are symmetric:
1287 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1288 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1289 down exactly as often as it rounds up.
1291 The functions are related like this:
1295 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1296 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1298 @code{truncate(x) = sign(x) * floor(abs(x))}
1301 Each of the classes @code{cl_R}, @code{cl_RA},
1302 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1303 defines the following operations:
1306 @item cl_I floor1 (const @var{type}& x)
1307 @cindex @code{floor1 ()}
1308 Returns @code{floor(x)}.
1309 @item cl_I ceiling1 (const @var{type}& x)
1310 @cindex @code{ceiling1 ()}
1311 Returns @code{ceiling(x)}.
1312 @item cl_I truncate1 (const @var{type}& x)
1313 @cindex @code{truncate1 ()}
1314 Returns @code{truncate(x)}.
1315 @item cl_I round1 (const @var{type}& x)
1316 @cindex @code{round1 ()}
1317 Returns @code{round(x)}.
1320 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1321 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1322 defines the following operations:
1325 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1326 Returns @code{floor(x/y)}.
1327 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1328 Returns @code{ceiling(x/y)}.
1329 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1330 Returns @code{truncate(x/y)}.
1331 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1332 Returns @code{round(x/y)}.
1335 These functions are called @samp{floor1}, @dots{} here instead of
1336 @samp{floor}, @dots{}, because on some systems, system dependent include
1337 files define @samp{floor} and @samp{ceiling} as macros.
1339 In many cases, one needs both the quotient and the remainder of a division.
1340 It is more efficient to compute both at the same time than to perform
1341 two divisions, one for quotient and the next one for the remainder.
1342 The following functions therefore return a structure containing both
1343 the quotient and the remainder. The suffix @samp{2} indicates the number
1344 of ``return values''. The remainder is defined as follows:
1348 for the computation of @code{quotient = floor(x)},
1349 @code{remainder = x - quotient},
1351 for the computation of @code{quotient = floor(x,y)},
1352 @code{remainder = x - quotient*y},
1355 and similarly for the other three operations.
1357 Each of the classes @code{cl_R}, @code{cl_RA},
1358 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1359 defines the following operations:
1362 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1363 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1364 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1365 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1366 @itemx @var{type}_div_t round2 (const @var{type}& x)
1369 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1370 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1371 defines the following operations:
1374 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1375 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1376 @cindex @code{floor2 ()}
1377 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1378 @cindex @code{ceiling2 ()}
1379 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1380 @cindex @code{truncate2 ()}
1381 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1382 @cindex @code{round2 ()}
1385 Sometimes, one wants the quotient as a floating-point number (of the
1386 same format as the argument, if the argument is a float) instead of as
1387 an integer. The prefix @samp{f} indicates this.
1390 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1391 defines the following operations:
1394 @item @var{type} ffloor (const @var{type}& x)
1395 @cindex @code{ffloor ()}
1396 @itemx @var{type} fceiling (const @var{type}& x)
1397 @cindex @code{fceiling ()}
1398 @itemx @var{type} ftruncate (const @var{type}& x)
1399 @cindex @code{ftruncate ()}
1400 @itemx @var{type} fround (const @var{type}& x)
1401 @cindex @code{fround ()}
1404 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1406 The class @code{cl_R} defines the following operations:
1409 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1410 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1411 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1412 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1415 These functions also exist in versions which return both the quotient
1416 and the remainder. The suffix @samp{2} indicates this.
1419 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1420 defines the following operations:
1421 @cindex @code{cl_F_fdiv_t}
1422 @cindex @code{cl_SF_fdiv_t}
1423 @cindex @code{cl_FF_fdiv_t}
1424 @cindex @code{cl_DF_fdiv_t}
1425 @cindex @code{cl_LF_fdiv_t}
1428 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1429 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1430 @cindex @code{ffloor2 ()}
1431 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1432 @cindex @code{fceiling2 ()}
1433 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1434 @cindex @code{ftruncate2 ()}
1435 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1436 @cindex @code{fround2 ()}
1438 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1439 @cindex @code{cl_R_fdiv_t}
1441 The class @code{cl_R} defines the following operations:
1444 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1445 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1446 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1447 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1448 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1451 Other applications need only the remainder of a division.
1452 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1453 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1454 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1458 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1460 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1463 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1464 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1465 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1467 The classes @code{cl_R}, @code{cl_I} define the following operations:
1470 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1471 @cindex @code{mod ()}
1472 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1473 @cindex @code{rem ()}
1477 @node Roots, Transcendental functions, Rounding functions, Functions on numbers
1480 Each of the classes @code{cl_R},
1481 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1482 defines the following operation:
1485 @item @var{type} sqrt (const @var{type}& x)
1486 @cindex @code{sqrt ()}
1487 @code{x} must be >= 0. This function returns the square root of @code{x},
1488 normalized to be >= 0. If @code{x} is the square of a rational number,
1489 @code{sqrt(x)} will be a rational number, else it will return a
1490 floating-point approximation.
1493 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1496 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1497 @cindex @code{sqrtp ()}
1498 This tests whether @code{x} is a perfect square. If so, it returns true
1499 and the exact square root in @code{*root}, else it returns false.
1502 Furthermore, for integers, similarly:
1505 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1506 @cindex @code{isqrt ()}
1507 @code{x} should be >= 0. This function sets @code{*root} to
1508 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1509 the boolean value @code{(expt(*root,2) == x)}.
1512 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1513 define the following operation:
1516 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1517 @cindex @code{rootp ()}
1518 @code{x} must be >= 0. @code{n} must be > 0.
1519 This tests whether @code{x} is an @code{n}th power of a rational number.
1520 If so, it returns true and the exact root in @code{*root}, else it returns
1524 The only square root function which accepts negative numbers is the one
1525 for class @code{cl_N}:
1528 @item cl_N sqrt (const cl_N& z)
1529 @cindex @code{sqrt ()}
1530 Returns the square root of @code{z}, as defined by the formula
1531 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1532 or to a complex number are done if necessary. The range of the result is the
1533 right half plane @code{realpart(sqrt(z)) >= 0}
1534 including the positive imaginary axis and 0, but excluding
1535 the negative imaginary axis.
1536 The result is an exact number only if @code{z} is an exact number.
1540 @node Transcendental functions, Functions on integers, Roots, Functions on numbers
1541 @section Transcendental functions
1542 @cindex transcendental functions
1544 The transcendental functions return an exact result if the argument
1545 is exact and the result is exact as well. Otherwise they must return
1546 inexact numbers even if the argument is exact.
1547 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1551 * Exponential and logarithmic functions::
1552 * Trigonometric functions::
1553 * Hyperbolic functions::
1558 @node Exponential and logarithmic functions, Trigonometric functions, Transcendental functions, Transcendental functions
1559 @subsection Exponential and logarithmic functions
1562 @item cl_R exp (const cl_R& x)
1563 @cindex @code{exp ()}
1564 @itemx cl_N exp (const cl_N& x)
1565 Returns the exponential function of @code{x}. This is @code{e^x} where
1566 @code{e} is the base of the natural logarithms. The range of the result
1567 is the entire complex plane excluding 0.
1569 @item cl_R ln (const cl_R& x)
1570 @cindex @code{ln ()}
1571 @code{x} must be > 0. Returns the (natural) logarithm of x.
1573 @item cl_N log (const cl_N& x)
1574 @cindex @code{log ()}
1575 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1576 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1577 The range of the result is the strip in the complex plane
1578 @code{-pi < imagpart(log(x)) <= pi}.
1580 @item cl_R phase (const cl_N& x)
1581 @cindex @code{phase ()}
1582 Returns the angle part of @code{x} in its polar representation as a
1583 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1584 This is also the imaginary part of @code{log(x)}.
1585 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1586 The result will be an exact number only if @code{zerop(x)} or
1587 if @code{x} is real and positive.
1589 @item cl_R log (const cl_R& a, const cl_R& b)
1590 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1591 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1592 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1595 @item cl_N log (const cl_N& a, const cl_N& b)
1596 Returns the logarithm of @code{a} with respect to base @code{b}.
1597 @code{log(a,b) = log(a)/log(b)}.
1599 @item cl_N expt (const cl_N& x, const cl_N& y)
1600 @cindex @code{expt ()}
1601 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1604 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1607 @item cl_F exp1 (cl_float_format_t f)
1608 @cindex @code{exp1 ()}
1609 Returns e as a float of format @code{f}.
1611 @item cl_F exp1 (const cl_F& y)
1612 Returns e in the float format of @code{y}.
1614 @item cl_F exp1 (void)
1615 Returns e as a float of format @code{default_float_format}.
1619 @node Trigonometric functions, Hyperbolic functions, Exponential and logarithmic functions, Transcendental functions
1620 @subsection Trigonometric functions
1623 @item cl_R sin (const cl_R& x)
1624 @cindex @code{sin ()}
1625 Returns @code{sin(x)}. The range of the result is the interval
1626 @code{-1 <= sin(x) <= 1}.
1628 @item cl_N sin (const cl_N& z)
1629 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1631 @item cl_R cos (const cl_R& x)
1632 @cindex @code{cos ()}
1633 Returns @code{cos(x)}. The range of the result is the interval
1634 @code{-1 <= cos(x) <= 1}.
1636 @item cl_N cos (const cl_N& x)
1637 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1639 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1640 @cindex @code{cos_sin_t}
1641 @itemx cos_sin_t cos_sin (const cl_R& x)
1642 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1643 @cindex @code{cos_sin ()}
1644 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1645 hold only approximately.
1647 @item cl_R tan (const cl_R& x)
1648 @cindex @code{tan ()}
1649 @itemx cl_N tan (const cl_N& x)
1650 Returns @code{tan(x) = sin(x)/cos(x)}.
1652 @item cl_N cis (const cl_R& x)
1653 @cindex @code{cis ()}
1654 @itemx cl_N cis (const cl_N& x)
1655 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1656 @code{e^(i*x) = cos(x) + i*sin(x)}.
1659 @cindex @code{asin ()}
1660 @item cl_N asin (const cl_N& z)
1661 Returns @code{arcsin(z)}. This is defined as
1662 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1663 @code{arcsin(-z) = -arcsin(z)}.
1664 The range of the result is the strip in the complex domain
1665 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1666 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1667 with @code{realpart = pi/2} and @code{imagpart > 0}.
1669 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1673 @item cl_N acos (const cl_N& z)
1674 @cindex @code{acos ()}
1675 Returns @code{arccos(z)}. This is defined as
1676 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1679 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1681 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1682 The range of the result is the strip in the complex domain
1683 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1684 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1685 with @code{realpart = pi} and @code{imagpart > 0}.
1687 Proof: This follows from the results about arcsin.
1691 @cindex @code{atan ()}
1692 @item cl_R atan (const cl_R& x, const cl_R& y)
1693 Returns the angle of the polar representation of the complex number
1694 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1695 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1696 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1697 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1698 with reversed order of arguments.
1700 @item cl_R atan (const cl_R& x)
1701 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1702 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1703 will be an exact number only if @code{x} is the exact @code{0}.
1705 @item cl_N atan (const cl_N& z)
1706 Returns @code{arctan(z)}. This is defined as
1707 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1708 @code{arctan(-z) = -arctan(z)}. The range of the result is
1709 the strip in the complex domain
1710 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1711 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1712 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1714 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1720 @cindex Archimedes' constant
1721 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1724 @item cl_F pi (cl_float_format_t f)
1725 @cindex @code{pi ()}
1726 Returns pi as a float of format @code{f}.
1728 @item cl_F pi (const cl_F& y)
1729 Returns pi in the float format of @code{y}.
1731 @item cl_F pi (void)
1732 Returns pi as a float of format @code{default_float_format}.
1736 @node Hyperbolic functions, Euler gamma, Trigonometric functions, Transcendental functions
1737 @subsection Hyperbolic functions
1740 @item cl_R sinh (const cl_R& x)
1741 @cindex @code{sinh ()}
1742 Returns @code{sinh(x)}.
1744 @item cl_N sinh (const cl_N& z)
1745 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1747 @item cl_R cosh (const cl_R& x)
1748 @cindex @code{cosh ()}
1749 Returns @code{cosh(x)}. The range of the result is the interval
1750 @code{cosh(x) >= 1}.
1752 @item cl_N cosh (const cl_N& z)
1753 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1755 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1756 @cindex @code{cosh_sinh_t}
1757 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1758 @cindex @code{cosh_sinh ()}
1759 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1760 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1761 hold only approximately.
1763 @item cl_R tanh (const cl_R& x)
1764 @cindex @code{tanh ()}
1765 @itemx cl_N tanh (const cl_N& x)
1766 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1768 @item cl_N asinh (const cl_N& z)
1769 @cindex @code{asinh ()}
1770 Returns @code{arsinh(z)}. This is defined as
1771 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1772 @code{arsinh(-z) = -arsinh(z)}.
1774 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1775 Actually, z+sqrt(1+z^2) can never be real and <0, so
1776 -pi < imagpart(arsinh(z)) < pi.
1777 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1778 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1780 The range of the result is the strip in the complex domain
1781 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1782 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1783 with @code{imagpart = pi/2} and @code{realpart < 0}.
1785 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1786 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1787 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1788 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1789 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1790 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1791 If y >= 1, the imagpart is pi/2 and the realpart is
1792 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1795 Moreover, if z is in Range(sqrt),
1796 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1797 (for a proof, see file src/cl_C_asinh.cc).
1800 @item cl_N acosh (const cl_N& z)
1801 @cindex @code{acosh ()}
1802 Returns @code{arcosh(z)}. This is defined as
1803 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1804 The range of the result is the half-strip in the complex domain
1805 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1806 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1808 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1809 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1810 If z is in Range(sqrt), we have
1811 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1812 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1814 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1815 and since the imagpart of both expressions is > -pi, <= pi
1816 ==> arcosh(z) = log(z+sqrt(z^2-1))
1817 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1818 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1819 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1820 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1821 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1823 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1824 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1825 = x^2 + y^2 + sqrt(u^2+v^2)
1830 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1831 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1832 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1833 Otherwise, -z is in Range(sqrt).
1834 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1835 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1836 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1837 and this has realpart > 0.
1838 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1839 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1840 has realpart = 0 and imagpart > 0.
1841 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1842 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1843 This has realpart >= 0 and imagpart = pi.
1846 @item cl_N atanh (const cl_N& z)
1847 @cindex @code{atanh ()}
1848 Returns @code{artanh(z)}. This is defined as
1849 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1850 @code{artanh(-z) = -artanh(z)}. The range of the result is
1851 the strip in the complex domain
1852 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1853 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1854 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1856 Proof: Write z = x+iy. Examine
1857 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1859 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1860 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1861 |x| < 1 ==> imagpart = 0
1864 = (atan(1+x,y) - atan(1-x,-y))/2
1865 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1866 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1867 > (pi - pi/2 - pi/2 )/2 = 0
1868 and (1+x)/y > (1-x)/y
1869 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1870 ==> imagpart < pi/2.
1871 Hence 0 < imagpart < pi/2.
1873 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1878 @node Euler gamma, Riemann zeta, Hyperbolic functions, Transcendental functions
1879 @subsection Euler gamma
1880 @cindex Euler's constant
1882 Euler's constant C = 0.577@dots{} is returned by the following functions:
1885 @item cl_F eulerconst (cl_float_format_t f)
1886 @cindex @code{eulerconst ()}
1887 Returns Euler's constant as a float of format @code{f}.
1889 @item cl_F eulerconst (const cl_F& y)
1890 Returns Euler's constant in the float format of @code{y}.
1892 @item cl_F eulerconst (void)
1893 Returns Euler's constant as a float of format @code{default_float_format}.
1896 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1897 @cindex Catalan's constant
1900 @item cl_F catalanconst (cl_float_format_t f)
1901 @cindex @code{catalanconst ()}
1902 Returns Catalan's constant as a float of format @code{f}.
1904 @item cl_F catalanconst (const cl_F& y)
1905 Returns Catalan's constant in the float format of @code{y}.
1907 @item cl_F catalanconst (void)
1908 Returns Catalan's constant as a float of format @code{default_float_format}.
1912 @node Riemann zeta, , Euler gamma, Transcendental functions
1913 @subsection Riemann zeta
1914 @cindex Riemann's zeta
1916 Riemann's zeta function at an integral point @code{s>1} is returned by the
1917 following functions:
1920 @item cl_F zeta (int s, cl_float_format_t f)
1921 @cindex @code{zeta ()}
1922 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1924 @item cl_F zeta (int s, const cl_F& y)
1925 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1927 @item cl_F zeta (int s)
1928 Returns Riemann's zeta function at @code{s} as a float of format
1929 @code{default_float_format}.
1933 @node Functions on integers, Functions on floating-point numbers, Transcendental functions, Functions on numbers
1934 @section Functions on integers
1937 * Logical functions::
1938 * Number theoretic functions::
1939 * Combinatorial functions::
1942 @node Logical functions, Number theoretic functions, Functions on integers, Functions on integers
1943 @subsection Logical functions
1945 Integers, when viewed as in two's complement notation, can be thought as
1946 infinite bit strings where the bits' values eventually are constant.
1953 The logical operations view integers as such bit strings and operate
1954 on each of the bit positions in parallel.
1957 @item cl_I lognot (const cl_I& x)
1958 @cindex @code{lognot ()}
1959 @itemx cl_I operator ~ (const cl_I& x)
1960 @cindex @code{operator ~ ()}
1961 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1963 @item cl_I logand (const cl_I& x, const cl_I& y)
1964 @cindex @code{logand ()}
1965 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1966 @cindex @code{operator & ()}
1967 Logical and, like @code{x & y} in C.
1969 @item cl_I logior (const cl_I& x, const cl_I& y)
1970 @cindex @code{logior ()}
1971 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1972 @cindex @code{operator | ()}
1973 Logical (inclusive) or, like @code{x | y} in C.
1975 @item cl_I logxor (const cl_I& x, const cl_I& y)
1976 @cindex @code{logxor ()}
1977 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1978 @cindex @code{operator ^ ()}
1979 Exclusive or, like @code{x ^ y} in C.
1981 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1982 @cindex @code{logeqv ()}
1983 Bitwise equivalence, like @code{~(x ^ y)} in C.
1985 @item cl_I lognand (const cl_I& x, const cl_I& y)
1986 @cindex @code{lognand ()}
1987 Bitwise not and, like @code{~(x & y)} in C.
1989 @item cl_I lognor (const cl_I& x, const cl_I& y)
1990 @cindex @code{lognor ()}
1991 Bitwise not or, like @code{~(x | y)} in C.
1993 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1994 @cindex @code{logandc1 ()}
1995 Logical and, complementing the first argument, like @code{~x & y} in C.
1997 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1998 @cindex @code{logandc2 ()}
1999 Logical and, complementing the second argument, like @code{x & ~y} in C.
2001 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
2002 @cindex @code{logorc1 ()}
2003 Logical or, complementing the first argument, like @code{~x | y} in C.
2005 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
2006 @cindex @code{logorc2 ()}
2007 Logical or, complementing the second argument, like @code{x | ~y} in C.
2010 These operations are all available though the function
2012 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
2013 @cindex @code{boole ()}
2015 where @code{op} must have one of the 16 values (each one stands for a function
2016 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
2017 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
2018 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
2019 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
2020 @code{boole_orc1}, @code{boole_orc2}.
2021 @cindex @code{boole_clr}
2022 @cindex @code{boole_set}
2023 @cindex @code{boole_1}
2024 @cindex @code{boole_2}
2025 @cindex @code{boole_c1}
2026 @cindex @code{boole_c2}
2027 @cindex @code{boole_and}
2028 @cindex @code{boole_xor}
2029 @cindex @code{boole_eqv}
2030 @cindex @code{boole_nand}
2031 @cindex @code{boole_nor}
2032 @cindex @code{boole_andc1}
2033 @cindex @code{boole_andc2}
2034 @cindex @code{boole_orc1}
2035 @cindex @code{boole_orc2}
2038 Other functions that view integers as bit strings:
2041 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
2042 @cindex @code{logtest ()}
2043 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
2044 @code{logand(x,y) != 0}.
2046 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
2047 @cindex @code{logbitp ()}
2048 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
2049 Bit 0 is the least significant bit.
2051 @item uintL logcount (const cl_I& x)
2052 @cindex @code{logcount ()}
2053 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
2054 the number of zero bits in @code{x}, if @code{x} < 0.
2057 The following functions operate on intervals of bits in integers.
2060 struct cl_byte @{ uintL size; uintL position; @};
2062 @cindex @code{cl_byte}
2063 represents the bit interval containing the bits
2064 @code{position}@dots{}@code{position+size-1} of an integer.
2065 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
2068 @item cl_I ldb (const cl_I& n, const cl_byte& b)
2069 @cindex @code{ldb ()}
2070 extracts the bits of @code{n} described by the bit interval @code{b}
2071 and returns them as a nonnegative integer with @code{b.size} bits.
2073 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
2074 @cindex @code{ldb_test ()}
2075 Returns true if some bit described by the bit interval @code{b} is set in
2078 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2079 @cindex @code{dpb ()}
2080 Returns @code{n}, with the bits described by the bit interval @code{b}
2081 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
2082 @code{newbyte} are relevant.
2085 The functions @code{ldb} and @code{dpb} implicitly shift. The following
2086 functions are their counterparts without shifting:
2089 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
2090 @cindex @code{mask_field ()}
2091 returns an integer with the bits described by the bit interval @code{b}
2092 copied from the corresponding bits in @code{n}, the other bits zero.
2094 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2095 @cindex @code{deposit_field ()}
2096 returns an integer where the bits described by the bit interval @code{b}
2097 come from @code{newbyte} and the other bits come from @code{n}.
2100 The following relations hold:
2104 @code{ldb (n, b) = mask_field(n, b) >> b.position},
2106 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
2108 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
2111 The following operations on integers as bit strings are efficient shortcuts
2112 for common arithmetic operations:
2115 @item cl_boolean oddp (const cl_I& x)
2116 @cindex @code{oddp ()}
2117 Returns true if the least significant bit of @code{x} is 1. Equivalent to
2118 @code{mod(x,2) != 0}.
2120 @item cl_boolean evenp (const cl_I& x)
2121 @cindex @code{evenp ()}
2122 Returns true if the least significant bit of @code{x} is 0. Equivalent to
2123 @code{mod(x,2) == 0}.
2125 @item cl_I operator << (const cl_I& x, const cl_I& n)
2126 @cindex @code{operator << ()}
2127 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
2128 Equivalent to @code{x * expt(2,n)}.
2130 @item cl_I operator >> (const cl_I& x, const cl_I& n)
2131 @cindex @code{operator >> ()}
2132 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
2133 Bits shifted out to the right are thrown away.
2134 Equivalent to @code{floor(x / expt(2,n))}.
2136 @item cl_I ash (const cl_I& x, const cl_I& y)
2137 @cindex @code{ash ()}
2138 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
2139 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
2140 returns @code{floor(x * expt(2,y))}.
2142 @item uintL integer_length (const cl_I& x)
2143 @cindex @code{integer_length ()}
2144 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
2145 in two's complement notation. This is the smallest n >= 0 such that
2146 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
2149 @item uintL ord2 (const cl_I& x)
2150 @cindex @code{ord2 ()}
2151 @code{x} must be non-zero. This function returns the number of 0 bits at the
2152 right of @code{x} in two's complement notation. This is the largest n >= 0
2153 such that 2^n divides @code{x}.
2155 @item uintL power2p (const cl_I& x)
2156 @cindex @code{power2p ()}
2157 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
2158 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
2159 (See also the function @code{logp}.)
2163 @node Number theoretic functions, Combinatorial functions, Logical functions, Functions on integers
2164 @subsection Number theoretic functions
2167 @item uint32 gcd (uint32 a, uint32 b)
2168 @cindex @code{gcd ()}
2169 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
2170 This function returns the greatest common divisor of @code{a} and @code{b},
2171 normalized to be >= 0.
2173 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
2174 @cindex @code{xgcd ()}
2175 This function (``extended gcd'') returns the greatest common divisor @code{g} of
2176 @code{a} and @code{b} and at the same time the representation of @code{g}
2177 as an integral linear combination of @code{a} and @code{b}:
2178 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
2179 @code{u} and @code{v} will be normalized to be of smallest possible absolute
2180 value, in the following sense: If @code{a} and @code{b} are non-zero, and
2181 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
2182 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
2184 @item cl_I lcm (const cl_I& a, const cl_I& b)
2185 @cindex @code{lcm ()}
2186 This function returns the least common multiple of @code{a} and @code{b},
2187 normalized to be >= 0.
2189 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
2190 @cindex @code{logp ()}
2191 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2192 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2193 rational number, this function returns true and sets *l = log(a,b), else
2198 @node Combinatorial functions, , Number theoretic functions, Functions on integers
2199 @subsection Combinatorial functions
2202 @item cl_I factorial (uintL n)
2203 @cindex @code{factorial ()}
2204 @code{n} must be a small integer >= 0. This function returns the factorial
2205 @code{n}! = @code{1*2*@dots{}*n}.
2207 @item cl_I doublefactorial (uintL n)
2208 @cindex @code{doublefactorial ()}
2209 @code{n} must be a small integer >= 0. This function returns the
2210 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2211 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2213 @item cl_I binomial (uintL n, uintL k)
2214 @cindex @code{binomial ()}
2215 @code{n} and @code{k} must be small integers >= 0. This function returns the
2216 binomial coefficient
2218 ${n \choose k} = {n! \over n! (n-k)!}$
2221 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2223 for 0 <= k <= n, 0 else.
2227 @node Functions on floating-point numbers, Conversion functions, Functions on integers, Functions on numbers
2228 @section Functions on floating-point numbers
2230 Recall that a floating-point number consists of a sign @code{s}, an
2231 exponent @code{e} and a mantissa @code{m}. The value of the number is
2232 @code{(-1)^s * 2^e * m}.
2235 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2236 defines the following operations.
2239 @item @var{type} scale_float (const @var{type}& x, sintL delta)
2240 @cindex @code{scale_float ()}
2241 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2242 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2243 because it copies @code{x} and modifies the exponent.
2246 The following functions provide an abstract interface to the underlying
2247 representation of floating-point numbers.
2250 @item sintL float_exponent (const @var{type}& x)
2251 @cindex @code{float_exponent ()}
2252 Returns the exponent @code{e} of @code{x}.
2253 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2254 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2256 @item sintL float_radix (const @var{type}& x)
2257 @cindex @code{float_radix ()}
2258 Returns the base of the floating-point representation. This is always @code{2}.
2260 @item @var{type} float_sign (const @var{type}& x)
2261 @cindex @code{float_sign ()}
2262 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2263 @code{x} >= 0, -1 for @code{x} < 0.
2265 @item uintL float_digits (const @var{type}& x)
2266 @cindex @code{float_digits ()}
2267 Returns the number of mantissa bits in the floating-point representation
2268 of @code{x}, including the hidden bit. The value only depends on the type
2269 of @code{x}, not on its value.
2271 @item uintL float_precision (const @var{type}& x)
2272 @cindex @code{float_precision ()}
2273 Returns the number of significant mantissa bits in the floating-point
2274 representation of @code{x}. Since denormalized numbers are not supported,
2275 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2279 The complete internal representation of a float is encoded in the type
2280 @cindex @code{decoded_float}
2281 @cindex @code{decoded_sfloat}
2282 @cindex @code{decoded_ffloat}
2283 @cindex @code{decoded_dfloat}
2284 @cindex @code{decoded_lfloat}
2285 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2286 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2288 struct decoded_@var{type}float @{
2289 @var{type} mantissa; cl_I exponent; @var{type} sign;
2293 and returned by the function
2296 @item decoded_@var{type}float decode_float (const @var{type}& x)
2297 @cindex @code{decode_float ()}
2298 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2299 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2300 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2301 @code{e} is the same as returned by the function @code{float_exponent}.
2304 A complete decoding in terms of integers is provided as type
2305 @cindex @code{cl_idecoded_float}
2307 struct cl_idecoded_float @{
2308 cl_I mantissa; cl_I exponent; cl_I sign;
2311 by the following function:
2314 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2315 @cindex @code{integer_decode_float ()}
2316 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2317 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2318 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2319 WARNING: The exponent @code{e} is not the same as the one returned by
2320 the functions @code{decode_float} and @code{float_exponent}.
2323 Some other function, implemented only for class @code{cl_F}:
2326 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2327 @cindex @code{float_sign ()}
2328 This returns a floating point number whose precision and absolute value
2329 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2330 zero, it is treated as positive. Same for @code{y}.
2334 @node Conversion functions, Random number generators, Functions on floating-point numbers, Functions on numbers
2335 @section Conversion functions
2339 * Conversion to floating-point numbers::
2340 * Conversion to rational numbers::
2343 @node Conversion to floating-point numbers, Conversion to rational numbers, Conversion functions, Conversion functions
2344 @subsection Conversion to floating-point numbers
2346 The type @code{cl_float_format_t} describes a floating-point format.
2347 @cindex @code{cl_float_format_t}
2350 @item cl_float_format_t cl_float_format (uintL n)
2351 @cindex @code{cl_float_format ()}
2352 Returns the smallest float format which guarantees at least @code{n}
2353 decimal digits in the mantissa (after the decimal point).
2355 @item cl_float_format_t cl_float_format (const cl_F& x)
2356 Returns the floating point format of @code{x}.
2358 @item cl_float_format_t default_float_format
2359 @cindex @code{default_float_format}
2360 Global variable: the default float format used when converting rational numbers
2364 To convert a real number to a float, each of the types
2365 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2366 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2367 defines the following operations:
2370 @item cl_F cl_float (const @var{type}&x, cl_float_format_t f)
2371 @cindex @code{cl_float ()}
2372 Returns @code{x} as a float of format @code{f}.
2373 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2374 Returns @code{x} in the float format of @code{y}.
2375 @item cl_F cl_float (const @var{type}&x)
2376 Returns @code{x} as a float of format @code{default_float_format} if
2377 it is an exact number, or @code{x} itself if it is already a float.
2380 Of course, converting a number to a float can lose precision.
2382 Every floating-point format has some characteristic numbers:
2385 @item cl_F most_positive_float (cl_float_format_t f)
2386 @cindex @code{most_positive_float ()}
2387 Returns the largest (most positive) floating point number in float format @code{f}.
2389 @item cl_F most_negative_float (cl_float_format_t f)
2390 @cindex @code{most_negative_float ()}
2391 Returns the smallest (most negative) floating point number in float format @code{f}.
2393 @item cl_F least_positive_float (cl_float_format_t f)
2394 @cindex @code{least_positive_float ()}
2395 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2396 in float format @code{f}.
2398 @item cl_F least_negative_float (cl_float_format_t f)
2399 @cindex @code{least_negative_float ()}
2400 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2401 in float format @code{f}.
2403 @item cl_F float_epsilon (cl_float_format_t f)
2404 @cindex @code{float_epsilon ()}
2405 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2407 @item cl_F float_negative_epsilon (cl_float_format_t f)
2408 @cindex @code{float_negative_epsilon ()}
2409 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2413 @node Conversion to rational numbers, , Conversion to floating-point numbers, Conversion functions
2414 @subsection Conversion to rational numbers
2416 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2417 defines the following operation:
2420 @item cl_RA rational (const @var{type}& x)
2421 @cindex @code{rational ()}
2422 Returns the value of @code{x} as an exact number. If @code{x} is already
2423 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2424 the value is a rational number whose denominator is a power of 2.
2427 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2431 @item cl_RA rationalize (const cl_R& x)
2432 @cindex @code{rationalize ()}
2433 If @code{x} is a floating-point number, it actually represents an interval
2434 of real numbers, and this function returns the rational number with
2435 smallest denominator (and smallest numerator, in magnitude)
2436 which lies in this interval.
2437 If @code{x} is already an exact number, this function returns @code{x}.
2440 If @code{x} is any float, one has
2444 @code{cl_float(rational(x),x) = x}
2446 @code{cl_float(rationalize(x),x) = x}
2450 @node Random number generators, Obfuscating operators, Conversion functions, Functions on numbers
2451 @section Random number generators
2454 A random generator is a machine which produces (pseudo-)random numbers.
2455 The include file @code{<cln/random.h>} defines a class @code{random_state}
2456 which contains the state of a random generator. If you make a copy
2457 of the random number generator, the original one and the copy will produce
2458 the same sequence of random numbers.
2460 The following functions return (pseudo-)random numbers in different formats.
2461 Calling one of these modifies the state of the random number generator in
2462 a complicated but deterministic way.
2465 @cindex @code{random_state}
2466 @cindex @code{default_random_state}
2468 random_state default_random_state
2470 contains a default random number generator. It is used when the functions
2471 below are called without @code{random_state} argument.
2474 @item uint32 random32 (random_state& randomstate)
2475 @itemx uint32 random32 ()
2476 @cindex @code{random32 ()}
2477 Returns a random unsigned 32-bit number. All bits are equally random.
2479 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2480 @itemx cl_I random_I (const cl_I& n)
2481 @cindex @code{random_I ()}
2482 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2483 in the range @code{0 <= x < n}.
2485 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2486 @itemx cl_F random_F (const cl_F& n)
2487 @cindex @code{random_F ()}
2488 @code{n} must be a float > 0. This function returns a random floating-point
2489 number of the same format as @code{n} in the range @code{0 <= x < n}.
2491 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2492 @itemx cl_R random_R (const cl_R& n)
2493 @cindex @code{random_R ()}
2494 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2495 if @code{n} is a float.
2499 @node Obfuscating operators, , Random number generators, Functions on numbers
2500 @section Obfuscating operators
2501 @cindex modifying operators
2503 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2504 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2505 are not available by default because their
2506 use tends to make programs unreadable. It is trivial to get away without
2507 them. However, if you feel that you absolutely need these operators
2508 to get happy, then add
2510 #define WANT_OBFUSCATING_OPERATORS
2512 @cindex @code{WANT_OBFUSCATING_OPERATORS}
2513 to the beginning of your source files, before the inclusion of any CLN
2514 include files. This flag will enable the following operators:
2516 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2517 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2520 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2521 @cindex @code{operator += ()}
2522 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2523 @cindex @code{operator -= ()}
2524 @itemx @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 /= ()}
2530 For the class @code{cl_I}:
2533 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2534 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2535 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2536 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2537 @cindex @code{operator &= ()}
2538 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2539 @cindex @code{operator |= ()}
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 >>= ()}
2548 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2549 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2552 @item @var{type}& operator ++ (@var{type}& x)
2553 @cindex @code{operator ++ ()}
2554 The prefix operator @code{++x}.
2556 @item void operator ++ (@var{type}& x, int)
2557 The postfix operator @code{x++}.
2559 @item @var{type}& operator -- (@var{type}& x)
2560 @cindex @code{operator -- ()}
2561 The prefix operator @code{--x}.
2563 @item void operator -- (@var{type}& x, int)
2564 The postfix operator @code{x--}.
2567 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2568 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2572 @node Input/Output, Rings, Functions on numbers, Top
2573 @chapter Input/Output
2574 @cindex Input/Output
2577 * Internal and printed representation::
2579 * Output functions::
2582 @node Internal and printed representation, Input functions, Input/Output, Input/Output
2583 @section Internal and printed representation
2584 @cindex representation
2586 All computations deal with the internal representations of the numbers.
2588 Every number has an external representation as a sequence of ASCII characters.
2589 Several external representations may denote the same number, for example,
2590 "20.0" and "20.000".
2592 Converting an internal to an external representation is called ``printing'',
2594 converting an external to an internal representation is called ``reading''.
2596 In CLN, it is always true that conversion of an internal to an external
2597 representation and then back to an internal representation will yield the
2598 same internal representation. Symbolically: @code{read(print(x)) == x}.
2599 This is called ``print-read consistency''.
2601 Different types of numbers have different external representations (case
2606 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2607 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2608 for decimal integers
2609 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2611 @item Rational numbers
2612 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2613 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2616 @item Floating-point numbers
2617 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2618 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2619 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2620 of the form _@var{prec} may be appended. There must be at least
2621 one digit in the non-exponent part. The exponent has the syntax
2622 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2623 The exponent marker is
2627 @samp{s} for short-floats,
2629 @samp{f} for single-floats,
2631 @samp{d} for double-floats,
2633 @samp{L} for long-floats,
2636 or @samp{e}, which denotes a default float format. The precision specifying
2637 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2638 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2639 function @samp{cl_float_format}.
2641 @item Complex numbers
2642 External representation:
2645 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2646 if @var{imagpart} is negative, its printed representation begins with
2647 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2648 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2649 is rational and the rational number's base is >18, because the @samp{i}
2650 is then read as a digit.
2652 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2657 @node Input functions, Output functions, Internal and printed representation, Input/Output
2658 @section Input functions
2660 Including @code{<cln/io.h>} defines a type @code{cl_istream}, which is
2661 the type of the first argument to all input functions. @code{cl_istream}
2662 is the same as @code{std::istream&}.
2667 @code{cl_istream stdin}
2669 contains the standard input stream.
2671 These are the simple input functions:
2674 @item int freadchar (cl_istream stream)
2675 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2676 if the end of stream was encountered or an error occurred.
2678 @item int funreadchar (cl_istream stream, int c)
2679 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2680 last @code{freadchar} operation on @code{stream}.
2683 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2684 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2685 defines, in @code{<cln/@var{type}_io.h>}, the following input function:
2688 @item cl_istream operator>> (cl_istream stream, @var{type}& result)
2689 Reads a number from @code{stream} and stores it in the @code{result}.
2692 The most flexible input functions, defined in @code{<cln/@var{type}_io.h>},
2696 @item cl_N read_complex (cl_istream stream, const cl_read_flags& flags)
2697 @itemx cl_R read_real (cl_istream stream, const cl_read_flags& flags)
2698 @itemx cl_F read_float (cl_istream stream, const cl_read_flags& flags)
2699 @itemx cl_RA read_rational (cl_istream stream, const cl_read_flags& flags)
2700 @itemx cl_I read_integer (cl_istream stream, const cl_read_flags& flags)
2701 Reads a number from @code{stream}. The @code{flags} are parameters which
2702 affect the input syntax. Whitespace before the number is silently skipped.
2704 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2705 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2706 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2707 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2708 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2709 Reads a number from a string in memory. The @code{flags} are parameters which
2710 affect the input syntax. The string starts at @code{string} and ends at
2711 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2712 @code{NULL}, denoting the entire string, i.e. equivalent to
2713 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2714 @code{NULL}, the string in memory must contain exactly one number and nothing
2715 more, else a fatal error will be signalled. If @code{end_of_parse}
2716 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2717 the last parsed character (i.e. @code{string_limit} if nothing came after
2718 the number). Whitespace is not allowed.
2721 The structure @code{cl_read_flags} contains the following fields:
2724 @item cl_read_syntax_t syntax
2725 The possible results of the read operation. Possible values are
2726 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2727 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2728 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2730 @item cl_read_lsyntax_t lsyntax
2731 Specifies the language-dependent syntax variant for the read operation.
2735 @item lsyntax_standard
2736 accept standard algebraic notation only, no complex numbers,
2737 @item lsyntax_algebraic
2738 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2739 @item lsyntax_commonlisp
2740 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2741 hexadecimal numbers,
2742 @code{#@var{base}R} for rational numbers in a given base,
2743 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2745 accept all of these extensions.
2748 @item unsigned int rational_base
2749 The base in which rational numbers are read.
2751 @item cl_float_format_t float_flags.default_float_format
2752 The float format used when reading floats with exponent marker @samp{e}.
2754 @item cl_float_format_t float_flags.default_lfloat_format
2755 The float format used when reading floats with exponent marker @samp{l}.
2757 @item cl_boolean float_flags.mantissa_dependent_float_format
2758 When this flag is true, floats specified with more digits than corresponding
2759 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2760 precision corresponding to their number of significant digits.
2764 @node Output functions, , Input functions, Input/Output
2765 @section Output functions
2767 Including @code{<cln/io.h>} defines a type @code{cl_ostream}, which is
2768 the type of the first argument to all output functions. @code{cl_ostream}
2769 is the same as @code{std::ostream&}.
2774 @code{cl_ostream stdout}
2776 contains the standard output stream.
2781 @code{cl_ostream stderr}
2783 contains the standard error output stream.
2785 These are the simple output functions:
2788 @item void fprintchar (cl_ostream stream, char c)
2789 Prints the character @code{x} literally on the @code{stream}.
2791 @item void fprint (cl_ostream stream, const char * string)
2792 Prints the @code{string} literally on the @code{stream}.
2794 @item void fprintdecimal (cl_ostream stream, int x)
2795 @itemx void fprintdecimal (cl_ostream stream, const cl_I& x)
2796 Prints the integer @code{x} in decimal on the @code{stream}.
2798 @item void fprintbinary (cl_ostream stream, const cl_I& x)
2799 Prints the integer @code{x} in binary (base 2, without prefix)
2800 on the @code{stream}.
2802 @item void fprintoctal (cl_ostream stream, const cl_I& x)
2803 Prints the integer @code{x} in octal (base 8, without prefix)
2804 on the @code{stream}.
2806 @item void fprinthexadecimal (cl_ostream stream, const cl_I& x)
2807 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2808 on the @code{stream}.
2811 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2812 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2813 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2816 @item void fprint (cl_ostream stream, const @var{type}& x)
2817 @itemx cl_ostream operator<< (cl_ostream stream, const @var{type}& x)
2818 Prints the number @code{x} on the @code{stream}. The output may depend
2819 on the global printer settings in the variable @code{default_print_flags}.
2820 The @code{ostream} flags and settings (flags, width and locale) are
2824 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2827 void print_complex (cl_ostream stream, const cl_print_flags& flags,
2829 void print_real (cl_ostream stream, const cl_print_flags& flags,
2831 void print_float (cl_ostream stream, const cl_print_flags& flags,
2833 void print_rational (cl_ostream stream, const cl_print_flags& flags,
2835 void print_integer (cl_ostream stream, const cl_print_flags& flags,
2838 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2839 parameters which affect the output.
2841 The structure type @code{cl_print_flags} contains the following fields:
2844 @item unsigned int rational_base
2845 The base in which rational numbers are printed. Default is @code{10}.
2847 @item cl_boolean rational_readably
2848 If this flag is true, rational numbers are printed with radix specifiers in
2849 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2850 prefixes, trailing dot). Default is false.
2852 @item cl_boolean float_readably
2853 If this flag is true, type specific exponent markers have precedence over 'E'.
2856 @item cl_float_format_t default_float_format
2857 Floating point numbers of this format will be printed using the 'E' exponent
2858 marker. Default is @code{cl_float_format_ffloat}.
2860 @item cl_boolean complex_readably
2861 If this flag is true, complex numbers will be printed using the Common Lisp
2862 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2864 @item cl_string univpoly_varname
2865 Univariate polynomials with no explicit indeterminate name will be printed
2866 using this variable name. Default is @code{"x"}.
2869 The global variable @code{default_print_flags} contains the default values,
2870 used by the function @code{fprint}.
2873 @node Rings, Modular integers, Input/Output, Top
2876 CLN has a class of abstract rings.
2884 Rings can be compared for equality:
2887 @item bool operator== (const cl_ring&, const cl_ring&)
2888 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2889 These compare two rings for equality.
2892 Given a ring @code{R}, the following members can be used.
2895 @item void R->fprint (cl_ostream stream, const cl_ring_element& x)
2896 @cindex @code{fprint ()}
2897 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2898 @cindex @code{equal ()}
2899 @itemx cl_ring_element R->zero ()
2900 @cindex @code{zero ()}
2901 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2902 @cindex @code{zerop ()}
2903 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2904 @cindex @code{plus ()}
2905 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2906 @cindex @code{minus ()}
2907 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2908 @cindex @code{uminus ()}
2909 @itemx cl_ring_element R->one ()
2910 @cindex @code{one ()}
2911 @itemx cl_ring_element R->canonhom (const cl_I& x)
2912 @cindex @code{canonhom ()}
2913 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2914 @cindex @code{mul ()}
2915 @itemx cl_ring_element R->square (const cl_ring_element& x)
2916 @cindex @code{square ()}
2917 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2918 @cindex @code{expt_pos ()}
2921 The following rings are built-in.
2924 @item cl_null_ring cl_0_ring
2925 The null ring, containing only zero.
2927 @item cl_complex_ring cl_C_ring
2928 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2930 @item cl_real_ring cl_R_ring
2931 The ring of real numbers. This corresponds to the type @code{cl_R}.
2933 @item cl_rational_ring cl_RA_ring
2934 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2936 @item cl_integer_ring cl_I_ring
2937 The ring of integers. This corresponds to the type @code{cl_I}.
2940 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2941 @code{cl_RA_ring}, @code{cl_I_ring}:
2944 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2945 @cindex @code{instanceof ()}
2946 Tests whether the given number is an element of the number ring R.
2950 @node Modular integers, Symbolic data types, Rings, Top
2951 @chapter Modular integers
2952 @cindex modular integer
2955 * Modular integer rings::
2956 * Functions on modular integers::
2959 @node Modular integer rings, Functions on modular integers, Modular integers, Modular integers
2960 @section Modular integer rings
2963 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2964 The modulus is explicitly part of every modular integer. CLN doesn't
2965 allow you to (accidentally) mix elements of different modular rings,
2966 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2967 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2968 doesn't have generic types. So one has to live with runtime checks.)
2970 The class of modular integer rings is
2978 Modular integer ring
2982 @cindex @code{cl_modint_ring}
2984 and the class of all modular integers (elements of modular integer rings) is
2992 Modular integer rings are constructed using the function
2995 @item cl_modint_ring find_modint_ring (const cl_I& N)
2996 @cindex @code{find_modint_ring ()}
2997 This function returns the modular ring @samp{Z/NZ}. It takes care
2998 of finding out about special cases of @code{N}, like powers of two
2999 and odd numbers for which Montgomery multiplication will be a win,
3000 @cindex Montgomery multiplication
3001 and precomputes any necessary auxiliary data for computing modulo @code{N}.
3002 There is a cache table of rings, indexed by @code{N} (or, more precisely,
3003 by @code{abs(N)}). This ensures that the precomputation costs are reduced
3007 Modular integer rings can be compared for equality:
3010 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
3011 @cindex @code{operator == ()}
3012 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
3013 @cindex @code{operator != ()}
3014 These compare two modular integer rings for equality. Two different calls
3015 to @code{find_modint_ring} with the same argument necessarily return the
3016 same ring because it is memoized in the cache table.
3019 @node Functions on modular integers, , Modular integer rings, Modular integers
3020 @section Functions on modular integers
3022 Given a modular integer ring @code{R}, the following members can be used.
3025 @item cl_I R->modulus
3026 @cindex @code{modulus}
3027 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
3029 @item cl_MI R->zero()
3030 @cindex @code{zero ()}
3031 This returns @code{0 mod N}.
3033 @item cl_MI R->one()
3034 @cindex @code{one ()}
3035 This returns @code{1 mod N}.
3037 @item cl_MI R->canonhom (const cl_I& x)
3038 @cindex @code{canonhom ()}
3039 This returns @code{x mod N}.
3041 @item cl_I R->retract (const cl_MI& x)
3042 @cindex @code{retract ()}
3043 This is a partial inverse function to @code{R->canonhom}. It returns the
3044 standard representative (@code{>=0}, @code{<N}) of @code{x}.
3046 @item cl_MI R->random(random_state& randomstate)
3047 @itemx cl_MI R->random()
3048 @cindex @code{random ()}
3049 This returns a random integer modulo @code{N}.
3052 The following operations are defined on modular integers.
3055 @item cl_modint_ring x.ring ()
3056 @cindex @code{ring ()}
3057 Returns the ring to which the modular integer @code{x} belongs.
3059 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
3060 @cindex @code{operator + ()}
3061 Returns the sum of two modular integers. One of the arguments may also
3064 @item cl_MI operator- (const cl_MI&, const cl_MI&)
3065 @cindex @code{operator - ()}
3066 Returns the difference of two modular integers. One of the arguments may also
3069 @item cl_MI operator- (const cl_MI&)
3070 Returns the negative of a modular integer.
3072 @item cl_MI operator* (const cl_MI&, const cl_MI&)
3073 @cindex @code{operator * ()}
3074 Returns the product of two modular integers. One of the arguments may also
3077 @item cl_MI square (const cl_MI&)
3078 @cindex @code{square ()}
3079 Returns the square of a modular integer.
3081 @item cl_MI recip (const cl_MI& x)
3082 @cindex @code{recip ()}
3083 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
3084 must be coprime to the modulus, otherwise an error message is issued.
3086 @item cl_MI div (const cl_MI& x, const cl_MI& y)
3087 @cindex @code{div ()}
3088 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
3089 @code{y} must be coprime to the modulus, otherwise an error message is issued.
3091 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
3092 @cindex @code{expt_pos ()}
3093 @code{y} must be > 0. Returns @code{x^y}.
3095 @item cl_MI expt (const cl_MI& x, const cl_I& y)
3096 @cindex @code{expt ()}
3097 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
3098 modulus, else an error message is issued.
3100 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
3101 @cindex @code{operator << ()}
3102 Returns @code{x*2^y}.
3104 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
3105 @cindex @code{operator >> ()}
3106 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
3107 or an error message is issued.
3109 @item bool operator== (const cl_MI&, const cl_MI&)
3110 @cindex @code{operator == ()}
3111 @itemx bool operator!= (const cl_MI&, const cl_MI&)
3112 @cindex @code{operator != ()}
3113 Compares two modular integers, belonging to the same modular integer ring,
3116 @item cl_boolean zerop (const cl_MI& x)
3117 @cindex @code{zerop ()}
3118 Returns true if @code{x} is @code{0 mod N}.
3121 The following output functions are defined (see also the chapter on
3125 @item void fprint (cl_ostream stream, const cl_MI& x)
3126 @cindex @code{fprint ()}
3127 @itemx cl_ostream operator<< (cl_ostream stream, const cl_MI& x)
3128 @cindex @code{operator << ()}
3129 Prints the modular integer @code{x} on the @code{stream}. The output may depend
3130 on the global printer settings in the variable @code{default_print_flags}.
3134 @node Symbolic data types, Univariate polynomials, Modular integers, Top
3135 @chapter Symbolic data types
3136 @cindex symbolic type
3138 CLN implements two symbolic (non-numeric) data types: strings and symbols.
3145 @node Strings, Symbols, Symbolic data types, Symbolic data types
3148 @cindex @code{cl_string}
3158 implements immutable strings.
3160 Strings are constructed through the following constructors:
3163 @item cl_string (const char * s)
3164 Returns an immutable copy of the (zero-terminated) C string @code{s}.
3166 @item cl_string (const char * ptr, unsigned long len)
3167 Returns an immutable copy of the @code{len} characters at
3168 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
3171 The following functions are available on strings:
3175 Assignment from @code{cl_string} and @code{const char *}.
3178 @cindex @code{length ()}
3180 @cindex @code{strlen ()}
3181 Returns the length of the string @code{s}.
3184 @cindex @code{operator [] ()}
3185 Returns the @code{i}th character of the string @code{s}.
3186 @code{i} must be in the range @code{0 <= i < s.length()}.
3188 @item bool equal (const cl_string& s1, const cl_string& s2)
3189 @cindex @code{equal ()}
3190 Compares two strings for equality. One of the arguments may also be a
3191 plain @code{const char *}.
3194 @node Symbols, , Strings, Symbolic data types
3197 @cindex @code{cl_symbol}
3199 Symbols are uniquified strings: all symbols with the same name are shared.
3200 This means that comparison of two symbols is fast (effectively just a pointer
3201 comparison), whereas comparison of two strings must in the worst case walk
3202 both strings until their end.
3203 Symbols are used, for example, as tags for properties, as names of variables
3204 in polynomial rings, etc.
3206 Symbols are constructed through the following constructor:
3209 @item cl_symbol (const cl_string& s)
3210 Looks up or creates a new symbol with a given name.
3213 The following operations are available on symbols:
3216 @item cl_string (const cl_symbol& sym)
3217 Conversion to @code{cl_string}: Returns the string which names the symbol
3220 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
3221 @cindex @code{equal ()}
3222 Compares two symbols for equality. This is very fast.
3226 @node Univariate polynomials, Internals, Symbolic data types, Top
3227 @chapter Univariate polynomials
3229 @cindex univariate polynomial
3232 * Univariate polynomial rings::
3233 * Functions on univariate polynomials::
3234 * Special polynomials::
3237 @node Univariate polynomial rings, Functions on univariate polynomials, Univariate polynomials, Univariate polynomials
3238 @section Univariate polynomial rings
3240 CLN implements univariate polynomials (polynomials in one variable) over an
3241 arbitrary ring. The indeterminate variable may be either unnamed (and will be
3242 printed according to @code{default_print_flags.univpoly_varname}, which
3243 defaults to @samp{x}) or carry a given name. The base ring and the
3244 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
3245 (accidentally) mix elements of different polynomial rings, e.g.
3246 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
3247 return a multivariate polynomial, but they are not yet implemented in CLN.)
3249 The classes of univariate polynomial rings are
3257 Univariate polynomial ring
3261 +----------------+-------------------+
3263 Complex polynomial ring | Modular integer polynomial ring
3264 cl_univpoly_complex_ring | cl_univpoly_modint_ring
3265 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3269 Real polynomial ring |
3270 cl_univpoly_real_ring |
3271 <cln/univpoly_real.h> |
3275 Rational polynomial ring |
3276 cl_univpoly_rational_ring |
3277 <cln/univpoly_rational.h> |
3281 Integer polynomial ring
3282 cl_univpoly_integer_ring
3283 <cln/univpoly_integer.h>
3286 and the corresponding classes of univariate polynomials are
3289 Univariate polynomial
3293 +----------------+-------------------+
3295 Complex polynomial | Modular integer polynomial
3297 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3303 <cln/univpoly_real.h> |
3307 Rational polynomial |
3309 <cln/univpoly_rational.h> |
3315 <cln/univpoly_integer.h>
3318 Univariate polynomial rings are constructed using the functions
3321 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3322 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3323 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3324 @code{R} may be an arbitrary ring. This function takes care of finding out
3325 about special cases of @code{R}, such as the rings of complex numbers,
3326 real numbers, rational numbers, integers, or modular integer rings.
3327 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3328 This ensures that two calls of this function with the same arguments will
3329 return the same polynomial ring.
3331 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3332 @cindex @code{find_univpoly_ring ()}
3333 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3334 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3335 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3336 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3337 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3338 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3339 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3340 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3341 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3342 These functions are equivalent to the general @code{find_univpoly_ring},
3343 only the return type is more specific, according to the base ring's type.
3346 @node Functions on univariate polynomials, Special polynomials, Univariate polynomial rings, Univariate polynomials
3347 @section Functions on univariate polynomials
3349 Given a univariate polynomial ring @code{R}, the following members can be used.
3352 @item cl_ring R->basering()
3353 @cindex @code{basering ()}
3354 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3356 @item cl_UP R->zero()
3357 @cindex @code{zero ()}
3358 This returns @code{0 in R}, a polynomial of degree -1.
3360 @item cl_UP R->one()
3361 @cindex @code{one ()}
3362 This returns @code{1 in R}, a polynomial of degree <= 0.
3364 @item cl_UP R->canonhom (const cl_I& x)
3365 @cindex @code{canonhom ()}
3366 This returns @code{x in R}, a polynomial of degree <= 0.
3368 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3369 @cindex @code{monomial ()}
3370 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3373 @item cl_UP R->create (sintL degree)
3374 @cindex @code{create ()}
3375 Creates a new polynomial with a given degree. The zero polynomial has degree
3376 @code{-1}. After creating the polynomial, you should put in the coefficients,
3377 using the @code{set_coeff} member function, and then call the @code{finalize}
3381 The following are the only destructive operations on univariate polynomials.
3384 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3385 @cindex @code{set_coeff ()}
3386 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3387 After changing a polynomial and before applying any "normal" operation on it,
3388 you should call its @code{finalize} member function.
3390 @item void finalize (cl_UP& x)
3391 @cindex @code{finalize ()}
3392 This function marks the endpoint of destructive modifications of a polynomial.
3393 It normalizes the internal representation so that subsequent computations have
3394 less overhead. Doing normal computations on unnormalized polynomials may
3395 produce wrong results or crash the program.
3398 The following operations are defined on univariate polynomials.
3401 @item cl_univpoly_ring x.ring ()
3402 @cindex @code{ring ()}
3403 Returns the ring to which the univariate polynomial @code{x} belongs.
3405 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3406 @cindex @code{operator + ()}
3407 Returns the sum of two univariate polynomials.
3409 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3410 @cindex @code{operator - ()}
3411 Returns the difference of two univariate polynomials.
3413 @item cl_UP operator- (const cl_UP&)
3414 Returns the negative of a univariate polynomial.
3416 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3417 @cindex @code{operator * ()}
3418 Returns the product of two univariate polynomials. One of the arguments may
3419 also be a plain integer or an element of the base ring.
3421 @item cl_UP square (const cl_UP&)
3422 @cindex @code{square ()}
3423 Returns the square of a univariate polynomial.
3425 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3426 @cindex @code{expt_pos ()}
3427 @code{y} must be > 0. Returns @code{x^y}.
3429 @item bool operator== (const cl_UP&, const cl_UP&)
3430 @cindex @code{operator == ()}
3431 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3432 @cindex @code{operator != ()}
3433 Compares two univariate polynomials, belonging to the same univariate
3434 polynomial ring, for equality.
3436 @item cl_boolean zerop (const cl_UP& x)
3437 @cindex @code{zerop ()}
3438 Returns true if @code{x} is @code{0 in R}.
3440 @item sintL degree (const cl_UP& x)
3441 @cindex @code{degree ()}
3442 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3444 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3445 @cindex @code{coeff ()}
3446 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3448 @item cl_ring_element x (const cl_ring_element& y)
3449 @cindex @code{operator () ()}
3450 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3451 then @samp{x(y)} returns the value of the substitution of @code{y} into
3454 @item cl_UP deriv (const cl_UP& x)
3455 @cindex @code{deriv ()}
3456 Returns the derivative of the polynomial @code{x} with respect to the
3457 indeterminate @code{X}.
3460 The following output functions are defined (see also the chapter on
3464 @item void fprint (cl_ostream stream, const cl_UP& x)
3465 @cindex @code{fprint ()}
3466 @itemx cl_ostream operator<< (cl_ostream stream, const cl_UP& x)
3467 @cindex @code{operator << ()}
3468 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3469 depend on the global printer settings in the variable
3470 @code{default_print_flags}.
3473 @node Special polynomials, , Functions on univariate polynomials, Univariate polynomials
3474 @section Special polynomials
3476 The following functions return special polynomials.
3479 @item cl_UP_I tschebychev (sintL n)
3480 @cindex @code{tschebychev ()}
3481 @cindex Chebyshev polynomial
3482 Returns the n-th Chebyshev polynomial (n >= 0).
3484 @item cl_UP_I hermite (sintL n)
3485 @cindex @code{hermite ()}
3486 @cindex Hermite polynomial
3487 Returns the n-th Hermite polynomial (n >= 0).
3489 @item cl_UP_RA legendre (sintL n)
3490 @cindex @code{legendre ()}
3491 @cindex Legende polynomial
3492 Returns the n-th Legendre polynomial (n >= 0).
3494 @item cl_UP_I laguerre (sintL n)
3495 @cindex @code{laguerre ()}
3496 @cindex Laguerre polynomial
3497 Returns the n-th Laguerre polynomial (n >= 0).
3500 Information how to derive the differential equation satisfied by each
3501 of these polynomials from their definition can be found in the
3502 @code{doc/polynomial/} directory.
3505 @node Internals, Using the library, Univariate polynomials, Top
3510 * Memory efficiency::
3511 * Speed efficiency::
3512 * Garbage collection::
3515 @node Why C++ ?, Memory efficiency, Internals, Internals
3519 Using C++ as an implementation language provides
3523 Efficiency: It compiles to machine code.
3527 Portability: It runs on all platforms supporting a C++ compiler. Because
3528 of the availability of GNU C++, this includes all currently used 32-bit and
3529 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3532 Type safety: The C++ compilers knows about the number types and complains if,
3533 for example, you try to assign a float to an integer variable. However,
3534 a drawback is that C++ doesn't know about generic types, hence a restriction
3535 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3536 arguments belong to the same modular ring cannot be expressed as a compile-time
3540 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3541 @code{=}, @code{==}, ... can be used in infix notation, which is more
3542 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3545 With these language features, there is no need for two separate languages,
3546 one for the implementation of the library and one in which the library's users
3547 can program. This means that a prototype implementation of an algorithm
3548 can be integrated into the library immediately after it has been tested and
3549 debugged. No need to rewrite it in a low-level language after having prototyped
3550 in a high-level language.
3553 @node Memory efficiency, Speed efficiency, Why C++ ?, Internals
3554 @section Memory efficiency
3556 In order to save memory allocations, CLN implements:
3560 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3563 @cindex garbage collection
3564 @cindex reference counting
3565 Garbage collection: A reference counting mechanism makes sure that any
3566 number object's storage is freed immediately when the last reference to the
3569 Small integers are represented as immediate values instead of pointers
3570 to heap allocated storage. This means that integers @code{> -2^29},
3571 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3576 @node Speed efficiency, Garbage collection, Memory efficiency, Internals
3577 @section Speed efficiency
3579 Speed efficiency is obtained by the combination of the following tricks
3584 Small integers, being represented as immediate values, don't require
3585 memory access, just a couple of instructions for each elementary operation.
3587 The kernel of CLN has been written in assembly language for some CPUs
3588 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3590 On all CPUs, CLN may be configured to use the superefficient low-level
3591 routines from GNU GMP version 3.
3593 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3594 algorithm, the Karatsuba multiplication, which is an
3605 For very large numbers (more than 12000 decimal digits), CLN uses
3607 Sch{@"o}nhage-Strassen
3608 @cindex Sch{@"o}nhage-Strassen multiplication
3612 @cindex Schönhage-Strassen multiplication
3614 multiplication, which is an asymptotically optimal multiplication
3617 These fast multiplication algorithms also give improvements in the speed
3618 of division and radix conversion.
3622 @node Garbage collection, , Speed efficiency, Internals
3623 @section Garbage collection
3624 @cindex garbage collection
3626 All the number classes are reference count classes: They only contain a pointer
3627 to an object in the heap. Upon construction, assignment and destruction of
3628 number objects, only the objects' reference count are manipulated.
3630 Memory occupied by number objects are automatically reclaimed as soon as
3631 their reference count drops to zero.
3633 For number rings, another strategy is implemented: There is a cache of,
3634 for example, the modular integer rings. A modular integer ring is destroyed
3635 only if its reference count dropped to zero and the cache is about to be
3636 resized. The effect of this strategy is that recently used rings remain
3637 cached, whereas undue memory consumption through cached rings is avoided.
3640 @node Using the library, Customizing, Internals, Top
3641 @chapter Using the library
3643 For the following discussion, we will assume that you have installed
3644 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3645 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3646 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3647 environment variables, or directly substitute the appropriate values.
3651 * Compiler options::
3652 * Compatibility to old CLN versions::
3655 * Debugging support::
3658 @node Compiler options, Compatibility to old CLN versions, Using the library, Using the library
3659 @section Compiler options
3660 @cindex compiler options
3662 Until you have installed CLN in a public place, the following options are
3665 When you compile CLN application code, add the flags
3667 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3669 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3670 When you link CLN application code to form an executable, add the flags
3672 $CLN_TARGETDIR/src/libcln.a
3674 to the C/C++ compiler's command line (@code{make} variable LIBS).
3676 If you did a @code{make install}, the include files are installed in a
3677 public directory (normally @code{/usr/local/include}), hence you don't
3678 need special flags for compiling. The library has been installed to a
3679 public directory as well (normally @code{/usr/local/lib}), hence when
3680 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3683 @node Compatibility to old CLN versions, Include files, Compiler options, Using the library
3684 @section Compatibility to old CLN versions
3686 @cindex compatibility
3688 As of CLN version 1.1 all non-macro identifiers were hidden in namespace
3689 @code{cln} in order to avoid potential name clashes with other C++
3690 libraries. If you have an old application, you will have to manually
3691 port it to the new scheme. The following principles will help during
3695 All headers are now in a separate subdirectory. Instead of including
3696 @code{cl_}@var{something}@code{.h}, include
3697 @code{cln/}@var{something}@code{.h} now.
3699 All public identifiers (typenames and functions) have lost their
3700 @code{cl_} prefix. Exceptions are all the typenames of number types,
3701 (cl_N, cl_I, cl_MI, @dots{}), rings, symbolic types (cl_string,
3702 cl_symbol) and polynomials (cl_UP_@var{type}). (This is because their
3703 names would not be mnemonic enough once the namespace @code{cln} is
3704 imported. Even in a namespace we favor @code{cl_N} over @code{N}.)
3706 All public @emph{functions} that had by a @code{cl_} in their name still
3707 carry that @code{cl_} if it is intrinsic part of a typename (as in
3708 @code{cl_I_to_int ()}).
3710 When developing other libraries, please keep in mind not to import the
3711 namespace @code{cln} in one of your public header files by saying
3712 @code{using namespace cln;}. This would propagate to other applications
3713 and can cause name clashes there.
3716 @node Include files, An Example, Compatibility to old CLN versions, Using the library
3717 @section Include files
3718 @cindex include files
3719 @cindex header files
3721 Here is a summary of the include files and their contents.
3724 @item <cln/object.h>
3725 General definitions, reference counting, garbage collection.
3726 @item <cln/number.h>
3727 The class cl_number.
3728 @item <cln/complex.h>
3729 Functions for class cl_N, the complex numbers.
3731 Functions for class cl_R, the real numbers.
3733 Functions for class cl_F, the floats.
3734 @item <cln/sfloat.h>
3735 Functions for class cl_SF, the short-floats.
3736 @item <cln/ffloat.h>
3737 Functions for class cl_FF, the single-floats.
3738 @item <cln/dfloat.h>
3739 Functions for class cl_DF, the double-floats.
3740 @item <cln/lfloat.h>
3741 Functions for class cl_LF, the long-floats.
3742 @item <cln/rational.h>
3743 Functions for class cl_RA, the rational numbers.
3744 @item <cln/integer.h>
3745 Functions for class cl_I, the integers.
3748 @item <cln/complex_io.h>
3749 Input/Output for class cl_N, the complex numbers.
3750 @item <cln/real_io.h>
3751 Input/Output for class cl_R, the real numbers.
3752 @item <cln/float_io.h>
3753 Input/Output for class cl_F, the floats.
3754 @item <cln/sfloat_io.h>
3755 Input/Output for class cl_SF, the short-floats.
3756 @item <cln/ffloat_io.h>
3757 Input/Output for class cl_FF, the single-floats.
3758 @item <cln/dfloat_io.h>
3759 Input/Output for class cl_DF, the double-floats.
3760 @item <cln/lfloat_io.h>
3761 Input/Output for class cl_LF, the long-floats.
3762 @item <cln/rational_io.h>
3763 Input/Output for class cl_RA, the rational numbers.
3764 @item <cln/integer_io.h>
3765 Input/Output for class cl_I, the integers.
3767 Flags for customizing input operations.
3768 @item <cln/output.h>
3769 Flags for customizing output operations.
3770 @item <cln/malloc.h>
3771 @code{malloc_hook}, @code{free_hook}.
3774 @item <cln/condition.h>
3775 Conditions/exceptions.
3776 @item <cln/string.h>
3778 @item <cln/symbol.h>
3780 @item <cln/proplist.h>
3784 @item <cln/null_ring.h>
3786 @item <cln/complex_ring.h>
3787 The ring of complex numbers.
3788 @item <cln/real_ring.h>
3789 The ring of real numbers.
3790 @item <cln/rational_ring.h>
3791 The ring of rational numbers.
3792 @item <cln/integer_ring.h>
3793 The ring of integers.
3794 @item <cln/numtheory.h>
3795 Number threory functions.
3796 @item <cln/modinteger.h>
3802 @item <cln/GV_number.h>
3803 General vectors over cl_number.
3804 @item <cln/GV_complex.h>
3805 General vectors over cl_N.
3806 @item <cln/GV_real.h>
3807 General vectors over cl_R.
3808 @item <cln/GV_rational.h>
3809 General vectors over cl_RA.
3810 @item <cln/GV_integer.h>
3811 General vectors over cl_I.
3812 @item <cln/GV_modinteger.h>
3813 General vectors of modular integers.
3816 @item <cln/SV_number.h>
3817 Simple vectors over cl_number.
3818 @item <cln/SV_complex.h>
3819 Simple vectors over cl_N.
3820 @item <cln/SV_real.h>
3821 Simple vectors over cl_R.
3822 @item <cln/SV_rational.h>
3823 Simple vectors over cl_RA.
3824 @item <cln/SV_integer.h>
3825 Simple vectors over cl_I.
3826 @item <cln/SV_ringelt.h>
3827 Simple vectors of general ring elements.
3828 @item <cln/univpoly.h>
3829 Univariate polynomials.
3830 @item <cln/univpoly_integer.h>
3831 Univariate polynomials over the integers.
3832 @item <cln/univpoly_rational.h>
3833 Univariate polynomials over the rational numbers.
3834 @item <cln/univpoly_real.h>
3835 Univariate polynomials over the real numbers.
3836 @item <cln/univpoly_complex.h>
3837 Univariate polynomials over the complex numbers.
3838 @item <cln/univpoly_modint.h>
3839 Univariate polynomials over modular integer rings.
3840 @item <cln/timing.h>
3843 Includes all of the above.
3847 @node An Example, Debugging support, Include files, Using the library
3850 A function which computes the nth Fibonacci number can be written as follows.
3851 @cindex Fibonacci number
3854 #include <cln/integer.h>
3855 #include <cln/real.h>
3856 using namespace cln;
3858 // Returns F_n, computed as the nearest integer to
3859 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3860 const cl_I fibonacci (int n)
3862 // Need a precision of ((1+sqrt(5))/2)^-n.
3863 cl_float_format_t prec = cl_float_format((int)(0.208987641*n+5));
3864 cl_R sqrt5 = sqrt(cl_float(5,prec));
3865 cl_R phi = (1+sqrt5)/2;
3866 return round1( expt(phi,n)/sqrt5 );
3870 Let's explain what is going on in detail.
3872 The include file @code{<cln/integer.h>} is necessary because the type
3873 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3874 is needed for the type @code{cl_R} and the floating point number functions.
3875 The order of the include files does not matter. In order not to write out
3876 @code{cln::}@var{foo} we can safely import the whole namespace @code{cln}.
3878 Then comes the function declaration. The argument is an @code{int}, the
3879 result an integer. The return type is defined as @samp{const cl_I}, not
3880 simply @samp{cl_I}, because that allows the compiler to detect typos like
3881 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3882 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3883 number). We use the most specialized possible return type because functions
3884 which call @samp{fibonacci} will be able to profit from the compiler's type
3885 analysis: Adding two integers is slightly more efficient than adding the
3886 same objects declared as complex numbers, because it needs less type
3887 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3888 the size of the resulting executable program.
3890 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3891 integer. In order to get a correct result, the absolute error should be less
3892 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3893 To this end, the first line computes a floating point precision for sqrt(5)
3896 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3897 number and than taking the square root. The converse, first taking the square
3898 root of 5, and then converting to the desired precision, would not work in
3899 CLN: The square root would be computed to a default precision (normally
3900 single-float precision), and the following conversion could not help about
3901 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3902 system and does not represent sqrt(5) in a non-numeric way.
3904 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3905 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3906 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3907 @code{cl_N} because a @samp{round1} does not exist for general complex
3910 When the function returns, all the local variables in the function are
3911 automatically reclaimed (garbage collected). Only the result survives and
3912 gets passed to the caller.
3914 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3915 contains this implementation together with an even faster algorithm.
3917 @node Debugging support, , An Example, Using the library
3918 @section Debugging support
3921 When debugging a CLN application with GNU @code{gdb}, two facilities are
3922 available from the library:
3925 @item The library does type checks, range checks, consistency checks at
3926 many places. When one of these fails, the function @code{cl_abort()} is
3927 called. Its default implementation is to perform an @code{exit(1)}, so
3928 you won't have a core dump. But for debugging, it is best to set a
3929 breakpoint at this function:
3931 (gdb) break cl_abort
3933 When this breakpoint is hit, look at the stack's backtrace:
3938 @item The debugger's normal @code{print} command doesn't know about
3939 CLN's types and therefore prints mostly useless hexadecimal addresses.
3940 CLN offers a function @code{cl_print}, callable from the debugger,
3941 for printing number objects. In order to get this function, you have
3942 to define the macro @samp{CL_DEBUG} and then include all the header files
3943 for which you want @code{cl_print} debugging support. For example:
3944 @cindex @code{CL_DEBUG}
3947 #include <cln/string.h>
3949 Now, if you have in your program a variable @code{cl_string s}, and
3950 inspect it under @code{gdb}, the output may look like this:
3953 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3954 word = 134568800@}@}, @}
3955 (gdb) call cl_print(s)
3959 Note that the output of @code{cl_print} goes to the program's error output,
3960 not to gdb's standard output.
3962 Note, however, that the above facility does not work with all CLN types,
3963 only with number objects and similar. Therefore CLN offers a member function
3964 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3965 is needed for this member function to be implemented. Under @code{gdb},
3966 you call it like this:
3967 @cindex @code{debug_print ()}
3970 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3971 word = 134568800@}@}, @}
3972 (gdb) call s.debug_print()
3975 >call ($1).debug_print()
3980 Unfortunately, this feature does not seem to work under all circumstances.
3984 @node Customizing, Index, Using the library, Top
3985 @chapter Customizing
3990 * Floating-point underflow::
3992 * Customizing the memory allocator::
3995 @node Error handling, Floating-point underflow, Customizing, Customizing
3996 @section Error handling
3998 When a fatal error occurs, an error message is output to the standard error
3999 output stream, and the function @code{cl_abort} is called. The default
4000 version of this function (provided in the library) terminates the application.
4001 To catch such a fatal error, you need to define the function @code{cl_abort}
4002 yourself, with the prototype
4004 #include <cln/abort.h>
4005 void cl_abort (void);
4007 @cindex @code{cl_abort ()}
4008 This function must not return control to its caller.
4011 @node Floating-point underflow, Customizing I/O, Error handling, Customizing
4012 @section Floating-point underflow
4015 Floating point underflow denotes the situation when a floating-point number
4016 is to be created which is so close to @code{0} that its exponent is too
4017 low to be represented internally. By default, this causes a fatal error.
4018 If you set the global variable
4020 cl_boolean cl_inhibit_floating_point_underflow
4022 to @code{cl_true}, the error will be inhibited, and a floating-point zero
4023 will be generated instead. The default value of
4024 @code{cl_inhibit_floating_point_underflow} is @code{cl_false}.
4027 @node Customizing I/O, Customizing the memory allocator, Floating-point underflow, Customizing
4028 @section Customizing I/O
4030 The output of the function @code{fprint} may be customized by changing the
4031 value of the global variable @code{default_print_flags}.
4032 @cindex @code{default_print_flags}
4035 @node Customizing the memory allocator, , Customizing I/O, Customizing
4036 @section Customizing the memory allocator
4038 Every memory allocation of CLN is done through the function pointer
4039 @code{malloc_hook}. Freeing of this memory is done through the function
4040 pointer @code{free_hook}. The default versions of these functions,
4041 provided in the library, call @code{malloc} and @code{free} and check
4042 the @code{malloc} result against @code{NULL}.
4043 If you want to provide another memory allocator, you need to define
4044 the variables @code{malloc_hook} and @code{free_hook} yourself,
4047 #include <cln/malloc.h>
4049 void* (*malloc_hook) (size_t size) = @dots{};
4050 void (*free_hook) (void* ptr) = @dots{};
4053 @cindex @code{malloc_hook ()}
4054 @cindex @code{free_hook ()}
4055 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
4057 It is not possible to change the memory allocator at runtime, because
4058 it is already called at program startup by the constructors of some
4066 @node Index, , Customizing, Top
4072 @c Table of contents