1 \input texinfo @c -*-texinfo-*-
4 @settitle CLN, a Class Library for Numbers
5 @c @setchapternewpage off
6 @c I hate putting "@noindent" in front of every paragraph.
7 @c For `info' and TeX only.
12 * CLN: (cln). Class Library for Numbers (C++).
17 @c Don't need the other types of indices.
28 This file documents @sc{cln}, a Class Library for Numbers.
30 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
31 Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
33 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007.
34 Copyright (C) Richard B. Kreckel 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007.
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, 2001, 2002, 2003, 2004, 2005, 2006, 2007.
70 Copyright @copyright{} Richard Kreckel 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007.
73 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
74 Richard Kreckel, @code{<kreckel@@ginac.de>}.
76 Permission is granted to make and distribute verbatim copies of
77 this manual provided the copyright notice and this permission notice
78 are preserved on all copies.
80 Permission is granted to copy and distribute modified versions of this
81 manual under the conditions for verbatim copying, provided that the entire
82 resulting derived work is distributed under the terms of a permission
83 notice identical to this one.
85 Permission is granted to copy and distribute translations of this manual
86 into another language, under the above conditions for modified versions,
87 except that this permission notice may be stated in a translation approved
98 @node Top, Introduction, (dir), (dir)
101 @c * Introduction:: Introduction
105 @node Introduction, Top, Top, Top
106 @comment node-name, next, previous, up
107 @chapter Introduction
110 CLN is a library for computations with all kinds of numbers.
111 It has a rich set of number classes:
115 Integers (with unlimited precision),
121 Floating-point numbers:
131 Long float (with unlimited precision),
138 Modular integers (integers modulo a fixed integer),
141 Univariate polynomials.
145 The subtypes of the complex numbers among these are exactly the
146 types of numbers known to the Common Lisp language. Therefore
147 @code{CLN} can be used for Common Lisp implementations, giving
148 @samp{CLN} another meaning: it becomes an abbreviation of
149 ``Common Lisp Numbers''.
152 The CLN package implements
156 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
157 comparisons, @dots{}),
160 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
163 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
164 functions and their inverse functions).
168 CLN is a C++ library. Using C++ as an implementation language provides
172 efficiency: it compiles to machine code,
174 type safety: the C++ compiler knows about the number types and complains
175 if, for example, you try to assign a float to an integer variable.
177 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
178 @code{==}, @dots{} operators as in C or C++.
182 CLN is memory efficient:
186 Small integers and short floats are immediate, not heap allocated.
188 Heap-allocated memory is reclaimed through an automatic, non-interruptive
193 CLN is speed efficient:
197 The kernel of CLN has been written in assembly language for some CPUs
198 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
201 On all CPUs, CLN may be configured to use the superefficient low-level
202 routines from GNU GMP version 3.
204 It uses Karatsuba multiplication, which is significantly faster
205 for large numbers than the standard multiplication algorithm.
207 For very large numbers (more than 12000 decimal digits), it uses
209 Sch{@"o}nhage-Strassen
210 @cindex Sch{@"o}nhage-Strassen multiplication
214 @cindex Schnhage-Strassen multiplication
216 multiplication, which is an asymptotically optimal multiplication
217 algorithm, for multiplication, division and radix conversion.
221 CLN aims at being easily integrated into larger software packages:
225 The garbage collection imposes no burden on the main application.
227 The library provides hooks for memory allocation and throws exceptions
231 All non-macro identifiers are hidden in namespace @code{cln} in
232 order to avoid name clashes.
236 @chapter Installation
238 This section describes how to install the CLN package on your system.
241 @section Prerequisites
243 @subsection C++ compiler
245 To build CLN, you need a C++ compiler.
246 Actually, you need GNU @code{g++ 3.0.0} or newer.
248 The following C++ features are used:
249 classes, member functions, overloading of functions and operators,
250 constructors and destructors, inline, const, multiple inheritance,
251 templates and namespaces.
253 The following C++ features are not used:
254 @code{new}, @code{delete}, virtual inheritance.
256 CLN relies on semi-automatic ordering of initializations of static and
257 global variables, a feature which I could implement for GNU g++
258 only. Also, it is not known whether this semi-automatic ordering works
259 on all platforms when a non-GNU assembler is being used.
261 @subsection Make utility
264 To build CLN, you also need to have GNU @code{make} installed.
266 Only GNU @code{make} 3.77 is unusable for CLN; other versions work fine.
268 @subsection Sed utility
271 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
272 This is because the libtool script, which creates the CLN library, relies
273 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
277 @section Building the library
279 As with any autoconfiguring GNU software, installation is as easy as this:
287 If on your system, @samp{make} is not GNU @code{make}, you have to use
288 @samp{gmake} instead of @samp{make} above.
290 The @code{configure} command checks out some features of your system and
291 C++ compiler and builds the @code{Makefile}s. The @code{make} command
292 builds the library. This step may take about an hour on an average workstation.
293 The @code{make check} runs some test to check that no important subroutine
294 has been miscompiled.
296 The @code{configure} command accepts options. To get a summary of them, try
302 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
304 You can specify the C compiler, the C++ compiler and their options through
305 the following environment variables when running @code{configure}:
309 Specifies the C compiler.
312 Flags to be given to the C compiler when compiling programs (not when linking).
315 Specifies the C++ compiler.
318 Flags to be given to the C++ compiler when compiling programs (not when linking).
324 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
325 $ CC="gcc -V 3.0.4" CFLAGS="-O2 -finline-limit=1000" \
326 CXX="g++ -V 3.0.4" CXXFLAGS="-O2 -finline-limit=1000" \
328 $ CC="gcc-4.1" CFLAGS="-O2" CXX="g++-4.1" CXXFLAGS="-O2" ./configure
331 Note that for these environment variables to take effect, you have to set
332 them (assuming a Bourne-compatible shell) on the same line as the
333 @code{configure} command. If you made the settings in earlier shell
334 commands, you have to @code{export} the environment variables before
335 calling @code{configure}. In a @code{csh} shell, you have to use the
336 @samp{setenv} command for setting each of the environment variables.
338 Currently CLN works only with the GNU @code{g++} compiler, and only in
339 optimizing mode. So you should specify at least @code{-O} in the CXXFLAGS,
340 or no CXXFLAGS at all. (If CXXFLAGS is not set, CLN will use @code{-O}.)
342 If you use @code{g++} 3.x, I recommend adding @samp{-finline-limit=1000}
343 to the CXXFLAGS. This is essential for good code.
345 If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
346 @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
347 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
348 routines. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
351 Also, please do not compile CLN with @code{g++} using the @code{-O3}
352 optimization level. This leads to inferior code quality.
354 If you use @code{g++} from gcc-3.1, it will need 235 MB of virtual memory.
355 You might need some swap space if your machine doesn't have 512 MB of RAM.
357 By default, both a shared and a static library are built. You can build
358 CLN as a static (or shared) library only, by calling @code{configure} with
359 the option @samp{--disable-shared} (or @samp{--disable-static}). While
360 shared libraries are usually more convenient to use, they may not work
361 on all architectures. Try disabling them if you run into linker
362 problems. Also, they are generally somewhat slower than static
363 libraries so runtime-critical applications should be linked statically.
365 If you use @code{g++} from gcc-3.1 with option @samp{-g}, you will need
366 some disk space: 335 MB for building as both a shared and a static library,
367 or 130 MB when building as a shared library only.
370 @subsection Using the GNU MP Library
373 Starting with version 1.1, CLN may be configured to make use of a
374 preinstalled @code{gmp} library. Please make sure that you have at
375 least @code{gmp} version 3.0 installed since earlier versions are
376 unsupported and likely not to work. Enabling this feature by calling
377 @code{configure} with the option @samp{--with-gmp} is known to be quite
378 a boost for CLN's performance.
380 If you have installed the @code{gmp} library and its header file in
381 some place where your compiler cannot find it by default, you must help
382 @code{configure} by setting @code{CPPFLAGS} and @code{LDFLAGS}. Here is
386 $ CC="gcc" CFLAGS="-O2" CXX="g++" CXXFLAGS="-O2" \
387 CPPFLAGS="-I/opt/gmp/include" LDFLAGS="-L/opt/gmp/lib" ./configure --with-gmp
391 @section Installing the library
394 As with any autoconfiguring GNU software, installation is as easy as this:
400 The @samp{make install} command installs the library and the include files
401 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
402 if you haven't specified a @code{--prefix} option to @code{configure}).
403 This step may require superuser privileges.
405 If you have already built the library and wish to install it, but didn't
406 specify @code{--prefix=@dots{}} at configure time, just re-run
407 @code{configure}, giving it the same options as the first time, plus
408 the @code{--prefix=@dots{}} option.
413 You can remove system-dependent files generated by @code{make} through
419 You can remove all files generated by @code{make}, thus reverting to a
420 virgin distribution of CLN, through
427 @chapter Ordinary number types
429 CLN implements the following class hierarchy:
437 Real or complex number
446 +-------------------+-------------------+
448 Rational number Floating-point number
450 <cln/rational.h> <cln/float.h>
452 | +--------------+--------------+--------------+
454 cl_I Short-Float Single-Float Double-Float Long-Float
455 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
456 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
459 @cindex @code{cl_number}
460 @cindex abstract class
461 The base class @code{cl_number} is an abstract base class.
462 It is not useful to declare a variable of this type except if you want
463 to completely disable compile-time type checking and use run-time type
468 @cindex complex number
469 The class @code{cl_N} comprises real and complex numbers. There is
470 no special class for complex numbers since complex numbers with imaginary
471 part @code{0} are automatically converted to real numbers.
474 The class @code{cl_R} comprises real numbers of different kinds. It is an
478 @cindex rational number
480 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
481 integers. There is no special class for non-integral rational numbers
482 since rational numbers with denominator @code{1} are automatically converted
486 The class @code{cl_F} implements floating-point approximations to real numbers.
487 It is an abstract class.
490 @section Exact numbers
493 Some numbers are represented as exact numbers: there is no loss of information
494 when such a number is converted from its mathematical value to its internal
495 representation. On exact numbers, the elementary operations (@code{+},
496 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
499 In CLN, the exact numbers are:
503 rational numbers (including integers),
505 complex numbers whose real and imaginary parts are both rational numbers.
508 Rational numbers are always normalized to the form
509 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
510 are coprime integers and the denominator is positive. If the resulting
511 denominator is @code{1}, the rational number is converted to an integer.
513 @cindex immediate numbers
514 Small integers (typically in the range @code{-2^29}@dots{}@code{2^29-1},
515 for 32-bit machines) are especially efficient, because they consume no heap
516 allocation. Otherwise the distinction between these immediate integers
517 (called ``fixnums'') and heap allocated integers (called ``bignums'')
518 is completely transparent.
521 @section Floating-point numbers
522 @cindex floating-point number
524 Not all real numbers can be represented exactly. (There is an easy mathematical
525 proof for this: Only a countable set of numbers can be stored exactly in
526 a computer, even if one assumes that it has unlimited storage. But there
527 are uncountably many real numbers.) So some approximation is needed.
528 CLN implements ordinary floating-point numbers, with mantissa and exponent.
530 @cindex rounding error
531 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
532 only return approximate results. For example, the value of the expression
533 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
534 @samp{0.7}. Rounding errors like this one are inevitable when computing
535 with floating-point numbers.
537 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
538 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
539 rule: It first computes the exact mathematical result and then returns the
540 floating-point number which is nearest to this. If two floating-point numbers
541 are equally distant from the ideal result, the one with a @code{0} in its least
542 significant mantissa bit is chosen.
544 Similarly, testing floating point numbers for equality @samp{x == y}
545 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
546 for some well-chosen @code{epsilon}.
548 Floating point numbers come in four flavors:
553 Short floats, type @code{cl_SF}.
554 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
555 and 17 mantissa bits (including the ``hidden'' bit).
556 They don't consume heap allocation.
560 Single floats, type @code{cl_FF}.
561 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
562 and 24 mantissa bits (including the ``hidden'' bit).
563 In CLN, they are represented as IEEE single-precision floating point numbers.
564 This corresponds closely to the C/C++ type @samp{float}.
568 Double floats, type @code{cl_DF}.
569 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
570 and 53 mantissa bits (including the ``hidden'' bit).
571 In CLN, they are represented as IEEE double-precision floating point numbers.
572 This corresponds closely to the C/C++ type @samp{double}.
576 Long floats, type @code{cl_LF}.
577 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
578 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
579 The precision of a long float is unlimited, but once created, a long float
580 has a fixed precision. (No ``lazy recomputation''.)
583 Of course, computations with long floats are more expensive than those
584 with smaller floating-point formats.
586 CLN does not implement features like NaNs, denormalized numbers and
587 gradual underflow. If the exponent range of some floating-point type
588 is too limited for your application, choose another floating-point type
589 with larger exponent range.
592 As a user of CLN, you can forget about the differences between the
593 four floating-point types and just declare all your floating-point
594 variables as being of type @code{cl_F}. This has the advantage that
595 when you change the precision of some computation (say, from @code{cl_DF}
596 to @code{cl_LF}), you don't have to change the code, only the precision
597 of the initial values. Also, many transcendental functions have been
598 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
599 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
600 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
601 the floating point contagion rule happened to change in the future.)
604 @section Complex numbers
605 @cindex complex number
607 Complex numbers, as implemented by the class @code{cl_N}, have a real
608 part and an imaginary part, both real numbers. A complex number whose
609 imaginary part is the exact number @code{0} is automatically converted
612 Complex numbers can arise from real numbers alone, for example
613 through application of @code{sqrt} or transcendental functions.
619 Conversions from any class to any its superclasses (``base classes'' in
620 C++ terminology) is done automatically.
622 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
623 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
624 @code{cl_N} and @code{cl_number}.
626 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
627 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
628 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
629 efficiency. On 32-bit systems, their range is therefore limited:
633 The conversion from @samp{int} works only if the argument is < 2^29 and >= -2^29.
635 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
638 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
639 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
640 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
641 in error on 32-bit machines.
642 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
643 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
644 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
645 @samp{cl_I}, first convert it to an @samp{unsigned long}. On 64-bit machines
646 there is no such restriction. There, conversions from arbitrary 32-bit @samp{int}
647 values always works correctly.
649 Conversions from the C built-in type @samp{float} are provided for the classes
650 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
652 Conversions from the C built-in type @samp{double} are provided for the classes
653 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
655 Conversions from @samp{const char *} are provided for the classes
656 @code{cl_I}, @code{cl_RA},
657 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
658 @code{cl_R}, @code{cl_N}.
659 The easiest way to specify a value which is outside of the range of the
660 C++ built-in types is therefore to specify it as a string, like this:
663 cl_I order_of_rubiks_cube_group = "43252003274489856000";
665 Note that this conversion is done at runtime, not at compile-time.
667 Conversions from @code{cl_I} to the C built-in types @samp{int},
668 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
672 @item int cl_I_to_int (const cl_I& x)
673 @cindex @code{cl_I_to_int ()}
674 @itemx unsigned int cl_I_to_uint (const cl_I& x)
675 @cindex @code{cl_I_to_uint ()}
676 @itemx long cl_I_to_long (const cl_I& x)
677 @cindex @code{cl_I_to_long ()}
678 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
679 @cindex @code{cl_I_to_ulong ()}
680 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
681 representable in the range of @var{ctype}, a runtime error occurs.
684 Conversions from the classes @code{cl_I}, @code{cl_RA},
685 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
687 to the C built-in types @samp{float} and @samp{double} are provided through
691 @item float float_approx (const @var{type}& x)
692 @cindex @code{float_approx ()}
693 @itemx double double_approx (const @var{type}& x)
694 @cindex @code{double_approx ()}
695 Returns an approximation of @code{x} of C type @var{ctype}.
696 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
697 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
700 Conversions from any class to any of its subclasses (``derived classes'' in
701 C++ terminology) are not provided. Instead, you can assert and check
702 that a value belongs to a certain subclass, and return it as element of that
703 class, using the @samp{As} and @samp{The} macros.
705 @cindex @code{As()()}
706 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
707 @var{type} and returns it as such.
708 @cindex @code{The()()}
709 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
710 @var{type} and returns it as such. It is your responsibility to ensure
711 that this assumption is valid. Since macros and namespaces don't go
712 together well, there is an equivalent to @samp{The}: the template
720 if (!(x >= 0)) abort();
721 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
722 // In general, it would be a rational number.
723 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
728 @chapter Functions on numbers
730 Each of the number classes declares its mathematical operations in the
731 corresponding include file. For example, if your code operates with
732 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
735 @section Constructing numbers
737 Here is how to create number objects ``from nothing''.
740 @subsection Constructing integers
742 @code{cl_I} objects are most easily constructed from C integers and from
743 strings. See @ref{Conversions}.
746 @subsection Constructing rational numbers
748 @code{cl_RA} objects can be constructed from strings. The syntax
749 for rational numbers is described in @ref{Internal and printed representation}.
750 Another standard way to produce a rational number is through application
751 of @samp{operator /} or @samp{recip} on integers.
754 @subsection Constructing floating-point numbers
756 @code{cl_F} objects with low precision are most easily constructed from
757 C @samp{float} and @samp{double}. See @ref{Conversions}.
759 To construct a @code{cl_F} with high precision, you can use the conversion
760 from @samp{const char *}, but you have to specify the desired precision
761 within the string. (See @ref{Internal and printed representation}.)
764 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
766 will set @samp{e} to the given value, with a precision of 40 decimal digits.
768 The programmatic way to construct a @code{cl_F} with high precision is
769 through the @code{cl_float} conversion function, see
770 @ref{Conversion to floating-point numbers}. For example, to compute
771 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
772 and then apply the exponential function:
774 float_format_t precision = float_format(40);
775 cl_F e = exp(cl_float(1,precision));
779 @subsection Constructing complex numbers
781 Non-real @code{cl_N} objects are normally constructed through the function
783 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
785 See @ref{Elementary complex functions}.
788 @section Elementary functions
790 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
791 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
792 defines the following operations:
795 @item @var{type} operator + (const @var{type}&, const @var{type}&)
796 @cindex @code{operator + ()}
799 @item @var{type} operator - (const @var{type}&, const @var{type}&)
800 @cindex @code{operator - ()}
803 @item @var{type} operator - (const @var{type}&)
804 Returns the negative of the argument.
806 @item @var{type} plus1 (const @var{type}& x)
807 @cindex @code{plus1 ()}
808 Returns @code{x + 1}.
810 @item @var{type} minus1 (const @var{type}& x)
811 @cindex @code{minus1 ()}
812 Returns @code{x - 1}.
814 @item @var{type} operator * (const @var{type}&, const @var{type}&)
815 @cindex @code{operator * ()}
818 @item @var{type} square (const @var{type}& x)
819 @cindex @code{square ()}
820 Returns @code{x * x}.
823 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
824 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
825 defines the following operations:
828 @item @var{type} operator / (const @var{type}&, const @var{type}&)
829 @cindex @code{operator / ()}
832 @item @var{type} recip (const @var{type}&)
833 @cindex @code{recip ()}
834 Returns the reciprocal of the argument.
837 The class @code{cl_I} doesn't define a @samp{/} operation because
838 in the C/C++ language this operator, applied to integral types,
839 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
840 is implementation dependent). (@xref{Rounding functions}.)
841 Instead, @code{cl_I} defines an ``exact quotient'' function:
844 @item cl_I exquo (const cl_I& x, const cl_I& y)
845 @cindex @code{exquo ()}
846 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
849 The following exponentiation functions are defined:
852 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
853 @cindex @code{expt_pos ()}
854 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
855 @code{y} must be > 0. Returns @code{x^y}.
857 @item cl_RA expt (const cl_RA& x, const cl_I& y)
858 @cindex @code{expt ()}
859 @itemx cl_R expt (const cl_R& x, const cl_I& y)
860 @itemx cl_N expt (const cl_N& x, const cl_I& y)
864 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
865 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
866 defines the following operation:
869 @item @var{type} abs (const @var{type}& x)
870 @cindex @code{abs ()}
871 Returns the absolute value of @code{x}.
872 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
875 The class @code{cl_N} implements this as follows:
878 @item cl_R abs (const cl_N x)
879 Returns the absolute value of @code{x}.
882 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
883 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
884 defines the following operation:
887 @item @var{type} signum (const @var{type}& x)
888 @cindex @code{signum ()}
889 Returns the sign of @code{x}, in the same number format as @code{x}.
890 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
891 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
896 @section Elementary rational functions
898 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
901 @item cl_I numerator (const @var{type}& x)
902 @cindex @code{numerator ()}
903 Returns the numerator of @code{x}.
905 @item cl_I denominator (const @var{type}& x)
906 @cindex @code{denominator ()}
907 Returns the denominator of @code{x}.
910 The numerator and denominator of a rational number are normalized in such
911 a way that they have no factor in common and the denominator is positive.
914 @section Elementary complex functions
916 The class @code{cl_N} defines the following operation:
919 @item cl_N complex (const cl_R& a, const cl_R& b)
920 @cindex @code{complex ()}
921 Returns the complex number @code{a+bi}, that is, the complex number with
922 real part @code{a} and imaginary part @code{b}.
925 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
928 @item cl_R realpart (const @var{type}& x)
929 @cindex @code{realpart ()}
930 Returns the real part of @code{x}.
932 @item cl_R imagpart (const @var{type}& x)
933 @cindex @code{imagpart ()}
934 Returns the imaginary part of @code{x}.
936 @item @var{type} conjugate (const @var{type}& x)
937 @cindex @code{conjugate ()}
938 Returns the complex conjugate of @code{x}.
941 We have the relations
945 @code{x = complex(realpart(x), imagpart(x))}
947 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
954 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
955 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
956 defines the following operations:
959 @item bool operator == (const @var{type}&, const @var{type}&)
960 @cindex @code{operator == ()}
961 @itemx bool operator != (const @var{type}&, const @var{type}&)
962 @cindex @code{operator != ()}
963 Comparison, as in C and C++.
965 @item uint32 equal_hashcode (const @var{type}&)
966 @cindex @code{equal_hashcode ()}
967 Returns a 32-bit hash code that is the same for any two numbers which are
968 the same according to @code{==}. This hash code depends on the number's value,
969 not its type or precision.
971 @item cl_boolean zerop (const @var{type}& x)
972 @cindex @code{zerop ()}
973 Compare against zero: @code{x == 0}
976 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
977 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
978 defines the following operations:
981 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
982 @cindex @code{compare ()}
983 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
984 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
986 @item bool operator <= (const @var{type}&, const @var{type}&)
987 @cindex @code{operator <= ()}
988 @itemx bool operator < (const @var{type}&, const @var{type}&)
989 @cindex @code{operator < ()}
990 @itemx bool operator >= (const @var{type}&, const @var{type}&)
991 @cindex @code{operator >= ()}
992 @itemx bool operator > (const @var{type}&, const @var{type}&)
993 @cindex @code{operator > ()}
994 Comparison, as in C and C++.
996 @item cl_boolean minusp (const @var{type}& x)
997 @cindex @code{minusp ()}
998 Compare against zero: @code{x < 0}
1000 @item cl_boolean plusp (const @var{type}& x)
1001 @cindex @code{plusp ()}
1002 Compare against zero: @code{x > 0}
1004 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1005 @cindex @code{max ()}
1006 Return the maximum of @code{x} and @code{y}.
1008 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1009 @cindex @code{min ()}
1010 Return the minimum of @code{x} and @code{y}.
1013 When a floating point number and a rational number are compared, the float
1014 is first converted to a rational number using the function @code{rational}.
1015 Since a floating point number actually represents an interval of real numbers,
1016 the result might be surprising.
1017 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1018 there is no floating point number whose value is exactly @code{1/3}.
1021 @section Rounding functions
1024 When a real number is to be converted to an integer, there is no ``best''
1025 rounding. The desired rounding function depends on the application.
1026 The Common Lisp and ISO Lisp standards offer four rounding functions:
1030 This is the largest integer <=@code{x}.
1033 This is the smallest integer >=@code{x}.
1036 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1039 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1040 integers, choose the even one.
1043 These functions have different advantages:
1045 @code{floor} and @code{ceiling} are translation invariant:
1046 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1047 for every @code{x} and every integer @code{n}.
1049 On the other hand, @code{truncate} and @code{round} are symmetric:
1050 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1051 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1052 down exactly as often as it rounds up.
1054 The functions are related like this:
1058 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1059 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1061 @code{truncate(x) = sign(x) * floor(abs(x))}
1064 Each of the classes @code{cl_R}, @code{cl_RA},
1065 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1066 defines the following operations:
1069 @item cl_I floor1 (const @var{type}& x)
1070 @cindex @code{floor1 ()}
1071 Returns @code{floor(x)}.
1072 @item cl_I ceiling1 (const @var{type}& x)
1073 @cindex @code{ceiling1 ()}
1074 Returns @code{ceiling(x)}.
1075 @item cl_I truncate1 (const @var{type}& x)
1076 @cindex @code{truncate1 ()}
1077 Returns @code{truncate(x)}.
1078 @item cl_I round1 (const @var{type}& x)
1079 @cindex @code{round1 ()}
1080 Returns @code{round(x)}.
1083 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1084 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1085 defines the following operations:
1088 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1089 Returns @code{floor(x/y)}.
1090 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1091 Returns @code{ceiling(x/y)}.
1092 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1093 Returns @code{truncate(x/y)}.
1094 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1095 Returns @code{round(x/y)}.
1098 These functions are called @samp{floor1}, @dots{} here instead of
1099 @samp{floor}, @dots{}, because on some systems, system dependent include
1100 files define @samp{floor} and @samp{ceiling} as macros.
1102 In many cases, one needs both the quotient and the remainder of a division.
1103 It is more efficient to compute both at the same time than to perform
1104 two divisions, one for quotient and the next one for the remainder.
1105 The following functions therefore return a structure containing both
1106 the quotient and the remainder. The suffix @samp{2} indicates the number
1107 of ``return values''. The remainder is defined as follows:
1111 for the computation of @code{quotient = floor(x)},
1112 @code{remainder = x - quotient},
1114 for the computation of @code{quotient = floor(x,y)},
1115 @code{remainder = x - quotient*y},
1118 and similarly for the other three operations.
1120 Each of the classes @code{cl_R}, @code{cl_RA},
1121 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1122 defines the following operations:
1125 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1126 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1127 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1128 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1129 @itemx @var{type}_div_t round2 (const @var{type}& x)
1132 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1133 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1134 defines the following operations:
1137 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1138 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1139 @cindex @code{floor2 ()}
1140 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1141 @cindex @code{ceiling2 ()}
1142 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1143 @cindex @code{truncate2 ()}
1144 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1145 @cindex @code{round2 ()}
1148 Sometimes, one wants the quotient as a floating-point number (of the
1149 same format as the argument, if the argument is a float) instead of as
1150 an integer. The prefix @samp{f} indicates this.
1153 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1154 defines the following operations:
1157 @item @var{type} ffloor (const @var{type}& x)
1158 @cindex @code{ffloor ()}
1159 @itemx @var{type} fceiling (const @var{type}& x)
1160 @cindex @code{fceiling ()}
1161 @itemx @var{type} ftruncate (const @var{type}& x)
1162 @cindex @code{ftruncate ()}
1163 @itemx @var{type} fround (const @var{type}& x)
1164 @cindex @code{fround ()}
1167 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1169 The class @code{cl_R} defines the following operations:
1172 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1173 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1174 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1175 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1178 These functions also exist in versions which return both the quotient
1179 and the remainder. The suffix @samp{2} indicates this.
1182 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1183 defines the following operations:
1184 @cindex @code{cl_F_fdiv_t}
1185 @cindex @code{cl_SF_fdiv_t}
1186 @cindex @code{cl_FF_fdiv_t}
1187 @cindex @code{cl_DF_fdiv_t}
1188 @cindex @code{cl_LF_fdiv_t}
1191 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1192 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1193 @cindex @code{ffloor2 ()}
1194 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1195 @cindex @code{fceiling2 ()}
1196 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1197 @cindex @code{ftruncate2 ()}
1198 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1199 @cindex @code{fround2 ()}
1201 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1202 @cindex @code{cl_R_fdiv_t}
1204 The class @code{cl_R} defines the following operations:
1207 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1208 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1209 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1210 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1211 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1214 Other applications need only the remainder of a division.
1215 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1216 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1217 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1221 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1223 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1226 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1227 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1228 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1230 The classes @code{cl_R}, @code{cl_I} define the following operations:
1233 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1234 @cindex @code{mod ()}
1235 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1236 @cindex @code{rem ()}
1242 Each of the classes @code{cl_R},
1243 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1244 defines the following operation:
1247 @item @var{type} sqrt (const @var{type}& x)
1248 @cindex @code{sqrt ()}
1249 @code{x} must be >= 0. This function returns the square root of @code{x},
1250 normalized to be >= 0. If @code{x} is the square of a rational number,
1251 @code{sqrt(x)} will be a rational number, else it will return a
1252 floating-point approximation.
1255 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1258 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1259 @cindex @code{sqrtp ()}
1260 This tests whether @code{x} is a perfect square. If so, it returns true
1261 and the exact square root in @code{*root}, else it returns false.
1264 Furthermore, for integers, similarly:
1267 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1268 @cindex @code{isqrt ()}
1269 @code{x} should be >= 0. This function sets @code{*root} to
1270 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1271 the boolean value @code{(expt(*root,2) == x)}.
1274 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1275 define the following operation:
1278 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1279 @cindex @code{rootp ()}
1280 @code{x} must be >= 0. @code{n} must be > 0.
1281 This tests whether @code{x} is an @code{n}th power of a rational number.
1282 If so, it returns true and the exact root in @code{*root}, else it returns
1286 The only square root function which accepts negative numbers is the one
1287 for class @code{cl_N}:
1290 @item cl_N sqrt (const cl_N& z)
1291 @cindex @code{sqrt ()}
1292 Returns the square root of @code{z}, as defined by the formula
1293 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1294 or to a complex number are done if necessary. The range of the result is the
1295 right half plane @code{realpart(sqrt(z)) >= 0}
1296 including the positive imaginary axis and 0, but excluding
1297 the negative imaginary axis.
1298 The result is an exact number only if @code{z} is an exact number.
1302 @section Transcendental functions
1303 @cindex transcendental functions
1305 The transcendental functions return an exact result if the argument
1306 is exact and the result is exact as well. Otherwise they must return
1307 inexact numbers even if the argument is exact.
1308 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1311 @subsection Exponential and logarithmic functions
1314 @item cl_R exp (const cl_R& x)
1315 @cindex @code{exp ()}
1316 @itemx cl_N exp (const cl_N& x)
1317 Returns the exponential function of @code{x}. This is @code{e^x} where
1318 @code{e} is the base of the natural logarithms. The range of the result
1319 is the entire complex plane excluding 0.
1321 @item cl_R ln (const cl_R& x)
1322 @cindex @code{ln ()}
1323 @code{x} must be > 0. Returns the (natural) logarithm of x.
1325 @item cl_N log (const cl_N& x)
1326 @cindex @code{log ()}
1327 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1328 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1329 The range of the result is the strip in the complex plane
1330 @code{-pi < imagpart(log(x)) <= pi}.
1332 @item cl_R phase (const cl_N& x)
1333 @cindex @code{phase ()}
1334 Returns the angle part of @code{x} in its polar representation as a
1335 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1336 This is also the imaginary part of @code{log(x)}.
1337 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1338 The result will be an exact number only if @code{zerop(x)} or
1339 if @code{x} is real and positive.
1341 @item cl_R log (const cl_R& a, const cl_R& b)
1342 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1343 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1344 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1347 @item cl_N log (const cl_N& a, const cl_N& b)
1348 Returns the logarithm of @code{a} with respect to base @code{b}.
1349 @code{log(a,b) = log(a)/log(b)}.
1351 @item cl_N expt (const cl_N& x, const cl_N& y)
1352 @cindex @code{expt ()}
1353 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1356 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1359 @item cl_F exp1 (float_format_t f)
1360 @cindex @code{exp1 ()}
1361 Returns e as a float of format @code{f}.
1363 @item cl_F exp1 (const cl_F& y)
1364 Returns e in the float format of @code{y}.
1366 @item cl_F exp1 (void)
1367 Returns e as a float of format @code{default_float_format}.
1371 @subsection Trigonometric functions
1374 @item cl_R sin (const cl_R& x)
1375 @cindex @code{sin ()}
1376 Returns @code{sin(x)}. The range of the result is the interval
1377 @code{-1 <= sin(x) <= 1}.
1379 @item cl_N sin (const cl_N& z)
1380 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1382 @item cl_R cos (const cl_R& x)
1383 @cindex @code{cos ()}
1384 Returns @code{cos(x)}. The range of the result is the interval
1385 @code{-1 <= cos(x) <= 1}.
1387 @item cl_N cos (const cl_N& x)
1388 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1390 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1391 @cindex @code{cos_sin_t}
1392 @itemx cos_sin_t cos_sin (const cl_R& x)
1393 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1394 @cindex @code{cos_sin ()}
1395 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1396 hold only approximately.
1398 @item cl_R tan (const cl_R& x)
1399 @cindex @code{tan ()}
1400 @itemx cl_N tan (const cl_N& x)
1401 Returns @code{tan(x) = sin(x)/cos(x)}.
1403 @item cl_N cis (const cl_R& x)
1404 @cindex @code{cis ()}
1405 @itemx cl_N cis (const cl_N& x)
1406 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1407 @code{e^(i*x) = cos(x) + i*sin(x)}.
1410 @cindex @code{asin ()}
1411 @item cl_N asin (const cl_N& z)
1412 Returns @code{arcsin(z)}. This is defined as
1413 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1414 @code{arcsin(-z) = -arcsin(z)}.
1415 The range of the result is the strip in the complex domain
1416 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1417 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1418 with @code{realpart = pi/2} and @code{imagpart > 0}.
1420 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1424 @item cl_N acos (const cl_N& z)
1425 @cindex @code{acos ()}
1426 Returns @code{arccos(z)}. This is defined as
1427 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1430 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1432 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1433 The range of the result is the strip in the complex domain
1434 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1435 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1436 with @code{realpart = pi} and @code{imagpart > 0}.
1438 Proof: This follows from the results about arcsin.
1442 @cindex @code{atan ()}
1443 @item cl_R atan (const cl_R& x, const cl_R& y)
1444 Returns the angle of the polar representation of the complex number
1445 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1446 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1447 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1448 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1449 with reversed order of arguments.
1451 @item cl_R atan (const cl_R& x)
1452 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1453 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1454 will be an exact number only if @code{x} is the exact @code{0}.
1456 @item cl_N atan (const cl_N& z)
1457 Returns @code{arctan(z)}. This is defined as
1458 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1459 @code{arctan(-z) = -arctan(z)}. The range of the result is
1460 the strip in the complex domain
1461 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1462 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1463 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1465 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1471 @cindex Archimedes' constant
1472 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1475 @item cl_F pi (float_format_t f)
1476 @cindex @code{pi ()}
1477 Returns pi as a float of format @code{f}.
1479 @item cl_F pi (const cl_F& y)
1480 Returns pi in the float format of @code{y}.
1482 @item cl_F pi (void)
1483 Returns pi as a float of format @code{default_float_format}.
1487 @subsection Hyperbolic functions
1490 @item cl_R sinh (const cl_R& x)
1491 @cindex @code{sinh ()}
1492 Returns @code{sinh(x)}.
1494 @item cl_N sinh (const cl_N& z)
1495 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1497 @item cl_R cosh (const cl_R& x)
1498 @cindex @code{cosh ()}
1499 Returns @code{cosh(x)}. The range of the result is the interval
1500 @code{cosh(x) >= 1}.
1502 @item cl_N cosh (const cl_N& z)
1503 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1505 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1506 @cindex @code{cosh_sinh_t}
1507 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1508 @cindex @code{cosh_sinh ()}
1509 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1510 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1511 hold only approximately.
1513 @item cl_R tanh (const cl_R& x)
1514 @cindex @code{tanh ()}
1515 @itemx cl_N tanh (const cl_N& x)
1516 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1518 @item cl_N asinh (const cl_N& z)
1519 @cindex @code{asinh ()}
1520 Returns @code{arsinh(z)}. This is defined as
1521 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1522 @code{arsinh(-z) = -arsinh(z)}.
1524 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1525 Actually, z+sqrt(1+z^2) can never be real and <0, so
1526 -pi < imagpart(arsinh(z)) < pi.
1527 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1528 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1530 The range of the result is the strip in the complex domain
1531 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1532 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1533 with @code{imagpart = pi/2} and @code{realpart < 0}.
1535 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1536 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1537 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1538 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1539 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1540 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1541 If y >= 1, the imagpart is pi/2 and the realpart is
1542 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1545 Moreover, if z is in Range(sqrt),
1546 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1547 (for a proof, see file src/cl_C_asinh.cc).
1550 @item cl_N acosh (const cl_N& z)
1551 @cindex @code{acosh ()}
1552 Returns @code{arcosh(z)}. This is defined as
1553 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1554 The range of the result is the half-strip in the complex domain
1555 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1556 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1558 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1559 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1560 If z is in Range(sqrt), we have
1561 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1562 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1564 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1565 and since the imagpart of both expressions is > -pi, <= pi
1566 ==> arcosh(z) = log(z+sqrt(z^2-1))
1567 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1568 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1569 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1570 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1571 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1573 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1574 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1575 = x^2 + y^2 + sqrt(u^2+v^2)
1580 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1581 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1582 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1583 Otherwise, -z is in Range(sqrt).
1584 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1585 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1586 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1587 and this has realpart > 0.
1588 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1589 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1590 has realpart = 0 and imagpart > 0.
1591 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1592 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1593 This has realpart >= 0 and imagpart = pi.
1596 @item cl_N atanh (const cl_N& z)
1597 @cindex @code{atanh ()}
1598 Returns @code{artanh(z)}. This is defined as
1599 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1600 @code{artanh(-z) = -artanh(z)}. The range of the result is
1601 the strip in the complex domain
1602 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1603 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1604 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1606 Proof: Write z = x+iy. Examine
1607 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1609 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1610 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1611 |x| < 1 ==> imagpart = 0
1614 = (atan(1+x,y) - atan(1-x,-y))/2
1615 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1616 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1617 > (pi - pi/2 - pi/2 )/2 = 0
1618 and (1+x)/y > (1-x)/y
1619 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1620 ==> imagpart < pi/2.
1621 Hence 0 < imagpart < pi/2.
1623 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1628 @subsection Euler gamma
1629 @cindex Euler's constant
1631 Euler's constant C = 0.577@dots{} is returned by the following functions:
1634 @item cl_F eulerconst (float_format_t f)
1635 @cindex @code{eulerconst ()}
1636 Returns Euler's constant as a float of format @code{f}.
1638 @item cl_F eulerconst (const cl_F& y)
1639 Returns Euler's constant in the float format of @code{y}.
1641 @item cl_F eulerconst (void)
1642 Returns Euler's constant as a float of format @code{default_float_format}.
1645 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1646 @cindex Catalan's constant
1649 @item cl_F catalanconst (float_format_t f)
1650 @cindex @code{catalanconst ()}
1651 Returns Catalan's constant as a float of format @code{f}.
1653 @item cl_F catalanconst (const cl_F& y)
1654 Returns Catalan's constant in the float format of @code{y}.
1656 @item cl_F catalanconst (void)
1657 Returns Catalan's constant as a float of format @code{default_float_format}.
1661 @subsection Riemann zeta
1662 @cindex Riemann's zeta
1664 Riemann's zeta function at an integral point @code{s>1} is returned by the
1665 following functions:
1668 @item cl_F zeta (int s, float_format_t f)
1669 @cindex @code{zeta ()}
1670 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1672 @item cl_F zeta (int s, const cl_F& y)
1673 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1675 @item cl_F zeta (int s)
1676 Returns Riemann's zeta function at @code{s} as a float of format
1677 @code{default_float_format}.
1681 @section Functions on integers
1683 @subsection Logical functions
1685 Integers, when viewed as in two's complement notation, can be thought as
1686 infinite bit strings where the bits' values eventually are constant.
1693 The logical operations view integers as such bit strings and operate
1694 on each of the bit positions in parallel.
1697 @item cl_I lognot (const cl_I& x)
1698 @cindex @code{lognot ()}
1699 @itemx cl_I operator ~ (const cl_I& x)
1700 @cindex @code{operator ~ ()}
1701 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1703 @item cl_I logand (const cl_I& x, const cl_I& y)
1704 @cindex @code{logand ()}
1705 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1706 @cindex @code{operator & ()}
1707 Logical and, like @code{x & y} in C.
1709 @item cl_I logior (const cl_I& x, const cl_I& y)
1710 @cindex @code{logior ()}
1711 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1712 @cindex @code{operator | ()}
1713 Logical (inclusive) or, like @code{x | y} in C.
1715 @item cl_I logxor (const cl_I& x, const cl_I& y)
1716 @cindex @code{logxor ()}
1717 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1718 @cindex @code{operator ^ ()}
1719 Exclusive or, like @code{x ^ y} in C.
1721 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1722 @cindex @code{logeqv ()}
1723 Bitwise equivalence, like @code{~(x ^ y)} in C.
1725 @item cl_I lognand (const cl_I& x, const cl_I& y)
1726 @cindex @code{lognand ()}
1727 Bitwise not and, like @code{~(x & y)} in C.
1729 @item cl_I lognor (const cl_I& x, const cl_I& y)
1730 @cindex @code{lognor ()}
1731 Bitwise not or, like @code{~(x | y)} in C.
1733 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1734 @cindex @code{logandc1 ()}
1735 Logical and, complementing the first argument, like @code{~x & y} in C.
1737 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1738 @cindex @code{logandc2 ()}
1739 Logical and, complementing the second argument, like @code{x & ~y} in C.
1741 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1742 @cindex @code{logorc1 ()}
1743 Logical or, complementing the first argument, like @code{~x | y} in C.
1745 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1746 @cindex @code{logorc2 ()}
1747 Logical or, complementing the second argument, like @code{x | ~y} in C.
1750 These operations are all available though the function
1752 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
1753 @cindex @code{boole ()}
1755 where @code{op} must have one of the 16 values (each one stands for a function
1756 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
1757 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
1758 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
1759 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
1760 @code{boole_orc1}, @code{boole_orc2}.
1761 @cindex @code{boole_clr}
1762 @cindex @code{boole_set}
1763 @cindex @code{boole_1}
1764 @cindex @code{boole_2}
1765 @cindex @code{boole_c1}
1766 @cindex @code{boole_c2}
1767 @cindex @code{boole_and}
1768 @cindex @code{boole_xor}
1769 @cindex @code{boole_eqv}
1770 @cindex @code{boole_nand}
1771 @cindex @code{boole_nor}
1772 @cindex @code{boole_andc1}
1773 @cindex @code{boole_andc2}
1774 @cindex @code{boole_orc1}
1775 @cindex @code{boole_orc2}
1778 Other functions that view integers as bit strings:
1781 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
1782 @cindex @code{logtest ()}
1783 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
1784 @code{logand(x,y) != 0}.
1786 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
1787 @cindex @code{logbitp ()}
1788 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
1789 Bit 0 is the least significant bit.
1791 @item uintC logcount (const cl_I& x)
1792 @cindex @code{logcount ()}
1793 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
1794 the number of zero bits in @code{x}, if @code{x} < 0.
1797 The following functions operate on intervals of bits in integers.
1800 struct cl_byte @{ uintC size; uintC position; @};
1802 @cindex @code{cl_byte}
1803 represents the bit interval containing the bits
1804 @code{position}@dots{}@code{position+size-1} of an integer.
1805 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
1808 @item cl_I ldb (const cl_I& n, const cl_byte& b)
1809 @cindex @code{ldb ()}
1810 extracts the bits of @code{n} described by the bit interval @code{b}
1811 and returns them as a nonnegative integer with @code{b.size} bits.
1813 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
1814 @cindex @code{ldb_test ()}
1815 Returns true if some bit described by the bit interval @code{b} is set in
1818 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1819 @cindex @code{dpb ()}
1820 Returns @code{n}, with the bits described by the bit interval @code{b}
1821 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
1822 @code{newbyte} are relevant.
1825 The functions @code{ldb} and @code{dpb} implicitly shift. The following
1826 functions are their counterparts without shifting:
1829 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
1830 @cindex @code{mask_field ()}
1831 returns an integer with the bits described by the bit interval @code{b}
1832 copied from the corresponding bits in @code{n}, the other bits zero.
1834 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1835 @cindex @code{deposit_field ()}
1836 returns an integer where the bits described by the bit interval @code{b}
1837 come from @code{newbyte} and the other bits come from @code{n}.
1840 The following relations hold:
1844 @code{ldb (n, b) = mask_field(n, b) >> b.position},
1846 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
1848 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
1851 The following operations on integers as bit strings are efficient shortcuts
1852 for common arithmetic operations:
1855 @item cl_boolean oddp (const cl_I& x)
1856 @cindex @code{oddp ()}
1857 Returns true if the least significant bit of @code{x} is 1. Equivalent to
1858 @code{mod(x,2) != 0}.
1860 @item cl_boolean evenp (const cl_I& x)
1861 @cindex @code{evenp ()}
1862 Returns true if the least significant bit of @code{x} is 0. Equivalent to
1863 @code{mod(x,2) == 0}.
1865 @item cl_I operator << (const cl_I& x, const cl_I& n)
1866 @cindex @code{operator << ()}
1867 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
1868 Equivalent to @code{x * expt(2,n)}.
1870 @item cl_I operator >> (const cl_I& x, const cl_I& n)
1871 @cindex @code{operator >> ()}
1872 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
1873 Bits shifted out to the right are thrown away.
1874 Equivalent to @code{floor(x / expt(2,n))}.
1876 @item cl_I ash (const cl_I& x, const cl_I& y)
1877 @cindex @code{ash ()}
1878 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
1879 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
1880 returns @code{floor(x * expt(2,y))}.
1882 @item uintC integer_length (const cl_I& x)
1883 @cindex @code{integer_length ()}
1884 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
1885 in two's complement notation. This is the smallest n >= 0 such that
1886 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
1889 @item uintC ord2 (const cl_I& x)
1890 @cindex @code{ord2 ()}
1891 @code{x} must be non-zero. This function returns the number of 0 bits at the
1892 right of @code{x} in two's complement notation. This is the largest n >= 0
1893 such that 2^n divides @code{x}.
1895 @item uintC power2p (const cl_I& x)
1896 @cindex @code{power2p ()}
1897 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
1898 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
1899 (See also the function @code{logp}.)
1903 @subsection Number theoretic functions
1906 @item uint32 gcd (unsigned long a, unsigned long b)
1907 @cindex @code{gcd ()}
1908 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
1909 This function returns the greatest common divisor of @code{a} and @code{b},
1910 normalized to be >= 0.
1912 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
1913 @cindex @code{xgcd ()}
1914 This function (``extended gcd'') returns the greatest common divisor @code{g} of
1915 @code{a} and @code{b} and at the same time the representation of @code{g}
1916 as an integral linear combination of @code{a} and @code{b}:
1917 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
1918 @code{u} and @code{v} will be normalized to be of smallest possible absolute
1919 value, in the following sense: If @code{a} and @code{b} are non-zero, and
1920 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
1921 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
1923 @item cl_I lcm (const cl_I& a, const cl_I& b)
1924 @cindex @code{lcm ()}
1925 This function returns the least common multiple of @code{a} and @code{b},
1926 normalized to be >= 0.
1928 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
1929 @cindex @code{logp ()}
1930 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
1931 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
1932 rational number, this function returns true and sets *l = log(a,b), else
1935 @item int jacobi (signed long a, signed long b)
1936 @cindex @code{jacobi()}
1937 @itemx int jacobi (const cl_I& a, const cl_I& b)
1938 Returns the Jacobi symbol
1940 $\left({a\over b}\right)$,
1945 @code{a,b} must be integers, @code{b>0} and odd. The result is 0
1948 @item cl_boolean isprobprime (const cl_I& n)
1950 @cindex @code{isprobprime()}
1951 Returns true if @code{n} is a small prime or passes the Miller-Rabin
1952 primality test. The probability of a false positive is 1:10^30.
1954 @item cl_I nextprobprime (const cl_R& x)
1955 @cindex @code{nextprobprime()}
1956 Returns the smallest probable prime >=@code{x}.
1960 @subsection Combinatorial functions
1963 @item cl_I factorial (uintL n)
1964 @cindex @code{factorial ()}
1965 @code{n} must be a small integer >= 0. This function returns the factorial
1966 @code{n}! = @code{1*2*@dots{}*n}.
1968 @item cl_I doublefactorial (uintL n)
1969 @cindex @code{doublefactorial ()}
1970 @code{n} must be a small integer >= 0. This function returns the
1971 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
1972 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
1974 @item cl_I binomial (uintL n, uintL k)
1975 @cindex @code{binomial ()}
1976 @code{n} and @code{k} must be small integers >= 0. This function returns the
1977 binomial coefficient
1979 ${n \choose k} = {n! \over n! (n-k)!}$
1982 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
1984 for 0 <= k <= n, 0 else.
1988 @section Functions on floating-point numbers
1990 Recall that a floating-point number consists of a sign @code{s}, an
1991 exponent @code{e} and a mantissa @code{m}. The value of the number is
1992 @code{(-1)^s * 2^e * m}.
1995 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1996 defines the following operations.
1999 @item @var{type} scale_float (const @var{type}& x, sintC delta)
2000 @cindex @code{scale_float ()}
2001 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2002 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2003 because it copies @code{x} and modifies the exponent.
2006 The following functions provide an abstract interface to the underlying
2007 representation of floating-point numbers.
2010 @item sintE float_exponent (const @var{type}& x)
2011 @cindex @code{float_exponent ()}
2012 Returns the exponent @code{e} of @code{x}.
2013 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2014 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2016 @item sintL float_radix (const @var{type}& x)
2017 @cindex @code{float_radix ()}
2018 Returns the base of the floating-point representation. This is always @code{2}.
2020 @item @var{type} float_sign (const @var{type}& x)
2021 @cindex @code{float_sign ()}
2022 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2023 @code{x} >= 0, -1 for @code{x} < 0.
2025 @item uintC float_digits (const @var{type}& x)
2026 @cindex @code{float_digits ()}
2027 Returns the number of mantissa bits in the floating-point representation
2028 of @code{x}, including the hidden bit. The value only depends on the type
2029 of @code{x}, not on its value.
2031 @item uintC float_precision (const @var{type}& x)
2032 @cindex @code{float_precision ()}
2033 Returns the number of significant mantissa bits in the floating-point
2034 representation of @code{x}. Since denormalized numbers are not supported,
2035 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2039 The complete internal representation of a float is encoded in the type
2040 @cindex @code{decoded_float}
2041 @cindex @code{decoded_sfloat}
2042 @cindex @code{decoded_ffloat}
2043 @cindex @code{decoded_dfloat}
2044 @cindex @code{decoded_lfloat}
2045 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2046 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2048 struct decoded_@var{type}float @{
2049 @var{type} mantissa; cl_I exponent; @var{type} sign;
2053 and returned by the function
2056 @item decoded_@var{type}float decode_float (const @var{type}& x)
2057 @cindex @code{decode_float ()}
2058 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2059 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2060 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2061 @code{e} is the same as returned by the function @code{float_exponent}.
2064 A complete decoding in terms of integers is provided as type
2065 @cindex @code{cl_idecoded_float}
2067 struct cl_idecoded_float @{
2068 cl_I mantissa; cl_I exponent; cl_I sign;
2071 by the following function:
2074 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2075 @cindex @code{integer_decode_float ()}
2076 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2077 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2078 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2079 WARNING: The exponent @code{e} is not the same as the one returned by
2080 the functions @code{decode_float} and @code{float_exponent}.
2083 Some other function, implemented only for class @code{cl_F}:
2086 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2087 @cindex @code{float_sign ()}
2088 This returns a floating point number whose precision and absolute value
2089 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2090 zero, it is treated as positive. Same for @code{y}.
2094 @section Conversion functions
2097 @subsection Conversion to floating-point numbers
2099 The type @code{float_format_t} describes a floating-point format.
2100 @cindex @code{float_format_t}
2103 @item float_format_t float_format (uintE n)
2104 @cindex @code{float_format ()}
2105 Returns the smallest float format which guarantees at least @code{n}
2106 decimal digits in the mantissa (after the decimal point).
2108 @item float_format_t float_format (const cl_F& x)
2109 Returns the floating point format of @code{x}.
2111 @item float_format_t default_float_format
2112 @cindex @code{default_float_format}
2113 Global variable: the default float format used when converting rational numbers
2117 To convert a real number to a float, each of the types
2118 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2119 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2120 defines the following operations:
2123 @item cl_F cl_float (const @var{type}&x, float_format_t f)
2124 @cindex @code{cl_float ()}
2125 Returns @code{x} as a float of format @code{f}.
2126 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2127 Returns @code{x} in the float format of @code{y}.
2128 @item cl_F cl_float (const @var{type}&x)
2129 Returns @code{x} as a float of format @code{default_float_format} if
2130 it is an exact number, or @code{x} itself if it is already a float.
2133 Of course, converting a number to a float can lose precision.
2135 Every floating-point format has some characteristic numbers:
2138 @item cl_F most_positive_float (float_format_t f)
2139 @cindex @code{most_positive_float ()}
2140 Returns the largest (most positive) floating point number in float format @code{f}.
2142 @item cl_F most_negative_float (float_format_t f)
2143 @cindex @code{most_negative_float ()}
2144 Returns the smallest (most negative) floating point number in float format @code{f}.
2146 @item cl_F least_positive_float (float_format_t f)
2147 @cindex @code{least_positive_float ()}
2148 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2149 in float format @code{f}.
2151 @item cl_F least_negative_float (float_format_t f)
2152 @cindex @code{least_negative_float ()}
2153 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2154 in float format @code{f}.
2156 @item cl_F float_epsilon (float_format_t f)
2157 @cindex @code{float_epsilon ()}
2158 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2160 @item cl_F float_negative_epsilon (float_format_t f)
2161 @cindex @code{float_negative_epsilon ()}
2162 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2166 @subsection Conversion to rational numbers
2168 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2169 defines the following operation:
2172 @item cl_RA rational (const @var{type}& x)
2173 @cindex @code{rational ()}
2174 Returns the value of @code{x} as an exact number. If @code{x} is already
2175 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2176 the value is a rational number whose denominator is a power of 2.
2179 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2183 @item cl_RA rationalize (const cl_R& x)
2184 @cindex @code{rationalize ()}
2185 If @code{x} is a floating-point number, it actually represents an interval
2186 of real numbers, and this function returns the rational number with
2187 smallest denominator (and smallest numerator, in magnitude)
2188 which lies in this interval.
2189 If @code{x} is already an exact number, this function returns @code{x}.
2192 If @code{x} is any float, one has
2196 @code{cl_float(rational(x),x) = x}
2198 @code{cl_float(rationalize(x),x) = x}
2202 @section Random number generators
2205 A random generator is a machine which produces (pseudo-)random numbers.
2206 The include file @code{<cln/random.h>} defines a class @code{random_state}
2207 which contains the state of a random generator. If you make a copy
2208 of the random number generator, the original one and the copy will produce
2209 the same sequence of random numbers.
2211 The following functions return (pseudo-)random numbers in different formats.
2212 Calling one of these modifies the state of the random number generator in
2213 a complicated but deterministic way.
2216 @cindex @code{random_state}
2217 @cindex @code{default_random_state}
2219 random_state default_random_state
2221 contains a default random number generator. It is used when the functions
2222 below are called without @code{random_state} argument.
2225 @item uint32 random32 (random_state& randomstate)
2226 @itemx uint32 random32 ()
2227 @cindex @code{random32 ()}
2228 Returns a random unsigned 32-bit number. All bits are equally random.
2230 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2231 @itemx cl_I random_I (const cl_I& n)
2232 @cindex @code{random_I ()}
2233 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2234 in the range @code{0 <= x < n}.
2236 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2237 @itemx cl_F random_F (const cl_F& n)
2238 @cindex @code{random_F ()}
2239 @code{n} must be a float > 0. This function returns a random floating-point
2240 number of the same format as @code{n} in the range @code{0 <= x < n}.
2242 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2243 @itemx cl_R random_R (const cl_R& n)
2244 @cindex @code{random_R ()}
2245 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2246 if @code{n} is a float.
2250 @section Obfuscating operators
2251 @cindex modifying operators
2253 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2254 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2255 are not available by default because their
2256 use tends to make programs unreadable. It is trivial to get away without
2257 them. However, if you feel that you absolutely need these operators
2258 to get happy, then add
2260 #define WANT_OBFUSCATING_OPERATORS
2262 @cindex @code{WANT_OBFUSCATING_OPERATORS}
2263 to the beginning of your source files, before the inclusion of any CLN
2264 include files. This flag will enable the following operators:
2266 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2267 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2270 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2271 @cindex @code{operator += ()}
2272 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2273 @cindex @code{operator -= ()}
2274 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2275 @cindex @code{operator *= ()}
2276 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2277 @cindex @code{operator /= ()}
2280 For the class @code{cl_I}:
2283 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2284 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2285 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2286 @itemx @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 <<= ()}
2294 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2295 @cindex @code{operator >>= ()}
2298 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2299 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2302 @item @var{type}& operator ++ (@var{type}& x)
2303 @cindex @code{operator ++ ()}
2304 The prefix operator @code{++x}.
2306 @item void operator ++ (@var{type}& x, int)
2307 The postfix operator @code{x++}.
2309 @item @var{type}& operator -- (@var{type}& x)
2310 @cindex @code{operator -- ()}
2311 The prefix operator @code{--x}.
2313 @item void operator -- (@var{type}& x, int)
2314 The postfix operator @code{x--}.
2317 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2318 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2322 @chapter Input/Output
2323 @cindex Input/Output
2325 @section Internal and printed representation
2326 @cindex representation
2328 All computations deal with the internal representations of the numbers.
2330 Every number has an external representation as a sequence of ASCII characters.
2331 Several external representations may denote the same number, for example,
2332 "20.0" and "20.000".
2334 Converting an internal to an external representation is called ``printing'',
2336 converting an external to an internal representation is called ``reading''.
2338 In CLN, it is always true that conversion of an internal to an external
2339 representation and then back to an internal representation will yield the
2340 same internal representation. Symbolically: @code{read(print(x)) == x}.
2341 This is called ``print-read consistency''.
2343 Different types of numbers have different external representations (case
2348 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2349 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2350 for decimal integers
2351 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2353 @item Rational numbers
2354 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2355 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2358 @item Floating-point numbers
2359 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2360 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2361 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2362 of the form _@var{prec} may be appended. There must be at least
2363 one digit in the non-exponent part. The exponent has the syntax
2364 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2365 The exponent marker is
2369 @samp{s} for short-floats,
2371 @samp{f} for single-floats,
2373 @samp{d} for double-floats,
2375 @samp{L} for long-floats,
2378 or @samp{e}, which denotes a default float format. The precision specifying
2379 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2380 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2381 function @samp{float_format}.
2383 @item Complex numbers
2384 External representation:
2387 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2388 if @var{imagpart} is negative, its printed representation begins with
2389 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2390 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2391 is rational and the rational number's base is >18, because the @samp{i}
2392 is then read as a digit.
2394 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2399 @section Input functions
2401 Including @code{<cln/io.h>} defines a number of simple input functions
2402 that read from @code{std::istream&}:
2405 @item int freadchar (std::istream& stream)
2406 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2407 if the end of stream was encountered or an error occurred.
2409 @item int funreadchar (std::istream& stream, int c)
2410 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2411 last @code{freadchar} operation on @code{stream}.
2414 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2415 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2416 defines, in @code{<cln/@var{type}_io.h>}, the following input function:
2419 @item std::istream& operator>> (std::istream& stream, @var{type}& result)
2420 Reads a number from @code{stream} and stores it in the @code{result}.
2423 The most flexible input functions, defined in @code{<cln/@var{type}_io.h>},
2427 @item cl_N read_complex (std::istream& stream, const cl_read_flags& flags)
2428 @itemx cl_R read_real (std::istream& stream, const cl_read_flags& flags)
2429 @itemx cl_F read_float (std::istream& stream, const cl_read_flags& flags)
2430 @itemx cl_RA read_rational (std::istream& stream, const cl_read_flags& flags)
2431 @itemx cl_I read_integer (std::istream& stream, const cl_read_flags& flags)
2432 Reads a number from @code{stream}. The @code{flags} are parameters which
2433 affect the input syntax. Whitespace before the number is silently skipped.
2435 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2436 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2437 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2438 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2439 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2440 Reads a number from a string in memory. The @code{flags} are parameters which
2441 affect the input syntax. The string starts at @code{string} and ends at
2442 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2443 @code{NULL}, denoting the entire string, i.e. equivalent to
2444 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2445 @code{NULL}, the string in memory must contain exactly one number and nothing
2446 more, else an exception will be thrown. If @code{end_of_parse}
2447 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2448 the last parsed character (i.e. @code{string_limit} if nothing came after
2449 the number). Whitespace is not allowed.
2452 The structure @code{cl_read_flags} contains the following fields:
2455 @item cl_read_syntax_t syntax
2456 The possible results of the read operation. Possible values are
2457 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2458 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2459 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2461 @item cl_read_lsyntax_t lsyntax
2462 Specifies the language-dependent syntax variant for the read operation.
2466 @item lsyntax_standard
2467 accept standard algebraic notation only, no complex numbers,
2468 @item lsyntax_algebraic
2469 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2470 @item lsyntax_commonlisp
2471 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2472 hexadecimal numbers,
2473 @code{#@var{base}R} for rational numbers in a given base,
2474 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2476 accept all of these extensions.
2479 @item unsigned int rational_base
2480 The base in which rational numbers are read.
2482 @item float_format_t float_flags.default_float_format
2483 The float format used when reading floats with exponent marker @samp{e}.
2485 @item float_format_t float_flags.default_lfloat_format
2486 The float format used when reading floats with exponent marker @samp{l}.
2488 @item cl_boolean float_flags.mantissa_dependent_float_format
2489 When this flag is true, floats specified with more digits than corresponding
2490 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2491 precision corresponding to their number of significant digits.
2495 @section Output functions
2497 Including @code{<cln/io.h>} defines a number of simple output functions
2498 that write to @code{std::ostream&}:
2501 @item void fprintchar (std::ostream& stream, char c)
2502 Prints the character @code{x} literally on the @code{stream}.
2504 @item void fprint (std::ostream& stream, const char * string)
2505 Prints the @code{string} literally on the @code{stream}.
2507 @item void fprintdecimal (std::ostream& stream, int x)
2508 @itemx void fprintdecimal (std::ostream& stream, const cl_I& x)
2509 Prints the integer @code{x} in decimal on the @code{stream}.
2511 @item void fprintbinary (std::ostream& stream, const cl_I& x)
2512 Prints the integer @code{x} in binary (base 2, without prefix)
2513 on the @code{stream}.
2515 @item void fprintoctal (std::ostream& stream, const cl_I& x)
2516 Prints the integer @code{x} in octal (base 8, without prefix)
2517 on the @code{stream}.
2519 @item void fprinthexadecimal (std::ostream& stream, const cl_I& x)
2520 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2521 on the @code{stream}.
2524 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2525 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2526 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2529 @item void fprint (std::ostream& stream, const @var{type}& x)
2530 @itemx std::ostream& operator<< (std::ostream& stream, const @var{type}& x)
2531 Prints the number @code{x} on the @code{stream}. The output may depend
2532 on the global printer settings in the variable @code{default_print_flags}.
2533 The @code{ostream} flags and settings (flags, width and locale) are
2537 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2540 void print_complex (std::ostream& stream, const cl_print_flags& flags,
2542 void print_real (std::ostream& stream, const cl_print_flags& flags,
2544 void print_float (std::ostream& stream, const cl_print_flags& flags,
2546 void print_rational (std::ostream& stream, const cl_print_flags& flags,
2548 void print_integer (std::ostream& stream, const cl_print_flags& flags,
2551 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2552 parameters which affect the output.
2554 The structure type @code{cl_print_flags} contains the following fields:
2557 @item unsigned int rational_base
2558 The base in which rational numbers are printed. Default is @code{10}.
2560 @item cl_boolean rational_readably
2561 If this flag is true, rational numbers are printed with radix specifiers in
2562 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2563 prefixes, trailing dot). Default is false.
2565 @item cl_boolean float_readably
2566 If this flag is true, type specific exponent markers have precedence over 'E'.
2569 @item float_format_t default_float_format
2570 Floating point numbers of this format will be printed using the 'E' exponent
2571 marker. Default is @code{float_format_ffloat}.
2573 @item cl_boolean complex_readably
2574 If this flag is true, complex numbers will be printed using the Common Lisp
2575 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2577 @item cl_string univpoly_varname
2578 Univariate polynomials with no explicit indeterminate name will be printed
2579 using this variable name. Default is @code{"x"}.
2582 The global variable @code{default_print_flags} contains the default values,
2583 used by the function @code{fprint}.
2588 CLN has a class of abstract rings.
2596 Rings can be compared for equality:
2599 @item bool operator== (const cl_ring&, const cl_ring&)
2600 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2601 These compare two rings for equality.
2604 Given a ring @code{R}, the following members can be used.
2607 @item void R->fprint (std::ostream& stream, const cl_ring_element& x)
2608 @cindex @code{fprint ()}
2609 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2610 @cindex @code{equal ()}
2611 @itemx cl_ring_element R->zero ()
2612 @cindex @code{zero ()}
2613 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2614 @cindex @code{zerop ()}
2615 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2616 @cindex @code{plus ()}
2617 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2618 @cindex @code{minus ()}
2619 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2620 @cindex @code{uminus ()}
2621 @itemx cl_ring_element R->one ()
2622 @cindex @code{one ()}
2623 @itemx cl_ring_element R->canonhom (const cl_I& x)
2624 @cindex @code{canonhom ()}
2625 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2626 @cindex @code{mul ()}
2627 @itemx cl_ring_element R->square (const cl_ring_element& x)
2628 @cindex @code{square ()}
2629 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2630 @cindex @code{expt_pos ()}
2633 The following rings are built-in.
2636 @item cl_null_ring cl_0_ring
2637 The null ring, containing only zero.
2639 @item cl_complex_ring cl_C_ring
2640 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2642 @item cl_real_ring cl_R_ring
2643 The ring of real numbers. This corresponds to the type @code{cl_R}.
2645 @item cl_rational_ring cl_RA_ring
2646 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2648 @item cl_integer_ring cl_I_ring
2649 The ring of integers. This corresponds to the type @code{cl_I}.
2652 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2653 @code{cl_RA_ring}, @code{cl_I_ring}:
2656 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2657 @cindex @code{instanceof ()}
2658 Tests whether the given number is an element of the number ring R.
2662 @chapter Modular integers
2663 @cindex modular integer
2665 @section Modular integer rings
2668 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2669 The modulus is explicitly part of every modular integer. CLN doesn't
2670 allow you to (accidentally) mix elements of different modular rings,
2671 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2672 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2673 doesn't have generic types. So one has to live with runtime checks.)
2675 The class of modular integer rings is
2683 Modular integer ring
2687 @cindex @code{cl_modint_ring}
2689 and the class of all modular integers (elements of modular integer rings) is
2697 Modular integer rings are constructed using the function
2700 @item cl_modint_ring find_modint_ring (const cl_I& N)
2701 @cindex @code{find_modint_ring ()}
2702 This function returns the modular ring @samp{Z/NZ}. It takes care
2703 of finding out about special cases of @code{N}, like powers of two
2704 and odd numbers for which Montgomery multiplication will be a win,
2705 @cindex Montgomery multiplication
2706 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2707 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2708 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2712 Modular integer rings can be compared for equality:
2715 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2716 @cindex @code{operator == ()}
2717 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2718 @cindex @code{operator != ()}
2719 These compare two modular integer rings for equality. Two different calls
2720 to @code{find_modint_ring} with the same argument necessarily return the
2721 same ring because it is memoized in the cache table.
2724 @section Functions on modular integers
2726 Given a modular integer ring @code{R}, the following members can be used.
2729 @item cl_I R->modulus
2730 @cindex @code{modulus}
2731 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2733 @item cl_MI R->zero()
2734 @cindex @code{zero ()}
2735 This returns @code{0 mod N}.
2737 @item cl_MI R->one()
2738 @cindex @code{one ()}
2739 This returns @code{1 mod N}.
2741 @item cl_MI R->canonhom (const cl_I& x)
2742 @cindex @code{canonhom ()}
2743 This returns @code{x mod N}.
2745 @item cl_I R->retract (const cl_MI& x)
2746 @cindex @code{retract ()}
2747 This is a partial inverse function to @code{R->canonhom}. It returns the
2748 standard representative (@code{>=0}, @code{<N}) of @code{x}.
2750 @item cl_MI R->random(random_state& randomstate)
2751 @itemx cl_MI R->random()
2752 @cindex @code{random ()}
2753 This returns a random integer modulo @code{N}.
2756 The following operations are defined on modular integers.
2759 @item cl_modint_ring x.ring ()
2760 @cindex @code{ring ()}
2761 Returns the ring to which the modular integer @code{x} belongs.
2763 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
2764 @cindex @code{operator + ()}
2765 Returns the sum of two modular integers. One of the arguments may also
2768 @item cl_MI operator- (const cl_MI&, const cl_MI&)
2769 @cindex @code{operator - ()}
2770 Returns the difference of two modular integers. One of the arguments may also
2773 @item cl_MI operator- (const cl_MI&)
2774 Returns the negative of a modular integer.
2776 @item cl_MI operator* (const cl_MI&, const cl_MI&)
2777 @cindex @code{operator * ()}
2778 Returns the product of two modular integers. One of the arguments may also
2781 @item cl_MI square (const cl_MI&)
2782 @cindex @code{square ()}
2783 Returns the square of a modular integer.
2785 @item cl_MI recip (const cl_MI& x)
2786 @cindex @code{recip ()}
2787 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
2788 must be coprime to the modulus, otherwise an error message is issued.
2790 @item cl_MI div (const cl_MI& x, const cl_MI& y)
2791 @cindex @code{div ()}
2792 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
2793 @code{y} must be coprime to the modulus, otherwise an error message is issued.
2795 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
2796 @cindex @code{expt_pos ()}
2797 @code{y} must be > 0. Returns @code{x^y}.
2799 @item cl_MI expt (const cl_MI& x, const cl_I& y)
2800 @cindex @code{expt ()}
2801 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
2802 modulus, else an error message is issued.
2804 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
2805 @cindex @code{operator << ()}
2806 Returns @code{x*2^y}.
2808 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
2809 @cindex @code{operator >> ()}
2810 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
2811 or an error message is issued.
2813 @item bool operator== (const cl_MI&, const cl_MI&)
2814 @cindex @code{operator == ()}
2815 @itemx bool operator!= (const cl_MI&, const cl_MI&)
2816 @cindex @code{operator != ()}
2817 Compares two modular integers, belonging to the same modular integer ring,
2820 @item cl_boolean zerop (const cl_MI& x)
2821 @cindex @code{zerop ()}
2822 Returns true if @code{x} is @code{0 mod N}.
2825 The following output functions are defined (see also the chapter on
2829 @item void fprint (std::ostream& stream, const cl_MI& x)
2830 @cindex @code{fprint ()}
2831 @itemx std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
2832 @cindex @code{operator << ()}
2833 Prints the modular integer @code{x} on the @code{stream}. The output may depend
2834 on the global printer settings in the variable @code{default_print_flags}.
2838 @chapter Symbolic data types
2839 @cindex symbolic type
2841 CLN implements two symbolic (non-numeric) data types: strings and symbols.
2845 @cindex @code{cl_string}
2855 implements immutable strings.
2857 Strings are constructed through the following constructors:
2860 @item cl_string (const char * s)
2861 Returns an immutable copy of the (zero-terminated) C string @code{s}.
2863 @item cl_string (const char * ptr, unsigned long len)
2864 Returns an immutable copy of the @code{len} characters at
2865 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
2868 The following functions are available on strings:
2872 Assignment from @code{cl_string} and @code{const char *}.
2875 @cindex @code{length ()}
2877 @cindex @code{strlen ()}
2878 Returns the length of the string @code{s}.
2881 @cindex @code{operator [] ()}
2882 Returns the @code{i}th character of the string @code{s}.
2883 @code{i} must be in the range @code{0 <= i < s.length()}.
2885 @item bool equal (const cl_string& s1, const cl_string& s2)
2886 @cindex @code{equal ()}
2887 Compares two strings for equality. One of the arguments may also be a
2888 plain @code{const char *}.
2893 @cindex @code{cl_symbol}
2895 Symbols are uniquified strings: all symbols with the same name are shared.
2896 This means that comparison of two symbols is fast (effectively just a pointer
2897 comparison), whereas comparison of two strings must in the worst case walk
2898 both strings until their end.
2899 Symbols are used, for example, as tags for properties, as names of variables
2900 in polynomial rings, etc.
2902 Symbols are constructed through the following constructor:
2905 @item cl_symbol (const cl_string& s)
2906 Looks up or creates a new symbol with a given name.
2909 The following operations are available on symbols:
2912 @item cl_string (const cl_symbol& sym)
2913 Conversion to @code{cl_string}: Returns the string which names the symbol
2916 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
2917 @cindex @code{equal ()}
2918 Compares two symbols for equality. This is very fast.
2922 @chapter Univariate polynomials
2924 @cindex univariate polynomial
2926 @section Univariate polynomial rings
2928 CLN implements univariate polynomials (polynomials in one variable) over an
2929 arbitrary ring. The indeterminate variable may be either unnamed (and will be
2930 printed according to @code{default_print_flags.univpoly_varname}, which
2931 defaults to @samp{x}) or carry a given name. The base ring and the
2932 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
2933 (accidentally) mix elements of different polynomial rings, e.g.
2934 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
2935 return a multivariate polynomial, but they are not yet implemented in CLN.)
2937 The classes of univariate polynomial rings are
2945 Univariate polynomial ring
2949 +----------------+-------------------+
2951 Complex polynomial ring | Modular integer polynomial ring
2952 cl_univpoly_complex_ring | cl_univpoly_modint_ring
2953 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
2957 Real polynomial ring |
2958 cl_univpoly_real_ring |
2959 <cln/univpoly_real.h> |
2963 Rational polynomial ring |
2964 cl_univpoly_rational_ring |
2965 <cln/univpoly_rational.h> |
2969 Integer polynomial ring
2970 cl_univpoly_integer_ring
2971 <cln/univpoly_integer.h>
2974 and the corresponding classes of univariate polynomials are
2977 Univariate polynomial
2981 +----------------+-------------------+
2983 Complex polynomial | Modular integer polynomial
2985 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
2991 <cln/univpoly_real.h> |
2995 Rational polynomial |
2997 <cln/univpoly_rational.h> |
3003 <cln/univpoly_integer.h>
3006 Univariate polynomial rings are constructed using the functions
3009 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3010 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3011 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3012 @code{R} may be an arbitrary ring. This function takes care of finding out
3013 about special cases of @code{R}, such as the rings of complex numbers,
3014 real numbers, rational numbers, integers, or modular integer rings.
3015 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3016 This ensures that two calls of this function with the same arguments will
3017 return the same polynomial ring.
3019 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3020 @cindex @code{find_univpoly_ring ()}
3021 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3022 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3023 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3024 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3025 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3026 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3027 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3028 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3029 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3030 These functions are equivalent to the general @code{find_univpoly_ring},
3031 only the return type is more specific, according to the base ring's type.
3034 @section Functions on univariate polynomials
3036 Given a univariate polynomial ring @code{R}, the following members can be used.
3039 @item cl_ring R->basering()
3040 @cindex @code{basering ()}
3041 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3043 @item cl_UP R->zero()
3044 @cindex @code{zero ()}
3045 This returns @code{0 in R}, a polynomial of degree -1.
3047 @item cl_UP R->one()
3048 @cindex @code{one ()}
3049 This returns @code{1 in R}, a polynomial of degree == 0.
3051 @item cl_UP R->canonhom (const cl_I& x)
3052 @cindex @code{canonhom ()}
3053 This returns @code{x in R}, a polynomial of degree <= 0.
3055 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3056 @cindex @code{monomial ()}
3057 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3060 @item cl_UP R->create (sintL degree)
3061 @cindex @code{create ()}
3062 Creates a new polynomial with a given degree. The zero polynomial has degree
3063 @code{-1}. After creating the polynomial, you should put in the coefficients,
3064 using the @code{set_coeff} member function, and then call the @code{finalize}
3068 The following are the only destructive operations on univariate polynomials.
3071 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3072 @cindex @code{set_coeff ()}
3073 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3074 After changing a polynomial and before applying any "normal" operation on it,
3075 you should call its @code{finalize} member function.
3077 @item void finalize (cl_UP& x)
3078 @cindex @code{finalize ()}
3079 This function marks the endpoint of destructive modifications of a polynomial.
3080 It normalizes the internal representation so that subsequent computations have
3081 less overhead. Doing normal computations on unnormalized polynomials may
3082 produce wrong results or crash the program.
3085 The following operations are defined on univariate polynomials.
3088 @item cl_univpoly_ring x.ring ()
3089 @cindex @code{ring ()}
3090 Returns the ring to which the univariate polynomial @code{x} belongs.
3092 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3093 @cindex @code{operator + ()}
3094 Returns the sum of two univariate polynomials.
3096 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3097 @cindex @code{operator - ()}
3098 Returns the difference of two univariate polynomials.
3100 @item cl_UP operator- (const cl_UP&)
3101 Returns the negative of a univariate polynomial.
3103 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3104 @cindex @code{operator * ()}
3105 Returns the product of two univariate polynomials. One of the arguments may
3106 also be a plain integer or an element of the base ring.
3108 @item cl_UP square (const cl_UP&)
3109 @cindex @code{square ()}
3110 Returns the square of a univariate polynomial.
3112 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3113 @cindex @code{expt_pos ()}
3114 @code{y} must be > 0. Returns @code{x^y}.
3116 @item bool operator== (const cl_UP&, const cl_UP&)
3117 @cindex @code{operator == ()}
3118 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3119 @cindex @code{operator != ()}
3120 Compares two univariate polynomials, belonging to the same univariate
3121 polynomial ring, for equality.
3123 @item cl_boolean zerop (const cl_UP& x)
3124 @cindex @code{zerop ()}
3125 Returns true if @code{x} is @code{0 in R}.
3127 @item sintL degree (const cl_UP& x)
3128 @cindex @code{degree ()}
3129 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3131 @item sintL ldegree (const cl_UP& x)
3132 @cindex @code{degree ()}
3133 Returns the low degree of the polynomial. This is the degree of the first
3134 non-vanishing polynomial coefficient. The zero polynomial has ldegree @code{-1}.
3136 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3137 @cindex @code{coeff ()}
3138 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3140 @item cl_ring_element x (const cl_ring_element& y)
3141 @cindex @code{operator () ()}
3142 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3143 then @samp{x(y)} returns the value of the substitution of @code{y} into
3146 @item cl_UP deriv (const cl_UP& x)
3147 @cindex @code{deriv ()}
3148 Returns the derivative of the polynomial @code{x} with respect to the
3149 indeterminate @code{X}.
3152 The following output functions are defined (see also the chapter on
3156 @item void fprint (std::ostream& stream, const cl_UP& x)
3157 @cindex @code{fprint ()}
3158 @itemx std::ostream& operator<< (std::ostream& stream, const cl_UP& x)
3159 @cindex @code{operator << ()}
3160 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3161 depend on the global printer settings in the variable
3162 @code{default_print_flags}.
3165 @section Special polynomials
3167 The following functions return special polynomials.
3170 @item cl_UP_I tschebychev (sintL n)
3171 @cindex @code{tschebychev ()}
3172 @cindex Chebyshev polynomial
3173 Returns the n-th Chebyshev polynomial (n >= 0).
3175 @item cl_UP_I hermite (sintL n)
3176 @cindex @code{hermite ()}
3177 @cindex Hermite polynomial
3178 Returns the n-th Hermite polynomial (n >= 0).
3180 @item cl_UP_RA legendre (sintL n)
3181 @cindex @code{legendre ()}
3182 @cindex Legende polynomial
3183 Returns the n-th Legendre polynomial (n >= 0).
3185 @item cl_UP_I laguerre (sintL n)
3186 @cindex @code{laguerre ()}
3187 @cindex Laguerre polynomial
3188 Returns the n-th Laguerre polynomial (n >= 0).
3191 Information how to derive the differential equation satisfied by each
3192 of these polynomials from their definition can be found in the
3193 @code{doc/polynomial/} directory.
3201 Using C++ as an implementation language provides
3205 Efficiency: It compiles to machine code.
3209 Portability: It runs on all platforms supporting a C++ compiler. Because
3210 of the availability of GNU C++, this includes all currently used 32-bit and
3211 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3214 Type safety: The C++ compilers knows about the number types and complains if,
3215 for example, you try to assign a float to an integer variable. However,
3216 a drawback is that C++ doesn't know about generic types, hence a restriction
3217 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3218 arguments belong to the same modular ring cannot be expressed as a compile-time
3222 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3223 @code{=}, @code{==}, ... can be used in infix notation, which is more
3224 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3227 With these language features, there is no need for two separate languages,
3228 one for the implementation of the library and one in which the library's users
3229 can program. This means that a prototype implementation of an algorithm
3230 can be integrated into the library immediately after it has been tested and
3231 debugged. No need to rewrite it in a low-level language after having prototyped
3232 in a high-level language.
3235 @section Memory efficiency
3237 In order to save memory allocations, CLN implements:
3241 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3244 @cindex garbage collection
3245 @cindex reference counting
3246 Garbage collection: A reference counting mechanism makes sure that any
3247 number object's storage is freed immediately when the last reference to the
3250 @cindex immediate numbers
3251 Small integers are represented as immediate values instead of pointers
3252 to heap allocated storage. This means that integers @code{>= -2^29},
3253 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3258 @section Speed efficiency
3260 Speed efficiency is obtained by the combination of the following tricks
3265 Small integers, being represented as immediate values, don't require
3266 memory access, just a couple of instructions for each elementary operation.
3268 The kernel of CLN has been written in assembly language for some CPUs
3269 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3271 On all CPUs, CLN may be configured to use the superefficient low-level
3272 routines from GNU GMP version 3.
3274 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3275 algorithm, the Karatsuba multiplication, which is an
3286 For very large numbers (more than 12000 decimal digits), CLN uses
3288 Sch{@"o}nhage-Strassen
3289 @cindex Sch{@"o}nhage-Strassen multiplication
3293 @cindex Schnhage-Strassen multiplication
3295 multiplication, which is an asymptotically optimal multiplication
3298 These fast multiplication algorithms also give improvements in the speed
3299 of division and radix conversion.
3303 @section Garbage collection
3304 @cindex garbage collection
3306 All the number classes are reference count classes: They only contain a pointer
3307 to an object in the heap. Upon construction, assignment and destruction of
3308 number objects, only the objects' reference count are manipulated.
3310 Memory occupied by number objects are automatically reclaimed as soon as
3311 their reference count drops to zero.
3313 For number rings, another strategy is implemented: There is a cache of,
3314 for example, the modular integer rings. A modular integer ring is destroyed
3315 only if its reference count dropped to zero and the cache is about to be
3316 resized. The effect of this strategy is that recently used rings remain
3317 cached, whereas undue memory consumption through cached rings is avoided.
3320 @chapter Using the library
3322 For the following discussion, we will assume that you have installed
3323 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3324 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3325 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3326 environment variables, or directly substitute the appropriate values.
3329 @section Compiler options
3330 @cindex compiler options
3332 Until you have installed CLN in a public place, the following options are
3335 When you compile CLN application code, add the flags
3337 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3339 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3340 When you link CLN application code to form an executable, add the flags
3342 $CLN_TARGETDIR/src/libcln.a
3344 to the C/C++ compiler's command line (@code{make} variable LIBS).
3346 If you did a @code{make install}, the include files are installed in a
3347 public directory (normally @code{/usr/local/include}), hence you don't
3348 need special flags for compiling. The library has been installed to a
3349 public directory as well (normally @code{/usr/local/lib}), hence when
3350 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3352 @cindex @code{pkg-config}
3353 To make the creation of software packages that use CLN easier, the
3354 @code{pkg-config} utility can be used. CLN provides all the necessary
3355 metainformation in a file called @code{cln.pc} (installed in
3356 @code{/usr/local/lib/pkgconfig} by default). A program using CLN can
3357 be compiled and linked using @footnote{If you installed CLN to
3358 non-standard location @var{prefix}, you need to set the
3359 @env{PKG_CONFIG_PATH} environment variable to @var{prefix}/lib/pkgconfig
3362 g++ `pkg-config --libs cln` `pkg-config --cflags cln` prog.cc -o prog
3365 Software using GNU autoconf can check for CLN with the
3366 @code{PKG_CHECK_MODULES} macro supplied with @code{pkg-config}.
3368 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}])
3370 This will check for CLN version at least @var{MIN-VERSION}. If the
3371 required version was found, the variables @var{CLN_CFLAGS} and
3372 @var{CLN_LIBS} are set. Otherwise the configure script aborts. If this
3373 is not the desired behaviour, use the following code instead
3374 @footnote{See the @code{pkg-config} documentation for more details.}
3376 PKG_CHECK_MODULES([CLN], [cln >= @var{MIN-VERSION}], [],
3377 [AC_MSG_WARNING([No suitable version of CLN can be found])])
3381 @section Include files
3382 @cindex include files
3383 @cindex header files
3385 Here is a summary of the include files and their contents.
3388 @item <cln/object.h>
3389 General definitions, reference counting, garbage collection.
3390 @item <cln/number.h>
3391 The class cl_number.
3392 @item <cln/complex.h>
3393 Functions for class cl_N, the complex numbers.
3395 Functions for class cl_R, the real numbers.
3397 Functions for class cl_F, the floats.
3398 @item <cln/sfloat.h>
3399 Functions for class cl_SF, the short-floats.
3400 @item <cln/ffloat.h>
3401 Functions for class cl_FF, the single-floats.
3402 @item <cln/dfloat.h>
3403 Functions for class cl_DF, the double-floats.
3404 @item <cln/lfloat.h>
3405 Functions for class cl_LF, the long-floats.
3406 @item <cln/rational.h>
3407 Functions for class cl_RA, the rational numbers.
3408 @item <cln/integer.h>
3409 Functions for class cl_I, the integers.
3412 @item <cln/complex_io.h>
3413 Input/Output for class cl_N, the complex numbers.
3414 @item <cln/real_io.h>
3415 Input/Output for class cl_R, the real numbers.
3416 @item <cln/float_io.h>
3417 Input/Output for class cl_F, the floats.
3418 @item <cln/sfloat_io.h>
3419 Input/Output for class cl_SF, the short-floats.
3420 @item <cln/ffloat_io.h>
3421 Input/Output for class cl_FF, the single-floats.
3422 @item <cln/dfloat_io.h>
3423 Input/Output for class cl_DF, the double-floats.
3424 @item <cln/lfloat_io.h>
3425 Input/Output for class cl_LF, the long-floats.
3426 @item <cln/rational_io.h>
3427 Input/Output for class cl_RA, the rational numbers.
3428 @item <cln/integer_io.h>
3429 Input/Output for class cl_I, the integers.
3431 Flags for customizing input operations.
3432 @item <cln/output.h>
3433 Flags for customizing output operations.
3434 @item <cln/malloc.h>
3435 @code{malloc_hook}, @code{free_hook}.
3436 @item <cln/exception.h>
3437 Exception base class.
3438 @item <cln/condition.h>
3440 @item <cln/string.h>
3442 @item <cln/symbol.h>
3444 @item <cln/proplist.h>
3448 @item <cln/null_ring.h>
3450 @item <cln/complex_ring.h>
3451 The ring of complex numbers.
3452 @item <cln/real_ring.h>
3453 The ring of real numbers.
3454 @item <cln/rational_ring.h>
3455 The ring of rational numbers.
3456 @item <cln/integer_ring.h>
3457 The ring of integers.
3458 @item <cln/numtheory.h>
3459 Number threory functions.
3460 @item <cln/modinteger.h>
3466 @item <cln/GV_number.h>
3467 General vectors over cl_number.
3468 @item <cln/GV_complex.h>
3469 General vectors over cl_N.
3470 @item <cln/GV_real.h>
3471 General vectors over cl_R.
3472 @item <cln/GV_rational.h>
3473 General vectors over cl_RA.
3474 @item <cln/GV_integer.h>
3475 General vectors over cl_I.
3476 @item <cln/GV_modinteger.h>
3477 General vectors of modular integers.
3480 @item <cln/SV_number.h>
3481 Simple vectors over cl_number.
3482 @item <cln/SV_complex.h>
3483 Simple vectors over cl_N.
3484 @item <cln/SV_real.h>
3485 Simple vectors over cl_R.
3486 @item <cln/SV_rational.h>
3487 Simple vectors over cl_RA.
3488 @item <cln/SV_integer.h>
3489 Simple vectors over cl_I.
3490 @item <cln/SV_ringelt.h>
3491 Simple vectors of general ring elements.
3492 @item <cln/univpoly.h>
3493 Univariate polynomials.
3494 @item <cln/univpoly_integer.h>
3495 Univariate polynomials over the integers.
3496 @item <cln/univpoly_rational.h>
3497 Univariate polynomials over the rational numbers.
3498 @item <cln/univpoly_real.h>
3499 Univariate polynomials over the real numbers.
3500 @item <cln/univpoly_complex.h>
3501 Univariate polynomials over the complex numbers.
3502 @item <cln/univpoly_modint.h>
3503 Univariate polynomials over modular integer rings.
3504 @item <cln/timing.h>
3507 Includes all of the above.
3513 A function which computes the nth Fibonacci number can be written as follows.
3514 @cindex Fibonacci number
3517 #include <cln/integer.h>
3518 #include <cln/real.h>
3519 using namespace cln;
3521 // Returns F_n, computed as the nearest integer to
3522 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3523 const cl_I fibonacci (int n)
3525 // Need a precision of ((1+sqrt(5))/2)^-n.
3526 float_format_t prec = float_format((int)(0.208987641*n+5));
3527 cl_R sqrt5 = sqrt(cl_float(5,prec));
3528 cl_R phi = (1+sqrt5)/2;
3529 return round1( expt(phi,n)/sqrt5 );
3533 Let's explain what is going on in detail.
3535 The include file @code{<cln/integer.h>} is necessary because the type
3536 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3537 is needed for the type @code{cl_R} and the floating point number functions.
3538 The order of the include files does not matter. In order not to write
3539 out @code{cln::}@var{foo} in this simple example we can safely import
3540 the whole namespace @code{cln}.
3542 Then comes the function declaration. The argument is an @code{int}, the
3543 result an integer. The return type is defined as @samp{const cl_I}, not
3544 simply @samp{cl_I}, because that allows the compiler to detect typos like
3545 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3546 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3547 number). We use the most specialized possible return type because functions
3548 which call @samp{fibonacci} will be able to profit from the compiler's type
3549 analysis: Adding two integers is slightly more efficient than adding the
3550 same objects declared as complex numbers, because it needs less type
3551 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3552 the size of the resulting executable program.
3554 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3555 integer. In order to get a correct result, the absolute error should be less
3556 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3557 To this end, the first line computes a floating point precision for sqrt(5)
3560 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3561 number and than taking the square root. The converse, first taking the square
3562 root of 5, and then converting to the desired precision, would not work in
3563 CLN: The square root would be computed to a default precision (normally
3564 single-float precision), and the following conversion could not help about
3565 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3566 system and does not represent sqrt(5) in a non-numeric way.
3568 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3569 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3570 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3571 @code{cl_N} because a @samp{round1} does not exist for general complex
3574 When the function returns, all the local variables in the function are
3575 automatically reclaimed (garbage collected). Only the result survives and
3576 gets passed to the caller.
3578 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3579 contains this implementation together with an even faster algorithm.
3581 @section Debugging support
3584 When debugging a CLN application with GNU @code{gdb}, two facilities are
3585 available from the library:
3588 @item The library does type checks, range checks, consistency checks at
3589 many places. When one of these fails, an exception of a type derived from
3590 @code{runtime_exception} is thrown. When an exception is cought, the stack
3591 has already been unwound, so it is may not be possible to tell at which
3592 point the exception was thrown. For debugging, it is best to set up a
3593 catchpoint at the event of throwning a C++ exception:
3597 When this catchpoint is hit, look at the stack's backtrace:
3601 When control over the type of exception is required, it may be possible
3602 to set a breakpoint at the @code{g++} runtime library function
3603 @code{__raise_exception}. Refer to the documentation of GNU @code{gdb}
3606 @item The debugger's normal @code{print} command doesn't know about
3607 CLN's types and therefore prints mostly useless hexadecimal addresses.
3608 CLN offers a function @code{cl_print}, callable from the debugger,
3609 for printing number objects. In order to get this function, you have
3610 to define the macro @samp{CL_DEBUG} and then include all the header files
3611 for which you want @code{cl_print} debugging support. For example:
3612 @cindex @code{CL_DEBUG}
3615 #include <cln/string.h>
3617 Now, if you have in your program a variable @code{cl_string s}, and
3618 inspect it under @code{gdb}, the output may look like this:
3621 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3622 word = 134568800@}@}, @}
3623 (gdb) call cl_print(s)
3627 Note that the output of @code{cl_print} goes to the program's error output,
3628 not to gdb's standard output.
3630 Note, however, that the above facility does not work with all CLN types,
3631 only with number objects and similar. Therefore CLN offers a member function
3632 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3633 is needed for this member function to be implemented. Under @code{gdb},
3634 you call it like this:
3635 @cindex @code{debug_print ()}
3638 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3639 word = 134568800@}@}, @}
3640 (gdb) call s.debug_print()
3643 >call ($1).debug_print()
3648 Unfortunately, this feature does not seem to work under all circumstances.
3652 @chapter Customizing
3655 @section Error handling
3657 @cindex Error handling
3659 @cindex @code{runtime_exception}
3660 CLN signals abnormal situations by throwning exceptions. All exceptions
3661 thrown by the library are of type @code{runtime_exception} or of a
3662 derived type. Class @code{cln::runtime_exception} in turn is derived
3663 from the C++ standard library class @code{std::runtime_error} and
3664 inherits the @code{.what()} member function that can be used to query
3665 details about the cause of error.
3667 The most important classes thrown by the library are
3669 @cindex @code{floating_point_exception}
3670 @cindex @code{read_number_exception}
3672 Exception base class
3676 +----------------+----------------+
3678 Malformed number input Floating-point error
3679 read_number_exception floating_poing_exception
3680 <cln/number_io.h> <cln/float.h>
3683 CLN has many more exception classes that allow for more fine-grained
3684 control but I refrain from documenting them all here. They are all
3685 declared in the public header files and they are all subclasses of the
3686 above exceptions, so catching those you are always on the safe side.
3689 @section Floating-point underflow
3692 @cindex @code{floating_point_underflow_exception}
3693 Floating point underflow denotes the situation when a floating-point
3694 number is to be created which is so close to @code{0} that its exponent
3695 is too low to be represented internally. By default, this causes the
3696 exception @code{floating_point_underflow_exception} (subclass of
3697 @code{floating_point_exception}) to be thrown. If you set the global
3700 cl_boolean cl_inhibit_floating_point_underflow
3702 to @code{cl_true}, the exception will be inhibited, and a floating-point
3703 zero will be generated instead. The default value of
3704 @code{cl_inhibit_floating_point_underflow} is @code{cl_false}.
3707 @section Customizing I/O
3709 The output of the function @code{fprint} may be customized by changing the
3710 value of the global variable @code{default_print_flags}.
3711 @cindex @code{default_print_flags}
3714 @section Customizing the memory allocator
3716 Every memory allocation of CLN is done through the function pointer
3717 @code{malloc_hook}. Freeing of this memory is done through the function
3718 pointer @code{free_hook}. The default versions of these functions,
3719 provided in the library, call @code{malloc} and @code{free} and check
3720 the @code{malloc} result against @code{NULL}.
3721 If you want to provide another memory allocator, you need to define
3722 the variables @code{malloc_hook} and @code{free_hook} yourself,
3725 #include <cln/malloc.h>
3727 void* (*malloc_hook) (size_t size) = @dots{};
3728 void (*free_hook) (void* ptr) = @dots{};
3731 @cindex @code{malloc_hook ()}
3732 @cindex @code{free_hook ()}
3733 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
3735 It is not possible to change the memory allocator at runtime, because
3736 it is already called at program startup by the constructors of some