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
99 @node Introduction, Top, Top, Top
100 @comment node-name, next, previous, up
101 @chapter Introduction
104 CLN is a library for computations with all kinds of numbers.
105 It has a rich set of number classes:
109 Integers (with unlimited precision),
115 Floating-point numbers:
125 Long float (with unlimited precision),
132 Modular integers (integers modulo a fixed integer),
135 Univariate polynomials.
139 The subtypes of the complex numbers among these are exactly the
140 types of numbers known to the Common Lisp language. Therefore
141 @code{CLN} can be used for Common Lisp implementations, giving
142 @samp{CLN} another meaning: it becomes an abbreviation of
143 ``Common Lisp Numbers''.
146 The CLN package implements
150 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
151 comparisons, @dots{}),
154 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
157 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
158 functions and their inverse functions).
162 CLN is a C++ library. Using C++ as an implementation language provides
166 efficiency: it compiles to machine code,
168 type safety: the C++ compiler knows about the number types and complains
169 if, for example, you try to assign a float to an integer variable.
171 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
172 @code{==}, @dots{} operators as in C or C++.
176 CLN is memory efficient:
180 Small integers and short floats are immediate, not heap allocated.
182 Heap-allocated memory is reclaimed through an automatic, non-interruptive
187 CLN is speed efficient:
191 The kernel of CLN has been written in assembly language for some CPUs
192 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
195 On all CPUs, CLN may be configured to use the superefficient low-level
196 routines from GNU GMP version 3.
198 It uses Karatsuba multiplication, which is significantly faster
199 for large numbers than the standard multiplication algorithm.
201 For very large numbers (more than 12000 decimal digits), it uses
203 Sch{@"o}nhage-Strassen
204 @cindex Sch{@"o}nhage-Strassen multiplication
208 @cindex Schönhage-Strassen multiplication
210 multiplication, which is an asymptotically optimal multiplication
211 algorithm, for multiplication, division and radix conversion.
215 CLN aims at being easily integrated into larger software packages:
219 The garbage collection imposes no burden on the main application.
221 The library provides hooks for memory allocation and exceptions.
224 All non-macro identifiers are hidden in namespace @code{cln} in
225 order to avoid name clashes.
229 @chapter Installation
231 This section describes how to install the CLN package on your system.
234 @section Prerequisites
236 @subsection C++ compiler
238 To build CLN, you need a C++ compiler.
239 Actually, you need GNU @code{g++ 2.90} or newer, the EGCS compilers will
241 I recommend GNU @code{g++ 2.95} or newer.
243 The following C++ features are used:
244 classes, member functions, overloading of functions and operators,
245 constructors and destructors, inline, const, multiple inheritance,
246 templates and namespaces.
248 The following C++ features are not used:
249 @code{new}, @code{delete}, virtual inheritance, exceptions.
251 CLN relies on semi-automatic ordering of initializations
252 of static and global variables, a feature which I could
253 implement for GNU g++ only.
256 @comment cl_modules.h requires g++
257 Therefore nearly any C++ compiler will do.
259 The following C++ compilers are known to compile CLN:
262 GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
267 The following C++ compilers are known to be unusable for CLN:
270 On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
271 in lines containing @code{#if} or @code{#elif} preprocessor commands.
273 On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
274 in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
275 to have default constructors, and because it probably miscompiles the
276 integer multiplication routines.
278 On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
279 @code{short}s to @code{int}s by zero-extend.
283 On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
284 initializations will not work.
288 @subsection Make utility
291 To build CLN, you also need to have GNU @code{make} installed.
293 @subsection Sed utility
296 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
297 This is because the libtool script, which creates the CLN library, relies
298 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
302 @section Building the library
304 As with any autoconfiguring GNU software, installation is as easy as this:
312 If on your system, @samp{make} is not GNU @code{make}, you have to use
313 @samp{gmake} instead of @samp{make} above.
315 The @code{configure} command checks out some features of your system and
316 C++ compiler and builds the @code{Makefile}s. The @code{make} command
317 builds the library. This step may take 4 hours on an average workstation.
318 The @code{make check} runs some test to check that no important subroutine
319 has been miscompiled.
321 The @code{configure} command accepts options. To get a summary of them, try
327 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
329 You can specify the C compiler, the C++ compiler and their options through
330 the following environment variables when running @code{configure}:
334 Specifies the C compiler.
337 Flags to be given to the C compiler when compiling programs (not when linking).
340 Specifies the C++ compiler.
343 Flags to be given to the C++ compiler when compiling programs (not when linking).
349 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
350 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O -g" \
351 CXX="g++ -V egcs-2.91.60" CXXFLAGS="-O -g" ./configure
352 $ CC="gcc -V 2.95.2" CFLAGS="-O2 -fno-exceptions" \
353 CXX="g++ -V 2.95.2" CFLAGS="-O2 -fno-exceptions" ./configure
356 @comment cl_modules.h requires g++
357 You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
358 compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
361 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
362 $ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
365 On SGI Irix 5, if you wish not to use @code{g++}:
368 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
371 On SGI Irix 6, if you wish not to use @code{g++}:
374 $ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
375 ./configure --without-gmp
376 $ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
377 -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
378 ./configure --without-gmp
382 Note that for these environment variables to take effect, you have to set
383 them (assuming a Bourne-compatible shell) on the same line as the
384 @code{configure} command. If you made the settings in earlier shell
385 commands, you have to @code{export} the environment variables before
386 calling @code{configure}. In a @code{csh} shell, you have to use the
387 @samp{setenv} command for setting each of the environment variables.
389 Currently CLN works only with the GNU @code{g++} compiler, and only in
390 optimizing mode. So you should specify at least @code{-O} in the CXXFLAGS,
391 or no CXXFLAGS at all. (If CXXFLAGS is not set, CLN will use @code{-O}.)
393 If you use @code{g++} version 2.8.x or egcs-2.91.x (a.k.a. egcs-1.1) or
394 gcc-2.95.x, I recommend adding @samp{-fno-exceptions} to the CXXFLAGS.
395 This will likely generate better code.
397 If you use @code{g++} version egcs-2.91.x (egcs-1.1) or gcc-2.95.x on Sparc,
398 add either @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
399 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division routines.
400 Also, if you have @code{g++} version egcs-1.1.1 or older on Sparc, you must
401 specify @samp{--disable-shared} because @code{g++} would miscompile parts of
404 By default, both a shared and a static library are built. You can build
405 CLN as a static (or shared) library only, by calling @code{configure} with
406 the option @samp{--disable-shared} (or @samp{--disable-static}). While
407 shared libraries are usually more convenient to use, they may not work
408 on all architectures. Try disabling them if you run into linker
409 problems. Also, they are generally somewhat slower than static
410 libraries so runtime-critical applications should be linked statically.
413 @subsection Using the GNU MP Library
416 Starting with version 1.1, CLN may be configured to make use of a
417 preinstalled @code{gmp} library. Please make sure that you have at
418 least @code{gmp} version 3.0 installed since earlier versions are
419 unsupported and likely not to work. Enabling this feature by calling
420 @code{configure} with the option @samp{--with-gmp} is known to be quite
421 a boost for CLN's performance.
423 If you have installed the @code{gmp} library and its header file in
424 some place where your compiler cannot find it by default, you must help
425 @code{configure} by setting @code{CPPFLAGS} and @code{LDFLAGS}. Here is
429 $ CC="gcc" CFLAGS="-O2" CXX="g++" CXXFLAGS="-O2 -fno-exceptions" \
430 CPPFLAGS="-I/opt/gmp/include" LDFLAGS="-L/opt/gmp/lib" ./configure --with-gmp
434 @section Installing the library
437 As with any autoconfiguring GNU software, installation is as easy as this:
443 The @samp{make install} command installs the library and the include files
444 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
445 if you haven't specified a @code{--prefix} option to @code{configure}).
446 This step may require superuser privileges.
448 If you have already built the library and wish to install it, but didn't
449 specify @code{--prefix=@dots{}} at configure time, just re-run
450 @code{configure}, giving it the same options as the first time, plus
451 the @code{--prefix=@dots{}} option.
456 You can remove system-dependent files generated by @code{make} through
462 You can remove all files generated by @code{make}, thus reverting to a
463 virgin distribution of CLN, through
470 @chapter Ordinary number types
472 CLN implements the following class hierarchy:
480 Real or complex number
489 +-------------------+-------------------+
491 Rational number Floating-point number
493 <cln/rational.h> <cln/float.h>
495 | +--------------+--------------+--------------+
497 cl_I Short-Float Single-Float Double-Float Long-Float
498 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
499 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
502 @cindex @code{cl_number}
503 @cindex abstract class
504 The base class @code{cl_number} is an abstract base class.
505 It is not useful to declare a variable of this type except if you want
506 to completely disable compile-time type checking and use run-time type
511 @cindex complex number
512 The class @code{cl_N} comprises real and complex numbers. There is
513 no special class for complex numbers since complex numbers with imaginary
514 part @code{0} are automatically converted to real numbers.
517 The class @code{cl_R} comprises real numbers of different kinds. It is an
521 @cindex rational number
523 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
524 integers. There is no special class for non-integral rational numbers
525 since rational numbers with denominator @code{1} are automatically converted
529 The class @code{cl_F} implements floating-point approximations to real numbers.
530 It is an abstract class.
533 @section Exact numbers
536 Some numbers are represented as exact numbers: there is no loss of information
537 when such a number is converted from its mathematical value to its internal
538 representation. On exact numbers, the elementary operations (@code{+},
539 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
542 In CLN, the exact numbers are:
546 rational numbers (including integers),
548 complex numbers whose real and imaginary parts are both rational numbers.
551 Rational numbers are always normalized to the form
552 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
553 are coprime integers and the denominator is positive. If the resulting
554 denominator is @code{1}, the rational number is converted to an integer.
556 Small integers (typically in the range @code{-2^30}@dots{}@code{2^30-1},
557 for 32-bit machines) are especially efficient, because they consume no heap
558 allocation. Otherwise the distinction between these immediate integers
559 (called ``fixnums'') and heap allocated integers (called ``bignums'')
560 is completely transparent.
563 @section Floating-point numbers
564 @cindex floating-point number
566 Not all real numbers can be represented exactly. (There is an easy mathematical
567 proof for this: Only a countable set of numbers can be stored exactly in
568 a computer, even if one assumes that it has unlimited storage. But there
569 are uncountably many real numbers.) So some approximation is needed.
570 CLN implements ordinary floating-point numbers, with mantissa and exponent.
572 @cindex rounding error
573 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
574 only return approximate results. For example, the value of the expression
575 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
576 @samp{0.7}. Rounding errors like this one are inevitable when computing
577 with floating-point numbers.
579 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
580 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
581 rule: It first computes the exact mathematical result and then returns the
582 floating-point number which is nearest to this. If two floating-point numbers
583 are equally distant from the ideal result, the one with a @code{0} in its least
584 significant mantissa bit is chosen.
586 Similarly, testing floating point numbers for equality @samp{x == y}
587 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
588 for some well-chosen @code{epsilon}.
590 Floating point numbers come in four flavors:
595 Short floats, type @code{cl_SF}.
596 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
597 and 17 mantissa bits (including the ``hidden'' bit).
598 They don't consume heap allocation.
602 Single floats, type @code{cl_FF}.
603 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
604 and 24 mantissa bits (including the ``hidden'' bit).
605 In CLN, they are represented as IEEE single-precision floating point numbers.
606 This corresponds closely to the C/C++ type @samp{float}.
610 Double floats, type @code{cl_DF}.
611 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
612 and 53 mantissa bits (including the ``hidden'' bit).
613 In CLN, they are represented as IEEE double-precision floating point numbers.
614 This corresponds closely to the C/C++ type @samp{double}.
618 Long floats, type @code{cl_LF}.
619 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
620 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
621 The precision of a long float is unlimited, but once created, a long float
622 has a fixed precision. (No ``lazy recomputation''.)
625 Of course, computations with long floats are more expensive than those
626 with smaller floating-point formats.
628 CLN does not implement features like NaNs, denormalized numbers and
629 gradual underflow. If the exponent range of some floating-point type
630 is too limited for your application, choose another floating-point type
631 with larger exponent range.
634 As a user of CLN, you can forget about the differences between the
635 four floating-point types and just declare all your floating-point
636 variables as being of type @code{cl_F}. This has the advantage that
637 when you change the precision of some computation (say, from @code{cl_DF}
638 to @code{cl_LF}), you don't have to change the code, only the precision
639 of the initial values. Also, many transcendental functions have been
640 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
641 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
642 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
643 the floating point contagion rule happened to change in the future.)
646 @section Complex numbers
647 @cindex complex number
649 Complex numbers, as implemented by the class @code{cl_N}, have a real
650 part and an imaginary part, both real numbers. A complex number whose
651 imaginary part is the exact number @code{0} is automatically converted
654 Complex numbers can arise from real numbers alone, for example
655 through application of @code{sqrt} or transcendental functions.
661 Conversions from any class to any its superclasses (``base classes'' in
662 C++ terminology) is done automatically.
664 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
665 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
666 @code{cl_N} and @code{cl_number}.
668 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
669 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
670 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
671 efficiency. Their range is therefore limited:
675 The conversion from @samp{int} works only if the argument is < 2^29 and > -2^29.
677 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
680 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
681 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
682 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
684 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
685 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
686 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
687 @samp{cl_I}, first convert it to an @samp{unsigned long}.
689 Conversions from the C built-in type @samp{float} are provided for the classes
690 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
692 Conversions from the C built-in type @samp{double} are provided for the classes
693 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
695 Conversions from @samp{const char *} are provided for the classes
696 @code{cl_I}, @code{cl_RA},
697 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
698 @code{cl_R}, @code{cl_N}.
699 The easiest way to specify a value which is outside of the range of the
700 C++ built-in types is therefore to specify it as a string, like this:
703 cl_I order_of_rubiks_cube_group = "43252003274489856000";
705 Note that this conversion is done at runtime, not at compile-time.
707 Conversions from @code{cl_I} to the C built-in types @samp{int},
708 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
712 @item int cl_I_to_int (const cl_I& x)
713 @cindex @code{cl_I_to_int ()}
714 @itemx unsigned int cl_I_to_uint (const cl_I& x)
715 @cindex @code{cl_I_to_uint ()}
716 @itemx long cl_I_to_long (const cl_I& x)
717 @cindex @code{cl_I_to_long ()}
718 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
719 @cindex @code{cl_I_to_ulong ()}
720 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
721 representable in the range of @var{ctype}, a runtime error occurs.
724 Conversions from the classes @code{cl_I}, @code{cl_RA},
725 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
727 to the C built-in types @samp{float} and @samp{double} are provided through
731 @item float float_approx (const @var{type}& x)
732 @cindex @code{float_approx ()}
733 @itemx double double_approx (const @var{type}& x)
734 @cindex @code{double_approx ()}
735 Returns an approximation of @code{x} of C type @var{ctype}.
736 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
737 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
740 Conversions from any class to any of its subclasses (``derived classes'' in
741 C++ terminology) are not provided. Instead, you can assert and check
742 that a value belongs to a certain subclass, and return it as element of that
743 class, using the @samp{As} and @samp{The} macros.
744 @cindex @code{As()()}
745 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
746 @var{type} and returns it as such.
747 @cindex @code{The()()}
748 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
749 @var{type} and returns it as such. It is your responsibility to ensure
750 that this assumption is valid. Since macros and namespaces don't go
751 together well, there is an equivalent to @samp{The}: the template
759 if (!(x >= 0)) abort();
760 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
761 // In general, it would be a rational number.
762 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
767 @chapter Functions on numbers
769 Each of the number classes declares its mathematical operations in the
770 corresponding include file. For example, if your code operates with
771 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
774 @section Constructing numbers
776 Here is how to create number objects ``from nothing''.
779 @subsection Constructing integers
781 @code{cl_I} objects are most easily constructed from C integers and from
782 strings. See @ref{Conversions}.
785 @subsection Constructing rational numbers
787 @code{cl_RA} objects can be constructed from strings. The syntax
788 for rational numbers is described in @ref{Internal and printed representation}.
789 Another standard way to produce a rational number is through application
790 of @samp{operator /} or @samp{recip} on integers.
793 @subsection Constructing floating-point numbers
795 @code{cl_F} objects with low precision are most easily constructed from
796 C @samp{float} and @samp{double}. See @ref{Conversions}.
798 To construct a @code{cl_F} with high precision, you can use the conversion
799 from @samp{const char *}, but you have to specify the desired precision
800 within the string. (See @ref{Internal and printed representation}.)
803 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
805 will set @samp{e} to the given value, with a precision of 40 decimal digits.
807 The programmatic way to construct a @code{cl_F} with high precision is
808 through the @code{cl_float} conversion function, see
809 @ref{Conversion to floating-point numbers}. For example, to compute
810 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
811 and then apply the exponential function:
813 cl_float_format_t precision = cl_float_format(40);
814 cl_F e = exp(cl_float(1,precision));
818 @subsection Constructing complex numbers
820 Non-real @code{cl_N} objects are normally constructed through the function
822 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
824 See @ref{Elementary complex functions}.
827 @section Elementary functions
829 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
830 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
831 defines the following operations:
834 @item @var{type} operator + (const @var{type}&, const @var{type}&)
835 @cindex @code{operator + ()}
838 @item @var{type} operator - (const @var{type}&, const @var{type}&)
839 @cindex @code{operator - ()}
842 @item @var{type} operator - (const @var{type}&)
843 Returns the negative of the argument.
845 @item @var{type} plus1 (const @var{type}& x)
846 @cindex @code{plus1 ()}
847 Returns @code{x + 1}.
849 @item @var{type} minus1 (const @var{type}& x)
850 @cindex @code{minus1 ()}
851 Returns @code{x - 1}.
853 @item @var{type} operator * (const @var{type}&, const @var{type}&)
854 @cindex @code{operator * ()}
857 @item @var{type} square (const @var{type}& x)
858 @cindex @code{square ()}
859 Returns @code{x * x}.
862 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
863 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
864 defines the following operations:
867 @item @var{type} operator / (const @var{type}&, const @var{type}&)
868 @cindex @code{operator / ()}
871 @item @var{type} recip (const @var{type}&)
872 @cindex @code{recip ()}
873 Returns the reciprocal of the argument.
876 The class @code{cl_I} doesn't define a @samp{/} operation because
877 in the C/C++ language this operator, applied to integral types,
878 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
879 is implementation dependent). (@xref{Rounding functions}.)
880 Instead, @code{cl_I} defines an ``exact quotient'' function:
883 @item cl_I exquo (const cl_I& x, const cl_I& y)
884 @cindex @code{exquo ()}
885 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
888 The following exponentiation functions are defined:
891 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
892 @cindex @code{expt_pos ()}
893 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
894 @code{y} must be > 0. Returns @code{x^y}.
896 @item cl_RA expt (const cl_RA& x, const cl_I& y)
897 @cindex @code{expt ()}
898 @itemx cl_R expt (const cl_R& x, const cl_I& y)
899 @itemx cl_N expt (const cl_N& x, const cl_I& y)
903 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
904 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
905 defines the following operation:
908 @item @var{type} abs (const @var{type}& x)
909 @cindex @code{abs ()}
910 Returns the absolute value of @code{x}.
911 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
914 The class @code{cl_N} implements this as follows:
917 @item cl_R abs (const cl_N x)
918 Returns the absolute value of @code{x}.
921 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
922 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
923 defines the following operation:
926 @item @var{type} signum (const @var{type}& x)
927 @cindex @code{signum ()}
928 Returns the sign of @code{x}, in the same number format as @code{x}.
929 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
930 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
935 @section Elementary rational functions
937 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
940 @item cl_I numerator (const @var{type}& x)
941 @cindex @code{numerator ()}
942 Returns the numerator of @code{x}.
944 @item cl_I denominator (const @var{type}& x)
945 @cindex @code{denominator ()}
946 Returns the denominator of @code{x}.
949 The numerator and denominator of a rational number are normalized in such
950 a way that they have no factor in common and the denominator is positive.
953 @section Elementary complex functions
955 The class @code{cl_N} defines the following operation:
958 @item cl_N complex (const cl_R& a, const cl_R& b)
959 @cindex @code{complex ()}
960 Returns the complex number @code{a+bi}, that is, the complex number with
961 real part @code{a} and imaginary part @code{b}.
964 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
967 @item cl_R realpart (const @var{type}& x)
968 @cindex @code{realpart ()}
969 Returns the real part of @code{x}.
971 @item cl_R imagpart (const @var{type}& x)
972 @cindex @code{imagpart ()}
973 Returns the imaginary part of @code{x}.
975 @item @var{type} conjugate (const @var{type}& x)
976 @cindex @code{conjugate ()}
977 Returns the complex conjugate of @code{x}.
980 We have the relations
984 @code{x = complex(realpart(x), imagpart(x))}
986 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
993 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
994 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
995 defines the following operations:
998 @item bool operator == (const @var{type}&, const @var{type}&)
999 @cindex @code{operator == ()}
1000 @itemx bool operator != (const @var{type}&, const @var{type}&)
1001 @cindex @code{operator != ()}
1002 Comparison, as in C and C++.
1004 @item uint32 equal_hashcode (const @var{type}&)
1005 @cindex @code{equal_hashcode ()}
1006 Returns a 32-bit hash code that is the same for any two numbers which are
1007 the same according to @code{==}. This hash code depends on the number's value,
1008 not its type or precision.
1010 @item cl_boolean zerop (const @var{type}& x)
1011 @cindex @code{zerop ()}
1012 Compare against zero: @code{x == 0}
1015 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1016 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1017 defines the following operations:
1020 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1021 @cindex @code{compare ()}
1022 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1023 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1025 @item bool operator <= (const @var{type}&, const @var{type}&)
1026 @cindex @code{operator <= ()}
1027 @itemx bool operator < (const @var{type}&, const @var{type}&)
1028 @cindex @code{operator < ()}
1029 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1030 @cindex @code{operator >= ()}
1031 @itemx bool operator > (const @var{type}&, const @var{type}&)
1032 @cindex @code{operator > ()}
1033 Comparison, as in C and C++.
1035 @item cl_boolean minusp (const @var{type}& x)
1036 @cindex @code{minusp ()}
1037 Compare against zero: @code{x < 0}
1039 @item cl_boolean plusp (const @var{type}& x)
1040 @cindex @code{plusp ()}
1041 Compare against zero: @code{x > 0}
1043 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1044 @cindex @code{max ()}
1045 Return the maximum of @code{x} and @code{y}.
1047 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1048 @cindex @code{min ()}
1049 Return the minimum of @code{x} and @code{y}.
1052 When a floating point number and a rational number are compared, the float
1053 is first converted to a rational number using the function @code{rational}.
1054 Since a floating point number actually represents an interval of real numbers,
1055 the result might be surprising.
1056 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1057 there is no floating point number whose value is exactly @code{1/3}.
1060 @section Rounding functions
1063 When a real number is to be converted to an integer, there is no ``best''
1064 rounding. The desired rounding function depends on the application.
1065 The Common Lisp and ISO Lisp standards offer four rounding functions:
1069 This is the largest integer <=@code{x}.
1072 This is the smallest integer >=@code{x}.
1075 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1078 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1079 integers, choose the even one.
1082 These functions have different advantages:
1084 @code{floor} and @code{ceiling} are translation invariant:
1085 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1086 for every @code{x} and every integer @code{n}.
1088 On the other hand, @code{truncate} and @code{round} are symmetric:
1089 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1090 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1091 down exactly as often as it rounds up.
1093 The functions are related like this:
1097 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1098 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1100 @code{truncate(x) = sign(x) * floor(abs(x))}
1103 Each of the classes @code{cl_R}, @code{cl_RA},
1104 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1105 defines the following operations:
1108 @item cl_I floor1 (const @var{type}& x)
1109 @cindex @code{floor1 ()}
1110 Returns @code{floor(x)}.
1111 @item cl_I ceiling1 (const @var{type}& x)
1112 @cindex @code{ceiling1 ()}
1113 Returns @code{ceiling(x)}.
1114 @item cl_I truncate1 (const @var{type}& x)
1115 @cindex @code{truncate1 ()}
1116 Returns @code{truncate(x)}.
1117 @item cl_I round1 (const @var{type}& x)
1118 @cindex @code{round1 ()}
1119 Returns @code{round(x)}.
1122 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1123 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1124 defines the following operations:
1127 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1128 Returns @code{floor(x/y)}.
1129 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1130 Returns @code{ceiling(x/y)}.
1131 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1132 Returns @code{truncate(x/y)}.
1133 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1134 Returns @code{round(x/y)}.
1137 These functions are called @samp{floor1}, @dots{} here instead of
1138 @samp{floor}, @dots{}, because on some systems, system dependent include
1139 files define @samp{floor} and @samp{ceiling} as macros.
1141 In many cases, one needs both the quotient and the remainder of a division.
1142 It is more efficient to compute both at the same time than to perform
1143 two divisions, one for quotient and the next one for the remainder.
1144 The following functions therefore return a structure containing both
1145 the quotient and the remainder. The suffix @samp{2} indicates the number
1146 of ``return values''. The remainder is defined as follows:
1150 for the computation of @code{quotient = floor(x)},
1151 @code{remainder = x - quotient},
1153 for the computation of @code{quotient = floor(x,y)},
1154 @code{remainder = x - quotient*y},
1157 and similarly for the other three operations.
1159 Each of the classes @code{cl_R}, @code{cl_RA},
1160 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1161 defines the following operations:
1164 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1165 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1166 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1167 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1168 @itemx @var{type}_div_t round2 (const @var{type}& x)
1171 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1172 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1173 defines the following operations:
1176 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1177 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1178 @cindex @code{floor2 ()}
1179 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1180 @cindex @code{ceiling2 ()}
1181 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1182 @cindex @code{truncate2 ()}
1183 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1184 @cindex @code{round2 ()}
1187 Sometimes, one wants the quotient as a floating-point number (of the
1188 same format as the argument, if the argument is a float) instead of as
1189 an integer. The prefix @samp{f} indicates this.
1192 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1193 defines the following operations:
1196 @item @var{type} ffloor (const @var{type}& x)
1197 @cindex @code{ffloor ()}
1198 @itemx @var{type} fceiling (const @var{type}& x)
1199 @cindex @code{fceiling ()}
1200 @itemx @var{type} ftruncate (const @var{type}& x)
1201 @cindex @code{ftruncate ()}
1202 @itemx @var{type} fround (const @var{type}& x)
1203 @cindex @code{fround ()}
1206 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1208 The class @code{cl_R} defines the following operations:
1211 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1212 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1213 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1214 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1217 These functions also exist in versions which return both the quotient
1218 and the remainder. The suffix @samp{2} indicates this.
1221 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1222 defines the following operations:
1223 @cindex @code{cl_F_fdiv_t}
1224 @cindex @code{cl_SF_fdiv_t}
1225 @cindex @code{cl_FF_fdiv_t}
1226 @cindex @code{cl_DF_fdiv_t}
1227 @cindex @code{cl_LF_fdiv_t}
1230 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1231 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1232 @cindex @code{ffloor2 ()}
1233 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1234 @cindex @code{fceiling2 ()}
1235 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1236 @cindex @code{ftruncate2 ()}
1237 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1238 @cindex @code{fround2 ()}
1240 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1241 @cindex @code{cl_R_fdiv_t}
1243 The class @code{cl_R} defines the following operations:
1246 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1247 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1248 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1249 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1250 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1253 Other applications need only the remainder of a division.
1254 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1255 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1256 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1260 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1262 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1265 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1266 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1267 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1269 The classes @code{cl_R}, @code{cl_I} define the following operations:
1272 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1273 @cindex @code{mod ()}
1274 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1275 @cindex @code{rem ()}
1281 Each of the classes @code{cl_R},
1282 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1283 defines the following operation:
1286 @item @var{type} sqrt (const @var{type}& x)
1287 @cindex @code{sqrt ()}
1288 @code{x} must be >= 0. This function returns the square root of @code{x},
1289 normalized to be >= 0. If @code{x} is the square of a rational number,
1290 @code{sqrt(x)} will be a rational number, else it will return a
1291 floating-point approximation.
1294 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1297 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1298 @cindex @code{sqrtp ()}
1299 This tests whether @code{x} is a perfect square. If so, it returns true
1300 and the exact square root in @code{*root}, else it returns false.
1303 Furthermore, for integers, similarly:
1306 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1307 @cindex @code{isqrt ()}
1308 @code{x} should be >= 0. This function sets @code{*root} to
1309 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1310 the boolean value @code{(expt(*root,2) == x)}.
1313 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1314 define the following operation:
1317 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1318 @cindex @code{rootp ()}
1319 @code{x} must be >= 0. @code{n} must be > 0.
1320 This tests whether @code{x} is an @code{n}th power of a rational number.
1321 If so, it returns true and the exact root in @code{*root}, else it returns
1325 The only square root function which accepts negative numbers is the one
1326 for class @code{cl_N}:
1329 @item cl_N sqrt (const cl_N& z)
1330 @cindex @code{sqrt ()}
1331 Returns the square root of @code{z}, as defined by the formula
1332 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1333 or to a complex number are done if necessary. The range of the result is the
1334 right half plane @code{realpart(sqrt(z)) >= 0}
1335 including the positive imaginary axis and 0, but excluding
1336 the negative imaginary axis.
1337 The result is an exact number only if @code{z} is an exact number.
1341 @section Transcendental functions
1342 @cindex transcendental functions
1344 The transcendental functions return an exact result if the argument
1345 is exact and the result is exact as well. Otherwise they must return
1346 inexact numbers even if the argument is exact.
1347 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1350 @subsection Exponential and logarithmic functions
1353 @item cl_R exp (const cl_R& x)
1354 @cindex @code{exp ()}
1355 @itemx cl_N exp (const cl_N& x)
1356 Returns the exponential function of @code{x}. This is @code{e^x} where
1357 @code{e} is the base of the natural logarithms. The range of the result
1358 is the entire complex plane excluding 0.
1360 @item cl_R ln (const cl_R& x)
1361 @cindex @code{ln ()}
1362 @code{x} must be > 0. Returns the (natural) logarithm of x.
1364 @item cl_N log (const cl_N& x)
1365 @cindex @code{log ()}
1366 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1367 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1368 The range of the result is the strip in the complex plane
1369 @code{-pi < imagpart(log(x)) <= pi}.
1371 @item cl_R phase (const cl_N& x)
1372 @cindex @code{phase ()}
1373 Returns the angle part of @code{x} in its polar representation as a
1374 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1375 This is also the imaginary part of @code{log(x)}.
1376 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1377 The result will be an exact number only if @code{zerop(x)} or
1378 if @code{x} is real and positive.
1380 @item cl_R log (const cl_R& a, const cl_R& b)
1381 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1382 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1383 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1386 @item cl_N log (const cl_N& a, const cl_N& b)
1387 Returns the logarithm of @code{a} with respect to base @code{b}.
1388 @code{log(a,b) = log(a)/log(b)}.
1390 @item cl_N expt (const cl_N& x, const cl_N& y)
1391 @cindex @code{expt ()}
1392 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1395 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1398 @item cl_F exp1 (cl_float_format_t f)
1399 @cindex @code{exp1 ()}
1400 Returns e as a float of format @code{f}.
1402 @item cl_F exp1 (const cl_F& y)
1403 Returns e in the float format of @code{y}.
1405 @item cl_F exp1 (void)
1406 Returns e as a float of format @code{default_float_format}.
1410 @subsection Trigonometric functions
1413 @item cl_R sin (const cl_R& x)
1414 @cindex @code{sin ()}
1415 Returns @code{sin(x)}. The range of the result is the interval
1416 @code{-1 <= sin(x) <= 1}.
1418 @item cl_N sin (const cl_N& z)
1419 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1421 @item cl_R cos (const cl_R& x)
1422 @cindex @code{cos ()}
1423 Returns @code{cos(x)}. The range of the result is the interval
1424 @code{-1 <= cos(x) <= 1}.
1426 @item cl_N cos (const cl_N& x)
1427 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1429 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1430 @cindex @code{cos_sin_t}
1431 @itemx cos_sin_t cos_sin (const cl_R& x)
1432 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1433 @cindex @code{cos_sin ()}
1434 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1435 hold only approximately.
1437 @item cl_R tan (const cl_R& x)
1438 @cindex @code{tan ()}
1439 @itemx cl_N tan (const cl_N& x)
1440 Returns @code{tan(x) = sin(x)/cos(x)}.
1442 @item cl_N cis (const cl_R& x)
1443 @cindex @code{cis ()}
1444 @itemx cl_N cis (const cl_N& x)
1445 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1446 @code{e^(i*x) = cos(x) + i*sin(x)}.
1449 @cindex @code{asin ()}
1450 @item cl_N asin (const cl_N& z)
1451 Returns @code{arcsin(z)}. This is defined as
1452 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1453 @code{arcsin(-z) = -arcsin(z)}.
1454 The range of the result is the strip in the complex domain
1455 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1456 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1457 with @code{realpart = pi/2} and @code{imagpart > 0}.
1459 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1463 @item cl_N acos (const cl_N& z)
1464 @cindex @code{acos ()}
1465 Returns @code{arccos(z)}. This is defined as
1466 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1469 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1471 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1472 The range of the result is the strip in the complex domain
1473 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1474 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1475 with @code{realpart = pi} and @code{imagpart > 0}.
1477 Proof: This follows from the results about arcsin.
1481 @cindex @code{atan ()}
1482 @item cl_R atan (const cl_R& x, const cl_R& y)
1483 Returns the angle of the polar representation of the complex number
1484 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1485 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1486 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1487 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1488 with reversed order of arguments.
1490 @item cl_R atan (const cl_R& x)
1491 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1492 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1493 will be an exact number only if @code{x} is the exact @code{0}.
1495 @item cl_N atan (const cl_N& z)
1496 Returns @code{arctan(z)}. This is defined as
1497 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1498 @code{arctan(-z) = -arctan(z)}. The range of the result is
1499 the strip in the complex domain
1500 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1501 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1502 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1504 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1510 @cindex Archimedes' constant
1511 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1514 @item cl_F pi (cl_float_format_t f)
1515 @cindex @code{pi ()}
1516 Returns pi as a float of format @code{f}.
1518 @item cl_F pi (const cl_F& y)
1519 Returns pi in the float format of @code{y}.
1521 @item cl_F pi (void)
1522 Returns pi as a float of format @code{default_float_format}.
1526 @subsection Hyperbolic functions
1529 @item cl_R sinh (const cl_R& x)
1530 @cindex @code{sinh ()}
1531 Returns @code{sinh(x)}.
1533 @item cl_N sinh (const cl_N& z)
1534 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1536 @item cl_R cosh (const cl_R& x)
1537 @cindex @code{cosh ()}
1538 Returns @code{cosh(x)}. The range of the result is the interval
1539 @code{cosh(x) >= 1}.
1541 @item cl_N cosh (const cl_N& z)
1542 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1544 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1545 @cindex @code{cosh_sinh_t}
1546 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1547 @cindex @code{cosh_sinh ()}
1548 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1549 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1550 hold only approximately.
1552 @item cl_R tanh (const cl_R& x)
1553 @cindex @code{tanh ()}
1554 @itemx cl_N tanh (const cl_N& x)
1555 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1557 @item cl_N asinh (const cl_N& z)
1558 @cindex @code{asinh ()}
1559 Returns @code{arsinh(z)}. This is defined as
1560 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1561 @code{arsinh(-z) = -arsinh(z)}.
1563 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1564 Actually, z+sqrt(1+z^2) can never be real and <0, so
1565 -pi < imagpart(arsinh(z)) < pi.
1566 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1567 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1569 The range of the result is the strip in the complex domain
1570 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1571 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1572 with @code{imagpart = pi/2} and @code{realpart < 0}.
1574 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1575 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1576 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1577 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1578 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1579 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1580 If y >= 1, the imagpart is pi/2 and the realpart is
1581 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1584 Moreover, if z is in Range(sqrt),
1585 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1586 (for a proof, see file src/cl_C_asinh.cc).
1589 @item cl_N acosh (const cl_N& z)
1590 @cindex @code{acosh ()}
1591 Returns @code{arcosh(z)}. This is defined as
1592 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1593 The range of the result is the half-strip in the complex domain
1594 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1595 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1597 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1598 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1599 If z is in Range(sqrt), we have
1600 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1601 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1603 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1604 and since the imagpart of both expressions is > -pi, <= pi
1605 ==> arcosh(z) = log(z+sqrt(z^2-1))
1606 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1607 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1608 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1609 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1610 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1612 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1613 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1614 = x^2 + y^2 + sqrt(u^2+v^2)
1619 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1620 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1621 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1622 Otherwise, -z is in Range(sqrt).
1623 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1624 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1625 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1626 and this has realpart > 0.
1627 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1628 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1629 has realpart = 0 and imagpart > 0.
1630 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1631 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1632 This has realpart >= 0 and imagpart = pi.
1635 @item cl_N atanh (const cl_N& z)
1636 @cindex @code{atanh ()}
1637 Returns @code{artanh(z)}. This is defined as
1638 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1639 @code{artanh(-z) = -artanh(z)}. The range of the result is
1640 the strip in the complex domain
1641 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1642 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1643 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1645 Proof: Write z = x+iy. Examine
1646 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1648 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1649 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1650 |x| < 1 ==> imagpart = 0
1653 = (atan(1+x,y) - atan(1-x,-y))/2
1654 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1655 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1656 > (pi - pi/2 - pi/2 )/2 = 0
1657 and (1+x)/y > (1-x)/y
1658 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1659 ==> imagpart < pi/2.
1660 Hence 0 < imagpart < pi/2.
1662 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1667 @subsection Euler gamma
1668 @cindex Euler's constant
1670 Euler's constant C = 0.577@dots{} is returned by the following functions:
1673 @item cl_F eulerconst (cl_float_format_t f)
1674 @cindex @code{eulerconst ()}
1675 Returns Euler's constant as a float of format @code{f}.
1677 @item cl_F eulerconst (const cl_F& y)
1678 Returns Euler's constant in the float format of @code{y}.
1680 @item cl_F eulerconst (void)
1681 Returns Euler's constant as a float of format @code{default_float_format}.
1684 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1685 @cindex Catalan's constant
1688 @item cl_F catalanconst (cl_float_format_t f)
1689 @cindex @code{catalanconst ()}
1690 Returns Catalan's constant as a float of format @code{f}.
1692 @item cl_F catalanconst (const cl_F& y)
1693 Returns Catalan's constant in the float format of @code{y}.
1695 @item cl_F catalanconst (void)
1696 Returns Catalan's constant as a float of format @code{default_float_format}.
1700 @subsection Riemann zeta
1701 @cindex Riemann's zeta
1703 Riemann's zeta function at an integral point @code{s>1} is returned by the
1704 following functions:
1707 @item cl_F zeta (int s, cl_float_format_t f)
1708 @cindex @code{zeta ()}
1709 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1711 @item cl_F zeta (int s, const cl_F& y)
1712 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1714 @item cl_F zeta (int s)
1715 Returns Riemann's zeta function at @code{s} as a float of format
1716 @code{default_float_format}.
1720 @section Functions on integers
1722 @subsection Logical functions
1724 Integers, when viewed as in two's complement notation, can be thought as
1725 infinite bit strings where the bits' values eventually are constant.
1732 The logical operations view integers as such bit strings and operate
1733 on each of the bit positions in parallel.
1736 @item cl_I lognot (const cl_I& x)
1737 @cindex @code{lognot ()}
1738 @itemx cl_I operator ~ (const cl_I& x)
1739 @cindex @code{operator ~ ()}
1740 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1742 @item cl_I logand (const cl_I& x, const cl_I& y)
1743 @cindex @code{logand ()}
1744 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1745 @cindex @code{operator & ()}
1746 Logical and, like @code{x & y} in C.
1748 @item cl_I logior (const cl_I& x, const cl_I& y)
1749 @cindex @code{logior ()}
1750 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1751 @cindex @code{operator | ()}
1752 Logical (inclusive) or, like @code{x | y} in C.
1754 @item cl_I logxor (const cl_I& x, const cl_I& y)
1755 @cindex @code{logxor ()}
1756 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1757 @cindex @code{operator ^ ()}
1758 Exclusive or, like @code{x ^ y} in C.
1760 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1761 @cindex @code{logeqv ()}
1762 Bitwise equivalence, like @code{~(x ^ y)} in C.
1764 @item cl_I lognand (const cl_I& x, const cl_I& y)
1765 @cindex @code{lognand ()}
1766 Bitwise not and, like @code{~(x & y)} in C.
1768 @item cl_I lognor (const cl_I& x, const cl_I& y)
1769 @cindex @code{lognor ()}
1770 Bitwise not or, like @code{~(x | y)} in C.
1772 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1773 @cindex @code{logandc1 ()}
1774 Logical and, complementing the first argument, like @code{~x & y} in C.
1776 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1777 @cindex @code{logandc2 ()}
1778 Logical and, complementing the second argument, like @code{x & ~y} in C.
1780 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1781 @cindex @code{logorc1 ()}
1782 Logical or, complementing the first argument, like @code{~x | y} in C.
1784 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1785 @cindex @code{logorc2 ()}
1786 Logical or, complementing the second argument, like @code{x | ~y} in C.
1789 These operations are all available though the function
1791 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
1792 @cindex @code{boole ()}
1794 where @code{op} must have one of the 16 values (each one stands for a function
1795 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
1796 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
1797 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
1798 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
1799 @code{boole_orc1}, @code{boole_orc2}.
1800 @cindex @code{boole_clr}
1801 @cindex @code{boole_set}
1802 @cindex @code{boole_1}
1803 @cindex @code{boole_2}
1804 @cindex @code{boole_c1}
1805 @cindex @code{boole_c2}
1806 @cindex @code{boole_and}
1807 @cindex @code{boole_xor}
1808 @cindex @code{boole_eqv}
1809 @cindex @code{boole_nand}
1810 @cindex @code{boole_nor}
1811 @cindex @code{boole_andc1}
1812 @cindex @code{boole_andc2}
1813 @cindex @code{boole_orc1}
1814 @cindex @code{boole_orc2}
1817 Other functions that view integers as bit strings:
1820 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
1821 @cindex @code{logtest ()}
1822 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
1823 @code{logand(x,y) != 0}.
1825 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
1826 @cindex @code{logbitp ()}
1827 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
1828 Bit 0 is the least significant bit.
1830 @item uintL logcount (const cl_I& x)
1831 @cindex @code{logcount ()}
1832 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
1833 the number of zero bits in @code{x}, if @code{x} < 0.
1836 The following functions operate on intervals of bits in integers.
1839 struct cl_byte @{ uintL size; uintL position; @};
1841 @cindex @code{cl_byte}
1842 represents the bit interval containing the bits
1843 @code{position}@dots{}@code{position+size-1} of an integer.
1844 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
1847 @item cl_I ldb (const cl_I& n, const cl_byte& b)
1848 @cindex @code{ldb ()}
1849 extracts the bits of @code{n} described by the bit interval @code{b}
1850 and returns them as a nonnegative integer with @code{b.size} bits.
1852 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
1853 @cindex @code{ldb_test ()}
1854 Returns true if some bit described by the bit interval @code{b} is set in
1857 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1858 @cindex @code{dpb ()}
1859 Returns @code{n}, with the bits described by the bit interval @code{b}
1860 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
1861 @code{newbyte} are relevant.
1864 The functions @code{ldb} and @code{dpb} implicitly shift. The following
1865 functions are their counterparts without shifting:
1868 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
1869 @cindex @code{mask_field ()}
1870 returns an integer with the bits described by the bit interval @code{b}
1871 copied from the corresponding bits in @code{n}, the other bits zero.
1873 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1874 @cindex @code{deposit_field ()}
1875 returns an integer where the bits described by the bit interval @code{b}
1876 come from @code{newbyte} and the other bits come from @code{n}.
1879 The following relations hold:
1883 @code{ldb (n, b) = mask_field(n, b) >> b.position},
1885 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
1887 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
1890 The following operations on integers as bit strings are efficient shortcuts
1891 for common arithmetic operations:
1894 @item cl_boolean oddp (const cl_I& x)
1895 @cindex @code{oddp ()}
1896 Returns true if the least significant bit of @code{x} is 1. Equivalent to
1897 @code{mod(x,2) != 0}.
1899 @item cl_boolean evenp (const cl_I& x)
1900 @cindex @code{evenp ()}
1901 Returns true if the least significant bit of @code{x} is 0. Equivalent to
1902 @code{mod(x,2) == 0}.
1904 @item cl_I operator << (const cl_I& x, const cl_I& n)
1905 @cindex @code{operator << ()}
1906 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
1907 Equivalent to @code{x * expt(2,n)}.
1909 @item cl_I operator >> (const cl_I& x, const cl_I& n)
1910 @cindex @code{operator >> ()}
1911 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
1912 Bits shifted out to the right are thrown away.
1913 Equivalent to @code{floor(x / expt(2,n))}.
1915 @item cl_I ash (const cl_I& x, const cl_I& y)
1916 @cindex @code{ash ()}
1917 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
1918 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
1919 returns @code{floor(x * expt(2,y))}.
1921 @item uintL integer_length (const cl_I& x)
1922 @cindex @code{integer_length ()}
1923 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
1924 in two's complement notation. This is the smallest n >= 0 such that
1925 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
1928 @item uintL ord2 (const cl_I& x)
1929 @cindex @code{ord2 ()}
1930 @code{x} must be non-zero. This function returns the number of 0 bits at the
1931 right of @code{x} in two's complement notation. This is the largest n >= 0
1932 such that 2^n divides @code{x}.
1934 @item uintL power2p (const cl_I& x)
1935 @cindex @code{power2p ()}
1936 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
1937 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
1938 (See also the function @code{logp}.)
1942 @subsection Number theoretic functions
1945 @item uint32 gcd (uint32 a, uint32 b)
1946 @cindex @code{gcd ()}
1947 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
1948 This function returns the greatest common divisor of @code{a} and @code{b},
1949 normalized to be >= 0.
1951 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
1952 @cindex @code{xgcd ()}
1953 This function (``extended gcd'') returns the greatest common divisor @code{g} of
1954 @code{a} and @code{b} and at the same time the representation of @code{g}
1955 as an integral linear combination of @code{a} and @code{b}:
1956 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
1957 @code{u} and @code{v} will be normalized to be of smallest possible absolute
1958 value, in the following sense: If @code{a} and @code{b} are non-zero, and
1959 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
1960 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
1962 @item cl_I lcm (const cl_I& a, const cl_I& b)
1963 @cindex @code{lcm ()}
1964 This function returns the least common multiple of @code{a} and @code{b},
1965 normalized to be >= 0.
1967 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
1968 @cindex @code{logp ()}
1969 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
1970 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
1971 rational number, this function returns true and sets *l = log(a,b), else
1976 @subsection Combinatorial functions
1979 @item cl_I factorial (uintL n)
1980 @cindex @code{factorial ()}
1981 @code{n} must be a small integer >= 0. This function returns the factorial
1982 @code{n}! = @code{1*2*@dots{}*n}.
1984 @item cl_I doublefactorial (uintL n)
1985 @cindex @code{doublefactorial ()}
1986 @code{n} must be a small integer >= 0. This function returns the
1987 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
1988 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
1990 @item cl_I binomial (uintL n, uintL k)
1991 @cindex @code{binomial ()}
1992 @code{n} and @code{k} must be small integers >= 0. This function returns the
1993 binomial coefficient
1995 ${n \choose k} = {n! \over n! (n-k)!}$
1998 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2000 for 0 <= k <= n, 0 else.
2004 @section Functions on floating-point numbers
2006 Recall that a floating-point number consists of a sign @code{s}, an
2007 exponent @code{e} and a mantissa @code{m}. The value of the number is
2008 @code{(-1)^s * 2^e * m}.
2011 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2012 defines the following operations.
2015 @item @var{type} scale_float (const @var{type}& x, sintL delta)
2016 @cindex @code{scale_float ()}
2017 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2018 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2019 because it copies @code{x} and modifies the exponent.
2022 The following functions provide an abstract interface to the underlying
2023 representation of floating-point numbers.
2026 @item sintL float_exponent (const @var{type}& x)
2027 @cindex @code{float_exponent ()}
2028 Returns the exponent @code{e} of @code{x}.
2029 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2030 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2032 @item sintL float_radix (const @var{type}& x)
2033 @cindex @code{float_radix ()}
2034 Returns the base of the floating-point representation. This is always @code{2}.
2036 @item @var{type} float_sign (const @var{type}& x)
2037 @cindex @code{float_sign ()}
2038 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2039 @code{x} >= 0, -1 for @code{x} < 0.
2041 @item uintL float_digits (const @var{type}& x)
2042 @cindex @code{float_digits ()}
2043 Returns the number of mantissa bits in the floating-point representation
2044 of @code{x}, including the hidden bit. The value only depends on the type
2045 of @code{x}, not on its value.
2047 @item uintL float_precision (const @var{type}& x)
2048 @cindex @code{float_precision ()}
2049 Returns the number of significant mantissa bits in the floating-point
2050 representation of @code{x}. Since denormalized numbers are not supported,
2051 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2055 The complete internal representation of a float is encoded in the type
2056 @cindex @code{decoded_float}
2057 @cindex @code{decoded_sfloat}
2058 @cindex @code{decoded_ffloat}
2059 @cindex @code{decoded_dfloat}
2060 @cindex @code{decoded_lfloat}
2061 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2062 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2064 struct decoded_@var{type}float @{
2065 @var{type} mantissa; cl_I exponent; @var{type} sign;
2069 and returned by the function
2072 @item decoded_@var{type}float decode_float (const @var{type}& x)
2073 @cindex @code{decode_float ()}
2074 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2075 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2076 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2077 @code{e} is the same as returned by the function @code{float_exponent}.
2080 A complete decoding in terms of integers is provided as type
2081 @cindex @code{cl_idecoded_float}
2083 struct cl_idecoded_float @{
2084 cl_I mantissa; cl_I exponent; cl_I sign;
2087 by the following function:
2090 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2091 @cindex @code{integer_decode_float ()}
2092 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2093 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2094 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2095 WARNING: The exponent @code{e} is not the same as the one returned by
2096 the functions @code{decode_float} and @code{float_exponent}.
2099 Some other function, implemented only for class @code{cl_F}:
2102 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2103 @cindex @code{float_sign ()}
2104 This returns a floating point number whose precision and absolute value
2105 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2106 zero, it is treated as positive. Same for @code{y}.
2110 @section Conversion functions
2113 @subsection Conversion to floating-point numbers
2115 The type @code{cl_float_format_t} describes a floating-point format.
2116 @cindex @code{cl_float_format_t}
2119 @item cl_float_format_t cl_float_format (uintL n)
2120 @cindex @code{cl_float_format ()}
2121 Returns the smallest float format which guarantees at least @code{n}
2122 decimal digits in the mantissa (after the decimal point).
2124 @item cl_float_format_t cl_float_format (const cl_F& x)
2125 Returns the floating point format of @code{x}.
2127 @item cl_float_format_t default_float_format
2128 @cindex @code{default_float_format}
2129 Global variable: the default float format used when converting rational numbers
2133 To convert a real number to a float, each of the types
2134 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2135 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2136 defines the following operations:
2139 @item cl_F cl_float (const @var{type}&x, cl_float_format_t f)
2140 @cindex @code{cl_float ()}
2141 Returns @code{x} as a float of format @code{f}.
2142 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2143 Returns @code{x} in the float format of @code{y}.
2144 @item cl_F cl_float (const @var{type}&x)
2145 Returns @code{x} as a float of format @code{default_float_format} if
2146 it is an exact number, or @code{x} itself if it is already a float.
2149 Of course, converting a number to a float can lose precision.
2151 Every floating-point format has some characteristic numbers:
2154 @item cl_F most_positive_float (cl_float_format_t f)
2155 @cindex @code{most_positive_float ()}
2156 Returns the largest (most positive) floating point number in float format @code{f}.
2158 @item cl_F most_negative_float (cl_float_format_t f)
2159 @cindex @code{most_negative_float ()}
2160 Returns the smallest (most negative) floating point number in float format @code{f}.
2162 @item cl_F least_positive_float (cl_float_format_t f)
2163 @cindex @code{least_positive_float ()}
2164 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2165 in float format @code{f}.
2167 @item cl_F least_negative_float (cl_float_format_t f)
2168 @cindex @code{least_negative_float ()}
2169 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2170 in float format @code{f}.
2172 @item cl_F float_epsilon (cl_float_format_t f)
2173 @cindex @code{float_epsilon ()}
2174 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2176 @item cl_F float_negative_epsilon (cl_float_format_t f)
2177 @cindex @code{float_negative_epsilon ()}
2178 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2182 @subsection Conversion to rational numbers
2184 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2185 defines the following operation:
2188 @item cl_RA rational (const @var{type}& x)
2189 @cindex @code{rational ()}
2190 Returns the value of @code{x} as an exact number. If @code{x} is already
2191 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2192 the value is a rational number whose denominator is a power of 2.
2195 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2199 @item cl_RA rationalize (const cl_R& x)
2200 @cindex @code{rationalize ()}
2201 If @code{x} is a floating-point number, it actually represents an interval
2202 of real numbers, and this function returns the rational number with
2203 smallest denominator (and smallest numerator, in magnitude)
2204 which lies in this interval.
2205 If @code{x} is already an exact number, this function returns @code{x}.
2208 If @code{x} is any float, one has
2212 @code{cl_float(rational(x),x) = x}
2214 @code{cl_float(rationalize(x),x) = x}
2218 @section Random number generators
2221 A random generator is a machine which produces (pseudo-)random numbers.
2222 The include file @code{<cln/random.h>} defines a class @code{random_state}
2223 which contains the state of a random generator. If you make a copy
2224 of the random number generator, the original one and the copy will produce
2225 the same sequence of random numbers.
2227 The following functions return (pseudo-)random numbers in different formats.
2228 Calling one of these modifies the state of the random number generator in
2229 a complicated but deterministic way.
2232 @cindex @code{random_state}
2233 @cindex @code{default_random_state}
2235 random_state default_random_state
2237 contains a default random number generator. It is used when the functions
2238 below are called without @code{random_state} argument.
2241 @item uint32 random32 (random_state& randomstate)
2242 @itemx uint32 random32 ()
2243 @cindex @code{random32 ()}
2244 Returns a random unsigned 32-bit number. All bits are equally random.
2246 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2247 @itemx cl_I random_I (const cl_I& n)
2248 @cindex @code{random_I ()}
2249 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2250 in the range @code{0 <= x < n}.
2252 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2253 @itemx cl_F random_F (const cl_F& n)
2254 @cindex @code{random_F ()}
2255 @code{n} must be a float > 0. This function returns a random floating-point
2256 number of the same format as @code{n} in the range @code{0 <= x < n}.
2258 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2259 @itemx cl_R random_R (const cl_R& n)
2260 @cindex @code{random_R ()}
2261 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2262 if @code{n} is a float.
2266 @section Obfuscating operators
2267 @cindex modifying operators
2269 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2270 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2271 are not available by default because their
2272 use tends to make programs unreadable. It is trivial to get away without
2273 them. However, if you feel that you absolutely need these operators
2274 to get happy, then add
2276 #define WANT_OBFUSCATING_OPERATORS
2278 @cindex @code{WANT_OBFUSCATING_OPERATORS}
2279 to the beginning of your source files, before the inclusion of any CLN
2280 include files. This flag will enable the following operators:
2282 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2283 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2286 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2287 @cindex @code{operator += ()}
2288 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2289 @cindex @code{operator -= ()}
2290 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2291 @cindex @code{operator *= ()}
2292 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2293 @cindex @code{operator /= ()}
2296 For the class @code{cl_I}:
2299 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2300 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2301 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2302 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2303 @cindex @code{operator &= ()}
2304 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2305 @cindex @code{operator |= ()}
2306 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2307 @cindex @code{operator ^= ()}
2308 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2309 @cindex @code{operator <<= ()}
2310 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2311 @cindex @code{operator >>= ()}
2314 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2315 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2318 @item @var{type}& operator ++ (@var{type}& x)
2319 @cindex @code{operator ++ ()}
2320 The prefix operator @code{++x}.
2322 @item void operator ++ (@var{type}& x, int)
2323 The postfix operator @code{x++}.
2325 @item @var{type}& operator -- (@var{type}& x)
2326 @cindex @code{operator -- ()}
2327 The prefix operator @code{--x}.
2329 @item void operator -- (@var{type}& x, int)
2330 The postfix operator @code{x--}.
2333 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2334 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2338 @chapter Input/Output
2339 @cindex Input/Output
2341 @section Internal and printed representation
2342 @cindex representation
2344 All computations deal with the internal representations of the numbers.
2346 Every number has an external representation as a sequence of ASCII characters.
2347 Several external representations may denote the same number, for example,
2348 "20.0" and "20.000".
2350 Converting an internal to an external representation is called ``printing'',
2352 converting an external to an internal representation is called ``reading''.
2354 In CLN, it is always true that conversion of an internal to an external
2355 representation and then back to an internal representation will yield the
2356 same internal representation. Symbolically: @code{read(print(x)) == x}.
2357 This is called ``print-read consistency''.
2359 Different types of numbers have different external representations (case
2364 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2365 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2366 for decimal integers
2367 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2369 @item Rational numbers
2370 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2371 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2374 @item Floating-point numbers
2375 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2376 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2377 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2378 of the form _@var{prec} may be appended. There must be at least
2379 one digit in the non-exponent part. The exponent has the syntax
2380 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2381 The exponent marker is
2385 @samp{s} for short-floats,
2387 @samp{f} for single-floats,
2389 @samp{d} for double-floats,
2391 @samp{L} for long-floats,
2394 or @samp{e}, which denotes a default float format. The precision specifying
2395 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2396 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2397 function @samp{cl_float_format}.
2399 @item Complex numbers
2400 External representation:
2403 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2404 if @var{imagpart} is negative, its printed representation begins with
2405 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2406 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2407 is rational and the rational number's base is >18, because the @samp{i}
2408 is then read as a digit.
2410 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2415 @section Input functions
2417 Including @code{<cln/io.h>} defines a type @code{cl_istream}, which is
2418 the type of the first argument to all input functions. @code{cl_istream}
2419 is the same as @code{std::istream&}.
2424 @code{cl_istream stdin}
2426 contains the standard input stream.
2428 These are the simple input functions:
2431 @item int freadchar (cl_istream stream)
2432 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2433 if the end of stream was encountered or an error occurred.
2435 @item int funreadchar (cl_istream stream, int c)
2436 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2437 last @code{freadchar} operation on @code{stream}.
2440 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2441 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2442 defines, in @code{<cln/@var{type}_io.h>}, the following input function:
2445 @item cl_istream operator>> (cl_istream stream, @var{type}& result)
2446 Reads a number from @code{stream} and stores it in the @code{result}.
2449 The most flexible input functions, defined in @code{<cln/@var{type}_io.h>},
2453 @item cl_N read_complex (cl_istream stream, const cl_read_flags& flags)
2454 @itemx cl_R read_real (cl_istream stream, const cl_read_flags& flags)
2455 @itemx cl_F read_float (cl_istream stream, const cl_read_flags& flags)
2456 @itemx cl_RA read_rational (cl_istream stream, const cl_read_flags& flags)
2457 @itemx cl_I read_integer (cl_istream stream, const cl_read_flags& flags)
2458 Reads a number from @code{stream}. The @code{flags} are parameters which
2459 affect the input syntax. Whitespace before the number is silently skipped.
2461 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2462 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2463 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2464 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2465 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2466 Reads a number from a string in memory. The @code{flags} are parameters which
2467 affect the input syntax. The string starts at @code{string} and ends at
2468 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2469 @code{NULL}, denoting the entire string, i.e. equivalent to
2470 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2471 @code{NULL}, the string in memory must contain exactly one number and nothing
2472 more, else a fatal error will be signalled. If @code{end_of_parse}
2473 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2474 the last parsed character (i.e. @code{string_limit} if nothing came after
2475 the number). Whitespace is not allowed.
2478 The structure @code{cl_read_flags} contains the following fields:
2481 @item cl_read_syntax_t syntax
2482 The possible results of the read operation. Possible values are
2483 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2484 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2485 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2487 @item cl_read_lsyntax_t lsyntax
2488 Specifies the language-dependent syntax variant for the read operation.
2492 @item lsyntax_standard
2493 accept standard algebraic notation only, no complex numbers,
2494 @item lsyntax_algebraic
2495 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2496 @item lsyntax_commonlisp
2497 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2498 hexadecimal numbers,
2499 @code{#@var{base}R} for rational numbers in a given base,
2500 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2502 accept all of these extensions.
2505 @item unsigned int rational_base
2506 The base in which rational numbers are read.
2508 @item cl_float_format_t float_flags.default_float_format
2509 The float format used when reading floats with exponent marker @samp{e}.
2511 @item cl_float_format_t float_flags.default_lfloat_format
2512 The float format used when reading floats with exponent marker @samp{l}.
2514 @item cl_boolean float_flags.mantissa_dependent_float_format
2515 When this flag is true, floats specified with more digits than corresponding
2516 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2517 precision corresponding to their number of significant digits.
2521 @section Output functions
2523 Including @code{<cln/io.h>} defines a type @code{cl_ostream}, which is
2524 the type of the first argument to all output functions. @code{cl_ostream}
2525 is the same as @code{std::ostream&}.
2530 @code{cl_ostream stdout}
2532 contains the standard output stream.
2537 @code{cl_ostream stderr}
2539 contains the standard error output stream.
2541 These are the simple output functions:
2544 @item void fprintchar (cl_ostream stream, char c)
2545 Prints the character @code{x} literally on the @code{stream}.
2547 @item void fprint (cl_ostream stream, const char * string)
2548 Prints the @code{string} literally on the @code{stream}.
2550 @item void fprintdecimal (cl_ostream stream, int x)
2551 @itemx void fprintdecimal (cl_ostream stream, const cl_I& x)
2552 Prints the integer @code{x} in decimal on the @code{stream}.
2554 @item void fprintbinary (cl_ostream stream, const cl_I& x)
2555 Prints the integer @code{x} in binary (base 2, without prefix)
2556 on the @code{stream}.
2558 @item void fprintoctal (cl_ostream stream, const cl_I& x)
2559 Prints the integer @code{x} in octal (base 8, without prefix)
2560 on the @code{stream}.
2562 @item void fprinthexadecimal (cl_ostream stream, const cl_I& x)
2563 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2564 on the @code{stream}.
2567 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2568 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2569 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2572 @item void fprint (cl_ostream stream, const @var{type}& x)
2573 @itemx cl_ostream operator<< (cl_ostream stream, const @var{type}& x)
2574 Prints the number @code{x} on the @code{stream}. The output may depend
2575 on the global printer settings in the variable @code{default_print_flags}.
2576 The @code{ostream} flags and settings (flags, width and locale) are
2580 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2583 void print_complex (cl_ostream stream, const cl_print_flags& flags,
2585 void print_real (cl_ostream stream, const cl_print_flags& flags,
2587 void print_float (cl_ostream stream, const cl_print_flags& flags,
2589 void print_rational (cl_ostream stream, const cl_print_flags& flags,
2591 void print_integer (cl_ostream stream, const cl_print_flags& flags,
2594 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2595 parameters which affect the output.
2597 The structure type @code{cl_print_flags} contains the following fields:
2600 @item unsigned int rational_base
2601 The base in which rational numbers are printed. Default is @code{10}.
2603 @item cl_boolean rational_readably
2604 If this flag is true, rational numbers are printed with radix specifiers in
2605 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2606 prefixes, trailing dot). Default is false.
2608 @item cl_boolean float_readably
2609 If this flag is true, type specific exponent markers have precedence over 'E'.
2612 @item cl_float_format_t default_float_format
2613 Floating point numbers of this format will be printed using the 'E' exponent
2614 marker. Default is @code{cl_float_format_ffloat}.
2616 @item cl_boolean complex_readably
2617 If this flag is true, complex numbers will be printed using the Common Lisp
2618 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2620 @item cl_string univpoly_varname
2621 Univariate polynomials with no explicit indeterminate name will be printed
2622 using this variable name. Default is @code{"x"}.
2625 The global variable @code{default_print_flags} contains the default values,
2626 used by the function @code{fprint}.
2631 CLN has a class of abstract rings.
2639 Rings can be compared for equality:
2642 @item bool operator== (const cl_ring&, const cl_ring&)
2643 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2644 These compare two rings for equality.
2647 Given a ring @code{R}, the following members can be used.
2650 @item void R->fprint (cl_ostream stream, const cl_ring_element& x)
2651 @cindex @code{fprint ()}
2652 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2653 @cindex @code{equal ()}
2654 @itemx cl_ring_element R->zero ()
2655 @cindex @code{zero ()}
2656 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2657 @cindex @code{zerop ()}
2658 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2659 @cindex @code{plus ()}
2660 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2661 @cindex @code{minus ()}
2662 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2663 @cindex @code{uminus ()}
2664 @itemx cl_ring_element R->one ()
2665 @cindex @code{one ()}
2666 @itemx cl_ring_element R->canonhom (const cl_I& x)
2667 @cindex @code{canonhom ()}
2668 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2669 @cindex @code{mul ()}
2670 @itemx cl_ring_element R->square (const cl_ring_element& x)
2671 @cindex @code{square ()}
2672 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2673 @cindex @code{expt_pos ()}
2676 The following rings are built-in.
2679 @item cl_null_ring cl_0_ring
2680 The null ring, containing only zero.
2682 @item cl_complex_ring cl_C_ring
2683 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2685 @item cl_real_ring cl_R_ring
2686 The ring of real numbers. This corresponds to the type @code{cl_R}.
2688 @item cl_rational_ring cl_RA_ring
2689 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2691 @item cl_integer_ring cl_I_ring
2692 The ring of integers. This corresponds to the type @code{cl_I}.
2695 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2696 @code{cl_RA_ring}, @code{cl_I_ring}:
2699 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2700 @cindex @code{instanceof ()}
2701 Tests whether the given number is an element of the number ring R.
2705 @chapter Modular integers
2706 @cindex modular integer
2708 @section Modular integer rings
2711 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2712 The modulus is explicitly part of every modular integer. CLN doesn't
2713 allow you to (accidentally) mix elements of different modular rings,
2714 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2715 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2716 doesn't have generic types. So one has to live with runtime checks.)
2718 The class of modular integer rings is
2726 Modular integer ring
2730 @cindex @code{cl_modint_ring}
2732 and the class of all modular integers (elements of modular integer rings) is
2740 Modular integer rings are constructed using the function
2743 @item cl_modint_ring find_modint_ring (const cl_I& N)
2744 @cindex @code{find_modint_ring ()}
2745 This function returns the modular ring @samp{Z/NZ}. It takes care
2746 of finding out about special cases of @code{N}, like powers of two
2747 and odd numbers for which Montgomery multiplication will be a win,
2748 @cindex Montgomery multiplication
2749 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2750 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2751 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2755 Modular integer rings can be compared for equality:
2758 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2759 @cindex @code{operator == ()}
2760 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2761 @cindex @code{operator != ()}
2762 These compare two modular integer rings for equality. Two different calls
2763 to @code{find_modint_ring} with the same argument necessarily return the
2764 same ring because it is memoized in the cache table.
2767 @section Functions on modular integers
2769 Given a modular integer ring @code{R}, the following members can be used.
2772 @item cl_I R->modulus
2773 @cindex @code{modulus}
2774 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2776 @item cl_MI R->zero()
2777 @cindex @code{zero ()}
2778 This returns @code{0 mod N}.
2780 @item cl_MI R->one()
2781 @cindex @code{one ()}
2782 This returns @code{1 mod N}.
2784 @item cl_MI R->canonhom (const cl_I& x)
2785 @cindex @code{canonhom ()}
2786 This returns @code{x mod N}.
2788 @item cl_I R->retract (const cl_MI& x)
2789 @cindex @code{retract ()}
2790 This is a partial inverse function to @code{R->canonhom}. It returns the
2791 standard representative (@code{>=0}, @code{<N}) of @code{x}.
2793 @item cl_MI R->random(random_state& randomstate)
2794 @itemx cl_MI R->random()
2795 @cindex @code{random ()}
2796 This returns a random integer modulo @code{N}.
2799 The following operations are defined on modular integers.
2802 @item cl_modint_ring x.ring ()
2803 @cindex @code{ring ()}
2804 Returns the ring to which the modular integer @code{x} belongs.
2806 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
2807 @cindex @code{operator + ()}
2808 Returns the sum of two modular integers. One of the arguments may also
2811 @item cl_MI operator- (const cl_MI&, const cl_MI&)
2812 @cindex @code{operator - ()}
2813 Returns the difference of two modular integers. One of the arguments may also
2816 @item cl_MI operator- (const cl_MI&)
2817 Returns the negative of a modular integer.
2819 @item cl_MI operator* (const cl_MI&, const cl_MI&)
2820 @cindex @code{operator * ()}
2821 Returns the product of two modular integers. One of the arguments may also
2824 @item cl_MI square (const cl_MI&)
2825 @cindex @code{square ()}
2826 Returns the square of a modular integer.
2828 @item cl_MI recip (const cl_MI& x)
2829 @cindex @code{recip ()}
2830 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
2831 must be coprime to the modulus, otherwise an error message is issued.
2833 @item cl_MI div (const cl_MI& x, const cl_MI& y)
2834 @cindex @code{div ()}
2835 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
2836 @code{y} must be coprime to the modulus, otherwise an error message is issued.
2838 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
2839 @cindex @code{expt_pos ()}
2840 @code{y} must be > 0. Returns @code{x^y}.
2842 @item cl_MI expt (const cl_MI& x, const cl_I& y)
2843 @cindex @code{expt ()}
2844 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
2845 modulus, else an error message is issued.
2847 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
2848 @cindex @code{operator << ()}
2849 Returns @code{x*2^y}.
2851 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
2852 @cindex @code{operator >> ()}
2853 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
2854 or an error message is issued.
2856 @item bool operator== (const cl_MI&, const cl_MI&)
2857 @cindex @code{operator == ()}
2858 @itemx bool operator!= (const cl_MI&, const cl_MI&)
2859 @cindex @code{operator != ()}
2860 Compares two modular integers, belonging to the same modular integer ring,
2863 @item cl_boolean zerop (const cl_MI& x)
2864 @cindex @code{zerop ()}
2865 Returns true if @code{x} is @code{0 mod N}.
2868 The following output functions are defined (see also the chapter on
2872 @item void fprint (cl_ostream stream, const cl_MI& x)
2873 @cindex @code{fprint ()}
2874 @itemx cl_ostream operator<< (cl_ostream stream, const cl_MI& x)
2875 @cindex @code{operator << ()}
2876 Prints the modular integer @code{x} on the @code{stream}. The output may depend
2877 on the global printer settings in the variable @code{default_print_flags}.
2881 @chapter Symbolic data types
2882 @cindex symbolic type
2884 CLN implements two symbolic (non-numeric) data types: strings and symbols.
2888 @cindex @code{cl_string}
2898 implements immutable strings.
2900 Strings are constructed through the following constructors:
2903 @item cl_string (const char * s)
2904 Returns an immutable copy of the (zero-terminated) C string @code{s}.
2906 @item cl_string (const char * ptr, unsigned long len)
2907 Returns an immutable copy of the @code{len} characters at
2908 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
2911 The following functions are available on strings:
2915 Assignment from @code{cl_string} and @code{const char *}.
2918 @cindex @code{length ()}
2920 @cindex @code{strlen ()}
2921 Returns the length of the string @code{s}.
2924 @cindex @code{operator [] ()}
2925 Returns the @code{i}th character of the string @code{s}.
2926 @code{i} must be in the range @code{0 <= i < s.length()}.
2928 @item bool equal (const cl_string& s1, const cl_string& s2)
2929 @cindex @code{equal ()}
2930 Compares two strings for equality. One of the arguments may also be a
2931 plain @code{const char *}.
2936 @cindex @code{cl_symbol}
2938 Symbols are uniquified strings: all symbols with the same name are shared.
2939 This means that comparison of two symbols is fast (effectively just a pointer
2940 comparison), whereas comparison of two strings must in the worst case walk
2941 both strings until their end.
2942 Symbols are used, for example, as tags for properties, as names of variables
2943 in polynomial rings, etc.
2945 Symbols are constructed through the following constructor:
2948 @item cl_symbol (const cl_string& s)
2949 Looks up or creates a new symbol with a given name.
2952 The following operations are available on symbols:
2955 @item cl_string (const cl_symbol& sym)
2956 Conversion to @code{cl_string}: Returns the string which names the symbol
2959 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
2960 @cindex @code{equal ()}
2961 Compares two symbols for equality. This is very fast.
2965 @chapter Univariate polynomials
2967 @cindex univariate polynomial
2969 @section Univariate polynomial rings
2971 CLN implements univariate polynomials (polynomials in one variable) over an
2972 arbitrary ring. The indeterminate variable may be either unnamed (and will be
2973 printed according to @code{default_print_flags.univpoly_varname}, which
2974 defaults to @samp{x}) or carry a given name. The base ring and the
2975 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
2976 (accidentally) mix elements of different polynomial rings, e.g.
2977 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
2978 return a multivariate polynomial, but they are not yet implemented in CLN.)
2980 The classes of univariate polynomial rings are
2988 Univariate polynomial ring
2992 +----------------+-------------------+
2994 Complex polynomial ring | Modular integer polynomial ring
2995 cl_univpoly_complex_ring | cl_univpoly_modint_ring
2996 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3000 Real polynomial ring |
3001 cl_univpoly_real_ring |
3002 <cln/univpoly_real.h> |
3006 Rational polynomial ring |
3007 cl_univpoly_rational_ring |
3008 <cln/univpoly_rational.h> |
3012 Integer polynomial ring
3013 cl_univpoly_integer_ring
3014 <cln/univpoly_integer.h>
3017 and the corresponding classes of univariate polynomials are
3020 Univariate polynomial
3024 +----------------+-------------------+
3026 Complex polynomial | Modular integer polynomial
3028 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3034 <cln/univpoly_real.h> |
3038 Rational polynomial |
3040 <cln/univpoly_rational.h> |
3046 <cln/univpoly_integer.h>
3049 Univariate polynomial rings are constructed using the functions
3052 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3053 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3054 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3055 @code{R} may be an arbitrary ring. This function takes care of finding out
3056 about special cases of @code{R}, such as the rings of complex numbers,
3057 real numbers, rational numbers, integers, or modular integer rings.
3058 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3059 This ensures that two calls of this function with the same arguments will
3060 return the same polynomial ring.
3062 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3063 @cindex @code{find_univpoly_ring ()}
3064 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3065 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3066 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3067 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3068 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3069 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3070 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3071 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3072 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3073 These functions are equivalent to the general @code{find_univpoly_ring},
3074 only the return type is more specific, according to the base ring's type.
3077 @section Functions on univariate polynomials
3079 Given a univariate polynomial ring @code{R}, the following members can be used.
3082 @item cl_ring R->basering()
3083 @cindex @code{basering ()}
3084 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3086 @item cl_UP R->zero()
3087 @cindex @code{zero ()}
3088 This returns @code{0 in R}, a polynomial of degree -1.
3090 @item cl_UP R->one()
3091 @cindex @code{one ()}
3092 This returns @code{1 in R}, a polynomial of degree <= 0.
3094 @item cl_UP R->canonhom (const cl_I& x)
3095 @cindex @code{canonhom ()}
3096 This returns @code{x in R}, a polynomial of degree <= 0.
3098 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3099 @cindex @code{monomial ()}
3100 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3103 @item cl_UP R->create (sintL degree)
3104 @cindex @code{create ()}
3105 Creates a new polynomial with a given degree. The zero polynomial has degree
3106 @code{-1}. After creating the polynomial, you should put in the coefficients,
3107 using the @code{set_coeff} member function, and then call the @code{finalize}
3111 The following are the only destructive operations on univariate polynomials.
3114 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3115 @cindex @code{set_coeff ()}
3116 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3117 After changing a polynomial and before applying any "normal" operation on it,
3118 you should call its @code{finalize} member function.
3120 @item void finalize (cl_UP& x)
3121 @cindex @code{finalize ()}
3122 This function marks the endpoint of destructive modifications of a polynomial.
3123 It normalizes the internal representation so that subsequent computations have
3124 less overhead. Doing normal computations on unnormalized polynomials may
3125 produce wrong results or crash the program.
3128 The following operations are defined on univariate polynomials.
3131 @item cl_univpoly_ring x.ring ()
3132 @cindex @code{ring ()}
3133 Returns the ring to which the univariate polynomial @code{x} belongs.
3135 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3136 @cindex @code{operator + ()}
3137 Returns the sum of two univariate polynomials.
3139 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3140 @cindex @code{operator - ()}
3141 Returns the difference of two univariate polynomials.
3143 @item cl_UP operator- (const cl_UP&)
3144 Returns the negative of a univariate polynomial.
3146 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3147 @cindex @code{operator * ()}
3148 Returns the product of two univariate polynomials. One of the arguments may
3149 also be a plain integer or an element of the base ring.
3151 @item cl_UP square (const cl_UP&)
3152 @cindex @code{square ()}
3153 Returns the square of a univariate polynomial.
3155 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3156 @cindex @code{expt_pos ()}
3157 @code{y} must be > 0. Returns @code{x^y}.
3159 @item bool operator== (const cl_UP&, const cl_UP&)
3160 @cindex @code{operator == ()}
3161 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3162 @cindex @code{operator != ()}
3163 Compares two univariate polynomials, belonging to the same univariate
3164 polynomial ring, for equality.
3166 @item cl_boolean zerop (const cl_UP& x)
3167 @cindex @code{zerop ()}
3168 Returns true if @code{x} is @code{0 in R}.
3170 @item sintL degree (const cl_UP& x)
3171 @cindex @code{degree ()}
3172 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3174 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3175 @cindex @code{coeff ()}
3176 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3178 @item cl_ring_element x (const cl_ring_element& y)
3179 @cindex @code{operator () ()}
3180 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3181 then @samp{x(y)} returns the value of the substitution of @code{y} into
3184 @item cl_UP deriv (const cl_UP& x)
3185 @cindex @code{deriv ()}
3186 Returns the derivative of the polynomial @code{x} with respect to the
3187 indeterminate @code{X}.
3190 The following output functions are defined (see also the chapter on
3194 @item void fprint (cl_ostream stream, const cl_UP& x)
3195 @cindex @code{fprint ()}
3196 @itemx cl_ostream operator<< (cl_ostream stream, const cl_UP& x)
3197 @cindex @code{operator << ()}
3198 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3199 depend on the global printer settings in the variable
3200 @code{default_print_flags}.
3203 @section Special polynomials
3205 The following functions return special polynomials.
3208 @item cl_UP_I tschebychev (sintL n)
3209 @cindex @code{tschebychev ()}
3210 @cindex Chebyshev polynomial
3211 Returns the n-th Chebyshev polynomial (n >= 0).
3213 @item cl_UP_I hermite (sintL n)
3214 @cindex @code{hermite ()}
3215 @cindex Hermite polynomial
3216 Returns the n-th Hermite polynomial (n >= 0).
3218 @item cl_UP_RA legendre (sintL n)
3219 @cindex @code{legendre ()}
3220 @cindex Legende polynomial
3221 Returns the n-th Legendre polynomial (n >= 0).
3223 @item cl_UP_I laguerre (sintL n)
3224 @cindex @code{laguerre ()}
3225 @cindex Laguerre polynomial
3226 Returns the n-th Laguerre polynomial (n >= 0).
3229 Information how to derive the differential equation satisfied by each
3230 of these polynomials from their definition can be found in the
3231 @code{doc/polynomial/} directory.
3239 Using C++ as an implementation language provides
3243 Efficiency: It compiles to machine code.
3247 Portability: It runs on all platforms supporting a C++ compiler. Because
3248 of the availability of GNU C++, this includes all currently used 32-bit and
3249 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3252 Type safety: The C++ compilers knows about the number types and complains if,
3253 for example, you try to assign a float to an integer variable. However,
3254 a drawback is that C++ doesn't know about generic types, hence a restriction
3255 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3256 arguments belong to the same modular ring cannot be expressed as a compile-time
3260 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3261 @code{=}, @code{==}, ... can be used in infix notation, which is more
3262 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3265 With these language features, there is no need for two separate languages,
3266 one for the implementation of the library and one in which the library's users
3267 can program. This means that a prototype implementation of an algorithm
3268 can be integrated into the library immediately after it has been tested and
3269 debugged. No need to rewrite it in a low-level language after having prototyped
3270 in a high-level language.
3273 @section Memory efficiency
3275 In order to save memory allocations, CLN implements:
3279 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3282 @cindex garbage collection
3283 @cindex reference counting
3284 Garbage collection: A reference counting mechanism makes sure that any
3285 number object's storage is freed immediately when the last reference to the
3288 Small integers are represented as immediate values instead of pointers
3289 to heap allocated storage. This means that integers @code{> -2^29},
3290 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3295 @section Speed efficiency
3297 Speed efficiency is obtained by the combination of the following tricks
3302 Small integers, being represented as immediate values, don't require
3303 memory access, just a couple of instructions for each elementary operation.
3305 The kernel of CLN has been written in assembly language for some CPUs
3306 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3308 On all CPUs, CLN may be configured to use the superefficient low-level
3309 routines from GNU GMP version 3.
3311 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3312 algorithm, the Karatsuba multiplication, which is an
3323 For very large numbers (more than 12000 decimal digits), CLN uses
3325 Sch{@"o}nhage-Strassen
3326 @cindex Sch{@"o}nhage-Strassen multiplication
3330 @cindex Schönhage-Strassen multiplication
3332 multiplication, which is an asymptotically optimal multiplication
3335 These fast multiplication algorithms also give improvements in the speed
3336 of division and radix conversion.
3340 @section Garbage collection
3341 @cindex garbage collection
3343 All the number classes are reference count classes: They only contain a pointer
3344 to an object in the heap. Upon construction, assignment and destruction of
3345 number objects, only the objects' reference count are manipulated.
3347 Memory occupied by number objects are automatically reclaimed as soon as
3348 their reference count drops to zero.
3350 For number rings, another strategy is implemented: There is a cache of,
3351 for example, the modular integer rings. A modular integer ring is destroyed
3352 only if its reference count dropped to zero and the cache is about to be
3353 resized. The effect of this strategy is that recently used rings remain
3354 cached, whereas undue memory consumption through cached rings is avoided.
3357 @chapter Using the library
3359 For the following discussion, we will assume that you have installed
3360 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3361 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3362 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3363 environment variables, or directly substitute the appropriate values.
3366 @section Compiler options
3367 @cindex compiler options
3369 Until you have installed CLN in a public place, the following options are
3372 When you compile CLN application code, add the flags
3374 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3376 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3377 When you link CLN application code to form an executable, add the flags
3379 $CLN_TARGETDIR/src/libcln.a
3381 to the C/C++ compiler's command line (@code{make} variable LIBS).
3383 If you did a @code{make install}, the include files are installed in a
3384 public directory (normally @code{/usr/local/include}), hence you don't
3385 need special flags for compiling. The library has been installed to a
3386 public directory as well (normally @code{/usr/local/lib}), hence when
3387 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3390 @section Compatibility to old CLN versions
3392 @cindex compatibility
3394 As of CLN version 1.1 all non-macro identifiers were hidden in namespace
3395 @code{cln} in order to avoid potential name clashes with other C++
3396 libraries. If you have an old application, you will have to manually
3397 port it to the new scheme. The following principles will help during
3401 All headers are now in a separate subdirectory. Instead of including
3402 @code{cl_}@var{something}@code{.h}, include
3403 @code{cln/}@var{something}@code{.h} now.
3405 All public identifiers (typenames and functions) have lost their
3406 @code{cl_} prefix. Exceptions are all the typenames of number types,
3407 (cl_N, cl_I, cl_MI, @dots{}), rings, symbolic types (cl_string,
3408 cl_symbol) and polynomials (cl_UP_@var{type}). (This is because their
3409 names would not be mnemonic enough once the namespace @code{cln} is
3410 imported. Even in a namespace we favor @code{cl_N} over @code{N}.)
3412 All public @emph{functions} that had by a @code{cl_} in their name still
3413 carry that @code{cl_} if it is intrinsic part of a typename (as in
3414 @code{cl_I_to_int ()}).
3416 When developing other libraries, please keep in mind not to import the
3417 namespace @code{cln} in one of your public header files by saying
3418 @code{using namespace cln;}. This would propagate to other applications
3419 and can cause name clashes there.
3422 @section Include files
3423 @cindex include files
3424 @cindex header files
3426 Here is a summary of the include files and their contents.
3429 @item <cln/object.h>
3430 General definitions, reference counting, garbage collection.
3431 @item <cln/number.h>
3432 The class cl_number.
3433 @item <cln/complex.h>
3434 Functions for class cl_N, the complex numbers.
3436 Functions for class cl_R, the real numbers.
3438 Functions for class cl_F, the floats.
3439 @item <cln/sfloat.h>
3440 Functions for class cl_SF, the short-floats.
3441 @item <cln/ffloat.h>
3442 Functions for class cl_FF, the single-floats.
3443 @item <cln/dfloat.h>
3444 Functions for class cl_DF, the double-floats.
3445 @item <cln/lfloat.h>
3446 Functions for class cl_LF, the long-floats.
3447 @item <cln/rational.h>
3448 Functions for class cl_RA, the rational numbers.
3449 @item <cln/integer.h>
3450 Functions for class cl_I, the integers.
3453 @item <cln/complex_io.h>
3454 Input/Output for class cl_N, the complex numbers.
3455 @item <cln/real_io.h>
3456 Input/Output for class cl_R, the real numbers.
3457 @item <cln/float_io.h>
3458 Input/Output for class cl_F, the floats.
3459 @item <cln/sfloat_io.h>
3460 Input/Output for class cl_SF, the short-floats.
3461 @item <cln/ffloat_io.h>
3462 Input/Output for class cl_FF, the single-floats.
3463 @item <cln/dfloat_io.h>
3464 Input/Output for class cl_DF, the double-floats.
3465 @item <cln/lfloat_io.h>
3466 Input/Output for class cl_LF, the long-floats.
3467 @item <cln/rational_io.h>
3468 Input/Output for class cl_RA, the rational numbers.
3469 @item <cln/integer_io.h>
3470 Input/Output for class cl_I, the integers.
3472 Flags for customizing input operations.
3473 @item <cln/output.h>
3474 Flags for customizing output operations.
3475 @item <cln/malloc.h>
3476 @code{malloc_hook}, @code{free_hook}.
3479 @item <cln/condition.h>
3480 Conditions/exceptions.
3481 @item <cln/string.h>
3483 @item <cln/symbol.h>
3485 @item <cln/proplist.h>
3489 @item <cln/null_ring.h>
3491 @item <cln/complex_ring.h>
3492 The ring of complex numbers.
3493 @item <cln/real_ring.h>
3494 The ring of real numbers.
3495 @item <cln/rational_ring.h>
3496 The ring of rational numbers.
3497 @item <cln/integer_ring.h>
3498 The ring of integers.
3499 @item <cln/numtheory.h>
3500 Number threory functions.
3501 @item <cln/modinteger.h>
3507 @item <cln/GV_number.h>
3508 General vectors over cl_number.
3509 @item <cln/GV_complex.h>
3510 General vectors over cl_N.
3511 @item <cln/GV_real.h>
3512 General vectors over cl_R.
3513 @item <cln/GV_rational.h>
3514 General vectors over cl_RA.
3515 @item <cln/GV_integer.h>
3516 General vectors over cl_I.
3517 @item <cln/GV_modinteger.h>
3518 General vectors of modular integers.
3521 @item <cln/SV_number.h>
3522 Simple vectors over cl_number.
3523 @item <cln/SV_complex.h>
3524 Simple vectors over cl_N.
3525 @item <cln/SV_real.h>
3526 Simple vectors over cl_R.
3527 @item <cln/SV_rational.h>
3528 Simple vectors over cl_RA.
3529 @item <cln/SV_integer.h>
3530 Simple vectors over cl_I.
3531 @item <cln/SV_ringelt.h>
3532 Simple vectors of general ring elements.
3533 @item <cln/univpoly.h>
3534 Univariate polynomials.
3535 @item <cln/univpoly_integer.h>
3536 Univariate polynomials over the integers.
3537 @item <cln/univpoly_rational.h>
3538 Univariate polynomials over the rational numbers.
3539 @item <cln/univpoly_real.h>
3540 Univariate polynomials over the real numbers.
3541 @item <cln/univpoly_complex.h>
3542 Univariate polynomials over the complex numbers.
3543 @item <cln/univpoly_modint.h>
3544 Univariate polynomials over modular integer rings.
3545 @item <cln/timing.h>
3548 Includes all of the above.
3554 A function which computes the nth Fibonacci number can be written as follows.
3555 @cindex Fibonacci number
3558 #include <cln/integer.h>
3559 #include <cln/real.h>
3560 using namespace cln;
3562 // Returns F_n, computed as the nearest integer to
3563 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3564 const cl_I fibonacci (int n)
3566 // Need a precision of ((1+sqrt(5))/2)^-n.
3567 cl_float_format_t prec = cl_float_format((int)(0.208987641*n+5));
3568 cl_R sqrt5 = sqrt(cl_float(5,prec));
3569 cl_R phi = (1+sqrt5)/2;
3570 return round1( expt(phi,n)/sqrt5 );
3574 Let's explain what is going on in detail.
3576 The include file @code{<cln/integer.h>} is necessary because the type
3577 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3578 is needed for the type @code{cl_R} and the floating point number functions.
3579 The order of the include files does not matter. In order not to write out
3580 @code{cln::}@var{foo} we can safely import the whole namespace @code{cln}.
3582 Then comes the function declaration. The argument is an @code{int}, the
3583 result an integer. The return type is defined as @samp{const cl_I}, not
3584 simply @samp{cl_I}, because that allows the compiler to detect typos like
3585 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3586 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3587 number). We use the most specialized possible return type because functions
3588 which call @samp{fibonacci} will be able to profit from the compiler's type
3589 analysis: Adding two integers is slightly more efficient than adding the
3590 same objects declared as complex numbers, because it needs less type
3591 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3592 the size of the resulting executable program.
3594 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3595 integer. In order to get a correct result, the absolute error should be less
3596 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3597 To this end, the first line computes a floating point precision for sqrt(5)
3600 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3601 number and than taking the square root. The converse, first taking the square
3602 root of 5, and then converting to the desired precision, would not work in
3603 CLN: The square root would be computed to a default precision (normally
3604 single-float precision), and the following conversion could not help about
3605 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3606 system and does not represent sqrt(5) in a non-numeric way.
3608 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3609 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3610 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3611 @code{cl_N} because a @samp{round1} does not exist for general complex
3614 When the function returns, all the local variables in the function are
3615 automatically reclaimed (garbage collected). Only the result survives and
3616 gets passed to the caller.
3618 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3619 contains this implementation together with an even faster algorithm.
3621 @section Debugging support
3624 When debugging a CLN application with GNU @code{gdb}, two facilities are
3625 available from the library:
3628 @item The library does type checks, range checks, consistency checks at
3629 many places. When one of these fails, the function @code{cl_abort()} is
3630 called. Its default implementation is to perform an @code{exit(1)}, so
3631 you won't have a core dump. But for debugging, it is best to set a
3632 breakpoint at this function:
3634 (gdb) break cl_abort
3636 When this breakpoint is hit, look at the stack's backtrace:
3641 @item The debugger's normal @code{print} command doesn't know about
3642 CLN's types and therefore prints mostly useless hexadecimal addresses.
3643 CLN offers a function @code{cl_print}, callable from the debugger,
3644 for printing number objects. In order to get this function, you have
3645 to define the macro @samp{CL_DEBUG} and then include all the header files
3646 for which you want @code{cl_print} debugging support. For example:
3647 @cindex @code{CL_DEBUG}
3650 #include <cln/string.h>
3652 Now, if you have in your program a variable @code{cl_string s}, and
3653 inspect it under @code{gdb}, the output may look like this:
3656 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3657 word = 134568800@}@}, @}
3658 (gdb) call cl_print(s)
3662 Note that the output of @code{cl_print} goes to the program's error output,
3663 not to gdb's standard output.
3665 Note, however, that the above facility does not work with all CLN types,
3666 only with number objects and similar. Therefore CLN offers a member function
3667 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3668 is needed for this member function to be implemented. Under @code{gdb},
3669 you call it like this:
3670 @cindex @code{debug_print ()}
3673 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3674 word = 134568800@}@}, @}
3675 (gdb) call s.debug_print()
3678 >call ($1).debug_print()
3683 Unfortunately, this feature does not seem to work under all circumstances.
3687 @chapter Customizing
3690 @section Error handling
3692 When a fatal error occurs, an error message is output to the standard error
3693 output stream, and the function @code{cl_abort} is called. The default
3694 version of this function (provided in the library) terminates the application.
3695 To catch such a fatal error, you need to define the function @code{cl_abort}
3696 yourself, with the prototype
3698 #include <cln/abort.h>
3699 void cl_abort (void);
3701 @cindex @code{cl_abort ()}
3702 This function must not return control to its caller.
3705 @section Floating-point underflow
3708 Floating point underflow denotes the situation when a floating-point number
3709 is to be created which is so close to @code{0} that its exponent is too
3710 low to be represented internally. By default, this causes a fatal error.
3711 If you set the global variable
3713 cl_boolean cl_inhibit_floating_point_underflow
3715 to @code{cl_true}, the error will be inhibited, and a floating-point zero
3716 will be generated instead. The default value of
3717 @code{cl_inhibit_floating_point_underflow} is @code{cl_false}.
3720 @section Customizing I/O
3722 The output of the function @code{fprint} may be customized by changing the
3723 value of the global variable @code{default_print_flags}.
3724 @cindex @code{default_print_flags}
3727 @section Customizing the memory allocator
3729 Every memory allocation of CLN is done through the function pointer
3730 @code{malloc_hook}. Freeing of this memory is done through the function
3731 pointer @code{free_hook}. The default versions of these functions,
3732 provided in the library, call @code{malloc} and @code{free} and check
3733 the @code{malloc} result against @code{NULL}.
3734 If you want to provide another memory allocator, you need to define
3735 the variables @code{malloc_hook} and @code{free_hook} yourself,
3738 #include <cln/malloc.h>
3740 void* (*malloc_hook) (size_t size) = @dots{};
3741 void (*free_hook) (void* ptr) = @dots{};
3744 @cindex @code{malloc_hook ()}
3745 @cindex @code{free_hook ()}
3746 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
3748 It is not possible to change the memory allocator at runtime, because
3749 it is already called at program startup by the constructors of some
3762 @c Table of contents