1 \input texinfo @c -*-texinfo-*-
4 @settitle CLN, a Class Library for Numbers
5 @c @setchapternewpage off
10 @c I hate putting "@noindent" in front of every paragraph.
16 * CLN: (cln). Class Library for Numbers (C++).
21 @c Don't need the other types of indices.
32 This file documents @sc{cln}, a Class Library for Numbers.
34 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
35 Richard Kreckel, @code{<kreckel@@ginac.de>}.
37 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002.
38 Copyright (C) Richard Kreckel 2000, 2001, 2002.
40 Permission is granted to make and distribute verbatim copies of
41 this manual provided the copyright notice and this permission notice
42 are preserved on all copies.
45 Permission is granted to process this file through TeX and print the
46 results, provided the printed document carries copying permission
47 notice identical to this one except for the removal of this paragraph
48 (this paragraph not being relevant to the printed manual).
51 Permission is granted to copy and distribute modified versions of this
52 manual under the conditions for verbatim copying, provided that the entire
53 resulting derived work is distributed under the terms of a permission
54 notice identical to this one.
56 Permission is granted to copy and distribute translations of this manual
57 into another language, under the above conditions for modified versions,
58 except that this permission notice may be stated in a translation approved
64 @c prevent ugly black rectangles on overfull hbox lines:
67 @title CLN, a Class Library for Numbers
69 @author by Bruno Haible
71 @vskip 0pt plus 1filll
72 Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002.
74 Copyright @copyright{} Richard Kreckel 2000, 2001, 2002.
77 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
78 Richard Kreckel, @code{<kreckel@@ginac.de>}.
80 Permission is granted to make and distribute verbatim copies of
81 this manual provided the copyright notice and this permission notice
82 are preserved on all copies.
84 Permission is granted to copy and distribute modified versions of this
85 manual under the conditions for verbatim copying, provided that the entire
86 resulting derived work is distributed under the terms of a permission
87 notice identical to this one.
89 Permission is granted to copy and distribute translations of this manual
90 into another language, under the above conditions for modified versions,
91 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 Schönhage-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 exceptions.
230 All non-macro identifiers are hidden in namespace @code{cln} in
231 order to avoid name clashes.
235 @chapter Installation
237 This section describes how to install the CLN package on your system.
240 @section Prerequisites
242 @subsection C++ compiler
244 To build CLN, you need a C++ compiler.
245 Actually, you need GNU @code{g++ 2.95} or newer.
247 The following C++ features are used:
248 classes, member functions, overloading of functions and operators,
249 constructors and destructors, inline, const, multiple inheritance,
250 templates and namespaces.
252 The following C++ features are not used:
253 @code{new}, @code{delete}, virtual inheritance, exceptions.
255 CLN relies on semi-automatic ordering of initializations
256 of static and global variables, a feature which I could
257 implement for GNU g++ only.
260 @comment cl_modules.h requires g++
261 Therefore nearly any C++ compiler will do.
263 The following C++ compilers are known to compile CLN:
266 GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
271 The following C++ compilers are known to be unusable for CLN:
274 On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
275 in lines containing @code{#if} or @code{#elif} preprocessor commands.
277 On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
278 in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
279 to have default constructors, and because it probably miscompiles the
280 integer multiplication routines.
282 On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
283 @code{short}s to @code{int}s by zero-extend.
287 On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
288 initializations will not work.
292 @subsection Make utility
295 To build CLN, you also need to have GNU @code{make} installed.
297 Only GNU @code{make} 3.77 is unusable for CLN; other versions work fine.
299 @subsection Sed utility
302 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
303 This is because the libtool script, which creates the CLN library, relies
304 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
308 @section Building the library
310 As with any autoconfiguring GNU software, installation is as easy as this:
318 If on your system, @samp{make} is not GNU @code{make}, you have to use
319 @samp{gmake} instead of @samp{make} above.
321 The @code{configure} command checks out some features of your system and
322 C++ compiler and builds the @code{Makefile}s. The @code{make} command
323 builds the library. This step may take about an hour on an average workstation.
324 The @code{make check} runs some test to check that no important subroutine
325 has been miscompiled.
327 The @code{configure} command accepts options. To get a summary of them, try
333 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
335 You can specify the C compiler, the C++ compiler and their options through
336 the following environment variables when running @code{configure}:
340 Specifies the C compiler.
343 Flags to be given to the C compiler when compiling programs (not when linking).
346 Specifies the C++ compiler.
349 Flags to be given to the C++ compiler when compiling programs (not when linking).
355 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
356 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O -g" \
357 CXX="g++ -V egcs-2.91.60" CXXFLAGS="-O -g" ./configure
358 $ CC="gcc -V 2.95.2" CFLAGS="-O2 -fno-exceptions" \
359 CXX="g++ -V 2.95.2" CFLAGS="-O2 -fno-exceptions" ./configure
360 $ CC="gcc -V 3.0.4" CFLAGS="-O2 -finline-limit=1000 -fno-exceptions" \
361 CXX="g++ -V 3.0.4" CFLAGS="-O2 -finline-limit=1000 -fno-exceptions" \
365 @comment cl_modules.h requires g++
366 You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
367 compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
370 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
371 $ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
374 On SGI Irix 5, if you wish not to use @code{g++}:
377 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
380 On SGI Irix 6, if you wish not to use @code{g++}:
383 $ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
384 ./configure --without-gmp
385 $ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
386 -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
387 ./configure --without-gmp
391 Note that for these environment variables to take effect, you have to set
392 them (assuming a Bourne-compatible shell) on the same line as the
393 @code{configure} command. If you made the settings in earlier shell
394 commands, you have to @code{export} the environment variables before
395 calling @code{configure}. In a @code{csh} shell, you have to use the
396 @samp{setenv} command for setting each of the environment variables.
398 Currently CLN works only with the GNU @code{g++} compiler, and only in
399 optimizing mode. So you should specify at least @code{-O} in the CXXFLAGS,
400 or no CXXFLAGS at all. (If CXXFLAGS is not set, CLN will use @code{-O}.)
402 If you use @code{g++} 3.0.x or 3.1, I recommend adding
403 @samp{-finline-limit=1000} to the CXXFLAGS. This is essential for good code.
405 If you use @code{g++} gcc-2.95.x or gcc-3.x , I recommend adding
406 @samp{-fno-exceptions} to the CXXFLAGS. This will likely generate better code.
408 If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
409 @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
410 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
411 routines. If you use @code{g++} older than 2.95.3 on Sparc you should
412 also specify @samp{--disable-shared} because of bad code produced in the
413 shared library. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
416 If you use @code{g++} on OSF/1 or Tru64 using gcc-2.95.x, you should
417 specify @samp{--disable-shared} because of linker problems with
418 duplicate symbols in shared libraries. If you use @code{g++} from
419 gcc-3.0.n, with n larger than 1, you should @emph{not} add
420 @samp{-fno-exceptions} to the CXXFLAGS, since that will generate wrong
421 code (gcc-3.1 is okay again, as is gcc-3.0).
423 Also, please do not compile CLN with @code{g++} using the @code{-O3}
424 optimization level. This leads to inferior code quality.
426 If you use @code{g++} from gcc-3.1, it will need 235 MB of virtual memory.
427 You might need some swap space if your machine doesn't have 512 MB of RAM.
429 By default, both a shared and a static library are built. You can build
430 CLN as a static (or shared) library only, by calling @code{configure} with
431 the option @samp{--disable-shared} (or @samp{--disable-static}). While
432 shared libraries are usually more convenient to use, they may not work
433 on all architectures. Try disabling them if you run into linker
434 problems. Also, they are generally somewhat slower than static
435 libraries so runtime-critical applications should be linked statically.
437 If you use @code{g++} from gcc-3.1 with option @samp{-g}, you will need
438 some disk space: 335 MB for building as both a shared and a static library,
439 or 130 MB when building as a shared library only.
442 @subsection Using the GNU MP Library
445 Starting with version 1.1, CLN may be configured to make use of a
446 preinstalled @code{gmp} library. Please make sure that you have at
447 least @code{gmp} version 3.0 installed since earlier versions are
448 unsupported and likely not to work. Enabling this feature by calling
449 @code{configure} with the option @samp{--with-gmp} is known to be quite
450 a boost for CLN's performance.
452 If you have installed the @code{gmp} library and its header file in
453 some place where your compiler cannot find it by default, you must help
454 @code{configure} by setting @code{CPPFLAGS} and @code{LDFLAGS}. Here is
458 $ CC="gcc" CFLAGS="-O2" CXX="g++" CXXFLAGS="-O2 -fno-exceptions" \
459 CPPFLAGS="-I/opt/gmp/include" LDFLAGS="-L/opt/gmp/lib" ./configure --with-gmp
463 @section Installing the library
466 As with any autoconfiguring GNU software, installation is as easy as this:
472 The @samp{make install} command installs the library and the include files
473 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
474 if you haven't specified a @code{--prefix} option to @code{configure}).
475 This step may require superuser privileges.
477 If you have already built the library and wish to install it, but didn't
478 specify @code{--prefix=@dots{}} at configure time, just re-run
479 @code{configure}, giving it the same options as the first time, plus
480 the @code{--prefix=@dots{}} option.
485 You can remove system-dependent files generated by @code{make} through
491 You can remove all files generated by @code{make}, thus reverting to a
492 virgin distribution of CLN, through
499 @chapter Ordinary number types
501 CLN implements the following class hierarchy:
509 Real or complex number
518 +-------------------+-------------------+
520 Rational number Floating-point number
522 <cln/rational.h> <cln/float.h>
524 | +--------------+--------------+--------------+
526 cl_I Short-Float Single-Float Double-Float Long-Float
527 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
528 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
531 @cindex @code{cl_number}
532 @cindex abstract class
533 The base class @code{cl_number} is an abstract base class.
534 It is not useful to declare a variable of this type except if you want
535 to completely disable compile-time type checking and use run-time type
540 @cindex complex number
541 The class @code{cl_N} comprises real and complex numbers. There is
542 no special class for complex numbers since complex numbers with imaginary
543 part @code{0} are automatically converted to real numbers.
546 The class @code{cl_R} comprises real numbers of different kinds. It is an
550 @cindex rational number
552 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
553 integers. There is no special class for non-integral rational numbers
554 since rational numbers with denominator @code{1} are automatically converted
558 The class @code{cl_F} implements floating-point approximations to real numbers.
559 It is an abstract class.
562 @section Exact numbers
565 Some numbers are represented as exact numbers: there is no loss of information
566 when such a number is converted from its mathematical value to its internal
567 representation. On exact numbers, the elementary operations (@code{+},
568 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
571 In CLN, the exact numbers are:
575 rational numbers (including integers),
577 complex numbers whose real and imaginary parts are both rational numbers.
580 Rational numbers are always normalized to the form
581 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
582 are coprime integers and the denominator is positive. If the resulting
583 denominator is @code{1}, the rational number is converted to an integer.
585 @cindex immediate numbers
586 Small integers (typically in the range @code{-2^29}@dots{}@code{2^29-1},
587 for 32-bit machines) are especially efficient, because they consume no heap
588 allocation. Otherwise the distinction between these immediate integers
589 (called ``fixnums'') and heap allocated integers (called ``bignums'')
590 is completely transparent.
593 @section Floating-point numbers
594 @cindex floating-point number
596 Not all real numbers can be represented exactly. (There is an easy mathematical
597 proof for this: Only a countable set of numbers can be stored exactly in
598 a computer, even if one assumes that it has unlimited storage. But there
599 are uncountably many real numbers.) So some approximation is needed.
600 CLN implements ordinary floating-point numbers, with mantissa and exponent.
602 @cindex rounding error
603 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
604 only return approximate results. For example, the value of the expression
605 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
606 @samp{0.7}. Rounding errors like this one are inevitable when computing
607 with floating-point numbers.
609 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
610 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
611 rule: It first computes the exact mathematical result and then returns the
612 floating-point number which is nearest to this. If two floating-point numbers
613 are equally distant from the ideal result, the one with a @code{0} in its least
614 significant mantissa bit is chosen.
616 Similarly, testing floating point numbers for equality @samp{x == y}
617 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
618 for some well-chosen @code{epsilon}.
620 Floating point numbers come in four flavors:
625 Short floats, type @code{cl_SF}.
626 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
627 and 17 mantissa bits (including the ``hidden'' bit).
628 They don't consume heap allocation.
632 Single floats, type @code{cl_FF}.
633 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
634 and 24 mantissa bits (including the ``hidden'' bit).
635 In CLN, they are represented as IEEE single-precision floating point numbers.
636 This corresponds closely to the C/C++ type @samp{float}.
640 Double floats, type @code{cl_DF}.
641 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
642 and 53 mantissa bits (including the ``hidden'' bit).
643 In CLN, they are represented as IEEE double-precision floating point numbers.
644 This corresponds closely to the C/C++ type @samp{double}.
648 Long floats, type @code{cl_LF}.
649 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
650 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
651 The precision of a long float is unlimited, but once created, a long float
652 has a fixed precision. (No ``lazy recomputation''.)
655 Of course, computations with long floats are more expensive than those
656 with smaller floating-point formats.
658 CLN does not implement features like NaNs, denormalized numbers and
659 gradual underflow. If the exponent range of some floating-point type
660 is too limited for your application, choose another floating-point type
661 with larger exponent range.
664 As a user of CLN, you can forget about the differences between the
665 four floating-point types and just declare all your floating-point
666 variables as being of type @code{cl_F}. This has the advantage that
667 when you change the precision of some computation (say, from @code{cl_DF}
668 to @code{cl_LF}), you don't have to change the code, only the precision
669 of the initial values. Also, many transcendental functions have been
670 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
671 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
672 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
673 the floating point contagion rule happened to change in the future.)
676 @section Complex numbers
677 @cindex complex number
679 Complex numbers, as implemented by the class @code{cl_N}, have a real
680 part and an imaginary part, both real numbers. A complex number whose
681 imaginary part is the exact number @code{0} is automatically converted
684 Complex numbers can arise from real numbers alone, for example
685 through application of @code{sqrt} or transcendental functions.
691 Conversions from any class to any its superclasses (``base classes'' in
692 C++ terminology) is done automatically.
694 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
695 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
696 @code{cl_N} and @code{cl_number}.
698 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
699 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
700 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
701 efficiency. Their range is therefore limited:
705 The conversion from @samp{int} works only if the argument is < 2^29 and > -2^29.
707 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
710 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
711 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
712 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
714 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
715 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
716 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
717 @samp{cl_I}, first convert it to an @samp{unsigned long}.
719 Conversions from the C built-in type @samp{float} are provided for the classes
720 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
722 Conversions from the C built-in type @samp{double} are provided for the classes
723 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
725 Conversions from @samp{const char *} are provided for the classes
726 @code{cl_I}, @code{cl_RA},
727 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
728 @code{cl_R}, @code{cl_N}.
729 The easiest way to specify a value which is outside of the range of the
730 C++ built-in types is therefore to specify it as a string, like this:
733 cl_I order_of_rubiks_cube_group = "43252003274489856000";
735 Note that this conversion is done at runtime, not at compile-time.
737 Conversions from @code{cl_I} to the C built-in types @samp{int},
738 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
742 @item int cl_I_to_int (const cl_I& x)
743 @cindex @code{cl_I_to_int ()}
744 @itemx unsigned int cl_I_to_uint (const cl_I& x)
745 @cindex @code{cl_I_to_uint ()}
746 @itemx long cl_I_to_long (const cl_I& x)
747 @cindex @code{cl_I_to_long ()}
748 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
749 @cindex @code{cl_I_to_ulong ()}
750 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
751 representable in the range of @var{ctype}, a runtime error occurs.
754 Conversions from the classes @code{cl_I}, @code{cl_RA},
755 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
757 to the C built-in types @samp{float} and @samp{double} are provided through
761 @item float float_approx (const @var{type}& x)
762 @cindex @code{float_approx ()}
763 @itemx double double_approx (const @var{type}& x)
764 @cindex @code{double_approx ()}
765 Returns an approximation of @code{x} of C type @var{ctype}.
766 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
767 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
770 Conversions from any class to any of its subclasses (``derived classes'' in
771 C++ terminology) are not provided. Instead, you can assert and check
772 that a value belongs to a certain subclass, and return it as element of that
773 class, using the @samp{As} and @samp{The} macros.
774 @cindex @code{As()()}
775 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
776 @var{type} and returns it as such.
777 @cindex @code{The()()}
778 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
779 @var{type} and returns it as such. It is your responsibility to ensure
780 that this assumption is valid. Since macros and namespaces don't go
781 together well, there is an equivalent to @samp{The}: the template
789 if (!(x >= 0)) abort();
790 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
791 // In general, it would be a rational number.
792 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
797 @chapter Functions on numbers
799 Each of the number classes declares its mathematical operations in the
800 corresponding include file. For example, if your code operates with
801 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
804 @section Constructing numbers
806 Here is how to create number objects ``from nothing''.
809 @subsection Constructing integers
811 @code{cl_I} objects are most easily constructed from C integers and from
812 strings. See @ref{Conversions}.
815 @subsection Constructing rational numbers
817 @code{cl_RA} objects can be constructed from strings. The syntax
818 for rational numbers is described in @ref{Internal and printed representation}.
819 Another standard way to produce a rational number is through application
820 of @samp{operator /} or @samp{recip} on integers.
823 @subsection Constructing floating-point numbers
825 @code{cl_F} objects with low precision are most easily constructed from
826 C @samp{float} and @samp{double}. See @ref{Conversions}.
828 To construct a @code{cl_F} with high precision, you can use the conversion
829 from @samp{const char *}, but you have to specify the desired precision
830 within the string. (See @ref{Internal and printed representation}.)
833 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
835 will set @samp{e} to the given value, with a precision of 40 decimal digits.
837 The programmatic way to construct a @code{cl_F} with high precision is
838 through the @code{cl_float} conversion function, see
839 @ref{Conversion to floating-point numbers}. For example, to compute
840 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
841 and then apply the exponential function:
843 float_format_t precision = float_format(40);
844 cl_F e = exp(cl_float(1,precision));
848 @subsection Constructing complex numbers
850 Non-real @code{cl_N} objects are normally constructed through the function
852 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
854 See @ref{Elementary complex functions}.
857 @section Elementary functions
859 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
860 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
861 defines the following operations:
864 @item @var{type} operator + (const @var{type}&, const @var{type}&)
865 @cindex @code{operator + ()}
868 @item @var{type} operator - (const @var{type}&, const @var{type}&)
869 @cindex @code{operator - ()}
872 @item @var{type} operator - (const @var{type}&)
873 Returns the negative of the argument.
875 @item @var{type} plus1 (const @var{type}& x)
876 @cindex @code{plus1 ()}
877 Returns @code{x + 1}.
879 @item @var{type} minus1 (const @var{type}& x)
880 @cindex @code{minus1 ()}
881 Returns @code{x - 1}.
883 @item @var{type} operator * (const @var{type}&, const @var{type}&)
884 @cindex @code{operator * ()}
887 @item @var{type} square (const @var{type}& x)
888 @cindex @code{square ()}
889 Returns @code{x * x}.
892 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
893 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
894 defines the following operations:
897 @item @var{type} operator / (const @var{type}&, const @var{type}&)
898 @cindex @code{operator / ()}
901 @item @var{type} recip (const @var{type}&)
902 @cindex @code{recip ()}
903 Returns the reciprocal of the argument.
906 The class @code{cl_I} doesn't define a @samp{/} operation because
907 in the C/C++ language this operator, applied to integral types,
908 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
909 is implementation dependent). (@xref{Rounding functions}.)
910 Instead, @code{cl_I} defines an ``exact quotient'' function:
913 @item cl_I exquo (const cl_I& x, const cl_I& y)
914 @cindex @code{exquo ()}
915 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
918 The following exponentiation functions are defined:
921 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
922 @cindex @code{expt_pos ()}
923 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
924 @code{y} must be > 0. Returns @code{x^y}.
926 @item cl_RA expt (const cl_RA& x, const cl_I& y)
927 @cindex @code{expt ()}
928 @itemx cl_R expt (const cl_R& x, const cl_I& y)
929 @itemx cl_N expt (const cl_N& x, const cl_I& y)
933 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
934 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
935 defines the following operation:
938 @item @var{type} abs (const @var{type}& x)
939 @cindex @code{abs ()}
940 Returns the absolute value of @code{x}.
941 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
944 The class @code{cl_N} implements this as follows:
947 @item cl_R abs (const cl_N x)
948 Returns the absolute value of @code{x}.
951 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
952 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
953 defines the following operation:
956 @item @var{type} signum (const @var{type}& x)
957 @cindex @code{signum ()}
958 Returns the sign of @code{x}, in the same number format as @code{x}.
959 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
960 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
965 @section Elementary rational functions
967 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
970 @item cl_I numerator (const @var{type}& x)
971 @cindex @code{numerator ()}
972 Returns the numerator of @code{x}.
974 @item cl_I denominator (const @var{type}& x)
975 @cindex @code{denominator ()}
976 Returns the denominator of @code{x}.
979 The numerator and denominator of a rational number are normalized in such
980 a way that they have no factor in common and the denominator is positive.
983 @section Elementary complex functions
985 The class @code{cl_N} defines the following operation:
988 @item cl_N complex (const cl_R& a, const cl_R& b)
989 @cindex @code{complex ()}
990 Returns the complex number @code{a+bi}, that is, the complex number with
991 real part @code{a} and imaginary part @code{b}.
994 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
997 @item cl_R realpart (const @var{type}& x)
998 @cindex @code{realpart ()}
999 Returns the real part of @code{x}.
1001 @item cl_R imagpart (const @var{type}& x)
1002 @cindex @code{imagpart ()}
1003 Returns the imaginary part of @code{x}.
1005 @item @var{type} conjugate (const @var{type}& x)
1006 @cindex @code{conjugate ()}
1007 Returns the complex conjugate of @code{x}.
1010 We have the relations
1014 @code{x = complex(realpart(x), imagpart(x))}
1016 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1020 @section Comparisons
1023 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1024 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1025 defines the following operations:
1028 @item bool operator == (const @var{type}&, const @var{type}&)
1029 @cindex @code{operator == ()}
1030 @itemx bool operator != (const @var{type}&, const @var{type}&)
1031 @cindex @code{operator != ()}
1032 Comparison, as in C and C++.
1034 @item uint32 equal_hashcode (const @var{type}&)
1035 @cindex @code{equal_hashcode ()}
1036 Returns a 32-bit hash code that is the same for any two numbers which are
1037 the same according to @code{==}. This hash code depends on the number's value,
1038 not its type or precision.
1040 @item cl_boolean zerop (const @var{type}& x)
1041 @cindex @code{zerop ()}
1042 Compare against zero: @code{x == 0}
1045 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1046 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1047 defines the following operations:
1050 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1051 @cindex @code{compare ()}
1052 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1053 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1055 @item bool operator <= (const @var{type}&, const @var{type}&)
1056 @cindex @code{operator <= ()}
1057 @itemx bool operator < (const @var{type}&, const @var{type}&)
1058 @cindex @code{operator < ()}
1059 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1060 @cindex @code{operator >= ()}
1061 @itemx bool operator > (const @var{type}&, const @var{type}&)
1062 @cindex @code{operator > ()}
1063 Comparison, as in C and C++.
1065 @item cl_boolean minusp (const @var{type}& x)
1066 @cindex @code{minusp ()}
1067 Compare against zero: @code{x < 0}
1069 @item cl_boolean plusp (const @var{type}& x)
1070 @cindex @code{plusp ()}
1071 Compare against zero: @code{x > 0}
1073 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1074 @cindex @code{max ()}
1075 Return the maximum of @code{x} and @code{y}.
1077 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1078 @cindex @code{min ()}
1079 Return the minimum of @code{x} and @code{y}.
1082 When a floating point number and a rational number are compared, the float
1083 is first converted to a rational number using the function @code{rational}.
1084 Since a floating point number actually represents an interval of real numbers,
1085 the result might be surprising.
1086 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1087 there is no floating point number whose value is exactly @code{1/3}.
1090 @section Rounding functions
1093 When a real number is to be converted to an integer, there is no ``best''
1094 rounding. The desired rounding function depends on the application.
1095 The Common Lisp and ISO Lisp standards offer four rounding functions:
1099 This is the largest integer <=@code{x}.
1102 This is the smallest integer >=@code{x}.
1105 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1108 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1109 integers, choose the even one.
1112 These functions have different advantages:
1114 @code{floor} and @code{ceiling} are translation invariant:
1115 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1116 for every @code{x} and every integer @code{n}.
1118 On the other hand, @code{truncate} and @code{round} are symmetric:
1119 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1120 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1121 down exactly as often as it rounds up.
1123 The functions are related like this:
1127 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1128 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1130 @code{truncate(x) = sign(x) * floor(abs(x))}
1133 Each of the classes @code{cl_R}, @code{cl_RA},
1134 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1135 defines the following operations:
1138 @item cl_I floor1 (const @var{type}& x)
1139 @cindex @code{floor1 ()}
1140 Returns @code{floor(x)}.
1141 @item cl_I ceiling1 (const @var{type}& x)
1142 @cindex @code{ceiling1 ()}
1143 Returns @code{ceiling(x)}.
1144 @item cl_I truncate1 (const @var{type}& x)
1145 @cindex @code{truncate1 ()}
1146 Returns @code{truncate(x)}.
1147 @item cl_I round1 (const @var{type}& x)
1148 @cindex @code{round1 ()}
1149 Returns @code{round(x)}.
1152 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1153 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1154 defines the following operations:
1157 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1158 Returns @code{floor(x/y)}.
1159 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1160 Returns @code{ceiling(x/y)}.
1161 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1162 Returns @code{truncate(x/y)}.
1163 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1164 Returns @code{round(x/y)}.
1167 These functions are called @samp{floor1}, @dots{} here instead of
1168 @samp{floor}, @dots{}, because on some systems, system dependent include
1169 files define @samp{floor} and @samp{ceiling} as macros.
1171 In many cases, one needs both the quotient and the remainder of a division.
1172 It is more efficient to compute both at the same time than to perform
1173 two divisions, one for quotient and the next one for the remainder.
1174 The following functions therefore return a structure containing both
1175 the quotient and the remainder. The suffix @samp{2} indicates the number
1176 of ``return values''. The remainder is defined as follows:
1180 for the computation of @code{quotient = floor(x)},
1181 @code{remainder = x - quotient},
1183 for the computation of @code{quotient = floor(x,y)},
1184 @code{remainder = x - quotient*y},
1187 and similarly for the other three operations.
1189 Each of the classes @code{cl_R}, @code{cl_RA},
1190 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1191 defines the following operations:
1194 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1195 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1196 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1197 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1198 @itemx @var{type}_div_t round2 (const @var{type}& x)
1201 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1202 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1203 defines the following operations:
1206 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1207 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1208 @cindex @code{floor2 ()}
1209 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1210 @cindex @code{ceiling2 ()}
1211 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1212 @cindex @code{truncate2 ()}
1213 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1214 @cindex @code{round2 ()}
1217 Sometimes, one wants the quotient as a floating-point number (of the
1218 same format as the argument, if the argument is a float) instead of as
1219 an integer. The prefix @samp{f} indicates this.
1222 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1223 defines the following operations:
1226 @item @var{type} ffloor (const @var{type}& x)
1227 @cindex @code{ffloor ()}
1228 @itemx @var{type} fceiling (const @var{type}& x)
1229 @cindex @code{fceiling ()}
1230 @itemx @var{type} ftruncate (const @var{type}& x)
1231 @cindex @code{ftruncate ()}
1232 @itemx @var{type} fround (const @var{type}& x)
1233 @cindex @code{fround ()}
1236 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1238 The class @code{cl_R} defines the following operations:
1241 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1242 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1243 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1244 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1247 These functions also exist in versions which return both the quotient
1248 and the remainder. The suffix @samp{2} indicates this.
1251 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1252 defines the following operations:
1253 @cindex @code{cl_F_fdiv_t}
1254 @cindex @code{cl_SF_fdiv_t}
1255 @cindex @code{cl_FF_fdiv_t}
1256 @cindex @code{cl_DF_fdiv_t}
1257 @cindex @code{cl_LF_fdiv_t}
1260 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1261 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1262 @cindex @code{ffloor2 ()}
1263 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1264 @cindex @code{fceiling2 ()}
1265 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1266 @cindex @code{ftruncate2 ()}
1267 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1268 @cindex @code{fround2 ()}
1270 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1271 @cindex @code{cl_R_fdiv_t}
1273 The class @code{cl_R} defines the following operations:
1276 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1277 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1278 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1279 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1280 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1283 Other applications need only the remainder of a division.
1284 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1285 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1286 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1290 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1292 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1295 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1296 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1297 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1299 The classes @code{cl_R}, @code{cl_I} define the following operations:
1302 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1303 @cindex @code{mod ()}
1304 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1305 @cindex @code{rem ()}
1311 Each of the classes @code{cl_R},
1312 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1313 defines the following operation:
1316 @item @var{type} sqrt (const @var{type}& x)
1317 @cindex @code{sqrt ()}
1318 @code{x} must be >= 0. This function returns the square root of @code{x},
1319 normalized to be >= 0. If @code{x} is the square of a rational number,
1320 @code{sqrt(x)} will be a rational number, else it will return a
1321 floating-point approximation.
1324 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1327 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1328 @cindex @code{sqrtp ()}
1329 This tests whether @code{x} is a perfect square. If so, it returns true
1330 and the exact square root in @code{*root}, else it returns false.
1333 Furthermore, for integers, similarly:
1336 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1337 @cindex @code{isqrt ()}
1338 @code{x} should be >= 0. This function sets @code{*root} to
1339 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1340 the boolean value @code{(expt(*root,2) == x)}.
1343 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1344 define the following operation:
1347 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1348 @cindex @code{rootp ()}
1349 @code{x} must be >= 0. @code{n} must be > 0.
1350 This tests whether @code{x} is an @code{n}th power of a rational number.
1351 If so, it returns true and the exact root in @code{*root}, else it returns
1355 The only square root function which accepts negative numbers is the one
1356 for class @code{cl_N}:
1359 @item cl_N sqrt (const cl_N& z)
1360 @cindex @code{sqrt ()}
1361 Returns the square root of @code{z}, as defined by the formula
1362 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1363 or to a complex number are done if necessary. The range of the result is the
1364 right half plane @code{realpart(sqrt(z)) >= 0}
1365 including the positive imaginary axis and 0, but excluding
1366 the negative imaginary axis.
1367 The result is an exact number only if @code{z} is an exact number.
1371 @section Transcendental functions
1372 @cindex transcendental functions
1374 The transcendental functions return an exact result if the argument
1375 is exact and the result is exact as well. Otherwise they must return
1376 inexact numbers even if the argument is exact.
1377 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1380 @subsection Exponential and logarithmic functions
1383 @item cl_R exp (const cl_R& x)
1384 @cindex @code{exp ()}
1385 @itemx cl_N exp (const cl_N& x)
1386 Returns the exponential function of @code{x}. This is @code{e^x} where
1387 @code{e} is the base of the natural logarithms. The range of the result
1388 is the entire complex plane excluding 0.
1390 @item cl_R ln (const cl_R& x)
1391 @cindex @code{ln ()}
1392 @code{x} must be > 0. Returns the (natural) logarithm of x.
1394 @item cl_N log (const cl_N& x)
1395 @cindex @code{log ()}
1396 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1397 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1398 The range of the result is the strip in the complex plane
1399 @code{-pi < imagpart(log(x)) <= pi}.
1401 @item cl_R phase (const cl_N& x)
1402 @cindex @code{phase ()}
1403 Returns the angle part of @code{x} in its polar representation as a
1404 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1405 This is also the imaginary part of @code{log(x)}.
1406 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1407 The result will be an exact number only if @code{zerop(x)} or
1408 if @code{x} is real and positive.
1410 @item cl_R log (const cl_R& a, const cl_R& b)
1411 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1412 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1413 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1416 @item cl_N log (const cl_N& a, const cl_N& b)
1417 Returns the logarithm of @code{a} with respect to base @code{b}.
1418 @code{log(a,b) = log(a)/log(b)}.
1420 @item cl_N expt (const cl_N& x, const cl_N& y)
1421 @cindex @code{expt ()}
1422 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1425 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1428 @item cl_F exp1 (float_format_t f)
1429 @cindex @code{exp1 ()}
1430 Returns e as a float of format @code{f}.
1432 @item cl_F exp1 (const cl_F& y)
1433 Returns e in the float format of @code{y}.
1435 @item cl_F exp1 (void)
1436 Returns e as a float of format @code{default_float_format}.
1440 @subsection Trigonometric functions
1443 @item cl_R sin (const cl_R& x)
1444 @cindex @code{sin ()}
1445 Returns @code{sin(x)}. The range of the result is the interval
1446 @code{-1 <= sin(x) <= 1}.
1448 @item cl_N sin (const cl_N& z)
1449 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1451 @item cl_R cos (const cl_R& x)
1452 @cindex @code{cos ()}
1453 Returns @code{cos(x)}. The range of the result is the interval
1454 @code{-1 <= cos(x) <= 1}.
1456 @item cl_N cos (const cl_N& x)
1457 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1459 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1460 @cindex @code{cos_sin_t}
1461 @itemx cos_sin_t cos_sin (const cl_R& x)
1462 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1463 @cindex @code{cos_sin ()}
1464 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1465 hold only approximately.
1467 @item cl_R tan (const cl_R& x)
1468 @cindex @code{tan ()}
1469 @itemx cl_N tan (const cl_N& x)
1470 Returns @code{tan(x) = sin(x)/cos(x)}.
1472 @item cl_N cis (const cl_R& x)
1473 @cindex @code{cis ()}
1474 @itemx cl_N cis (const cl_N& x)
1475 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1476 @code{e^(i*x) = cos(x) + i*sin(x)}.
1479 @cindex @code{asin ()}
1480 @item cl_N asin (const cl_N& z)
1481 Returns @code{arcsin(z)}. This is defined as
1482 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1483 @code{arcsin(-z) = -arcsin(z)}.
1484 The range of the result is the strip in the complex domain
1485 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1486 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1487 with @code{realpart = pi/2} and @code{imagpart > 0}.
1489 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1493 @item cl_N acos (const cl_N& z)
1494 @cindex @code{acos ()}
1495 Returns @code{arccos(z)}. This is defined as
1496 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1499 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1501 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1502 The range of the result is the strip in the complex domain
1503 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1504 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1505 with @code{realpart = pi} and @code{imagpart > 0}.
1507 Proof: This follows from the results about arcsin.
1511 @cindex @code{atan ()}
1512 @item cl_R atan (const cl_R& x, const cl_R& y)
1513 Returns the angle of the polar representation of the complex number
1514 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1515 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1516 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1517 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1518 with reversed order of arguments.
1520 @item cl_R atan (const cl_R& x)
1521 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1522 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1523 will be an exact number only if @code{x} is the exact @code{0}.
1525 @item cl_N atan (const cl_N& z)
1526 Returns @code{arctan(z)}. This is defined as
1527 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1528 @code{arctan(-z) = -arctan(z)}. The range of the result is
1529 the strip in the complex domain
1530 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1531 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1532 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1534 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1540 @cindex Archimedes' constant
1541 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1544 @item cl_F pi (float_format_t f)
1545 @cindex @code{pi ()}
1546 Returns pi as a float of format @code{f}.
1548 @item cl_F pi (const cl_F& y)
1549 Returns pi in the float format of @code{y}.
1551 @item cl_F pi (void)
1552 Returns pi as a float of format @code{default_float_format}.
1556 @subsection Hyperbolic functions
1559 @item cl_R sinh (const cl_R& x)
1560 @cindex @code{sinh ()}
1561 Returns @code{sinh(x)}.
1563 @item cl_N sinh (const cl_N& z)
1564 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1566 @item cl_R cosh (const cl_R& x)
1567 @cindex @code{cosh ()}
1568 Returns @code{cosh(x)}. The range of the result is the interval
1569 @code{cosh(x) >= 1}.
1571 @item cl_N cosh (const cl_N& z)
1572 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1574 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1575 @cindex @code{cosh_sinh_t}
1576 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1577 @cindex @code{cosh_sinh ()}
1578 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1579 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1580 hold only approximately.
1582 @item cl_R tanh (const cl_R& x)
1583 @cindex @code{tanh ()}
1584 @itemx cl_N tanh (const cl_N& x)
1585 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1587 @item cl_N asinh (const cl_N& z)
1588 @cindex @code{asinh ()}
1589 Returns @code{arsinh(z)}. This is defined as
1590 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1591 @code{arsinh(-z) = -arsinh(z)}.
1593 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1594 Actually, z+sqrt(1+z^2) can never be real and <0, so
1595 -pi < imagpart(arsinh(z)) < pi.
1596 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1597 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1599 The range of the result is the strip in the complex domain
1600 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1601 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1602 with @code{imagpart = pi/2} and @code{realpart < 0}.
1604 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1605 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1606 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1607 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1608 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1609 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1610 If y >= 1, the imagpart is pi/2 and the realpart is
1611 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1614 Moreover, if z is in Range(sqrt),
1615 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1616 (for a proof, see file src/cl_C_asinh.cc).
1619 @item cl_N acosh (const cl_N& z)
1620 @cindex @code{acosh ()}
1621 Returns @code{arcosh(z)}. This is defined as
1622 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1623 The range of the result is the half-strip in the complex domain
1624 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1625 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1627 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1628 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1629 If z is in Range(sqrt), we have
1630 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1631 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1633 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1634 and since the imagpart of both expressions is > -pi, <= pi
1635 ==> arcosh(z) = log(z+sqrt(z^2-1))
1636 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1637 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1638 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1639 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1640 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1642 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1643 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1644 = x^2 + y^2 + sqrt(u^2+v^2)
1649 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1650 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1651 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1652 Otherwise, -z is in Range(sqrt).
1653 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1654 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1655 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1656 and this has realpart > 0.
1657 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1658 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1659 has realpart = 0 and imagpart > 0.
1660 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1661 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1662 This has realpart >= 0 and imagpart = pi.
1665 @item cl_N atanh (const cl_N& z)
1666 @cindex @code{atanh ()}
1667 Returns @code{artanh(z)}. This is defined as
1668 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1669 @code{artanh(-z) = -artanh(z)}. The range of the result is
1670 the strip in the complex domain
1671 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1672 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1673 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1675 Proof: Write z = x+iy. Examine
1676 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1678 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1679 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1680 |x| < 1 ==> imagpart = 0
1683 = (atan(1+x,y) - atan(1-x,-y))/2
1684 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1685 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1686 > (pi - pi/2 - pi/2 )/2 = 0
1687 and (1+x)/y > (1-x)/y
1688 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1689 ==> imagpart < pi/2.
1690 Hence 0 < imagpart < pi/2.
1692 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1697 @subsection Euler gamma
1698 @cindex Euler's constant
1700 Euler's constant C = 0.577@dots{} is returned by the following functions:
1703 @item cl_F eulerconst (float_format_t f)
1704 @cindex @code{eulerconst ()}
1705 Returns Euler's constant as a float of format @code{f}.
1707 @item cl_F eulerconst (const cl_F& y)
1708 Returns Euler's constant in the float format of @code{y}.
1710 @item cl_F eulerconst (void)
1711 Returns Euler's constant as a float of format @code{default_float_format}.
1714 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1715 @cindex Catalan's constant
1718 @item cl_F catalanconst (float_format_t f)
1719 @cindex @code{catalanconst ()}
1720 Returns Catalan's constant as a float of format @code{f}.
1722 @item cl_F catalanconst (const cl_F& y)
1723 Returns Catalan's constant in the float format of @code{y}.
1725 @item cl_F catalanconst (void)
1726 Returns Catalan's constant as a float of format @code{default_float_format}.
1730 @subsection Riemann zeta
1731 @cindex Riemann's zeta
1733 Riemann's zeta function at an integral point @code{s>1} is returned by the
1734 following functions:
1737 @item cl_F zeta (int s, float_format_t f)
1738 @cindex @code{zeta ()}
1739 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1741 @item cl_F zeta (int s, const cl_F& y)
1742 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1744 @item cl_F zeta (int s)
1745 Returns Riemann's zeta function at @code{s} as a float of format
1746 @code{default_float_format}.
1750 @section Functions on integers
1752 @subsection Logical functions
1754 Integers, when viewed as in two's complement notation, can be thought as
1755 infinite bit strings where the bits' values eventually are constant.
1762 The logical operations view integers as such bit strings and operate
1763 on each of the bit positions in parallel.
1766 @item cl_I lognot (const cl_I& x)
1767 @cindex @code{lognot ()}
1768 @itemx cl_I operator ~ (const cl_I& x)
1769 @cindex @code{operator ~ ()}
1770 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1772 @item cl_I logand (const cl_I& x, const cl_I& y)
1773 @cindex @code{logand ()}
1774 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1775 @cindex @code{operator & ()}
1776 Logical and, like @code{x & y} in C.
1778 @item cl_I logior (const cl_I& x, const cl_I& y)
1779 @cindex @code{logior ()}
1780 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1781 @cindex @code{operator | ()}
1782 Logical (inclusive) or, like @code{x | y} in C.
1784 @item cl_I logxor (const cl_I& x, const cl_I& y)
1785 @cindex @code{logxor ()}
1786 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1787 @cindex @code{operator ^ ()}
1788 Exclusive or, like @code{x ^ y} in C.
1790 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1791 @cindex @code{logeqv ()}
1792 Bitwise equivalence, like @code{~(x ^ y)} in C.
1794 @item cl_I lognand (const cl_I& x, const cl_I& y)
1795 @cindex @code{lognand ()}
1796 Bitwise not and, like @code{~(x & y)} in C.
1798 @item cl_I lognor (const cl_I& x, const cl_I& y)
1799 @cindex @code{lognor ()}
1800 Bitwise not or, like @code{~(x | y)} in C.
1802 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1803 @cindex @code{logandc1 ()}
1804 Logical and, complementing the first argument, like @code{~x & y} in C.
1806 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1807 @cindex @code{logandc2 ()}
1808 Logical and, complementing the second argument, like @code{x & ~y} in C.
1810 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1811 @cindex @code{logorc1 ()}
1812 Logical or, complementing the first argument, like @code{~x | y} in C.
1814 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1815 @cindex @code{logorc2 ()}
1816 Logical or, complementing the second argument, like @code{x | ~y} in C.
1819 These operations are all available though the function
1821 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
1822 @cindex @code{boole ()}
1824 where @code{op} must have one of the 16 values (each one stands for a function
1825 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
1826 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
1827 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
1828 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
1829 @code{boole_orc1}, @code{boole_orc2}.
1830 @cindex @code{boole_clr}
1831 @cindex @code{boole_set}
1832 @cindex @code{boole_1}
1833 @cindex @code{boole_2}
1834 @cindex @code{boole_c1}
1835 @cindex @code{boole_c2}
1836 @cindex @code{boole_and}
1837 @cindex @code{boole_xor}
1838 @cindex @code{boole_eqv}
1839 @cindex @code{boole_nand}
1840 @cindex @code{boole_nor}
1841 @cindex @code{boole_andc1}
1842 @cindex @code{boole_andc2}
1843 @cindex @code{boole_orc1}
1844 @cindex @code{boole_orc2}
1847 Other functions that view integers as bit strings:
1850 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
1851 @cindex @code{logtest ()}
1852 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
1853 @code{logand(x,y) != 0}.
1855 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
1856 @cindex @code{logbitp ()}
1857 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
1858 Bit 0 is the least significant bit.
1860 @item uintL logcount (const cl_I& x)
1861 @cindex @code{logcount ()}
1862 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
1863 the number of zero bits in @code{x}, if @code{x} < 0.
1866 The following functions operate on intervals of bits in integers.
1869 struct cl_byte @{ uintL size; uintL position; @};
1871 @cindex @code{cl_byte}
1872 represents the bit interval containing the bits
1873 @code{position}@dots{}@code{position+size-1} of an integer.
1874 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
1877 @item cl_I ldb (const cl_I& n, const cl_byte& b)
1878 @cindex @code{ldb ()}
1879 extracts the bits of @code{n} described by the bit interval @code{b}
1880 and returns them as a nonnegative integer with @code{b.size} bits.
1882 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
1883 @cindex @code{ldb_test ()}
1884 Returns true if some bit described by the bit interval @code{b} is set in
1887 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1888 @cindex @code{dpb ()}
1889 Returns @code{n}, with the bits described by the bit interval @code{b}
1890 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
1891 @code{newbyte} are relevant.
1894 The functions @code{ldb} and @code{dpb} implicitly shift. The following
1895 functions are their counterparts without shifting:
1898 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
1899 @cindex @code{mask_field ()}
1900 returns an integer with the bits described by the bit interval @code{b}
1901 copied from the corresponding bits in @code{n}, the other bits zero.
1903 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1904 @cindex @code{deposit_field ()}
1905 returns an integer where the bits described by the bit interval @code{b}
1906 come from @code{newbyte} and the other bits come from @code{n}.
1909 The following relations hold:
1913 @code{ldb (n, b) = mask_field(n, b) >> b.position},
1915 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
1917 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
1920 The following operations on integers as bit strings are efficient shortcuts
1921 for common arithmetic operations:
1924 @item cl_boolean oddp (const cl_I& x)
1925 @cindex @code{oddp ()}
1926 Returns true if the least significant bit of @code{x} is 1. Equivalent to
1927 @code{mod(x,2) != 0}.
1929 @item cl_boolean evenp (const cl_I& x)
1930 @cindex @code{evenp ()}
1931 Returns true if the least significant bit of @code{x} is 0. Equivalent to
1932 @code{mod(x,2) == 0}.
1934 @item cl_I operator << (const cl_I& x, const cl_I& n)
1935 @cindex @code{operator << ()}
1936 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
1937 Equivalent to @code{x * expt(2,n)}.
1939 @item cl_I operator >> (const cl_I& x, const cl_I& n)
1940 @cindex @code{operator >> ()}
1941 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
1942 Bits shifted out to the right are thrown away.
1943 Equivalent to @code{floor(x / expt(2,n))}.
1945 @item cl_I ash (const cl_I& x, const cl_I& y)
1946 @cindex @code{ash ()}
1947 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
1948 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
1949 returns @code{floor(x * expt(2,y))}.
1951 @item uintL integer_length (const cl_I& x)
1952 @cindex @code{integer_length ()}
1953 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
1954 in two's complement notation. This is the smallest n >= 0 such that
1955 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
1958 @item uintL ord2 (const cl_I& x)
1959 @cindex @code{ord2 ()}
1960 @code{x} must be non-zero. This function returns the number of 0 bits at the
1961 right of @code{x} in two's complement notation. This is the largest n >= 0
1962 such that 2^n divides @code{x}.
1964 @item uintL power2p (const cl_I& x)
1965 @cindex @code{power2p ()}
1966 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
1967 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
1968 (See also the function @code{logp}.)
1972 @subsection Number theoretic functions
1975 @item uint32 gcd (uint32 a, uint32 b)
1976 @cindex @code{gcd ()}
1977 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
1978 This function returns the greatest common divisor of @code{a} and @code{b},
1979 normalized to be >= 0.
1981 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
1982 @cindex @code{xgcd ()}
1983 This function (``extended gcd'') returns the greatest common divisor @code{g} of
1984 @code{a} and @code{b} and at the same time the representation of @code{g}
1985 as an integral linear combination of @code{a} and @code{b}:
1986 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
1987 @code{u} and @code{v} will be normalized to be of smallest possible absolute
1988 value, in the following sense: If @code{a} and @code{b} are non-zero, and
1989 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
1990 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
1992 @item cl_I lcm (const cl_I& a, const cl_I& b)
1993 @cindex @code{lcm ()}
1994 This function returns the least common multiple of @code{a} and @code{b},
1995 normalized to be >= 0.
1997 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
1998 @cindex @code{logp ()}
1999 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2000 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2001 rational number, this function returns true and sets *l = log(a,b), else
2006 @subsection Combinatorial functions
2009 @item cl_I factorial (uintL n)
2010 @cindex @code{factorial ()}
2011 @code{n} must be a small integer >= 0. This function returns the factorial
2012 @code{n}! = @code{1*2*@dots{}*n}.
2014 @item cl_I doublefactorial (uintL n)
2015 @cindex @code{doublefactorial ()}
2016 @code{n} must be a small integer >= 0. This function returns the
2017 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2018 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2020 @item cl_I binomial (uintL n, uintL k)
2021 @cindex @code{binomial ()}
2022 @code{n} and @code{k} must be small integers >= 0. This function returns the
2023 binomial coefficient
2025 ${n \choose k} = {n! \over n! (n-k)!}$
2028 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2030 for 0 <= k <= n, 0 else.
2034 @section Functions on floating-point numbers
2036 Recall that a floating-point number consists of a sign @code{s}, an
2037 exponent @code{e} and a mantissa @code{m}. The value of the number is
2038 @code{(-1)^s * 2^e * m}.
2041 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2042 defines the following operations.
2045 @item @var{type} scale_float (const @var{type}& x, sintL delta)
2046 @cindex @code{scale_float ()}
2047 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2048 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2049 because it copies @code{x} and modifies the exponent.
2052 The following functions provide an abstract interface to the underlying
2053 representation of floating-point numbers.
2056 @item sintL float_exponent (const @var{type}& x)
2057 @cindex @code{float_exponent ()}
2058 Returns the exponent @code{e} of @code{x}.
2059 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2060 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2062 @item sintL float_radix (const @var{type}& x)
2063 @cindex @code{float_radix ()}
2064 Returns the base of the floating-point representation. This is always @code{2}.
2066 @item @var{type} float_sign (const @var{type}& x)
2067 @cindex @code{float_sign ()}
2068 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2069 @code{x} >= 0, -1 for @code{x} < 0.
2071 @item uintL float_digits (const @var{type}& x)
2072 @cindex @code{float_digits ()}
2073 Returns the number of mantissa bits in the floating-point representation
2074 of @code{x}, including the hidden bit. The value only depends on the type
2075 of @code{x}, not on its value.
2077 @item uintL float_precision (const @var{type}& x)
2078 @cindex @code{float_precision ()}
2079 Returns the number of significant mantissa bits in the floating-point
2080 representation of @code{x}. Since denormalized numbers are not supported,
2081 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2085 The complete internal representation of a float is encoded in the type
2086 @cindex @code{decoded_float}
2087 @cindex @code{decoded_sfloat}
2088 @cindex @code{decoded_ffloat}
2089 @cindex @code{decoded_dfloat}
2090 @cindex @code{decoded_lfloat}
2091 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2092 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2094 struct decoded_@var{type}float @{
2095 @var{type} mantissa; cl_I exponent; @var{type} sign;
2099 and returned by the function
2102 @item decoded_@var{type}float decode_float (const @var{type}& x)
2103 @cindex @code{decode_float ()}
2104 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2105 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2106 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2107 @code{e} is the same as returned by the function @code{float_exponent}.
2110 A complete decoding in terms of integers is provided as type
2111 @cindex @code{cl_idecoded_float}
2113 struct cl_idecoded_float @{
2114 cl_I mantissa; cl_I exponent; cl_I sign;
2117 by the following function:
2120 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2121 @cindex @code{integer_decode_float ()}
2122 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2123 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2124 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2125 WARNING: The exponent @code{e} is not the same as the one returned by
2126 the functions @code{decode_float} and @code{float_exponent}.
2129 Some other function, implemented only for class @code{cl_F}:
2132 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2133 @cindex @code{float_sign ()}
2134 This returns a floating point number whose precision and absolute value
2135 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2136 zero, it is treated as positive. Same for @code{y}.
2140 @section Conversion functions
2143 @subsection Conversion to floating-point numbers
2145 The type @code{float_format_t} describes a floating-point format.
2146 @cindex @code{float_format_t}
2149 @item float_format_t float_format (uintL n)
2150 @cindex @code{float_format ()}
2151 Returns the smallest float format which guarantees at least @code{n}
2152 decimal digits in the mantissa (after the decimal point).
2154 @item float_format_t float_format (const cl_F& x)
2155 Returns the floating point format of @code{x}.
2157 @item float_format_t default_float_format
2158 @cindex @code{default_float_format}
2159 Global variable: the default float format used when converting rational numbers
2163 To convert a real number to a float, each of the types
2164 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2165 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2166 defines the following operations:
2169 @item cl_F cl_float (const @var{type}&x, float_format_t f)
2170 @cindex @code{cl_float ()}
2171 Returns @code{x} as a float of format @code{f}.
2172 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2173 Returns @code{x} in the float format of @code{y}.
2174 @item cl_F cl_float (const @var{type}&x)
2175 Returns @code{x} as a float of format @code{default_float_format} if
2176 it is an exact number, or @code{x} itself if it is already a float.
2179 Of course, converting a number to a float can lose precision.
2181 Every floating-point format has some characteristic numbers:
2184 @item cl_F most_positive_float (float_format_t f)
2185 @cindex @code{most_positive_float ()}
2186 Returns the largest (most positive) floating point number in float format @code{f}.
2188 @item cl_F most_negative_float (float_format_t f)
2189 @cindex @code{most_negative_float ()}
2190 Returns the smallest (most negative) floating point number in float format @code{f}.
2192 @item cl_F least_positive_float (float_format_t f)
2193 @cindex @code{least_positive_float ()}
2194 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2195 in float format @code{f}.
2197 @item cl_F least_negative_float (float_format_t f)
2198 @cindex @code{least_negative_float ()}
2199 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2200 in float format @code{f}.
2202 @item cl_F float_epsilon (float_format_t f)
2203 @cindex @code{float_epsilon ()}
2204 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2206 @item cl_F float_negative_epsilon (float_format_t f)
2207 @cindex @code{float_negative_epsilon ()}
2208 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2212 @subsection Conversion to rational numbers
2214 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2215 defines the following operation:
2218 @item cl_RA rational (const @var{type}& x)
2219 @cindex @code{rational ()}
2220 Returns the value of @code{x} as an exact number. If @code{x} is already
2221 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2222 the value is a rational number whose denominator is a power of 2.
2225 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2229 @item cl_RA rationalize (const cl_R& x)
2230 @cindex @code{rationalize ()}
2231 If @code{x} is a floating-point number, it actually represents an interval
2232 of real numbers, and this function returns the rational number with
2233 smallest denominator (and smallest numerator, in magnitude)
2234 which lies in this interval.
2235 If @code{x} is already an exact number, this function returns @code{x}.
2238 If @code{x} is any float, one has
2242 @code{cl_float(rational(x),x) = x}
2244 @code{cl_float(rationalize(x),x) = x}
2248 @section Random number generators
2251 A random generator is a machine which produces (pseudo-)random numbers.
2252 The include file @code{<cln/random.h>} defines a class @code{random_state}
2253 which contains the state of a random generator. If you make a copy
2254 of the random number generator, the original one and the copy will produce
2255 the same sequence of random numbers.
2257 The following functions return (pseudo-)random numbers in different formats.
2258 Calling one of these modifies the state of the random number generator in
2259 a complicated but deterministic way.
2262 @cindex @code{random_state}
2263 @cindex @code{default_random_state}
2265 random_state default_random_state
2267 contains a default random number generator. It is used when the functions
2268 below are called without @code{random_state} argument.
2271 @item uint32 random32 (random_state& randomstate)
2272 @itemx uint32 random32 ()
2273 @cindex @code{random32 ()}
2274 Returns a random unsigned 32-bit number. All bits are equally random.
2276 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2277 @itemx cl_I random_I (const cl_I& n)
2278 @cindex @code{random_I ()}
2279 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2280 in the range @code{0 <= x < n}.
2282 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2283 @itemx cl_F random_F (const cl_F& n)
2284 @cindex @code{random_F ()}
2285 @code{n} must be a float > 0. This function returns a random floating-point
2286 number of the same format as @code{n} in the range @code{0 <= x < n}.
2288 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2289 @itemx cl_R random_R (const cl_R& n)
2290 @cindex @code{random_R ()}
2291 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2292 if @code{n} is a float.
2296 @section Obfuscating operators
2297 @cindex modifying operators
2299 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2300 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2301 are not available by default because their
2302 use tends to make programs unreadable. It is trivial to get away without
2303 them. However, if you feel that you absolutely need these operators
2304 to get happy, then add
2306 #define WANT_OBFUSCATING_OPERATORS
2308 @cindex @code{WANT_OBFUSCATING_OPERATORS}
2309 to the beginning of your source files, before the inclusion of any CLN
2310 include files. This flag will enable the following operators:
2312 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2313 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2316 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2317 @cindex @code{operator += ()}
2318 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2319 @cindex @code{operator -= ()}
2320 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2321 @cindex @code{operator *= ()}
2322 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2323 @cindex @code{operator /= ()}
2326 For the class @code{cl_I}:
2329 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2330 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2331 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2332 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2333 @cindex @code{operator &= ()}
2334 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2335 @cindex @code{operator |= ()}
2336 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2337 @cindex @code{operator ^= ()}
2338 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2339 @cindex @code{operator <<= ()}
2340 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2341 @cindex @code{operator >>= ()}
2344 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2345 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2348 @item @var{type}& operator ++ (@var{type}& x)
2349 @cindex @code{operator ++ ()}
2350 The prefix operator @code{++x}.
2352 @item void operator ++ (@var{type}& x, int)
2353 The postfix operator @code{x++}.
2355 @item @var{type}& operator -- (@var{type}& x)
2356 @cindex @code{operator -- ()}
2357 The prefix operator @code{--x}.
2359 @item void operator -- (@var{type}& x, int)
2360 The postfix operator @code{x--}.
2363 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2364 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2368 @chapter Input/Output
2369 @cindex Input/Output
2371 @section Internal and printed representation
2372 @cindex representation
2374 All computations deal with the internal representations of the numbers.
2376 Every number has an external representation as a sequence of ASCII characters.
2377 Several external representations may denote the same number, for example,
2378 "20.0" and "20.000".
2380 Converting an internal to an external representation is called ``printing'',
2382 converting an external to an internal representation is called ``reading''.
2384 In CLN, it is always true that conversion of an internal to an external
2385 representation and then back to an internal representation will yield the
2386 same internal representation. Symbolically: @code{read(print(x)) == x}.
2387 This is called ``print-read consistency''.
2389 Different types of numbers have different external representations (case
2394 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2395 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2396 for decimal integers
2397 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2399 @item Rational numbers
2400 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2401 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2404 @item Floating-point numbers
2405 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2406 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2407 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2408 of the form _@var{prec} may be appended. There must be at least
2409 one digit in the non-exponent part. The exponent has the syntax
2410 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2411 The exponent marker is
2415 @samp{s} for short-floats,
2417 @samp{f} for single-floats,
2419 @samp{d} for double-floats,
2421 @samp{L} for long-floats,
2424 or @samp{e}, which denotes a default float format. The precision specifying
2425 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2426 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2427 function @samp{float_format}.
2429 @item Complex numbers
2430 External representation:
2433 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2434 if @var{imagpart} is negative, its printed representation begins with
2435 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2436 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2437 is rational and the rational number's base is >18, because the @samp{i}
2438 is then read as a digit.
2440 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2445 @section Input functions
2447 Including @code{<cln/io.h>} defines a number of simple input functions
2448 that read from @code{std::istream&}:
2451 @item int freadchar (std::istream& stream)
2452 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2453 if the end of stream was encountered or an error occurred.
2455 @item int funreadchar (std::istream& stream, int c)
2456 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2457 last @code{freadchar} operation on @code{stream}.
2460 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2461 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2462 defines, in @code{<cln/@var{type}_io.h>}, the following input function:
2465 @item std::istream& operator>> (std::istream& stream, @var{type}& result)
2466 Reads a number from @code{stream} and stores it in the @code{result}.
2469 The most flexible input functions, defined in @code{<cln/@var{type}_io.h>},
2473 @item cl_N read_complex (std::istream& stream, const cl_read_flags& flags)
2474 @itemx cl_R read_real (std::istream& stream, const cl_read_flags& flags)
2475 @itemx cl_F read_float (std::istream& stream, const cl_read_flags& flags)
2476 @itemx cl_RA read_rational (std::istream& stream, const cl_read_flags& flags)
2477 @itemx cl_I read_integer (std::istream& stream, const cl_read_flags& flags)
2478 Reads a number from @code{stream}. The @code{flags} are parameters which
2479 affect the input syntax. Whitespace before the number is silently skipped.
2481 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2482 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2483 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2484 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2485 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2486 Reads a number from a string in memory. The @code{flags} are parameters which
2487 affect the input syntax. The string starts at @code{string} and ends at
2488 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2489 @code{NULL}, denoting the entire string, i.e. equivalent to
2490 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2491 @code{NULL}, the string in memory must contain exactly one number and nothing
2492 more, else a fatal error will be signalled. If @code{end_of_parse}
2493 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2494 the last parsed character (i.e. @code{string_limit} if nothing came after
2495 the number). Whitespace is not allowed.
2498 The structure @code{cl_read_flags} contains the following fields:
2501 @item cl_read_syntax_t syntax
2502 The possible results of the read operation. Possible values are
2503 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2504 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2505 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2507 @item cl_read_lsyntax_t lsyntax
2508 Specifies the language-dependent syntax variant for the read operation.
2512 @item lsyntax_standard
2513 accept standard algebraic notation only, no complex numbers,
2514 @item lsyntax_algebraic
2515 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2516 @item lsyntax_commonlisp
2517 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2518 hexadecimal numbers,
2519 @code{#@var{base}R} for rational numbers in a given base,
2520 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2522 accept all of these extensions.
2525 @item unsigned int rational_base
2526 The base in which rational numbers are read.
2528 @item float_format_t float_flags.default_float_format
2529 The float format used when reading floats with exponent marker @samp{e}.
2531 @item float_format_t float_flags.default_lfloat_format
2532 The float format used when reading floats with exponent marker @samp{l}.
2534 @item cl_boolean float_flags.mantissa_dependent_float_format
2535 When this flag is true, floats specified with more digits than corresponding
2536 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2537 precision corresponding to their number of significant digits.
2541 @section Output functions
2543 Including @code{<cln/io.h>} defines a number of simple output functions
2544 that write to @code{std::ostream&}:
2547 @item void fprintchar (std::ostream& stream, char c)
2548 Prints the character @code{x} literally on the @code{stream}.
2550 @item void fprint (std::ostream& stream, const char * string)
2551 Prints the @code{string} literally on the @code{stream}.
2553 @item void fprintdecimal (std::ostream& stream, int x)
2554 @itemx void fprintdecimal (std::ostream& stream, const cl_I& x)
2555 Prints the integer @code{x} in decimal on the @code{stream}.
2557 @item void fprintbinary (std::ostream& stream, const cl_I& x)
2558 Prints the integer @code{x} in binary (base 2, without prefix)
2559 on the @code{stream}.
2561 @item void fprintoctal (std::ostream& stream, const cl_I& x)
2562 Prints the integer @code{x} in octal (base 8, without prefix)
2563 on the @code{stream}.
2565 @item void fprinthexadecimal (std::ostream& stream, const cl_I& x)
2566 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2567 on the @code{stream}.
2570 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2571 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2572 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2575 @item void fprint (std::ostream& stream, const @var{type}& x)
2576 @itemx std::ostream& operator<< (std::ostream& stream, const @var{type}& x)
2577 Prints the number @code{x} on the @code{stream}. The output may depend
2578 on the global printer settings in the variable @code{default_print_flags}.
2579 The @code{ostream} flags and settings (flags, width and locale) are
2583 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2586 void print_complex (std::ostream& stream, const cl_print_flags& flags,
2588 void print_real (std::ostream& stream, const cl_print_flags& flags,
2590 void print_float (std::ostream& stream, const cl_print_flags& flags,
2592 void print_rational (std::ostream& stream, const cl_print_flags& flags,
2594 void print_integer (std::ostream& stream, const cl_print_flags& flags,
2597 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2598 parameters which affect the output.
2600 The structure type @code{cl_print_flags} contains the following fields:
2603 @item unsigned int rational_base
2604 The base in which rational numbers are printed. Default is @code{10}.
2606 @item cl_boolean rational_readably
2607 If this flag is true, rational numbers are printed with radix specifiers in
2608 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2609 prefixes, trailing dot). Default is false.
2611 @item cl_boolean float_readably
2612 If this flag is true, type specific exponent markers have precedence over 'E'.
2615 @item float_format_t default_float_format
2616 Floating point numbers of this format will be printed using the 'E' exponent
2617 marker. Default is @code{float_format_ffloat}.
2619 @item cl_boolean complex_readably
2620 If this flag is true, complex numbers will be printed using the Common Lisp
2621 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2623 @item cl_string univpoly_varname
2624 Univariate polynomials with no explicit indeterminate name will be printed
2625 using this variable name. Default is @code{"x"}.
2628 The global variable @code{default_print_flags} contains the default values,
2629 used by the function @code{fprint}.
2634 CLN has a class of abstract rings.
2642 Rings can be compared for equality:
2645 @item bool operator== (const cl_ring&, const cl_ring&)
2646 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2647 These compare two rings for equality.
2650 Given a ring @code{R}, the following members can be used.
2653 @item void R->fprint (std::ostream& stream, const cl_ring_element& x)
2654 @cindex @code{fprint ()}
2655 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2656 @cindex @code{equal ()}
2657 @itemx cl_ring_element R->zero ()
2658 @cindex @code{zero ()}
2659 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2660 @cindex @code{zerop ()}
2661 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2662 @cindex @code{plus ()}
2663 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2664 @cindex @code{minus ()}
2665 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2666 @cindex @code{uminus ()}
2667 @itemx cl_ring_element R->one ()
2668 @cindex @code{one ()}
2669 @itemx cl_ring_element R->canonhom (const cl_I& x)
2670 @cindex @code{canonhom ()}
2671 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2672 @cindex @code{mul ()}
2673 @itemx cl_ring_element R->square (const cl_ring_element& x)
2674 @cindex @code{square ()}
2675 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2676 @cindex @code{expt_pos ()}
2679 The following rings are built-in.
2682 @item cl_null_ring cl_0_ring
2683 The null ring, containing only zero.
2685 @item cl_complex_ring cl_C_ring
2686 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2688 @item cl_real_ring cl_R_ring
2689 The ring of real numbers. This corresponds to the type @code{cl_R}.
2691 @item cl_rational_ring cl_RA_ring
2692 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2694 @item cl_integer_ring cl_I_ring
2695 The ring of integers. This corresponds to the type @code{cl_I}.
2698 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2699 @code{cl_RA_ring}, @code{cl_I_ring}:
2702 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2703 @cindex @code{instanceof ()}
2704 Tests whether the given number is an element of the number ring R.
2708 @chapter Modular integers
2709 @cindex modular integer
2711 @section Modular integer rings
2714 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2715 The modulus is explicitly part of every modular integer. CLN doesn't
2716 allow you to (accidentally) mix elements of different modular rings,
2717 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2718 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2719 doesn't have generic types. So one has to live with runtime checks.)
2721 The class of modular integer rings is
2729 Modular integer ring
2733 @cindex @code{cl_modint_ring}
2735 and the class of all modular integers (elements of modular integer rings) is
2743 Modular integer rings are constructed using the function
2746 @item cl_modint_ring find_modint_ring (const cl_I& N)
2747 @cindex @code{find_modint_ring ()}
2748 This function returns the modular ring @samp{Z/NZ}. It takes care
2749 of finding out about special cases of @code{N}, like powers of two
2750 and odd numbers for which Montgomery multiplication will be a win,
2751 @cindex Montgomery multiplication
2752 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2753 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2754 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2758 Modular integer rings can be compared for equality:
2761 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2762 @cindex @code{operator == ()}
2763 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2764 @cindex @code{operator != ()}
2765 These compare two modular integer rings for equality. Two different calls
2766 to @code{find_modint_ring} with the same argument necessarily return the
2767 same ring because it is memoized in the cache table.
2770 @section Functions on modular integers
2772 Given a modular integer ring @code{R}, the following members can be used.
2775 @item cl_I R->modulus
2776 @cindex @code{modulus}
2777 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2779 @item cl_MI R->zero()
2780 @cindex @code{zero ()}
2781 This returns @code{0 mod N}.
2783 @item cl_MI R->one()
2784 @cindex @code{one ()}
2785 This returns @code{1 mod N}.
2787 @item cl_MI R->canonhom (const cl_I& x)
2788 @cindex @code{canonhom ()}
2789 This returns @code{x mod N}.
2791 @item cl_I R->retract (const cl_MI& x)
2792 @cindex @code{retract ()}
2793 This is a partial inverse function to @code{R->canonhom}. It returns the
2794 standard representative (@code{>=0}, @code{<N}) of @code{x}.
2796 @item cl_MI R->random(random_state& randomstate)
2797 @itemx cl_MI R->random()
2798 @cindex @code{random ()}
2799 This returns a random integer modulo @code{N}.
2802 The following operations are defined on modular integers.
2805 @item cl_modint_ring x.ring ()
2806 @cindex @code{ring ()}
2807 Returns the ring to which the modular integer @code{x} belongs.
2809 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
2810 @cindex @code{operator + ()}
2811 Returns the sum of two modular integers. One of the arguments may also
2814 @item cl_MI operator- (const cl_MI&, const cl_MI&)
2815 @cindex @code{operator - ()}
2816 Returns the difference of two modular integers. One of the arguments may also
2819 @item cl_MI operator- (const cl_MI&)
2820 Returns the negative of a modular integer.
2822 @item cl_MI operator* (const cl_MI&, const cl_MI&)
2823 @cindex @code{operator * ()}
2824 Returns the product of two modular integers. One of the arguments may also
2827 @item cl_MI square (const cl_MI&)
2828 @cindex @code{square ()}
2829 Returns the square of a modular integer.
2831 @item cl_MI recip (const cl_MI& x)
2832 @cindex @code{recip ()}
2833 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
2834 must be coprime to the modulus, otherwise an error message is issued.
2836 @item cl_MI div (const cl_MI& x, const cl_MI& y)
2837 @cindex @code{div ()}
2838 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
2839 @code{y} must be coprime to the modulus, otherwise an error message is issued.
2841 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
2842 @cindex @code{expt_pos ()}
2843 @code{y} must be > 0. Returns @code{x^y}.
2845 @item cl_MI expt (const cl_MI& x, const cl_I& y)
2846 @cindex @code{expt ()}
2847 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
2848 modulus, else an error message is issued.
2850 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
2851 @cindex @code{operator << ()}
2852 Returns @code{x*2^y}.
2854 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
2855 @cindex @code{operator >> ()}
2856 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
2857 or an error message is issued.
2859 @item bool operator== (const cl_MI&, const cl_MI&)
2860 @cindex @code{operator == ()}
2861 @itemx bool operator!= (const cl_MI&, const cl_MI&)
2862 @cindex @code{operator != ()}
2863 Compares two modular integers, belonging to the same modular integer ring,
2866 @item cl_boolean zerop (const cl_MI& x)
2867 @cindex @code{zerop ()}
2868 Returns true if @code{x} is @code{0 mod N}.
2871 The following output functions are defined (see also the chapter on
2875 @item void fprint (std::ostream& stream, const cl_MI& x)
2876 @cindex @code{fprint ()}
2877 @itemx std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
2878 @cindex @code{operator << ()}
2879 Prints the modular integer @code{x} on the @code{stream}. The output may depend
2880 on the global printer settings in the variable @code{default_print_flags}.
2884 @chapter Symbolic data types
2885 @cindex symbolic type
2887 CLN implements two symbolic (non-numeric) data types: strings and symbols.
2891 @cindex @code{cl_string}
2901 implements immutable strings.
2903 Strings are constructed through the following constructors:
2906 @item cl_string (const char * s)
2907 Returns an immutable copy of the (zero-terminated) C string @code{s}.
2909 @item cl_string (const char * ptr, unsigned long len)
2910 Returns an immutable copy of the @code{len} characters at
2911 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
2914 The following functions are available on strings:
2918 Assignment from @code{cl_string} and @code{const char *}.
2921 @cindex @code{length ()}
2923 @cindex @code{strlen ()}
2924 Returns the length of the string @code{s}.
2927 @cindex @code{operator [] ()}
2928 Returns the @code{i}th character of the string @code{s}.
2929 @code{i} must be in the range @code{0 <= i < s.length()}.
2931 @item bool equal (const cl_string& s1, const cl_string& s2)
2932 @cindex @code{equal ()}
2933 Compares two strings for equality. One of the arguments may also be a
2934 plain @code{const char *}.
2939 @cindex @code{cl_symbol}
2941 Symbols are uniquified strings: all symbols with the same name are shared.
2942 This means that comparison of two symbols is fast (effectively just a pointer
2943 comparison), whereas comparison of two strings must in the worst case walk
2944 both strings until their end.
2945 Symbols are used, for example, as tags for properties, as names of variables
2946 in polynomial rings, etc.
2948 Symbols are constructed through the following constructor:
2951 @item cl_symbol (const cl_string& s)
2952 Looks up or creates a new symbol with a given name.
2955 The following operations are available on symbols:
2958 @item cl_string (const cl_symbol& sym)
2959 Conversion to @code{cl_string}: Returns the string which names the symbol
2962 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
2963 @cindex @code{equal ()}
2964 Compares two symbols for equality. This is very fast.
2968 @chapter Univariate polynomials
2970 @cindex univariate polynomial
2972 @section Univariate polynomial rings
2974 CLN implements univariate polynomials (polynomials in one variable) over an
2975 arbitrary ring. The indeterminate variable may be either unnamed (and will be
2976 printed according to @code{default_print_flags.univpoly_varname}, which
2977 defaults to @samp{x}) or carry a given name. The base ring and the
2978 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
2979 (accidentally) mix elements of different polynomial rings, e.g.
2980 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
2981 return a multivariate polynomial, but they are not yet implemented in CLN.)
2983 The classes of univariate polynomial rings are
2991 Univariate polynomial ring
2995 +----------------+-------------------+
2997 Complex polynomial ring | Modular integer polynomial ring
2998 cl_univpoly_complex_ring | cl_univpoly_modint_ring
2999 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3003 Real polynomial ring |
3004 cl_univpoly_real_ring |
3005 <cln/univpoly_real.h> |
3009 Rational polynomial ring |
3010 cl_univpoly_rational_ring |
3011 <cln/univpoly_rational.h> |
3015 Integer polynomial ring
3016 cl_univpoly_integer_ring
3017 <cln/univpoly_integer.h>
3020 and the corresponding classes of univariate polynomials are
3023 Univariate polynomial
3027 +----------------+-------------------+
3029 Complex polynomial | Modular integer polynomial
3031 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3037 <cln/univpoly_real.h> |
3041 Rational polynomial |
3043 <cln/univpoly_rational.h> |
3049 <cln/univpoly_integer.h>
3052 Univariate polynomial rings are constructed using the functions
3055 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3056 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3057 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3058 @code{R} may be an arbitrary ring. This function takes care of finding out
3059 about special cases of @code{R}, such as the rings of complex numbers,
3060 real numbers, rational numbers, integers, or modular integer rings.
3061 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3062 This ensures that two calls of this function with the same arguments will
3063 return the same polynomial ring.
3065 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3066 @cindex @code{find_univpoly_ring ()}
3067 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3068 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3069 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3070 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3071 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3072 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3073 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3074 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3075 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3076 These functions are equivalent to the general @code{find_univpoly_ring},
3077 only the return type is more specific, according to the base ring's type.
3080 @section Functions on univariate polynomials
3082 Given a univariate polynomial ring @code{R}, the following members can be used.
3085 @item cl_ring R->basering()
3086 @cindex @code{basering ()}
3087 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3089 @item cl_UP R->zero()
3090 @cindex @code{zero ()}
3091 This returns @code{0 in R}, a polynomial of degree -1.
3093 @item cl_UP R->one()
3094 @cindex @code{one ()}
3095 This returns @code{1 in R}, a polynomial of degree <= 0.
3097 @item cl_UP R->canonhom (const cl_I& x)
3098 @cindex @code{canonhom ()}
3099 This returns @code{x in R}, a polynomial of degree <= 0.
3101 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3102 @cindex @code{monomial ()}
3103 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3106 @item cl_UP R->create (sintL degree)
3107 @cindex @code{create ()}
3108 Creates a new polynomial with a given degree. The zero polynomial has degree
3109 @code{-1}. After creating the polynomial, you should put in the coefficients,
3110 using the @code{set_coeff} member function, and then call the @code{finalize}
3114 The following are the only destructive operations on univariate polynomials.
3117 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3118 @cindex @code{set_coeff ()}
3119 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3120 After changing a polynomial and before applying any "normal" operation on it,
3121 you should call its @code{finalize} member function.
3123 @item void finalize (cl_UP& x)
3124 @cindex @code{finalize ()}
3125 This function marks the endpoint of destructive modifications of a polynomial.
3126 It normalizes the internal representation so that subsequent computations have
3127 less overhead. Doing normal computations on unnormalized polynomials may
3128 produce wrong results or crash the program.
3131 The following operations are defined on univariate polynomials.
3134 @item cl_univpoly_ring x.ring ()
3135 @cindex @code{ring ()}
3136 Returns the ring to which the univariate polynomial @code{x} belongs.
3138 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3139 @cindex @code{operator + ()}
3140 Returns the sum of two univariate polynomials.
3142 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3143 @cindex @code{operator - ()}
3144 Returns the difference of two univariate polynomials.
3146 @item cl_UP operator- (const cl_UP&)
3147 Returns the negative of a univariate polynomial.
3149 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3150 @cindex @code{operator * ()}
3151 Returns the product of two univariate polynomials. One of the arguments may
3152 also be a plain integer or an element of the base ring.
3154 @item cl_UP square (const cl_UP&)
3155 @cindex @code{square ()}
3156 Returns the square of a univariate polynomial.
3158 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3159 @cindex @code{expt_pos ()}
3160 @code{y} must be > 0. Returns @code{x^y}.
3162 @item bool operator== (const cl_UP&, const cl_UP&)
3163 @cindex @code{operator == ()}
3164 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3165 @cindex @code{operator != ()}
3166 Compares two univariate polynomials, belonging to the same univariate
3167 polynomial ring, for equality.
3169 @item cl_boolean zerop (const cl_UP& x)
3170 @cindex @code{zerop ()}
3171 Returns true if @code{x} is @code{0 in R}.
3173 @item sintL degree (const cl_UP& x)
3174 @cindex @code{degree ()}
3175 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3177 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3178 @cindex @code{coeff ()}
3179 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3181 @item cl_ring_element x (const cl_ring_element& y)
3182 @cindex @code{operator () ()}
3183 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3184 then @samp{x(y)} returns the value of the substitution of @code{y} into
3187 @item cl_UP deriv (const cl_UP& x)
3188 @cindex @code{deriv ()}
3189 Returns the derivative of the polynomial @code{x} with respect to the
3190 indeterminate @code{X}.
3193 The following output functions are defined (see also the chapter on
3197 @item void fprint (std::ostream& stream, const cl_UP& x)
3198 @cindex @code{fprint ()}
3199 @itemx std::ostream& operator<< (std::ostream& stream, const cl_UP& x)
3200 @cindex @code{operator << ()}
3201 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3202 depend on the global printer settings in the variable
3203 @code{default_print_flags}.
3206 @section Special polynomials
3208 The following functions return special polynomials.
3211 @item cl_UP_I tschebychev (sintL n)
3212 @cindex @code{tschebychev ()}
3213 @cindex Chebyshev polynomial
3214 Returns the n-th Chebyshev polynomial (n >= 0).
3216 @item cl_UP_I hermite (sintL n)
3217 @cindex @code{hermite ()}
3218 @cindex Hermite polynomial
3219 Returns the n-th Hermite polynomial (n >= 0).
3221 @item cl_UP_RA legendre (sintL n)
3222 @cindex @code{legendre ()}
3223 @cindex Legende polynomial
3224 Returns the n-th Legendre polynomial (n >= 0).
3226 @item cl_UP_I laguerre (sintL n)
3227 @cindex @code{laguerre ()}
3228 @cindex Laguerre polynomial
3229 Returns the n-th Laguerre polynomial (n >= 0).
3232 Information how to derive the differential equation satisfied by each
3233 of these polynomials from their definition can be found in the
3234 @code{doc/polynomial/} directory.
3242 Using C++ as an implementation language provides
3246 Efficiency: It compiles to machine code.
3250 Portability: It runs on all platforms supporting a C++ compiler. Because
3251 of the availability of GNU C++, this includes all currently used 32-bit and
3252 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3255 Type safety: The C++ compilers knows about the number types and complains if,
3256 for example, you try to assign a float to an integer variable. However,
3257 a drawback is that C++ doesn't know about generic types, hence a restriction
3258 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3259 arguments belong to the same modular ring cannot be expressed as a compile-time
3263 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3264 @code{=}, @code{==}, ... can be used in infix notation, which is more
3265 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3268 With these language features, there is no need for two separate languages,
3269 one for the implementation of the library and one in which the library's users
3270 can program. This means that a prototype implementation of an algorithm
3271 can be integrated into the library immediately after it has been tested and
3272 debugged. No need to rewrite it in a low-level language after having prototyped
3273 in a high-level language.
3276 @section Memory efficiency
3278 In order to save memory allocations, CLN implements:
3282 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3285 @cindex garbage collection
3286 @cindex reference counting
3287 Garbage collection: A reference counting mechanism makes sure that any
3288 number object's storage is freed immediately when the last reference to the
3291 @cindex immediate numbers
3292 Small integers are represented as immediate values instead of pointers
3293 to heap allocated storage. This means that integers @code{> -2^29},
3294 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3299 @section Speed efficiency
3301 Speed efficiency is obtained by the combination of the following tricks
3306 Small integers, being represented as immediate values, don't require
3307 memory access, just a couple of instructions for each elementary operation.
3309 The kernel of CLN has been written in assembly language for some CPUs
3310 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3312 On all CPUs, CLN may be configured to use the superefficient low-level
3313 routines from GNU GMP version 3.
3315 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3316 algorithm, the Karatsuba multiplication, which is an
3327 For very large numbers (more than 12000 decimal digits), CLN uses
3329 Sch{@"o}nhage-Strassen
3330 @cindex Sch{@"o}nhage-Strassen multiplication
3334 @cindex Schönhage-Strassen multiplication
3336 multiplication, which is an asymptotically optimal multiplication
3339 These fast multiplication algorithms also give improvements in the speed
3340 of division and radix conversion.
3344 @section Garbage collection
3345 @cindex garbage collection
3347 All the number classes are reference count classes: They only contain a pointer
3348 to an object in the heap. Upon construction, assignment and destruction of
3349 number objects, only the objects' reference count are manipulated.
3351 Memory occupied by number objects are automatically reclaimed as soon as
3352 their reference count drops to zero.
3354 For number rings, another strategy is implemented: There is a cache of,
3355 for example, the modular integer rings. A modular integer ring is destroyed
3356 only if its reference count dropped to zero and the cache is about to be
3357 resized. The effect of this strategy is that recently used rings remain
3358 cached, whereas undue memory consumption through cached rings is avoided.
3361 @chapter Using the library
3363 For the following discussion, we will assume that you have installed
3364 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3365 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3366 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3367 environment variables, or directly substitute the appropriate values.
3370 @section Compiler options
3371 @cindex compiler options
3373 Until you have installed CLN in a public place, the following options are
3376 When you compile CLN application code, add the flags
3378 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3380 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3381 When you link CLN application code to form an executable, add the flags
3383 $CLN_TARGETDIR/src/libcln.a
3385 to the C/C++ compiler's command line (@code{make} variable LIBS).
3387 If you did a @code{make install}, the include files are installed in a
3388 public directory (normally @code{/usr/local/include}), hence you don't
3389 need special flags for compiling. The library has been installed to a
3390 public directory as well (normally @code{/usr/local/lib}), hence when
3391 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3393 Since CLN version 1.1, there are two tools to make the creation of
3394 software packages that use CLN easier:
3397 @cindex @code{cln-config}
3398 @code{cln-config} is a shell script that you can use to determine the
3399 compiler and linker command line options required to compile and link a
3400 program with CLN. Start it with @code{--help} to learn about its options
3401 or consult the manpage that comes with it.
3403 @cindex @code{AC_PATH_CLN}
3404 @code{AC_PATH_CLN} is for packages configured using GNU automake.
3407 @code{AC_PATH_CLN([@var{MIN-VERSION}, [@var{ACTION-IF-FOUND} [, @var{ACTION-IF-NOT-FOUND}]]])}
3409 This macro determines the location of CLN using @code{cln-config}, which
3410 is either found in the user's path, or from the environment variable
3411 @code{CLN_CONFIG}. It tests the installed libraries to make sure that
3412 their version is not earlier than @var{MIN-VERSION} (a default version
3413 will be used if not specified). If the required version was found, sets
3414 the @env{CLN_CPPFLAGS} and the @env{CLN_LIBS} variables. This
3415 macro is in the file @file{cln.m4} which is installed in
3416 @file{$datadir/aclocal}. Note that if automake was installed with a
3417 different @samp{--prefix} than CLN, you will either have to manually
3418 move @file{cln.m4} to automake's @file{$datadir/aclocal}, or give
3419 aclocal the @samp{-I} option when running it. Here is a possible example
3420 to be included in your package's @file{configure.ac}:
3422 AC_PATH_CLN(1.1.0, [
3423 LIBS="$LIBS $CLN_LIBS"
3424 CPPFLAGS="$CPPFLAGS $CLN_CPPFLAGS"
3425 ], AC_MSG_ERROR([No suitable installed version of CLN could be found.]))
3430 @section Compatibility to old CLN versions
3432 @cindex compatibility
3434 As of CLN version 1.1 all non-macro identifiers were hidden in namespace
3435 @code{cln} in order to avoid potential name clashes with other C++
3436 libraries. If you have an old application, you will have to manually
3437 port it to the new scheme. The following principles will help during
3441 All headers are now in a separate subdirectory. Instead of including
3442 @code{cl_}@var{something}@code{.h}, include
3443 @code{cln/}@var{something}@code{.h} now.
3445 All public identifiers (typenames and functions) have lost their
3446 @code{cl_} prefix. Exceptions are all the typenames of number types,
3447 (cl_N, cl_I, cl_MI, @dots{}), rings, symbolic types (cl_string,
3448 cl_symbol) and polynomials (cl_UP_@var{type}). (This is because their
3449 names would not be mnemonic enough once the namespace @code{cln} is
3450 imported. Even in a namespace we favor @code{cl_N} over @code{N}.)
3452 All public @emph{functions} that had by a @code{cl_} in their name still
3453 carry that @code{cl_} if it is intrinsic part of a typename (as in
3454 @code{cl_I_to_int ()}).
3456 When developing other libraries, please keep in mind not to import the
3457 namespace @code{cln} in one of your public header files by saying
3458 @code{using namespace cln;}. This would propagate to other applications
3459 and can cause name clashes there.
3462 @section Include files
3463 @cindex include files
3464 @cindex header files
3466 Here is a summary of the include files and their contents.
3469 @item <cln/object.h>
3470 General definitions, reference counting, garbage collection.
3471 @item <cln/number.h>
3472 The class cl_number.
3473 @item <cln/complex.h>
3474 Functions for class cl_N, the complex numbers.
3476 Functions for class cl_R, the real numbers.
3478 Functions for class cl_F, the floats.
3479 @item <cln/sfloat.h>
3480 Functions for class cl_SF, the short-floats.
3481 @item <cln/ffloat.h>
3482 Functions for class cl_FF, the single-floats.
3483 @item <cln/dfloat.h>
3484 Functions for class cl_DF, the double-floats.
3485 @item <cln/lfloat.h>
3486 Functions for class cl_LF, the long-floats.
3487 @item <cln/rational.h>
3488 Functions for class cl_RA, the rational numbers.
3489 @item <cln/integer.h>
3490 Functions for class cl_I, the integers.
3493 @item <cln/complex_io.h>
3494 Input/Output for class cl_N, the complex numbers.
3495 @item <cln/real_io.h>
3496 Input/Output for class cl_R, the real numbers.
3497 @item <cln/float_io.h>
3498 Input/Output for class cl_F, the floats.
3499 @item <cln/sfloat_io.h>
3500 Input/Output for class cl_SF, the short-floats.
3501 @item <cln/ffloat_io.h>
3502 Input/Output for class cl_FF, the single-floats.
3503 @item <cln/dfloat_io.h>
3504 Input/Output for class cl_DF, the double-floats.
3505 @item <cln/lfloat_io.h>
3506 Input/Output for class cl_LF, the long-floats.
3507 @item <cln/rational_io.h>
3508 Input/Output for class cl_RA, the rational numbers.
3509 @item <cln/integer_io.h>
3510 Input/Output for class cl_I, the integers.
3512 Flags for customizing input operations.
3513 @item <cln/output.h>
3514 Flags for customizing output operations.
3515 @item <cln/malloc.h>
3516 @code{malloc_hook}, @code{free_hook}.
3519 @item <cln/condition.h>
3520 Conditions/exceptions.
3521 @item <cln/string.h>
3523 @item <cln/symbol.h>
3525 @item <cln/proplist.h>
3529 @item <cln/null_ring.h>
3531 @item <cln/complex_ring.h>
3532 The ring of complex numbers.
3533 @item <cln/real_ring.h>
3534 The ring of real numbers.
3535 @item <cln/rational_ring.h>
3536 The ring of rational numbers.
3537 @item <cln/integer_ring.h>
3538 The ring of integers.
3539 @item <cln/numtheory.h>
3540 Number threory functions.
3541 @item <cln/modinteger.h>
3547 @item <cln/GV_number.h>
3548 General vectors over cl_number.
3549 @item <cln/GV_complex.h>
3550 General vectors over cl_N.
3551 @item <cln/GV_real.h>
3552 General vectors over cl_R.
3553 @item <cln/GV_rational.h>
3554 General vectors over cl_RA.
3555 @item <cln/GV_integer.h>
3556 General vectors over cl_I.
3557 @item <cln/GV_modinteger.h>
3558 General vectors of modular integers.
3561 @item <cln/SV_number.h>
3562 Simple vectors over cl_number.
3563 @item <cln/SV_complex.h>
3564 Simple vectors over cl_N.
3565 @item <cln/SV_real.h>
3566 Simple vectors over cl_R.
3567 @item <cln/SV_rational.h>
3568 Simple vectors over cl_RA.
3569 @item <cln/SV_integer.h>
3570 Simple vectors over cl_I.
3571 @item <cln/SV_ringelt.h>
3572 Simple vectors of general ring elements.
3573 @item <cln/univpoly.h>
3574 Univariate polynomials.
3575 @item <cln/univpoly_integer.h>
3576 Univariate polynomials over the integers.
3577 @item <cln/univpoly_rational.h>
3578 Univariate polynomials over the rational numbers.
3579 @item <cln/univpoly_real.h>
3580 Univariate polynomials over the real numbers.
3581 @item <cln/univpoly_complex.h>
3582 Univariate polynomials over the complex numbers.
3583 @item <cln/univpoly_modint.h>
3584 Univariate polynomials over modular integer rings.
3585 @item <cln/timing.h>
3588 Includes all of the above.
3594 A function which computes the nth Fibonacci number can be written as follows.
3595 @cindex Fibonacci number
3598 #include <cln/integer.h>
3599 #include <cln/real.h>
3600 using namespace cln;
3602 // Returns F_n, computed as the nearest integer to
3603 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3604 const cl_I fibonacci (int n)
3606 // Need a precision of ((1+sqrt(5))/2)^-n.
3607 float_format_t prec = float_format((int)(0.208987641*n+5));
3608 cl_R sqrt5 = sqrt(cl_float(5,prec));
3609 cl_R phi = (1+sqrt5)/2;
3610 return round1( expt(phi,n)/sqrt5 );
3614 Let's explain what is going on in detail.
3616 The include file @code{<cln/integer.h>} is necessary because the type
3617 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3618 is needed for the type @code{cl_R} and the floating point number functions.
3619 The order of the include files does not matter. In order not to write
3620 out @code{cln::}@var{foo} in this simple example we can safely import
3621 the whole namespace @code{cln}.
3623 Then comes the function declaration. The argument is an @code{int}, the
3624 result an integer. The return type is defined as @samp{const cl_I}, not
3625 simply @samp{cl_I}, because that allows the compiler to detect typos like
3626 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3627 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3628 number). We use the most specialized possible return type because functions
3629 which call @samp{fibonacci} will be able to profit from the compiler's type
3630 analysis: Adding two integers is slightly more efficient than adding the
3631 same objects declared as complex numbers, because it needs less type
3632 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3633 the size of the resulting executable program.
3635 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3636 integer. In order to get a correct result, the absolute error should be less
3637 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3638 To this end, the first line computes a floating point precision for sqrt(5)
3641 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3642 number and than taking the square root. The converse, first taking the square
3643 root of 5, and then converting to the desired precision, would not work in
3644 CLN: The square root would be computed to a default precision (normally
3645 single-float precision), and the following conversion could not help about
3646 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3647 system and does not represent sqrt(5) in a non-numeric way.
3649 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3650 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3651 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3652 @code{cl_N} because a @samp{round1} does not exist for general complex
3655 When the function returns, all the local variables in the function are
3656 automatically reclaimed (garbage collected). Only the result survives and
3657 gets passed to the caller.
3659 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3660 contains this implementation together with an even faster algorithm.
3662 @section Debugging support
3665 When debugging a CLN application with GNU @code{gdb}, two facilities are
3666 available from the library:
3669 @item The library does type checks, range checks, consistency checks at
3670 many places. When one of these fails, the function @code{cl_abort()} is
3671 called. Its default implementation is to perform an @code{exit(1)}, so
3672 you won't have a core dump. But for debugging, it is best to set a
3673 breakpoint at this function:
3675 (gdb) break cl_abort
3677 When this breakpoint is hit, look at the stack's backtrace:
3682 @item The debugger's normal @code{print} command doesn't know about
3683 CLN's types and therefore prints mostly useless hexadecimal addresses.
3684 CLN offers a function @code{cl_print}, callable from the debugger,
3685 for printing number objects. In order to get this function, you have
3686 to define the macro @samp{CL_DEBUG} and then include all the header files
3687 for which you want @code{cl_print} debugging support. For example:
3688 @cindex @code{CL_DEBUG}
3691 #include <cln/string.h>
3693 Now, if you have in your program a variable @code{cl_string s}, and
3694 inspect it under @code{gdb}, the output may look like this:
3697 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3698 word = 134568800@}@}, @}
3699 (gdb) call cl_print(s)
3703 Note that the output of @code{cl_print} goes to the program's error output,
3704 not to gdb's standard output.
3706 Note, however, that the above facility does not work with all CLN types,
3707 only with number objects and similar. Therefore CLN offers a member function
3708 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3709 is needed for this member function to be implemented. Under @code{gdb},
3710 you call it like this:
3711 @cindex @code{debug_print ()}
3714 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3715 word = 134568800@}@}, @}
3716 (gdb) call s.debug_print()
3719 >call ($1).debug_print()
3724 Unfortunately, this feature does not seem to work under all circumstances.
3728 @chapter Customizing
3731 @section Error handling
3733 When a fatal error occurs, an error message is output to the standard error
3734 output stream, and the function @code{cl_abort} is called. The default
3735 version of this function (provided in the library) terminates the application.
3736 To catch such a fatal error, you need to define the function @code{cl_abort}
3737 yourself, with the prototype
3739 #include <cln/abort.h>
3740 void cl_abort (void);
3742 @cindex @code{cl_abort ()}
3743 This function must not return control to its caller.
3746 @section Floating-point underflow
3749 Floating point underflow denotes the situation when a floating-point number
3750 is to be created which is so close to @code{0} that its exponent is too
3751 low to be represented internally. By default, this causes a fatal error.
3752 If you set the global variable
3754 cl_boolean cl_inhibit_floating_point_underflow
3756 to @code{cl_true}, the error will be inhibited, and a floating-point zero
3757 will be generated instead. The default value of
3758 @code{cl_inhibit_floating_point_underflow} is @code{cl_false}.
3761 @section Customizing I/O
3763 The output of the function @code{fprint} may be customized by changing the
3764 value of the global variable @code{default_print_flags}.
3765 @cindex @code{default_print_flags}
3768 @section Customizing the memory allocator
3770 Every memory allocation of CLN is done through the function pointer
3771 @code{malloc_hook}. Freeing of this memory is done through the function
3772 pointer @code{free_hook}. The default versions of these functions,
3773 provided in the library, call @code{malloc} and @code{free} and check
3774 the @code{malloc} result against @code{NULL}.
3775 If you want to provide another memory allocator, you need to define
3776 the variables @code{malloc_hook} and @code{free_hook} yourself,
3779 #include <cln/malloc.h>
3781 void* (*malloc_hook) (size_t size) = @dots{};
3782 void (*free_hook) (void* ptr) = @dots{};
3785 @cindex @code{malloc_hook ()}
3786 @cindex @code{free_hook ()}
3787 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
3789 It is not possible to change the memory allocator at runtime, because
3790 it is already called at program startup by the constructors of some
3803 @c Table of contents