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::
216 * Debugging support::
221 * Floating-point underflow::
223 * Customizing the memory allocator::
228 @node Introduction, Installation, Top, Top
229 @comment node-name, next, previous, up
230 @chapter Introduction
233 CLN is a library for computations with all kinds of numbers.
234 It has a rich set of number classes:
238 Integers (with unlimited precision),
244 Floating-point numbers:
254 Long float (with unlimited precision),
261 Modular integers (integers modulo a fixed integer),
264 Univariate polynomials.
268 The subtypes of the complex numbers among these are exactly the
269 types of numbers known to the Common Lisp language. Therefore
270 @code{CLN} can be used for Common Lisp implementations, giving
271 @samp{CLN} another meaning: it becomes an abbreviation of
272 ``Common Lisp Numbers''.
275 The CLN package implements
279 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
280 comparisons, @dots{}),
283 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
286 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
287 functions and their inverse functions).
291 CLN is a C++ library. Using C++ as an implementation language provides
295 efficiency: it compiles to machine code,
297 type safety: the C++ compiler knows about the number types and complains
298 if, for example, you try to assign a float to an integer variable.
300 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
301 @code{==}, @dots{} operators as in C or C++.
305 CLN is memory efficient:
309 Small integers and short floats are immediate, not heap allocated.
311 Heap-allocated memory is reclaimed through an automatic, non-interruptive
316 CLN is speed efficient:
320 The kernel of CLN has been written in assembly language for some CPUs
321 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
324 On all CPUs, CLN may be configured to use the superefficient low-level
325 routines from GNU GMP version 3.
327 It uses Karatsuba multiplication, which is significantly faster
328 for large numbers than the standard multiplication algorithm.
330 For very large numbers (more than 12000 decimal digits), it uses
332 Sch{@"o}nhage-Strassen
333 @cindex Sch{@"o}nhage-Strassen multiplication
337 @cindex Schönhage-Strassen multiplication
339 multiplication, which is an asymptotically optimal multiplication
340 algorithm, for multiplication, division and radix conversion.
344 CLN aims at being easily integrated into larger software packages:
348 The garbage collection imposes no burden on the main application.
350 The library provides hooks for memory allocation and exceptions.
354 @node Installation, Ordinary number types, Introduction, Top
355 @chapter Installation
357 This section describes how to install the CLN package on your system.
362 * Building the library::
363 * Installing the library::
367 @node Prerequisites, Building the library, Installation, Installation
368 @section Prerequisites
376 @node C++ compiler, Make utility, Prerequisites, Prerequisites
377 @subsection C++ compiler
379 To build CLN, you need a C++ compiler.
380 Actually, you need GNU @code{g++ 2.7.0} or newer.
381 On HPPA, you need GNU @code{g++ 2.8.0} or newer.
382 I recommend GNU @code{g++ 2.95} or newer.
384 The following C++ features are used:
385 classes, member functions,
386 overloading of functions and operators,
387 constructors and destructors, inline, const,
388 multiple inheritance, templates.
390 The following C++ features are not used:
391 @code{new}, @code{delete}, virtual inheritance,
394 CLN relies on semi-automatic ordering of initializations
395 of static and global variables, a feature which I could
396 implement for GNU g++ only.
399 @comment cl_modules.h requires g++
400 Therefore nearly any C++ compiler will do.
402 The following C++ compilers are known to compile CLN:
405 GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
410 The following C++ compilers are known to be unusable for CLN:
413 On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
414 in lines containing @code{#if} or @code{#elif} preprocessor commands.
416 On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
417 in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
418 to have default constructors, and because it probably miscompiles the
419 integer multiplication routines.
421 On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
422 @code{short}s to @code{int}s by zero-extend.
426 On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
427 initializations will not work.
431 @node Make utility, Sed utility, C++ compiler, Prerequisites
432 @subsection Make utility
435 To build CLN, you also need to have GNU @code{make} installed.
437 @node Sed utility, , Make utility, Prerequisites
438 @subsection Sed utility
441 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
442 This is because the libtool script, which creates the CLN library, relies
443 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
447 @node Building the library, Installing the library, Prerequisites, Installation
448 @section Building the library
450 As with any autoconfiguring GNU software, installation is as easy as this:
458 If on your system, @samp{make} is not GNU @code{make}, you have to use
459 @samp{gmake} instead of @samp{make} above.
461 The @code{configure} command checks out some features of your system and
462 C++ compiler and builds the @code{Makefile}s. The @code{make} command
463 builds the library. This step may take 4 hours on an average workstation.
464 The @code{make check} runs some test to check that no important subroutine
465 has been miscompiled.
467 The @code{configure} command accepts options. To get a summary of them, try
473 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
475 You can specify the C compiler, the C++ compiler and their options through
476 the following environment variables when running @code{configure}:
480 Specifies the C compiler.
483 Flags to be given to the C compiler when compiling programs (not when linking).
486 Specifies the C++ compiler.
489 Flags to be given to the C++ compiler when compiling programs (not when linking).
495 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
496 $ CC="gcc -V 2.7.2" CFLAGS="-O -g" \
497 CXX="g++ -V 2.7.2" CXXFLAGS="-O -g" ./configure
498 $ CC="gcc -V 2.8.1" CFLAGS="-O -fno-exceptions" \
499 CXX="g++ -V 2.8.1" CXXFLAGS="-O -fno-exceptions" ./configure
500 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O2 -fno-exceptions" \
501 CXX="g++ -V egcs-2.91.60" CFLAGS="-O2 -fno-exceptions" ./configure
504 @comment cl_modules.h requires g++
505 You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
506 compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
509 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
510 $ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
513 On SGI Irix 5, if you wish not to use @code{g++}:
516 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
519 On SGI Irix 6, if you wish not to use @code{g++}:
522 $ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
523 ./configure --without-gmp
524 $ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
525 -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
526 ./configure --without-gmp
530 Note that for these environment variables to take effect, you have to set
531 them (assuming a Bourne-compatible shell) on the same line as the
532 @code{configure} command. If you made the settings in earlier shell
533 commands, you have to @code{export} the environment variables before
534 calling @code{configure}. In a @code{csh} shell, you have to use the
535 @samp{setenv} command for setting each of the environment variables.
537 On Linux, @code{g++} needs 15 MB to compile the tests. So you should better
538 have 17 MB swap space and 1 MB room in $TMPDIR.
540 If you use @code{g++} version 2.7.x, don't add @samp{-O2} to the CXXFLAGS,
541 because @samp{g++ -O} generates better code for CLN than @samp{g++ -O2}.
543 If you use @code{g++} version 2.8.x or egcs-2.91.x (a.k.a. egcs-1.1) or
544 gcc-2.95.x, I recommend adding @samp{-fno-exceptions} to the CXXFLAGS.
545 This will likely generate better code.
547 If you use @code{g++} version egcs-2.91.x (egcs-1.1) or gcc-2.95.x on Sparc,
548 add either @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
549 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division routines.
550 Also, if you have @code{g++} version egcs-1.1.1 or older on Sparc, you must
551 specify @samp{--disable-shared} because @code{g++} would miscompile parts of
554 By default, both a shared and a static library are built. You can build
555 CLN as a static (or shared) library only, by calling @code{configure} with
556 the option @samp{--disable-shared} (or @samp{--disable-static}). While
557 shared libraries are usually more convenient to use, they may not work
558 on all architectures. Try disabling them if you run into linker
559 problems. Also, they are generally somewhat slower than static
560 libraries so runtime-critical applications should be linked statically.
564 * Using the GNU MP Library::
567 @node Using the GNU MP Library, , Building the library, Building the library
568 @subsection Using the GNU MP Library
571 Starting with version 1.1, CLN may be configured to make use of a
572 preinstalled @code{gmp} library. Please make sure that you have at
573 least @code{gmp} version 3.0 installed since earlier versions are
574 unsupported and likely not to work. Enabling this feature by calling
575 @code{configure} with the option @samp{--with-gmp} is known to be quite
576 a boost for CLN's performance.
578 If you have installed the @code{gmp} library and its header file in
579 some place where your compiler cannot find it by default, you must help
580 @code{configure} by setting @code{CPPFLAGS} and @code{LDFLAGS}. Here is
584 $ CC="gcc" CFLAGS="-O2" CXX="g++" CXXFLAGS="-O2 -fno-exceptions" \
585 CPPFLAGS="-I/opt/gmp/include" LDFLAGS="-L/opt/gmp/lib" ./configure --with-gmp
589 @node Installing the library, Cleaning up, Building the library, Installation
590 @section Installing the library
593 As with any autoconfiguring GNU software, installation is as easy as this:
599 The @samp{make install} command installs the library and the include files
600 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
601 if you haven't specified a @code{--prefix} option to @code{configure}).
602 This step may require superuser privileges.
604 If you have already built the library and wish to install it, but didn't
605 specify @code{--prefix=@dots{}} at configure time, just re-run
606 @code{configure}, giving it the same options as the first time, plus
607 the @code{--prefix=@dots{}} option.
610 @node Cleaning up, , Installing the library, Installation
613 You can remove system-dependent files generated by @code{make} through
619 You can remove all files generated by @code{make}, thus reverting to a
620 virgin distribution of CLN, through
627 @node Ordinary number types, Functions on numbers, Installation, Top
628 @chapter Ordinary number types
630 CLN implements the following class hierarchy:
638 Real or complex number
647 +-------------------+-------------------+
649 Rational number Floating-point number
651 <cl_rational.h> <cl_float.h>
653 | +-------------+-------------+-------------+
655 cl_I Short-Float Single-Float Double-Float Long-Float
656 <cl_integer.h> cl_SF cl_FF cl_DF cl_LF
657 <cl_sfloat.h> <cl_ffloat.h> <cl_dfloat.h> <cl_lfloat.h>
660 @cindex @code{cl_number}
661 @cindex abstract class
662 The base class @code{cl_number} is an abstract base class.
663 It is not useful to declare a variable of this type except if you want
664 to completely disable compile-time type checking and use run-time type
669 @cindex complex number
670 The class @code{cl_N} comprises real and complex numbers. There is
671 no special class for complex numbers since complex numbers with imaginary
672 part @code{0} are automatically converted to real numbers.
675 The class @code{cl_R} comprises real numbers of different kinds. It is an
679 @cindex rational number
681 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
682 integers. There is no special class for non-integral rational numbers
683 since rational numbers with denominator @code{1} are automatically converted
687 The class @code{cl_F} implements floating-point approximations to real numbers.
688 It is an abstract class.
693 * Floating-point numbers::
698 @node Exact numbers, Floating-point numbers, Ordinary number types, Ordinary number types
699 @section Exact numbers
702 Some numbers are represented as exact numbers: there is no loss of information
703 when such a number is converted from its mathematical value to its internal
704 representation. On exact numbers, the elementary operations (@code{+},
705 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
708 In CLN, the exact numbers are:
712 rational numbers (including integers),
714 complex numbers whose real and imaginary parts are both rational numbers.
717 Rational numbers are always normalized to the form
718 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
719 are coprime integers and the denominator is positive. If the resulting
720 denominator is @code{1}, the rational number is converted to an integer.
722 Small integers (typically in the range @code{-2^30}@dots{}@code{2^30-1},
723 for 32-bit machines) are especially efficient, because they consume no heap
724 allocation. Otherwise the distinction between these immediate integers
725 (called ``fixnums'') and heap allocated integers (called ``bignums'')
726 is completely transparent.
729 @node Floating-point numbers, Complex numbers, Exact numbers, Ordinary number types
730 @section Floating-point numbers
731 @cindex floating-point number
733 Not all real numbers can be represented exactly. (There is an easy mathematical
734 proof for this: Only a countable set of numbers can be stored exactly in
735 a computer, even if one assumes that it has unlimited storage. But there
736 are uncountably many real numbers.) So some approximation is needed.
737 CLN implements ordinary floating-point numbers, with mantissa and exponent.
739 @cindex rounding error
740 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
741 only return approximate results. For example, the value of the expression
742 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
743 @samp{0.7}. Rounding errors like this one are inevitable when computing
744 with floating-point numbers.
746 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
747 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
748 rule: It first computes the exact mathematical result and then returns the
749 floating-point number which is nearest to this. If two floating-point numbers
750 are equally distant from the ideal result, the one with a @code{0} in its least
751 significant mantissa bit is chosen.
753 Similarly, testing floating point numbers for equality @samp{x == y}
754 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
755 for some well-chosen @code{epsilon}.
757 Floating point numbers come in four flavors:
762 Short floats, type @code{cl_SF}.
763 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
764 and 17 mantissa bits (including the ``hidden'' bit).
765 They don't consume heap allocation.
769 Single floats, type @code{cl_FF}.
770 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
771 and 24 mantissa bits (including the ``hidden'' bit).
772 In CLN, they are represented as IEEE single-precision floating point numbers.
773 This corresponds closely to the C/C++ type @samp{float}.
777 Double floats, type @code{cl_DF}.
778 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
779 and 53 mantissa bits (including the ``hidden'' bit).
780 In CLN, they are represented as IEEE double-precision floating point numbers.
781 This corresponds closely to the C/C++ type @samp{double}.
785 Long floats, type @code{cl_LF}.
786 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
787 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
788 The precision of a long float is unlimited, but once created, a long float
789 has a fixed precision. (No ``lazy recomputation''.)
792 Of course, computations with long floats are more expensive than those
793 with smaller floating-point formats.
795 CLN does not implement features like NaNs, denormalized numbers and
796 gradual underflow. If the exponent range of some floating-point type
797 is too limited for your application, choose another floating-point type
798 with larger exponent range.
801 As a user of CLN, you can forget about the differences between the
802 four floating-point types and just declare all your floating-point
803 variables as being of type @code{cl_F}. This has the advantage that
804 when you change the precision of some computation (say, from @code{cl_DF}
805 to @code{cl_LF}), you don't have to change the code, only the precision
806 of the initial values. Also, many transcendental functions have been
807 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
808 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
809 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
810 the floating point contagion rule happened to change in the future.)
813 @node Complex numbers, Conversions, Floating-point numbers, Ordinary number types
814 @section Complex numbers
815 @cindex complex number
817 Complex numbers, as implemented by the class @code{cl_N}, have a real
818 part and an imaginary part, both real numbers. A complex number whose
819 imaginary part is the exact number @code{0} is automatically converted
822 Complex numbers can arise from real numbers alone, for example
823 through application of @code{sqrt} or transcendental functions.
826 @node Conversions, , Complex numbers, Ordinary number types
830 Conversions from any class to any its superclasses (``base classes'' in
831 C++ terminology) is done automatically.
833 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
834 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
835 @code{cl_N} and @code{cl_number}.
837 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
838 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
839 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
840 efficiency. Their range is therefore limited:
844 The conversion from @samp{int} works only if the argument is < 2^29 and > -2^29.
846 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
849 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
850 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
851 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
853 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
854 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
855 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
856 @samp{cl_I}, first convert it to an @samp{unsigned long}.
858 Conversions from the C built-in type @samp{float} are provided for the classes
859 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
861 Conversions from the C built-in type @samp{double} are provided for the classes
862 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
864 Conversions from @samp{const char *} are provided for the classes
865 @code{cl_I}, @code{cl_RA},
866 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
867 @code{cl_R}, @code{cl_N}.
868 The easiest way to specify a value which is outside of the range of the
869 C++ built-in types is therefore to specify it as a string, like this:
872 cl_I order_of_rubiks_cube_group = "43252003274489856000";
874 Note that this conversion is done at runtime, not at compile-time.
876 Conversions from @code{cl_I} to the C built-in types @samp{int},
877 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
881 @item int cl_I_to_int (const cl_I& x)
882 @cindex @code{cl_I_to_int ()}
883 @itemx unsigned int cl_I_to_uint (const cl_I& x)
884 @cindex @code{cl_I_to_uint ()}
885 @itemx long cl_I_to_long (const cl_I& x)
886 @cindex @code{cl_I_to_long ()}
887 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
888 @cindex @code{cl_I_to_ulong ()}
889 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
890 representable in the range of @var{ctype}, a runtime error occurs.
893 Conversions from the classes @code{cl_I}, @code{cl_RA},
894 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
896 to the C built-in types @samp{float} and @samp{double} are provided through
900 @item float cl_float_approx (const @var{type}& x)
901 @cindex @code{cl_float_approx ()}
902 @itemx double cl_double_approx (const @var{type}& x)
903 @cindex @code{cl_double_approx ()}
904 Returns an approximation of @code{x} of C type @var{ctype}.
905 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
906 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
909 Conversions from any class to any of its subclasses (``derived classes'' in
910 C++ terminology) are not provided. Instead, you can assert and check
911 that a value belongs to a certain subclass, and return it as element of that
912 class, using the @samp{As} and @samp{The} macros.
913 @cindex @code{As()()}
914 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
915 @var{type} and returns it as such.
916 @cindex @code{The()()}
917 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
918 @var{type} and returns it as such. It is your responsibility to ensure
919 that this assumption is valid.
925 if (!(x >= 0)) abort();
926 cl_I ten_x = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
927 // In general, it would be a rational number.
932 @node Functions on numbers, Input/Output, Ordinary number types, Top
933 @chapter Functions on numbers
935 Each of the number classes declares its mathematical operations in the
936 corresponding include file. For example, if your code operates with
937 objects of type @code{cl_I}, it should @code{#include <cl_integer.h>}.
941 * Constructing numbers::
942 * Elementary functions::
943 * Elementary rational functions::
944 * Elementary complex functions::
946 * Rounding functions::
948 * Transcendental functions::
949 * Functions on integers::
950 * Functions on floating-point numbers::
951 * Conversion functions::
952 * Random number generators::
953 * Obfuscating operators::
956 @node Constructing numbers, Elementary functions, Functions on numbers, Functions on numbers
957 @section Constructing numbers
959 Here is how to create number objects ``from nothing''.
963 * Constructing integers::
964 * Constructing rational numbers::
965 * Constructing floating-point numbers::
966 * Constructing complex numbers::
969 @node Constructing integers, Constructing rational numbers, Constructing numbers, Constructing numbers
970 @subsection Constructing integers
972 @code{cl_I} objects are most easily constructed from C integers and from
973 strings. See @ref{Conversions}.
976 @node Constructing rational numbers, Constructing floating-point numbers, Constructing integers, Constructing numbers
977 @subsection Constructing rational numbers
979 @code{cl_RA} objects can be constructed from strings. The syntax
980 for rational numbers is described in @ref{Internal and printed representation}.
981 Another standard way to produce a rational number is through application
982 of @samp{operator /} or @samp{recip} on integers.
985 @node Constructing floating-point numbers, Constructing complex numbers, Constructing rational numbers, Constructing numbers
986 @subsection Constructing floating-point numbers
988 @code{cl_F} objects with low precision are most easily constructed from
989 C @samp{float} and @samp{double}. See @ref{Conversions}.
991 To construct a @code{cl_F} with high precision, you can use the conversion
992 from @samp{const char *}, but you have to specify the desired precision
993 within the string. (See @ref{Internal and printed representation}.)
996 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
998 will set @samp{e} to the given value, with a precision of 40 decimal digits.
1000 The programmatic way to construct a @code{cl_F} with high precision is
1001 through the @code{cl_float} conversion function, see
1002 @ref{Conversion to floating-point numbers}. For example, to compute
1003 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
1004 and then apply the exponential function:
1006 cl_float_format_t precision = cl_float_format(40);
1007 cl_F e = exp(cl_float(1,precision));
1011 @node Constructing complex numbers, , Constructing floating-point numbers, Constructing numbers
1012 @subsection Constructing complex numbers
1014 Non-real @code{cl_N} objects are normally constructed through the function
1016 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
1018 See @ref{Elementary complex functions}.
1021 @node Elementary functions, Elementary rational functions, Constructing numbers, Functions on numbers
1022 @section Elementary functions
1024 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1025 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1026 defines the following operations:
1029 @item @var{type} operator + (const @var{type}&, const @var{type}&)
1030 @cindex @code{operator + ()}
1033 @item @var{type} operator - (const @var{type}&, const @var{type}&)
1034 @cindex @code{operator - ()}
1037 @item @var{type} operator - (const @var{type}&)
1038 Returns the negative of the argument.
1040 @item @var{type} plus1 (const @var{type}& x)
1041 @cindex @code{plus1 ()}
1042 Returns @code{x + 1}.
1044 @item @var{type} minus1 (const @var{type}& x)
1045 @cindex @code{minus1 ()}
1046 Returns @code{x - 1}.
1048 @item @var{type} operator * (const @var{type}&, const @var{type}&)
1049 @cindex @code{operator * ()}
1052 @item @var{type} square (const @var{type}& x)
1053 @cindex @code{square ()}
1054 Returns @code{x * x}.
1057 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
1058 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1059 defines the following operations:
1062 @item @var{type} operator / (const @var{type}&, const @var{type}&)
1063 @cindex @code{operator / ()}
1066 @item @var{type} recip (const @var{type}&)
1067 @cindex @code{recip ()}
1068 Returns the reciprocal of the argument.
1071 The class @code{cl_I} doesn't define a @samp{/} operation because
1072 in the C/C++ language this operator, applied to integral types,
1073 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
1074 is implementation dependent). (@xref{Rounding functions}.)
1075 Instead, @code{cl_I} defines an ``exact quotient'' function:
1078 @item cl_I exquo (const cl_I& x, const cl_I& y)
1079 @cindex @code{exquo ()}
1080 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
1083 The following exponentiation functions are defined:
1086 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
1087 @cindex @code{expt_pos ()}
1088 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
1089 @code{y} must be > 0. Returns @code{x^y}.
1091 @item cl_RA expt (const cl_RA& x, const cl_I& y)
1092 @cindex @code{expt ()}
1093 @itemx cl_R expt (const cl_R& x, const cl_I& y)
1094 @itemx cl_N expt (const cl_N& x, const cl_I& y)
1098 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1099 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1100 defines the following operation:
1103 @item @var{type} abs (const @var{type}& x)
1104 @cindex @code{abs ()}
1105 Returns the absolute value of @code{x}.
1106 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
1109 The class @code{cl_N} implements this as follows:
1112 @item cl_R abs (const cl_N x)
1113 Returns the absolute value of @code{x}.
1116 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1117 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1118 defines the following operation:
1121 @item @var{type} signum (const @var{type}& x)
1122 @cindex @code{signum ()}
1123 Returns the sign of @code{x}, in the same number format as @code{x}.
1124 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
1125 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
1130 @node Elementary rational functions, Elementary complex functions, Elementary functions, Functions on numbers
1131 @section Elementary rational functions
1133 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
1136 @item cl_I numerator (const @var{type}& x)
1137 @cindex @code{numerator ()}
1138 Returns the numerator of @code{x}.
1140 @item cl_I denominator (const @var{type}& x)
1141 @cindex @code{denominator ()}
1142 Returns the denominator of @code{x}.
1145 The numerator and denominator of a rational number are normalized in such
1146 a way that they have no factor in common and the denominator is positive.
1149 @node Elementary complex functions, Comparisons, Elementary rational functions, Functions on numbers
1150 @section Elementary complex functions
1152 The class @code{cl_N} defines the following operation:
1155 @item cl_N complex (const cl_R& a, const cl_R& b)
1156 @cindex @code{complex ()}
1157 Returns the complex number @code{a+bi}, that is, the complex number with
1158 real part @code{a} and imaginary part @code{b}.
1161 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1164 @item cl_R realpart (const @var{type}& x)
1165 @cindex @code{realpart ()}
1166 Returns the real part of @code{x}.
1168 @item cl_R imagpart (const @var{type}& x)
1169 @cindex @code{imagpart ()}
1170 Returns the imaginary part of @code{x}.
1172 @item @var{type} conjugate (const @var{type}& x)
1173 @cindex @code{conjugate ()}
1174 Returns the complex conjugate of @code{x}.
1177 We have the relations
1181 @code{x = complex(realpart(x), imagpart(x))}
1183 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1187 @node Comparisons, Rounding functions, Elementary complex functions, Functions on numbers
1188 @section Comparisons
1191 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1192 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1193 defines the following operations:
1196 @item bool operator == (const @var{type}&, const @var{type}&)
1197 @cindex @code{operator == ()}
1198 @itemx bool operator != (const @var{type}&, const @var{type}&)
1199 @cindex @code{operator != ()}
1200 Comparison, as in C and C++.
1202 @item uint32 cl_equal_hashcode (const @var{type}&)
1203 @cindex @code{cl_equal_hashcode ()}
1204 Returns a 32-bit hash code that is the same for any two numbers which are
1205 the same according to @code{==}. This hash code depends on the number's value,
1206 not its type or precision.
1208 @item cl_boolean zerop (const @var{type}& x)
1209 @cindex @code{zerop ()}
1210 Compare against zero: @code{x == 0}
1213 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1214 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1215 defines the following operations:
1218 @item cl_signean cl_compare (const @var{type}& x, const @var{type}& y)
1219 @cindex @code{cl_compare ()}
1220 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1221 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1223 @item bool operator <= (const @var{type}&, const @var{type}&)
1224 @cindex @code{operator <= ()}
1225 @itemx bool operator < (const @var{type}&, const @var{type}&)
1226 @cindex @code{operator < ()}
1227 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1228 @cindex @code{operator >= ()}
1229 @itemx bool operator > (const @var{type}&, const @var{type}&)
1230 @cindex @code{operator > ()}
1231 Comparison, as in C and C++.
1233 @item cl_boolean minusp (const @var{type}& x)
1234 @cindex @code{minusp ()}
1235 Compare against zero: @code{x < 0}
1237 @item cl_boolean plusp (const @var{type}& x)
1238 @cindex @code{plusp ()}
1239 Compare against zero: @code{x > 0}
1241 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1242 @cindex @code{max ()}
1243 Return the maximum of @code{x} and @code{y}.
1245 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1246 @cindex @code{min ()}
1247 Return the minimum of @code{x} and @code{y}.
1250 When a floating point number and a rational number are compared, the float
1251 is first converted to a rational number using the function @code{rational}.
1252 Since a floating point number actually represents an interval of real numbers,
1253 the result might be surprising.
1254 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1255 there is no floating point number whose value is exactly @code{1/3}.
1258 @node Rounding functions, Roots, Comparisons, Functions on numbers
1259 @section Rounding functions
1262 When a real number is to be converted to an integer, there is no ``best''
1263 rounding. The desired rounding function depends on the application.
1264 The Common Lisp and ISO Lisp standards offer four rounding functions:
1268 This is the largest integer <=@code{x}.
1271 This is the smallest integer >=@code{x}.
1274 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1277 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1278 integers, choose the even one.
1281 These functions have different advantages:
1283 @code{floor} and @code{ceiling} are translation invariant:
1284 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1285 for every @code{x} and every integer @code{n}.
1287 On the other hand, @code{truncate} and @code{round} are symmetric:
1288 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1289 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1290 down exactly as often as it rounds up.
1292 The functions are related like this:
1296 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1297 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1299 @code{truncate(x) = sign(x) * floor(abs(x))}
1302 Each of the classes @code{cl_R}, @code{cl_RA},
1303 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1304 defines the following operations:
1307 @item cl_I floor1 (const @var{type}& x)
1308 @cindex @code{floor1 ()}
1309 Returns @code{floor(x)}.
1310 @item cl_I ceiling1 (const @var{type}& x)
1311 @cindex @code{ceiling1 ()}
1312 Returns @code{ceiling(x)}.
1313 @item cl_I truncate1 (const @var{type}& x)
1314 @cindex @code{truncate1 ()}
1315 Returns @code{truncate(x)}.
1316 @item cl_I round1 (const @var{type}& x)
1317 @cindex @code{round1 ()}
1318 Returns @code{round(x)}.
1321 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1322 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1323 defines the following operations:
1326 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1327 Returns @code{floor(x/y)}.
1328 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1329 Returns @code{ceiling(x/y)}.
1330 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1331 Returns @code{truncate(x/y)}.
1332 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1333 Returns @code{round(x/y)}.
1336 These functions are called @samp{floor1}, @dots{} here instead of
1337 @samp{floor}, @dots{}, because on some systems, system dependent include
1338 files define @samp{floor} and @samp{ceiling} as macros.
1340 In many cases, one needs both the quotient and the remainder of a division.
1341 It is more efficient to compute both at the same time than to perform
1342 two divisions, one for quotient and the next one for the remainder.
1343 The following functions therefore return a structure containing both
1344 the quotient and the remainder. The suffix @samp{2} indicates the number
1345 of ``return values''. The remainder is defined as follows:
1349 for the computation of @code{quotient = floor(x)},
1350 @code{remainder = x - quotient},
1352 for the computation of @code{quotient = floor(x,y)},
1353 @code{remainder = x - quotient*y},
1356 and similarly for the other three operations.
1358 Each of the classes @code{cl_R}, @code{cl_RA},
1359 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1360 defines the following operations:
1363 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1364 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1365 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1366 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1367 @itemx @var{type}_div_t round2 (const @var{type}& x)
1370 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1371 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1372 defines the following operations:
1375 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1376 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1377 @cindex @code{floor2 ()}
1378 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1379 @cindex @code{ceiling2 ()}
1380 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1381 @cindex @code{truncate2 ()}
1382 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1383 @cindex @code{round2 ()}
1386 Sometimes, one wants the quotient as a floating-point number (of the
1387 same format as the argument, if the argument is a float) instead of as
1388 an integer. The prefix @samp{f} indicates this.
1391 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1392 defines the following operations:
1395 @item @var{type} ffloor (const @var{type}& x)
1396 @cindex @code{ffloor ()}
1397 @itemx @var{type} fceiling (const @var{type}& x)
1398 @cindex @code{fceiling ()}
1399 @itemx @var{type} ftruncate (const @var{type}& x)
1400 @cindex @code{ftruncate ()}
1401 @itemx @var{type} fround (const @var{type}& x)
1402 @cindex @code{fround ()}
1405 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1407 The class @code{cl_R} defines the following operations:
1410 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1411 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1412 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1413 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1416 These functions also exist in versions which return both the quotient
1417 and the remainder. The suffix @samp{2} indicates this.
1420 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1421 defines the following operations:
1422 @cindex @code{cl_F_fdiv_t}
1423 @cindex @code{cl_SF_fdiv_t}
1424 @cindex @code{cl_FF_fdiv_t}
1425 @cindex @code{cl_DF_fdiv_t}
1426 @cindex @code{cl_LF_fdiv_t}
1429 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1430 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1431 @cindex @code{ffloor2 ()}
1432 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1433 @cindex @code{fceiling2 ()}
1434 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1435 @cindex @code{ftruncate2 ()}
1436 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1437 @cindex @code{fround2 ()}
1439 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1440 @cindex @code{cl_R_fdiv_t}
1442 The class @code{cl_R} defines the following operations:
1445 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1446 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1447 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1448 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1449 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1452 Other applications need only the remainder of a division.
1453 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1454 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1455 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1459 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1461 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1464 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1465 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1466 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1468 The classes @code{cl_R}, @code{cl_I} define the following operations:
1471 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1472 @cindex @code{mod ()}
1473 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1474 @cindex @code{rem ()}
1478 @node Roots, Transcendental functions, Rounding functions, Functions on numbers
1481 Each of the classes @code{cl_R},
1482 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1483 defines the following operation:
1486 @item @var{type} sqrt (const @var{type}& x)
1487 @cindex @code{sqrt ()}
1488 @code{x} must be >= 0. This function returns the square root of @code{x},
1489 normalized to be >= 0. If @code{x} is the square of a rational number,
1490 @code{sqrt(x)} will be a rational number, else it will return a
1491 floating-point approximation.
1494 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1497 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1498 @cindex @code{sqrtp ()}
1499 This tests whether @code{x} is a perfect square. If so, it returns true
1500 and the exact square root in @code{*root}, else it returns false.
1503 Furthermore, for integers, similarly:
1506 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1507 @cindex @code{isqrt ()}
1508 @code{x} should be >= 0. This function sets @code{*root} to
1509 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1510 the boolean value @code{(expt(*root,2) == x)}.
1513 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1514 define the following operation:
1517 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1518 @cindex @code{rootp ()}
1519 @code{x} must be >= 0. @code{n} must be > 0.
1520 This tests whether @code{x} is an @code{n}th power of a rational number.
1521 If so, it returns true and the exact root in @code{*root}, else it returns
1525 The only square root function which accepts negative numbers is the one
1526 for class @code{cl_N}:
1529 @item cl_N sqrt (const cl_N& z)
1530 @cindex @code{sqrt ()}
1531 Returns the square root of @code{z}, as defined by the formula
1532 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1533 or to a complex number are done if necessary. The range of the result is the
1534 right half plane @code{realpart(sqrt(z)) >= 0}
1535 including the positive imaginary axis and 0, but excluding
1536 the negative imaginary axis.
1537 The result is an exact number only if @code{z} is an exact number.
1541 @node Transcendental functions, Functions on integers, Roots, Functions on numbers
1542 @section Transcendental functions
1543 @cindex transcendental functions
1545 The transcendental functions return an exact result if the argument
1546 is exact and the result is exact as well. Otherwise they must return
1547 inexact numbers even if the argument is exact.
1548 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1552 * Exponential and logarithmic functions::
1553 * Trigonometric functions::
1554 * Hyperbolic functions::
1559 @node Exponential and logarithmic functions, Trigonometric functions, Transcendental functions, Transcendental functions
1560 @subsection Exponential and logarithmic functions
1563 @item cl_R exp (const cl_R& x)
1564 @cindex @code{exp ()}
1565 @itemx cl_N exp (const cl_N& x)
1566 Returns the exponential function of @code{x}. This is @code{e^x} where
1567 @code{e} is the base of the natural logarithms. The range of the result
1568 is the entire complex plane excluding 0.
1570 @item cl_R ln (const cl_R& x)
1571 @cindex @code{ln ()}
1572 @code{x} must be > 0. Returns the (natural) logarithm of x.
1574 @item cl_N log (const cl_N& x)
1575 @cindex @code{log ()}
1576 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1577 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1578 The range of the result is the strip in the complex plane
1579 @code{-pi < imagpart(log(x)) <= pi}.
1581 @item cl_R phase (const cl_N& x)
1582 @cindex @code{phase ()}
1583 Returns the angle part of @code{x} in its polar representation as a
1584 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1585 This is also the imaginary part of @code{log(x)}.
1586 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1587 The result will be an exact number only if @code{zerop(x)} or
1588 if @code{x} is real and positive.
1590 @item cl_R log (const cl_R& a, const cl_R& b)
1591 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1592 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1593 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1596 @item cl_N log (const cl_N& a, const cl_N& b)
1597 Returns the logarithm of @code{a} with respect to base @code{b}.
1598 @code{log(a,b) = log(a)/log(b)}.
1600 @item cl_N expt (const cl_N& x, const cl_N& y)
1601 @cindex @code{expt ()}
1602 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1605 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1608 @item cl_F cl_exp1 (cl_float_format_t f)
1609 @cindex @code{exp1 ()}
1610 Returns e as a float of format @code{f}.
1612 @item cl_F cl_exp1 (const cl_F& y)
1613 Returns e in the float format of @code{y}.
1615 @item cl_F cl_exp1 (void)
1616 Returns e as a float of format @code{cl_default_float_format}.
1620 @node Trigonometric functions, Hyperbolic functions, Exponential and logarithmic functions, Transcendental functions
1621 @subsection Trigonometric functions
1624 @item cl_R sin (const cl_R& x)
1625 @cindex @code{sin ()}
1626 Returns @code{sin(x)}. The range of the result is the interval
1627 @code{-1 <= sin(x) <= 1}.
1629 @item cl_N sin (const cl_N& z)
1630 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1632 @item cl_R cos (const cl_R& x)
1633 @cindex @code{cos ()}
1634 Returns @code{cos(x)}. The range of the result is the interval
1635 @code{-1 <= cos(x) <= 1}.
1637 @item cl_N cos (const cl_N& x)
1638 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1640 @item struct cl_cos_sin_t @{ cl_R cos; cl_R sin; @};
1641 @cindex @code{cl_cos_sin_t}
1642 @itemx cl_cos_sin_t cl_cos_sin (const cl_R& x)
1643 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1644 @cindex @code{cl_cos_sin ()}
1645 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1646 hold only approximately.
1648 @item cl_R tan (const cl_R& x)
1649 @cindex @code{tan ()}
1650 @itemx cl_N tan (const cl_N& x)
1651 Returns @code{tan(x) = sin(x)/cos(x)}.
1653 @item cl_N cis (const cl_R& x)
1654 @cindex @code{cis ()}
1655 @itemx cl_N cis (const cl_N& x)
1656 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1657 @code{e^(i*x) = cos(x) + i*sin(x)}.
1660 @cindex @code{asin ()}
1661 @item cl_N asin (const cl_N& z)
1662 Returns @code{arcsin(z)}. This is defined as
1663 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1664 @code{arcsin(-z) = -arcsin(z)}.
1665 The range of the result is the strip in the complex domain
1666 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1667 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1668 with @code{realpart = pi/2} and @code{imagpart > 0}.
1670 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1674 @item cl_N acos (const cl_N& z)
1675 @cindex @code{acos ()}
1676 Returns @code{arccos(z)}. This is defined as
1677 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1680 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1682 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1683 The range of the result is the strip in the complex domain
1684 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1685 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1686 with @code{realpart = pi} and @code{imagpart > 0}.
1688 Proof: This follows from the results about arcsin.
1692 @cindex @code{atan ()}
1693 @item cl_R atan (const cl_R& x, const cl_R& y)
1694 Returns the angle of the polar representation of the complex number
1695 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1696 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1697 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1698 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1699 with reversed order of arguments.
1701 @item cl_R atan (const cl_R& x)
1702 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1703 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1704 will be an exact number only if @code{x} is the exact @code{0}.
1706 @item cl_N atan (const cl_N& z)
1707 Returns @code{arctan(z)}. This is defined as
1708 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1709 @code{arctan(-z) = -arctan(z)}. The range of the result is
1710 the strip in the complex domain
1711 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1712 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1713 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1715 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1721 @cindex Archimedes' constant
1722 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1725 @item cl_F cl_pi (cl_float_format_t f)
1726 @cindex @code{cl_pi ()}
1727 Returns pi as a float of format @code{f}.
1729 @item cl_F cl_pi (const cl_F& y)
1730 Returns pi in the float format of @code{y}.
1732 @item cl_F cl_pi (void)
1733 Returns pi as a float of format @code{cl_default_float_format}.
1737 @node Hyperbolic functions, Euler gamma, Trigonometric functions, Transcendental functions
1738 @subsection Hyperbolic functions
1741 @item cl_R sinh (const cl_R& x)
1742 @cindex @code{sinh ()}
1743 Returns @code{sinh(x)}.
1745 @item cl_N sinh (const cl_N& z)
1746 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1748 @item cl_R cosh (const cl_R& x)
1749 @cindex @code{cosh ()}
1750 Returns @code{cosh(x)}. The range of the result is the interval
1751 @code{cosh(x) >= 1}.
1753 @item cl_N cosh (const cl_N& z)
1754 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1756 @item struct cl_cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1757 @cindex @code{cl_cosh_sinh_t}
1758 @itemx cl_cosh_sinh_t cl_cosh_sinh (const cl_R& x)
1759 @cindex @code{cl_cosh_sinh ()}
1760 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1761 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1762 hold only approximately.
1764 @item cl_R tanh (const cl_R& x)
1765 @cindex @code{tanh ()}
1766 @itemx cl_N tanh (const cl_N& x)
1767 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1769 @item cl_N asinh (const cl_N& z)
1770 @cindex @code{asinh ()}
1771 Returns @code{arsinh(z)}. This is defined as
1772 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1773 @code{arsinh(-z) = -arsinh(z)}.
1775 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1776 Actually, z+sqrt(1+z^2) can never be real and <0, so
1777 -pi < imagpart(arsinh(z)) < pi.
1778 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1779 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1781 The range of the result is the strip in the complex domain
1782 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1783 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1784 with @code{imagpart = pi/2} and @code{realpart < 0}.
1786 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1787 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1788 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1789 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1790 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1791 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1792 If y >= 1, the imagpart is pi/2 and the realpart is
1793 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1796 Moreover, if z is in Range(sqrt),
1797 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1798 (for a proof, see file src/cl_C_asinh.cc).
1801 @item cl_N acosh (const cl_N& z)
1802 @cindex @code{acosh ()}
1803 Returns @code{arcosh(z)}. This is defined as
1804 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1805 The range of the result is the half-strip in the complex domain
1806 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1807 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1809 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1810 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1811 If z is in Range(sqrt), we have
1812 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1813 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1815 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1816 and since the imagpart of both expressions is > -pi, <= pi
1817 ==> arcosh(z) = log(z+sqrt(z^2-1))
1818 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1819 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1820 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1821 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1822 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1824 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1825 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1826 = x^2 + y^2 + sqrt(u^2+v^2)
1831 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1832 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1833 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1834 Otherwise, -z is in Range(sqrt).
1835 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1836 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1837 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1838 and this has realpart > 0.
1839 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1840 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1841 has realpart = 0 and imagpart > 0.
1842 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1843 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1844 This has realpart >= 0 and imagpart = pi.
1847 @item cl_N atanh (const cl_N& z)
1848 @cindex @code{atanh ()}
1849 Returns @code{artanh(z)}. This is defined as
1850 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1851 @code{artanh(-z) = -artanh(z)}. The range of the result is
1852 the strip in the complex domain
1853 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1854 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1855 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1857 Proof: Write z = x+iy. Examine
1858 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1860 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1861 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1862 |x| < 1 ==> imagpart = 0
1865 = (atan(1+x,y) - atan(1-x,-y))/2
1866 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1867 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1868 > (pi - pi/2 - pi/2 )/2 = 0
1869 and (1+x)/y > (1-x)/y
1870 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1871 ==> imagpart < pi/2.
1872 Hence 0 < imagpart < pi/2.
1874 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1879 @node Euler gamma, Riemann zeta, Hyperbolic functions, Transcendental functions
1880 @subsection Euler gamma
1881 @cindex Euler's constant
1883 Euler's constant C = 0.577@dots{} is returned by the following functions:
1886 @item cl_F cl_eulerconst (cl_float_format_t f)
1887 @cindex @code{cl_eulerconst ()}
1888 Returns Euler's constant as a float of format @code{f}.
1890 @item cl_F cl_eulerconst (const cl_F& y)
1891 Returns Euler's constant in the float format of @code{y}.
1893 @item cl_F cl_eulerconst (void)
1894 Returns Euler's constant as a float of format @code{cl_default_float_format}.
1897 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1898 @cindex Catalan's constant
1901 @item cl_F cl_catalanconst (cl_float_format_t f)
1902 @cindex @code{cl_catalanconst ()}
1903 Returns Catalan's constant as a float of format @code{f}.
1905 @item cl_F cl_catalanconst (const cl_F& y)
1906 Returns Catalan's constant in the float format of @code{y}.
1908 @item cl_F cl_catalanconst (void)
1909 Returns Catalan's constant as a float of format @code{cl_default_float_format}.
1913 @node Riemann zeta, , Euler gamma, Transcendental functions
1914 @subsection Riemann zeta
1915 @cindex Riemann's zeta
1917 Riemann's zeta function at an integral point @code{s>1} is returned by the
1918 following functions:
1921 @item cl_F cl_zeta (int s, cl_float_format_t f)
1922 @cindex @code{cl_zeta ()}
1923 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1925 @item cl_F cl_zeta (int s, const cl_F& y)
1926 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1928 @item cl_F cl_zeta (int s)
1929 Returns Riemann's zeta function at @code{s} as a float of format
1930 @code{cl_default_float_format}.
1934 @node Functions on integers, Functions on floating-point numbers, Transcendental functions, Functions on numbers
1935 @section Functions on integers
1938 * Logical functions::
1939 * Number theoretic functions::
1940 * Combinatorial functions::
1943 @node Logical functions, Number theoretic functions, Functions on integers, Functions on integers
1944 @subsection Logical functions
1946 Integers, when viewed as in two's complement notation, can be thought as
1947 infinite bit strings where the bits' values eventually are constant.
1954 The logical operations view integers as such bit strings and operate
1955 on each of the bit positions in parallel.
1958 @item cl_I lognot (const cl_I& x)
1959 @cindex @code{lognot ()}
1960 @itemx cl_I operator ~ (const cl_I& x)
1961 @cindex @code{operator ~ ()}
1962 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1964 @item cl_I logand (const cl_I& x, const cl_I& y)
1965 @cindex @code{logand ()}
1966 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1967 @cindex @code{operator & ()}
1968 Logical and, like @code{x & y} in C.
1970 @item cl_I logior (const cl_I& x, const cl_I& y)
1971 @cindex @code{logior ()}
1972 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1973 @cindex @code{operator | ()}
1974 Logical (inclusive) or, like @code{x | y} in C.
1976 @item cl_I logxor (const cl_I& x, const cl_I& y)
1977 @cindex @code{logxor ()}
1978 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1979 @cindex @code{operator ^ ()}
1980 Exclusive or, like @code{x ^ y} in C.
1982 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1983 @cindex @code{logeqv ()}
1984 Bitwise equivalence, like @code{~(x ^ y)} in C.
1986 @item cl_I lognand (const cl_I& x, const cl_I& y)
1987 @cindex @code{lognand ()}
1988 Bitwise not and, like @code{~(x & y)} in C.
1990 @item cl_I lognor (const cl_I& x, const cl_I& y)
1991 @cindex @code{lognor ()}
1992 Bitwise not or, like @code{~(x | y)} in C.
1994 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1995 @cindex @code{logandc1 ()}
1996 Logical and, complementing the first argument, like @code{~x & y} in C.
1998 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1999 @cindex @code{logandc2 ()}
2000 Logical and, complementing the second argument, like @code{x & ~y} in C.
2002 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
2003 @cindex @code{logorc1 ()}
2004 Logical or, complementing the first argument, like @code{~x | y} in C.
2006 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
2007 @cindex @code{logorc2 ()}
2008 Logical or, complementing the second argument, like @code{x | ~y} in C.
2011 These operations are all available though the function
2013 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
2014 @cindex @code{boole ()}
2016 where @code{op} must have one of the 16 values (each one stands for a function
2017 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
2018 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
2019 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
2020 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
2021 @code{boole_orc1}, @code{boole_orc2}.
2022 @cindex @code{boole_clr}
2023 @cindex @code{boole_set}
2024 @cindex @code{boole_1}
2025 @cindex @code{boole_2}
2026 @cindex @code{boole_c1}
2027 @cindex @code{boole_c2}
2028 @cindex @code{boole_and}
2029 @cindex @code{boole_xor}
2030 @cindex @code{boole_eqv}
2031 @cindex @code{boole_nand}
2032 @cindex @code{boole_nor}
2033 @cindex @code{boole_andc1}
2034 @cindex @code{boole_andc2}
2035 @cindex @code{boole_orc1}
2036 @cindex @code{boole_orc2}
2039 Other functions that view integers as bit strings:
2042 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
2043 @cindex @code{logtest ()}
2044 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
2045 @code{logand(x,y) != 0}.
2047 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
2048 @cindex @code{logbitp ()}
2049 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
2050 Bit 0 is the least significant bit.
2052 @item uintL logcount (const cl_I& x)
2053 @cindex @code{logcount ()}
2054 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
2055 the number of zero bits in @code{x}, if @code{x} < 0.
2058 The following functions operate on intervals of bits in integers.
2061 struct cl_byte @{ uintL size; uintL position; @};
2063 @cindex @code{cl_byte}
2064 represents the bit interval containing the bits
2065 @code{position}@dots{}@code{position+size-1} of an integer.
2066 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
2069 @item cl_I ldb (const cl_I& n, const cl_byte& b)
2070 @cindex @code{ldb ()}
2071 extracts the bits of @code{n} described by the bit interval @code{b}
2072 and returns them as a nonnegative integer with @code{b.size} bits.
2074 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
2075 @cindex @code{ldb_test ()}
2076 Returns true if some bit described by the bit interval @code{b} is set in
2079 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2080 @cindex @code{dpb ()}
2081 Returns @code{n}, with the bits described by the bit interval @code{b}
2082 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
2083 @code{newbyte} are relevant.
2086 The functions @code{ldb} and @code{dpb} implicitly shift. The following
2087 functions are their counterparts without shifting:
2090 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
2091 @cindex @code{mask_field ()}
2092 returns an integer with the bits described by the bit interval @code{b}
2093 copied from the corresponding bits in @code{n}, the other bits zero.
2095 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
2096 @cindex @code{deposit_field ()}
2097 returns an integer where the bits described by the bit interval @code{b}
2098 come from @code{newbyte} and the other bits come from @code{n}.
2101 The following relations hold:
2105 @code{ldb (n, b) = mask_field(n, b) >> b.position},
2107 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
2109 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
2112 The following operations on integers as bit strings are efficient shortcuts
2113 for common arithmetic operations:
2116 @item cl_boolean oddp (const cl_I& x)
2117 @cindex @code{oddp ()}
2118 Returns true if the least significant bit of @code{x} is 1. Equivalent to
2119 @code{mod(x,2) != 0}.
2121 @item cl_boolean evenp (const cl_I& x)
2122 @cindex @code{evenp ()}
2123 Returns true if the least significant bit of @code{x} is 0. Equivalent to
2124 @code{mod(x,2) == 0}.
2126 @item cl_I operator << (const cl_I& x, const cl_I& n)
2127 @cindex @code{operator << ()}
2128 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
2129 Equivalent to @code{x * expt(2,n)}.
2131 @item cl_I operator >> (const cl_I& x, const cl_I& n)
2132 @cindex @code{operator >> ()}
2133 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
2134 Bits shifted out to the right are thrown away.
2135 Equivalent to @code{floor(x / expt(2,n))}.
2137 @item cl_I ash (const cl_I& x, const cl_I& y)
2138 @cindex @code{ash ()}
2139 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
2140 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
2141 returns @code{floor(x * expt(2,y))}.
2143 @item uintL integer_length (const cl_I& x)
2144 @cindex @code{integer_length ()}
2145 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
2146 in two's complement notation. This is the smallest n >= 0 such that
2147 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
2150 @item uintL ord2 (const cl_I& x)
2151 @cindex @code{ord2 ()}
2152 @code{x} must be non-zero. This function returns the number of 0 bits at the
2153 right of @code{x} in two's complement notation. This is the largest n >= 0
2154 such that 2^n divides @code{x}.
2156 @item uintL power2p (const cl_I& x)
2157 @cindex @code{power2p ()}
2158 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
2159 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
2160 (See also the function @code{logp}.)
2164 @node Number theoretic functions, Combinatorial functions, Logical functions, Functions on integers
2165 @subsection Number theoretic functions
2168 @item uint32 gcd (uint32 a, uint32 b)
2169 @cindex @code{gcd ()}
2170 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
2171 This function returns the greatest common divisor of @code{a} and @code{b},
2172 normalized to be >= 0.
2174 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
2175 @cindex @code{xgcd ()}
2176 This function (``extended gcd'') returns the greatest common divisor @code{g} of
2177 @code{a} and @code{b} and at the same time the representation of @code{g}
2178 as an integral linear combination of @code{a} and @code{b}:
2179 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
2180 @code{u} and @code{v} will be normalized to be of smallest possible absolute
2181 value, in the following sense: If @code{a} and @code{b} are non-zero, and
2182 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
2183 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
2185 @item cl_I lcm (const cl_I& a, const cl_I& b)
2186 @cindex @code{lcm ()}
2187 This function returns the least common multiple of @code{a} and @code{b},
2188 normalized to be >= 0.
2190 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
2191 @cindex @code{logp ()}
2192 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2193 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2194 rational number, this function returns true and sets *l = log(a,b), else
2199 @node Combinatorial functions, , Number theoretic functions, Functions on integers
2200 @subsection Combinatorial functions
2203 @item cl_I factorial (uintL n)
2204 @cindex @code{factorial ()}
2205 @code{n} must be a small integer >= 0. This function returns the factorial
2206 @code{n}! = @code{1*2*@dots{}*n}.
2208 @item cl_I doublefactorial (uintL n)
2209 @cindex @code{doublefactorial ()}
2210 @code{n} must be a small integer >= 0. This function returns the
2211 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2212 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2214 @item cl_I binomial (uintL n, uintL k)
2215 @cindex @code{binomial ()}
2216 @code{n} and @code{k} must be small integers >= 0. This function returns the
2217 binomial coefficient
2219 ${n \choose k} = {n! \over n! (n-k)!}$
2222 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2224 for 0 <= k <= n, 0 else.
2228 @node Functions on floating-point numbers, Conversion functions, Functions on integers, Functions on numbers
2229 @section Functions on floating-point numbers
2231 Recall that a floating-point number consists of a sign @code{s}, an
2232 exponent @code{e} and a mantissa @code{m}. The value of the number is
2233 @code{(-1)^s * 2^e * m}.
2236 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2237 defines the following operations.
2240 @item @var{type} scale_float (const @var{type}& x, sintL delta)
2241 @cindex @code{scale_float ()}
2242 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2243 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2244 because it copies @code{x} and modifies the exponent.
2247 The following functions provide an abstract interface to the underlying
2248 representation of floating-point numbers.
2251 @item sintL float_exponent (const @var{type}& x)
2252 @cindex @code{float_exponent ()}
2253 Returns the exponent @code{e} of @code{x}.
2254 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2255 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2257 @item sintL float_radix (const @var{type}& x)
2258 @cindex @code{float_radix ()}
2259 Returns the base of the floating-point representation. This is always @code{2}.
2261 @item @var{type} float_sign (const @var{type}& x)
2262 @cindex @code{float_sign ()}
2263 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2264 @code{x} >= 0, -1 for @code{x} < 0.
2266 @item uintL float_digits (const @var{type}& x)
2267 @cindex @code{float_digits ()}
2268 Returns the number of mantissa bits in the floating-point representation
2269 of @code{x}, including the hidden bit. The value only depends on the type
2270 of @code{x}, not on its value.
2272 @item uintL float_precision (const @var{type}& x)
2273 @cindex @code{float_precision ()}
2274 Returns the number of significant mantissa bits in the floating-point
2275 representation of @code{x}. Since denormalized numbers are not supported,
2276 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2280 The complete internal representation of a float is encoded in the type
2281 @cindex @code{cl_decoded_float}
2282 @cindex @code{cl_decoded_sfloat}
2283 @cindex @code{cl_decoded_ffloat}
2284 @cindex @code{cl_decoded_dfloat}
2285 @cindex @code{cl_decoded_lfloat}
2286 @code{cl_decoded_float} (or @code{cl_decoded_sfloat}, @code{cl_decoded_ffloat},
2287 @code{cl_decoded_dfloat}, @code{cl_decoded_lfloat}, respectively), defined by
2289 struct cl_decoded_@var{type}float @{
2290 @var{type} mantissa; cl_I exponent; @var{type} sign;
2294 and returned by the function
2297 @item cl_decoded_@var{type}float decode_float (const @var{type}& x)
2298 @cindex @code{decode_float ()}
2299 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2300 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2301 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2302 @code{e} is the same as returned by the function @code{float_exponent}.
2305 A complete decoding in terms of integers is provided as type
2307 @cindex @code{cl_idecoded_float}
2308 struct cl_idecoded_float @{
2309 cl_I mantissa; cl_I exponent; cl_I sign;
2312 by the following function:
2315 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2316 @cindex @code{integer_decode_float ()}
2317 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2318 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2319 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2320 WARNING: The exponent @code{e} is not the same as the one returned by
2321 the functions @code{decode_float} and @code{float_exponent}.
2324 Some other function, implemented only for class @code{cl_F}:
2327 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2328 @cindex @code{float_sign ()}
2329 This returns a floating point number whose precision and absolute value
2330 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2331 zero, it is treated as positive. Same for @code{y}.
2335 @node Conversion functions, Random number generators, Functions on floating-point numbers, Functions on numbers
2336 @section Conversion functions
2340 * Conversion to floating-point numbers::
2341 * Conversion to rational numbers::
2344 @node Conversion to floating-point numbers, Conversion to rational numbers, Conversion functions, Conversion functions
2345 @subsection Conversion to floating-point numbers
2347 The type @code{cl_float_format_t} describes a floating-point format.
2348 @cindex @code{cl_float_format_t}
2351 @item cl_float_format_t cl_float_format (uintL n)
2352 @cindex @code{cl_float_format ()}
2353 Returns the smallest float format which guarantees at least @code{n}
2354 decimal digits in the mantissa (after the decimal point).
2356 @item cl_float_format_t cl_float_format (const cl_F& x)
2357 Returns the floating point format of @code{x}.
2359 @item cl_float_format_t cl_default_float_format
2360 @cindex @code{cl_default_float_format}
2361 Global variable: the default float format used when converting rational numbers
2365 To convert a real number to a float, each of the types
2366 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2367 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2368 defines the following operations:
2371 @item cl_F cl_float (const @var{type}&x, cl_float_format_t f)
2372 @cindex @code{cl_float ()}
2373 Returns @code{x} as a float of format @code{f}.
2374 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2375 Returns @code{x} in the float format of @code{y}.
2376 @item cl_F cl_float (const @var{type}&x)
2377 Returns @code{x} as a float of format @code{cl_default_float_format} if
2378 it is an exact number, or @code{x} itself if it is already a float.
2381 Of course, converting a number to a float can lose precision.
2383 Every floating-point format has some characteristic numbers:
2386 @item cl_F most_positive_float (cl_float_format_t f)
2387 @cindex @code{most_positive_float ()}
2388 Returns the largest (most positive) floating point number in float format @code{f}.
2390 @item cl_F most_negative_float (cl_float_format_t f)
2391 @cindex @code{most_negative_float ()}
2392 Returns the smallest (most negative) floating point number in float format @code{f}.
2394 @item cl_F least_positive_float (cl_float_format_t f)
2395 @cindex @code{least_positive_float ()}
2396 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2397 in float format @code{f}.
2399 @item cl_F least_negative_float (cl_float_format_t f)
2400 @cindex @code{least_negative_float ()}
2401 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2402 in float format @code{f}.
2404 @item cl_F float_epsilon (cl_float_format_t f)
2405 @cindex @code{float_epsilon ()}
2406 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2408 @item cl_F float_negative_epsilon (cl_float_format_t f)
2409 @cindex @code{float_negative_epsilon ()}
2410 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2414 @node Conversion to rational numbers, , Conversion to floating-point numbers, Conversion functions
2415 @subsection Conversion to rational numbers
2417 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2418 defines the following operation:
2421 @item cl_RA rational (const @var{type}& x)
2422 @cindex @code{rational ()}
2423 Returns the value of @code{x} as an exact number. If @code{x} is already
2424 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2425 the value is a rational number whose denominator is a power of 2.
2428 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2432 @item cl_RA rationalize (const cl_R& x)
2433 @cindex @code{rationalize ()}
2434 If @code{x} is a floating-point number, it actually represents an interval
2435 of real numbers, and this function returns the rational number with
2436 smallest denominator (and smallest numerator, in magnitude)
2437 which lies in this interval.
2438 If @code{x} is already an exact number, this function returns @code{x}.
2441 If @code{x} is any float, one has
2445 @code{cl_float(rational(x),x) = x}
2447 @code{cl_float(rationalize(x),x) = x}
2451 @node Random number generators, Obfuscating operators, Conversion functions, Functions on numbers
2452 @section Random number generators
2455 A random generator is a machine which produces (pseudo-)random numbers.
2456 The include file @code{<cl_random.h>} defines a class @code{cl_random_state}
2457 which contains the state of a random generator. If you make a copy
2458 of the random number generator, the original one and the copy will produce
2459 the same sequence of random numbers.
2461 The following functions return (pseudo-)random numbers in different formats.
2462 Calling one of these modifies the state of the random number generator in
2463 a complicated but deterministic way.
2466 @cindex @code{cl_random_state}
2467 @cindex @code{cl_default_random_state}
2469 cl_random_state cl_default_random_state
2471 contains a default random number generator. It is used when the functions
2472 below are called without @code{cl_random_state} argument.
2475 @item uint32 random32 (cl_random_state& randomstate)
2476 @itemx uint32 random32 ()
2477 @cindex @code{random32 ()}
2478 Returns a random unsigned 32-bit number. All bits are equally random.
2480 @item cl_I random_I (cl_random_state& randomstate, const cl_I& n)
2481 @itemx cl_I random_I (const cl_I& n)
2482 @cindex @code{random_I ()}
2483 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2484 in the range @code{0 <= x < n}.
2486 @item cl_F random_F (cl_random_state& randomstate, const cl_F& n)
2487 @itemx cl_F random_F (const cl_F& n)
2488 @cindex @code{random_F ()}
2489 @code{n} must be a float > 0. This function returns a random floating-point
2490 number of the same format as @code{n} in the range @code{0 <= x < n}.
2492 @item cl_R random_R (cl_random_state& randomstate, const cl_R& n)
2493 @itemx cl_R random_R (const cl_R& n)
2494 @cindex @code{random_R ()}
2495 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2496 if @code{n} is a float.
2500 @node Obfuscating operators, , Random number generators, Functions on numbers
2501 @section Obfuscating operators
2502 @cindex modifying operators
2504 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2505 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2506 are not available by default because their
2507 use tends to make programs unreadable. It is trivial to get away without
2508 them. However, if you feel that you absolutely need these operators
2509 to get happy, then add
2511 #define WANT_OBFUSCATING_OPERATORS
2513 @cindex @code{WANT_OBFUSCATING_OPERATORS}
2514 to the beginning of your source files, before the inclusion of any CLN
2515 include files. This flag will enable the following operators:
2517 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2518 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2521 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2522 @cindex @code{operator += ()}
2523 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2524 @cindex @code{operator -= ()}
2525 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2526 @cindex @code{operator *= ()}
2527 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2528 @cindex @code{operator /= ()}
2531 For the class @code{cl_I}:
2534 @item @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 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2538 @cindex @code{operator &= ()}
2539 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2540 @cindex @code{operator |= ()}
2541 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2542 @cindex @code{operator ^= ()}
2543 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2544 @cindex @code{operator <<= ()}
2545 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2546 @cindex @code{operator >>= ()}
2549 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2550 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2553 @item @var{type}& operator ++ (@var{type}& x)
2554 @cindex @code{operator ++ ()}
2555 The prefix operator @code{++x}.
2557 @item void operator ++ (@var{type}& x, int)
2558 The postfix operator @code{x++}.
2560 @item @var{type}& operator -- (@var{type}& x)
2561 @cindex @code{operator -- ()}
2562 The prefix operator @code{--x}.
2564 @item void operator -- (@var{type}& x, int)
2565 The postfix operator @code{x--}.
2568 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2569 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2573 @node Input/Output, Rings, Functions on numbers, Top
2574 @chapter Input/Output
2575 @cindex Input/Output
2578 * Internal and printed representation::
2580 * Output functions::
2583 @node Internal and printed representation, Input functions, Input/Output, Input/Output
2584 @section Internal and printed representation
2585 @cindex representation
2587 All computations deal with the internal representations of the numbers.
2589 Every number has an external representation as a sequence of ASCII characters.
2590 Several external representations may denote the same number, for example,
2591 "20.0" and "20.000".
2593 Converting an internal to an external representation is called ``printing'',
2595 converting an external to an internal representation is called ``reading''.
2597 In CLN, it is always true that conversion of an internal to an external
2598 representation and then back to an internal representation will yield the
2599 same internal representation. Symbolically: @code{read(print(x)) == x}.
2600 This is called ``print-read consistency''.
2602 Different types of numbers have different external representations (case
2607 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2608 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2609 for decimal integers
2610 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2612 @item Rational numbers
2613 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2614 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2617 @item Floating-point numbers
2618 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2619 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2620 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2621 of the form _@var{prec} may be appended. There must be at least
2622 one digit in the non-exponent part. The exponent has the syntax
2623 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2624 The exponent marker is
2628 @samp{s} for short-floats,
2630 @samp{f} for single-floats,
2632 @samp{d} for double-floats,
2634 @samp{L} for long-floats,
2637 or @samp{e}, which denotes a default float format. The precision specifying
2638 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2639 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2640 function @samp{cl_float_format}.
2642 @item Complex numbers
2643 External representation:
2646 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2647 if @var{imagpart} is negative, its printed representation begins with
2648 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2649 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2650 is rational and the rational number's base is >18, because the @samp{i}
2651 is then read as a digit.
2653 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2658 @node Input functions, Output functions, Internal and printed representation, Input/Output
2659 @section Input functions
2661 Including @code{<cl_io.h>} defines a type @code{cl_istream}, which is
2662 the type of the first argument to all input functions. Unless you build
2663 and use CLN with the macro CL_IO_STDIO being defined, @code{cl_istream}
2664 is the same as @code{istream&}.
2669 @code{cl_istream cl_stdin}
2671 contains the standard input stream.
2673 These are the simple input functions:
2676 @item int freadchar (cl_istream stream)
2677 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2678 if the end of stream was encountered or an error occurred.
2680 @item int funreadchar (cl_istream stream, int c)
2681 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2682 last @code{freadchar} operation on @code{stream}.
2685 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2686 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2687 defines, in @code{<cl_@var{type}_io.h>}, the following input function:
2690 @item cl_istream operator>> (cl_istream stream, @var{type}& result)
2691 Reads a number from @code{stream} and stores it in the @code{result}.
2694 The most flexible input functions, defined in @code{<cl_@var{type}_io.h>},
2698 @item cl_N read_complex (cl_istream stream, const cl_read_flags& flags)
2699 @itemx cl_R read_real (cl_istream stream, const cl_read_flags& flags)
2700 @itemx cl_F read_float (cl_istream stream, const cl_read_flags& flags)
2701 @itemx cl_RA read_rational (cl_istream stream, const cl_read_flags& flags)
2702 @itemx cl_I read_integer (cl_istream stream, const cl_read_flags& flags)
2703 Reads a number from @code{stream}. The @code{flags} are parameters which
2704 affect the input syntax. Whitespace before the number is silently skipped.
2706 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2707 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2708 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2709 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2710 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2711 Reads a number from a string in memory. The @code{flags} are parameters which
2712 affect the input syntax. The string starts at @code{string} and ends at
2713 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2714 @code{NULL}, denoting the entire string, i.e. equivalent to
2715 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2716 @code{NULL}, the string in memory must contain exactly one number and nothing
2717 more, else a fatal error will be signalled. If @code{end_of_parse}
2718 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2719 the last parsed character (i.e. @code{string_limit} if nothing came after
2720 the number). Whitespace is not allowed.
2723 The structure @code{cl_read_flags} contains the following fields:
2726 @item cl_read_syntax_t syntax
2727 The possible results of the read operation. Possible values are
2728 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2729 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2730 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2732 @item cl_read_lsyntax_t lsyntax
2733 Specifies the language-dependent syntax variant for the read operation.
2737 @item lsyntax_standard
2738 accept standard algebraic notation only, no complex numbers,
2739 @item lsyntax_algebraic
2740 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2741 @item lsyntax_commonlisp
2742 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2743 hexadecimal numbers,
2744 @code{#@var{base}R} for rational numbers in a given base,
2745 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2747 accept all of these extensions.
2750 @item unsigned int rational_base
2751 The base in which rational numbers are read.
2753 @item cl_float_format_t float_flags.default_float_format
2754 The float format used when reading floats with exponent marker @samp{e}.
2756 @item cl_float_format_t float_flags.default_lfloat_format
2757 The float format used when reading floats with exponent marker @samp{l}.
2759 @item cl_boolean float_flags.mantissa_dependent_float_format
2760 When this flag is true, floats specified with more digits than corresponding
2761 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2762 precision corresponding to their number of significant digits.
2766 @node Output functions, , Input functions, Input/Output
2767 @section Output functions
2769 Including @code{<cl_io.h>} defines a type @code{cl_ostream}, which is
2770 the type of the first argument to all output functions. Unless you build
2771 and use CLN with the macro CL_IO_STDIO being defined, @code{cl_ostream}
2772 is the same as @code{ostream&}.
2777 @code{cl_ostream cl_stdout}
2779 contains the standard output stream.
2784 @code{cl_ostream cl_stderr}
2786 contains the standard error output stream.
2788 These are the simple output functions:
2791 @item void fprintchar (cl_ostream stream, char c)
2792 Prints the character @code{x} literally on the @code{stream}.
2794 @item void fprint (cl_ostream stream, const char * string)
2795 Prints the @code{string} literally on the @code{stream}.
2797 @item void fprintdecimal (cl_ostream stream, int x)
2798 @itemx void fprintdecimal (cl_ostream stream, const cl_I& x)
2799 Prints the integer @code{x} in decimal on the @code{stream}.
2801 @item void fprintbinary (cl_ostream stream, const cl_I& x)
2802 Prints the integer @code{x} in binary (base 2, without prefix)
2803 on the @code{stream}.
2805 @item void fprintoctal (cl_ostream stream, const cl_I& x)
2806 Prints the integer @code{x} in octal (base 8, without prefix)
2807 on the @code{stream}.
2809 @item void fprinthexadecimal (cl_ostream stream, const cl_I& x)
2810 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2811 on the @code{stream}.
2814 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2815 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2816 defines, in @code{<cl_@var{type}_io.h>}, the following output functions:
2819 @item void fprint (cl_ostream stream, const @var{type}& x)
2820 @itemx cl_ostream operator<< (cl_ostream stream, const @var{type}& x)
2821 Prints the number @code{x} on the @code{stream}. The output may depend
2822 on the global printer settings in the variable @code{cl_default_print_flags}.
2823 The @code{ostream} flags and settings (flags, width and locale) are
2827 The most flexible output function, defined in @code{<cl_@var{type}_io.h>},
2830 void print_complex (cl_ostream stream, const cl_print_flags& flags,
2832 void print_real (cl_ostream stream, const cl_print_flags& flags,
2834 void print_float (cl_ostream stream, const cl_print_flags& flags,
2836 void print_rational (cl_ostream stream, const cl_print_flags& flags,
2838 void print_integer (cl_ostream stream, const cl_print_flags& flags,
2841 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2842 parameters which affect the output.
2844 The structure type @code{cl_print_flags} contains the following fields:
2847 @item unsigned int rational_base
2848 The base in which rational numbers are printed. Default is @code{10}.
2850 @item cl_boolean rational_readably
2851 If this flag is true, rational numbers are printed with radix specifiers in
2852 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2853 prefixes, trailing dot). Default is false.
2855 @item cl_boolean float_readably
2856 If this flag is true, type specific exponent markers have precedence over 'E'.
2859 @item cl_float_format_t default_float_format
2860 Floating point numbers of this format will be printed using the 'E' exponent
2861 marker. Default is @code{cl_float_format_ffloat}.
2863 @item cl_boolean complex_readably
2864 If this flag is true, complex numbers will be printed using the Common Lisp
2865 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2867 @item cl_string univpoly_varname
2868 Univariate polynomials with no explicit indeterminate name will be printed
2869 using this variable name. Default is @code{"x"}.
2872 The global variable @code{cl_default_print_flags} contains the default values,
2873 used by the function @code{fprint}.
2876 @node Rings, Modular integers, Input/Output, Top
2879 CLN has a class of abstract rings.
2887 Rings can be compared for equality:
2890 @item bool operator== (const cl_ring&, const cl_ring&)
2891 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2892 These compare two rings for equality.
2895 Given a ring @code{R}, the following members can be used.
2898 @item void R->fprint (cl_ostream stream, const cl_ring_element& x)
2899 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2900 @itemx cl_ring_element R->zero ()
2901 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2902 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2903 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2904 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2905 @itemx cl_ring_element R->one ()
2906 @itemx cl_ring_element R->canonhom (const cl_I& x)
2907 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2908 @itemx cl_ring_element R->square (const cl_ring_element& x)
2909 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2912 The following rings are built-in.
2915 @item cl_null_ring cl_0_ring
2916 The null ring, containing only zero.
2918 @item cl_complex_ring cl_C_ring
2919 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2921 @item cl_real_ring cl_R_ring
2922 The ring of real numbers. This corresponds to the type @code{cl_R}.
2924 @item cl_rational_ring cl_RA_ring
2925 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2927 @item cl_integer_ring cl_I_ring
2928 The ring of integers. This corresponds to the type @code{cl_I}.
2931 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2932 @code{cl_RA_ring}, @code{cl_I_ring}:
2935 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2936 @cindex @code{instanceof ()}
2937 Tests whether the given number is an element of the number ring R.
2941 @node Modular integers, Symbolic data types, Rings, Top
2942 @chapter Modular integers
2943 @cindex modular integer
2946 * Modular integer rings::
2947 * Functions on modular integers::
2950 @node Modular integer rings, Functions on modular integers, Modular integers, Modular integers
2951 @section Modular integer rings
2954 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2955 The modulus is explicitly part of every modular integer. CLN doesn't
2956 allow you to (accidentally) mix elements of different modular rings,
2957 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2958 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2959 doesn't have generic types. So one has to live with runtime checks.)
2961 The class of modular integer rings is
2969 Modular integer ring
2973 @cindex @code{cl_modint_ring}
2975 and the class of all modular integers (elements of modular integer rings) is
2983 Modular integer rings are constructed using the function
2986 @item cl_modint_ring cl_find_modint_ring (const cl_I& N)
2987 @cindex @code{cl_find_modint_ring ()}
2988 This function returns the modular ring @samp{Z/NZ}. It takes care
2989 of finding out about special cases of @code{N}, like powers of two
2990 and odd numbers for which Montgomery multiplication will be a win,
2991 @cindex Montgomery multiplication
2992 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2993 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2994 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2998 Modular integer rings can be compared for equality:
3001 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
3002 @cindex @code{operator == ()}
3003 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
3004 @cindex @code{operator != ()}
3005 These compare two modular integer rings for equality. Two different calls
3006 to @code{cl_find_modint_ring} with the same argument necessarily return the
3007 same ring because it is memoized in the cache table.
3010 @node Functions on modular integers, , Modular integer rings, Modular integers
3011 @section Functions on modular integers
3013 Given a modular integer ring @code{R}, the following members can be used.
3016 @item cl_I R->modulus
3017 @cindex @code{modulus}
3018 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
3020 @item cl_MI R->zero()
3021 @cindex @code{zero ()}
3022 This returns @code{0 mod N}.
3024 @item cl_MI R->one()
3025 @cindex @code{one ()}
3026 This returns @code{1 mod N}.
3028 @item cl_MI R->canonhom (const cl_I& x)
3029 @cindex @code{canonhom ()}
3030 This returns @code{x mod N}.
3032 @item cl_I R->retract (const cl_MI& x)
3033 @cindex @code{retract ()}
3034 This is a partial inverse function to @code{R->canonhom}. It returns the
3035 standard representative (@code{>=0}, @code{<N}) of @code{x}.
3037 @item cl_MI R->random(cl_random_state& randomstate)
3038 @itemx cl_MI R->random()
3039 @cindex @code{random ()}
3040 This returns a random integer modulo @code{N}.
3043 The following operations are defined on modular integers.
3046 @item cl_modint_ring x.ring ()
3047 @cindex @code{ring ()}
3048 Returns the ring to which the modular integer @code{x} belongs.
3050 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
3051 @cindex @code{operator + ()}
3052 Returns the sum of two modular integers. One of the arguments may also
3055 @item cl_MI operator- (const cl_MI&, const cl_MI&)
3056 @cindex @code{operator - ()}
3057 Returns the difference of two modular integers. One of the arguments may also
3060 @item cl_MI operator- (const cl_MI&)
3061 Returns the negative of a modular integer.
3063 @item cl_MI operator* (const cl_MI&, const cl_MI&)
3064 @cindex @code{operator * ()}
3065 Returns the product of two modular integers. One of the arguments may also
3068 @item cl_MI square (const cl_MI&)
3069 @cindex @code{square ()}
3070 Returns the square of a modular integer.
3072 @item cl_MI recip (const cl_MI& x)
3073 @cindex @code{recip ()}
3074 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
3075 must be coprime to the modulus, otherwise an error message is issued.
3077 @item cl_MI div (const cl_MI& x, const cl_MI& y)
3078 @cindex @code{div ()}
3079 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
3080 @code{y} must be coprime to the modulus, otherwise an error message is issued.
3082 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
3083 @cindex @code{expt_pos ()}
3084 @code{y} must be > 0. Returns @code{x^y}.
3086 @item cl_MI expt (const cl_MI& x, const cl_I& y)
3087 @cindex @code{expt ()}
3088 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
3089 modulus, else an error message is issued.
3091 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
3092 @cindex @code{operator << ()}
3093 Returns @code{x*2^y}.
3095 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
3096 @cindex @code{operator >> ()}
3097 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
3098 or an error message is issued.
3100 @item bool operator== (const cl_MI&, const cl_MI&)
3101 @cindex @code{operator == ()}
3102 @itemx bool operator!= (const cl_MI&, const cl_MI&)
3103 @cindex @code{operator != ()}
3104 Compares two modular integers, belonging to the same modular integer ring,
3107 @item cl_boolean zerop (const cl_MI& x)
3108 @cindex @code{zerop ()}
3109 Returns true if @code{x} is @code{0 mod N}.
3112 The following output functions are defined (see also the chapter on
3116 @item void fprint (cl_ostream stream, const cl_MI& x)
3117 @cindex @code{fprint ()}
3118 @itemx cl_ostream operator<< (cl_ostream stream, const cl_MI& x)
3119 @cindex @code{operator << ()}
3120 Prints the modular integer @code{x} on the @code{stream}. The output may depend
3121 on the global printer settings in the variable @code{cl_default_print_flags}.
3125 @node Symbolic data types, Univariate polynomials, Modular integers, Top
3126 @chapter Symbolic data types
3127 @cindex symbolic type
3129 CLN implements two symbolic (non-numeric) data types: strings and symbols.
3136 @node Strings, Symbols, Symbolic data types, Symbolic data types
3148 implements immutable strings.
3150 Strings are constructed through the following constructors:
3153 @item cl_string (const char * s)
3154 @cindex @code{cl_string ()}
3155 Returns an immutable copy of the (zero-terminated) C string @code{s}.
3157 @item cl_string (const char * ptr, unsigned long len)
3158 Returns an immutable copy of the @code{len} characters at
3159 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
3162 The following functions are available on strings:
3166 Assignment from @code{cl_string} and @code{const char *}.
3169 @cindex @code{length ()}
3171 @cindex @code{strlen ()}
3172 Returns the length of the string @code{s}.
3175 @cindex @code{operator [] ()}
3176 Returns the @code{i}th character of the string @code{s}.
3177 @code{i} must be in the range @code{0 <= i < s.length()}.
3179 @item bool equal (const cl_string& s1, const cl_string& s2)
3180 @cindex @code{equal ()}
3181 Compares two strings for equality. One of the arguments may also be a
3182 plain @code{const char *}.
3185 @node Symbols, , Strings, Symbolic data types
3189 Symbols are uniquified strings: all symbols with the same name are shared.
3190 This means that comparison of two symbols is fast (effectively just a pointer
3191 comparison), whereas comparison of two strings must in the worst case walk
3192 both strings until their end.
3193 Symbols are used, for example, as tags for properties, as names of variables
3194 in polynomial rings, etc.
3196 Symbols are constructed through the following constructor:
3199 @item cl_symbol (const cl_string& s)
3200 @cindex @code{cl_symbol ()}
3201 Looks up or creates a new symbol with a given name.
3204 The following operations are available on symbols:
3207 @item cl_string (const cl_symbol& sym)
3208 Conversion to @code{cl_string}: Returns the string which names the symbol
3211 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
3212 @cindex @code{equal ()}
3213 Compares two symbols for equality. This is very fast.
3217 @node Univariate polynomials, Internals, Symbolic data types, Top
3218 @chapter Univariate polynomials
3220 @cindex univariate polynomial
3223 * Univariate polynomial rings::
3224 * Functions on univariate polynomials::
3225 * Special polynomials::
3228 @node Univariate polynomial rings, Functions on univariate polynomials, Univariate polynomials, Univariate polynomials
3229 @section Univariate polynomial rings
3231 CLN implements univariate polynomials (polynomials in one variable) over an
3232 arbitrary ring. The indeterminate variable may be either unnamed (and will be
3233 printed according to @code{cl_default_print_flags.univpoly_varname}, which
3234 defaults to @samp{x}) or carry a given name. The base ring and the
3235 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
3236 (accidentally) mix elements of different polynomial rings, e.g.
3237 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
3238 return a multivariate polynomial, but they are not yet implemented in CLN.)
3240 The classes of univariate polynomial rings are
3248 Univariate polynomial ring
3252 +----------------+-------------------+
3254 Complex polynomial ring | Modular integer polynomial ring
3255 cl_univpoly_complex_ring | cl_univpoly_modint_ring
3256 <cl_univpoly_complex.h> | <cl_univpoly_modint.h>
3260 Real polynomial ring |
3261 cl_univpoly_real_ring |
3262 <cl_univpoly_real.h> |
3266 Rational polynomial ring |
3267 cl_univpoly_rational_ring |
3268 <cl_univpoly_rational.h> |
3272 Integer polynomial ring
3273 cl_univpoly_integer_ring
3274 <cl_univpoly_integer.h>
3277 and the corresponding classes of univariate polynomials are
3280 Univariate polynomial
3284 +----------------+-------------------+
3286 Complex polynomial | Modular integer polynomial
3288 <cl_univpoly_complex.h> | <cl_univpoly_modint.h>
3294 <cl_univpoly_real.h> |
3298 Rational polynomial |
3300 <cl_univpoly_rational.h> |
3306 <cl_univpoly_integer.h>
3309 Univariate polynomial rings are constructed using the functions
3312 @item cl_univpoly_ring cl_find_univpoly_ring (const cl_ring& R)
3313 @itemx cl_univpoly_ring cl_find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3314 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3315 @code{R} may be an arbitrary ring. This function takes care of finding out
3316 about special cases of @code{R}, such as the rings of complex numbers,
3317 real numbers, rational numbers, integers, or modular integer rings.
3318 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3319 This ensures that two calls of this function with the same arguments will
3320 return the same polynomial ring.
3322 @itemx cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring& R)
3323 @cindex @code{cl_find_univpoly_ring ()}
3324 @itemx cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3325 @itemx cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring& R)
3326 @itemx cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3327 @itemx cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring& R)
3328 @itemx cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3329 @itemx cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring& R)
3330 @itemx cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3331 @itemx cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring& R)
3332 @itemx cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3333 These functions are equivalent to the general @code{cl_find_univpoly_ring},
3334 only the return type is more specific, according to the base ring's type.
3337 @node Functions on univariate polynomials, Special polynomials, Univariate polynomial rings, Univariate polynomials
3338 @section Functions on univariate polynomials
3340 Given a univariate polynomial ring @code{R}, the following members can be used.
3343 @item cl_ring R->basering()
3344 @cindex @code{basering ()}
3345 This returns the base ring, as passed to @samp{cl_find_univpoly_ring}.
3347 @item cl_UP R->zero()
3348 @cindex @code{zero ()}
3349 This returns @code{0 in R}, a polynomial of degree -1.
3351 @item cl_UP R->one()
3352 @cindex @code{one ()}
3353 This returns @code{1 in R}, a polynomial of degree <= 0.
3355 @item cl_UP R->canonhom (const cl_I& x)
3356 @cindex @code{canonhom ()}
3357 This returns @code{x in R}, a polynomial of degree <= 0.
3359 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3360 @cindex @code{monomial ()}
3361 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3364 @item cl_UP R->create (sintL degree)
3365 @cindex @code{create ()}
3366 Creates a new polynomial with a given degree. The zero polynomial has degree
3367 @code{-1}. After creating the polynomial, you should put in the coefficients,
3368 using the @code{set_coeff} member function, and then call the @code{finalize}
3372 The following are the only destructive operations on univariate polynomials.
3375 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3376 @cindex @code{set_coeff ()}
3377 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3378 After changing a polynomial and before applying any "normal" operation on it,
3379 you should call its @code{finalize} member function.
3381 @item void finalize (cl_UP& x)
3382 @cindex @code{finalize ()}
3383 This function marks the endpoint of destructive modifications of a polynomial.
3384 It normalizes the internal representation so that subsequent computations have
3385 less overhead. Doing normal computations on unnormalized polynomials may
3386 produce wrong results or crash the program.
3389 The following operations are defined on univariate polynomials.
3392 @item cl_univpoly_ring x.ring ()
3393 @cindex @code{ring ()}
3394 Returns the ring to which the univariate polynomial @code{x} belongs.
3396 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3397 @cindex @code{operator + ()}
3398 Returns the sum of two univariate polynomials.
3400 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3401 @cindex @code{operator - ()}
3402 Returns the difference of two univariate polynomials.
3404 @item cl_UP operator- (const cl_UP&)
3405 Returns the negative of a univariate polynomial.
3407 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3408 @cindex @code{operator * ()}
3409 Returns the product of two univariate polynomials. One of the arguments may
3410 also be a plain integer or an element of the base ring.
3412 @item cl_UP square (const cl_UP&)
3413 @cindex @code{square ()}
3414 Returns the square of a univariate polynomial.
3416 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3417 @cindex @code{expt_pos ()}
3418 @code{y} must be > 0. Returns @code{x^y}.
3420 @item bool operator== (const cl_UP&, const cl_UP&)
3421 @cindex @code{operator == ()}
3422 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3423 @cindex @code{operator != ()}
3424 Compares two univariate polynomials, belonging to the same univariate
3425 polynomial ring, for equality.
3427 @item cl_boolean zerop (const cl_UP& x)
3428 @cindex @code{zerop ()}
3429 Returns true if @code{x} is @code{0 in R}.
3431 @item sintL degree (const cl_UP& x)
3432 @cindex @code{degree ()}
3433 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3435 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3436 @cindex @code{coeff ()}
3437 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3439 @item cl_ring_element x (const cl_ring_element& y)
3440 @cindex @code{operator () ()}
3441 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3442 then @samp{x(y)} returns the value of the substitution of @code{y} into
3445 @item cl_UP deriv (const cl_UP& x)
3446 @cindex @code{deriv ()}
3447 Returns the derivative of the polynomial @code{x} with respect to the
3448 indeterminate @code{X}.
3451 The following output functions are defined (see also the chapter on
3455 @item void fprint (cl_ostream stream, const cl_UP& x)
3456 @cindex @code{fprint ()}
3457 @itemx cl_ostream operator<< (cl_ostream stream, const cl_UP& x)
3458 @cindex @code{operator << ()}
3459 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3460 depend on the global printer settings in the variable
3461 @code{cl_default_print_flags}.
3464 @node Special polynomials, , Functions on univariate polynomials, Univariate polynomials
3465 @section Special polynomials
3467 The following functions return special polynomials.
3470 @item cl_UP_I cl_tschebychev (sintL n)
3471 @cindex @code{cl_tschebychev ()}
3472 @cindex Tschebychev polynomial
3473 Returns the n-th Tchebychev polynomial (n >= 0).
3475 @item cl_UP_I cl_hermite (sintL n)
3476 @cindex @code{cl_hermite ()}
3477 @cindex Hermite polynomial
3478 Returns the n-th Hermite polynomial (n >= 0).
3480 @item cl_UP_RA cl_legendre (sintL n)
3481 @cindex @code{cl_legendre ()}
3482 @cindex Legende polynomial
3483 Returns the n-th Legendre polynomial (n >= 0).
3485 @item cl_UP_I cl_laguerre (sintL n)
3486 @cindex @code{cl_laguerre ()}
3487 @cindex Laguerre polynomial
3488 Returns the n-th Laguerre polynomial (n >= 0).
3491 Information how to derive the differential equation satisfied by each
3492 of these polynomials from their definition can be found in the
3493 @code{doc/polynomial/} directory.
3496 @node Internals, Using the library, Univariate polynomials, Top
3501 * Memory efficiency::
3502 * Speed efficiency::
3503 * Garbage collection::
3506 @node Why C++ ?, Memory efficiency, Internals, Internals
3510 Using C++ as an implementation language provides
3514 Efficiency: It compiles to machine code.
3518 Portability: It runs on all platforms supporting a C++ compiler. Because
3519 of the availability of GNU C++, this includes all currently used 32-bit and
3520 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3523 Type safety: The C++ compilers knows about the number types and complains if,
3524 for example, you try to assign a float to an integer variable. However,
3525 a drawback is that C++ doesn't know about generic types, hence a restriction
3526 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3527 arguments belong to the same modular ring cannot be expressed as a compile-time
3531 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3532 @code{=}, @code{==}, ... can be used in infix notation, which is more
3533 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3536 With these language features, there is no need for two separate languages,
3537 one for the implementation of the library and one in which the library's users
3538 can program. This means that a prototype implementation of an algorithm
3539 can be integrated into the library immediately after it has been tested and
3540 debugged. No need to rewrite it in a low-level language after having prototyped
3541 in a high-level language.
3544 @node Memory efficiency, Speed efficiency, Why C++ ?, Internals
3545 @section Memory efficiency
3547 In order to save memory allocations, CLN implements:
3551 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3554 @cindex garbage collection
3555 @cindex reference counting
3556 Garbage collection: A reference counting mechanism makes sure that any
3557 number object's storage is freed immediately when the last reference to the
3560 Small integers are represented as immediate values instead of pointers
3561 to heap allocated storage. This means that integers @code{> -2^29},
3562 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3567 @node Speed efficiency, Garbage collection, Memory efficiency, Internals
3568 @section Speed efficiency
3570 Speed efficiency is obtained by the combination of the following tricks
3575 Small integers, being represented as immediate values, don't require
3576 memory access, just a couple of instructions for each elementary operation.
3578 The kernel of CLN has been written in assembly language for some CPUs
3579 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3581 On all CPUs, CLN may be configured to use the superefficient low-level
3582 routines from GNU GMP version 3.
3584 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3585 algorithm, the Karatsuba multiplication, which is an
3596 For very large numbers (more than 12000 decimal digits), CLN uses
3598 Sch{@"o}nhage-Strassen
3599 @cindex Sch{@"o}nhage-Strassen multiplication
3603 @cindex Schönhage-Strassen multiplication
3605 multiplication, which is an asymptotically optimal multiplication
3608 These fast multiplication algorithms also give improvements in the speed
3609 of division and radix conversion.
3613 @node Garbage collection, , Speed efficiency, Internals
3614 @section Garbage collection
3615 @cindex garbage collection
3617 All the number classes are reference count classes: They only contain a pointer
3618 to an object in the heap. Upon construction, assignment and destruction of
3619 number objects, only the objects' reference count are manipulated.
3621 Memory occupied by number objects are automatically reclaimed as soon as
3622 their reference count drops to zero.
3624 For number rings, another strategy is implemented: There is a cache of,
3625 for example, the modular integer rings. A modular integer ring is destroyed
3626 only if its reference count dropped to zero and the cache is about to be
3627 resized. The effect of this strategy is that recently used rings remain
3628 cached, whereas undue memory consumption through cached rings is avoided.
3631 @node Using the library, Customizing, Internals, Top
3632 @chapter Using the library
3634 For the following discussion, we will assume that you have installed
3635 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3636 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3637 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3638 environment variables, or directly substitute the appropriate values.
3642 * Compiler options::
3645 * Debugging support::
3648 @node Compiler options, Include files, Using the library, Using the library
3649 @section Compiler options
3650 @cindex compiler options
3652 Until you have installed CLN in a public place, the following options are
3655 When you compile CLN application code, add the flags
3657 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3659 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3660 When you link CLN application code to form an executable, add the flags
3662 $CLN_TARGETDIR/src/libcln.a
3664 to the C/C++ compiler's command line (@code{make} variable LIBS).
3666 If you did a @code{make install}, the include files are installed in a
3667 public directory (normally @code{/usr/local/include}), hence you don't
3668 need special flags for compiling. The library has been installed to a
3669 public directory as well (normally @code{/usr/local/lib}), hence when
3670 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3673 @node Include files, An Example, Compiler options, Using the library
3674 @section Include files
3675 @cindex include files
3676 @cindex header files
3678 Here is a summary of the include files and their contents.
3682 General definitions, reference counting, garbage collection.
3684 The class cl_number.
3685 @item <cl_complex.h>
3686 Functions for class cl_N, the complex numbers.
3688 Functions for class cl_R, the real numbers.
3690 Functions for class cl_F, the floats.
3692 Functions for class cl_SF, the short-floats.
3694 Functions for class cl_FF, the single-floats.
3696 Functions for class cl_DF, the double-floats.
3698 Functions for class cl_LF, the long-floats.
3699 @item <cl_rational.h>
3700 Functions for class cl_RA, the rational numbers.
3701 @item <cl_integer.h>
3702 Functions for class cl_I, the integers.
3705 @item <cl_complex_io.h>
3706 Input/Output for class cl_N, the complex numbers.
3707 @item <cl_real_io.h>
3708 Input/Output for class cl_R, the real numbers.
3709 @item <cl_float_io.h>
3710 Input/Output for class cl_F, the floats.
3711 @item <cl_sfloat_io.h>
3712 Input/Output for class cl_SF, the short-floats.
3713 @item <cl_ffloat_io.h>
3714 Input/Output for class cl_FF, the single-floats.
3715 @item <cl_dfloat_io.h>
3716 Input/Output for class cl_DF, the double-floats.
3717 @item <cl_lfloat_io.h>
3718 Input/Output for class cl_LF, the long-floats.
3719 @item <cl_rational_io.h>
3720 Input/Output for class cl_RA, the rational numbers.
3721 @item <cl_integer_io.h>
3722 Input/Output for class cl_I, the integers.
3724 Flags for customizing input operations.
3726 Flags for customizing output operations.
3728 @code{cl_malloc_hook}, @code{cl_free_hook}.
3731 @item <cl_condition.h>
3732 Conditions/exceptions.
3737 @item <cl_proplist.h>
3741 @item <cl_null_ring.h>
3743 @item <cl_complex_ring.h>
3744 The ring of complex numbers.
3745 @item <cl_real_ring.h>
3746 The ring of real numbers.
3747 @item <cl_rational_ring.h>
3748 The ring of rational numbers.
3749 @item <cl_integer_ring.h>
3750 The ring of integers.
3751 @item <cl_numtheory.h>
3752 Number threory functions.
3753 @item <cl_modinteger.h>
3759 @item <cl_GV_number.h>
3760 General vectors over cl_number.
3761 @item <cl_GV_complex.h>
3762 General vectors over cl_N.
3763 @item <cl_GV_real.h>
3764 General vectors over cl_R.
3765 @item <cl_GV_rational.h>
3766 General vectors over cl_RA.
3767 @item <cl_GV_integer.h>
3768 General vectors over cl_I.
3769 @item <cl_GV_modinteger.h>
3770 General vectors of modular integers.
3773 @item <cl_SV_number.h>
3774 Simple vectors over cl_number.
3775 @item <cl_SV_complex.h>
3776 Simple vectors over cl_N.
3777 @item <cl_SV_real.h>
3778 Simple vectors over cl_R.
3779 @item <cl_SV_rational.h>
3780 Simple vectors over cl_RA.
3781 @item <cl_SV_integer.h>
3782 Simple vectors over cl_I.
3783 @item <cl_SV_ringelt.h>
3784 Simple vectors of general ring elements.
3785 @item <cl_univpoly.h>
3786 Univariate polynomials.
3787 @item <cl_univpoly_integer.h>
3788 Univariate polynomials over the integers.
3789 @item <cl_univpoly_rational.h>
3790 Univariate polynomials over the rational numbers.
3791 @item <cl_univpoly_real.h>
3792 Univariate polynomials over the real numbers.
3793 @item <cl_univpoly_complex.h>
3794 Univariate polynomials over the complex numbers.
3795 @item <cl_univpoly_modint.h>
3796 Univariate polynomials over modular integer rings.
3800 Includes all of the above.
3804 @node An Example, Debugging support, Include files, Using the library
3807 A function which computes the nth Fibonacci number can be written as follows.
3808 @cindex Fibonacci number
3811 #include <cl_integer.h>
3812 #include <cl_real.h>
3814 // Returns F_n, computed as the nearest integer to
3815 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3816 const cl_I fibonacci (int n)
3818 // Need a precision of ((1+sqrt(5))/2)^-n.
3819 cl_float_format_t prec = cl_float_format((int)(0.208987641*n+5));
3820 cl_R sqrt5 = sqrt(cl_float(5,prec));
3821 cl_R phi = (1+sqrt5)/2;
3822 return round1( expt(phi,n)/sqrt5 );
3826 Let's explain what is going on in detail.
3828 The include file @code{<cl_integer.h>} is necessary because the type
3829 @code{cl_I} is used in the function, and the include file @code{<cl_real.h>}
3830 is needed for the type @code{cl_R} and the floating point number functions.
3831 The order of the include files does not matter.
3833 Then comes the function declaration. The argument is an @code{int}, the
3834 result an integer. The return type is defined as @samp{const cl_I}, not
3835 simply @samp{cl_I}, because that allows the compiler to detect typos like
3836 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3837 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3838 number). We use the most specialized possible return type because functions
3839 which call @samp{fibonacci} will be able to profit from the compiler's type
3840 analysis: Adding two integers is slightly more efficient than adding the
3841 same objects declared as complex numbers, because it needs less type
3842 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3843 the size of the resulting executable program.
3845 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3846 integer. In order to get a correct result, the absolute error should be less
3847 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3848 To this end, the first line computes a floating point precision for sqrt(5)
3851 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3852 number and than taking the square root. The converse, first taking the square
3853 root of 5, and then converting to the desired precision, would not work in
3854 CLN: The square root would be computed to a default precision (normally
3855 single-float precision), and the following conversion could not help about
3856 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3857 system and does not represent sqrt(5) in a non-numeric way.
3859 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3860 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3861 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3862 @code{cl_N} because a @samp{round1} does not exist for general complex
3865 When the function returns, all the local variables in the function are
3866 automatically reclaimed (garbage collected). Only the result survives and
3867 gets passed to the caller.
3869 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3870 contains this implementation together with an even faster algorithm.
3872 @node Debugging support, , An Example, Using the library
3873 @section Debugging support
3876 When debugging a CLN application with GNU @code{gdb}, two facilities are
3877 available from the library:
3880 @item The library does type checks, range checks, consistency checks at
3881 many places. When one of these fails, the function @code{cl_abort()} is
3882 called. Its default implementation is to perform an @code{exit(1)}, so
3883 you won't have a core dump. But for debugging, it is best to set a
3884 breakpoint at this function:
3886 (gdb) break cl_abort
3888 When this breakpoint is hit, look at the stack's backtrace:
3893 @item The debugger's normal @code{print} command doesn't know about
3894 CLN's types and therefore prints mostly useless hexadecimal addresses.
3895 CLN offers a function @code{cl_print}, callable from the debugger,
3896 for printing number objects. In order to get this function, you have
3897 to define the macro @samp{CL_DEBUG} and then include all the header files
3898 for which you want @code{cl_print} debugging support. For example:
3899 @cindex @code{CL_DEBUG}
3902 #include <cl_string.h>
3904 Now, if you have in your program a variable @code{cl_string s}, and
3905 inspect it under @code{gdb}, the output may look like this:
3908 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3909 word = 134568800@}@}, @}
3910 (gdb) call cl_print(s)
3914 Note that the output of @code{cl_print} goes to the program's error output,
3915 not to gdb's standard output.
3917 Note, however, that the above facility does not work with all CLN types,
3918 only with number objects and similar. Therefore CLN offers a member function
3919 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3920 is needed for this member function to be implemented. Under @code{gdb},
3921 you call it like this:
3922 @cindex @code{debug_print ()}
3925 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3926 word = 134568800@}@}, @}
3927 (gdb) call s.debug_print()
3930 >call ($1).debug_print()
3935 Unfortunately, this feature does not seem to work under all circumstances.
3939 @node Customizing, Index, Using the library, Top
3940 @chapter Customizing
3945 * Floating-point underflow::
3947 * Customizing the memory allocator::
3950 @node Error handling, Floating-point underflow, Customizing, Customizing
3951 @section Error handling
3953 When a fatal error occurs, an error message is output to the standard error
3954 output stream, and the function @code{cl_abort} is called. The default
3955 version of this function (provided in the library) terminates the application.
3956 To catch such a fatal error, you need to define the function @code{cl_abort}
3957 yourself, with the prototype
3959 #include <cl_abort.h>
3960 void cl_abort (void);
3962 @cindex @code{cl_abort ()}
3963 This function must not return control to its caller.
3966 @node Floating-point underflow, Customizing I/O, Error handling, Customizing
3967 @section Floating-point underflow
3970 Floating point underflow denotes the situation when a floating-point number
3971 is to be created which is so close to @code{0} that its exponent is too
3972 low to be represented internally. By default, this causes a fatal error.
3973 If you set the global variable
3975 cl_boolean cl_inhibit_floating_point_underflow
3977 to @code{cl_true}, the error will be inhibited, and a floating-point zero
3978 will be generated instead. The default value of
3979 @code{cl_inhibit_floating_point_underflow} is @code{cl_false}.
3982 @node Customizing I/O, Customizing the memory allocator, Floating-point underflow, Customizing
3983 @section Customizing I/O
3985 The output of the function @code{fprint} may be customized by changing the
3986 value of the global variable @code{cl_default_print_flags}.
3987 @cindex @code{cl_default_print_flags}
3990 @node Customizing the memory allocator, , Customizing I/O, Customizing
3991 @section Customizing the memory allocator
3993 Every memory allocation of CLN is done through the function pointer
3994 @code{cl_malloc_hook}. Freeing of this memory is done through the function
3995 pointer @code{cl_free_hook}. The default versions of these functions,
3996 provided in the library, call @code{malloc} and @code{free} and check
3997 the @code{malloc} result against @code{NULL}.
3998 If you want to provide another memory allocator, you need to define
3999 the variables @code{cl_malloc_hook} and @code{cl_free_hook} yourself,
4002 #include <cl_malloc.h>
4003 void* (*cl_malloc_hook) (size_t size) = @dots{};
4004 void (*cl_free_hook) (void* ptr) = @dots{};
4006 @cindex @code{cl_malloc_hook ()}
4007 @cindex @code{cl_free_hook ()}
4008 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
4010 It is not possible to change the memory allocator at runtime, because
4011 it is already called at program startup by the constructors of some
4019 @node Index, , Customizing, Top
4025 @c Table of contents