1 \input texinfo @c -*-texinfo-*-
4 @settitle CLN, a Class Library for Numbers
5 @c @setchapternewpage off
10 @c I hate putting "@noindent" in front of every paragraph.
18 @c Don't need the other types of indices.
29 This file documents @sc{cln}, a Class Library for Numbers.
31 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
32 Richard Kreckel, @code{<kreckel@@ginac.de>}.
34 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
36 Permission is granted to make and distribute verbatim copies of
37 this manual provided the copyright notice and this permission notice
38 are preserved on all copies.
41 Permission is granted to process this file through TeX and print the
42 results, provided the printed document carries copying permission
43 notice identical to this one except for the removal of this paragraph
44 (this paragraph not being relevant to the printed manual).
47 Permission is granted to copy and distribute modified versions of this
48 manual under the conditions for verbatim copying, provided that the entire
49 resulting derived work is distributed under the terms of a permission
50 notice identical to this one.
52 Permission is granted to copy and distribute translations of this manual
53 into another language, under the above conditions for modified versions,
54 except that this permission notice may be stated in a translation approved
60 @c prevent ugly black rectangles on overfull hbox lines:
63 @title CLN, a Class Library for Numbers
65 @author by Bruno Haible
67 @vskip 0pt plus 1filll
68 Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
71 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
72 Richard Kreckel, @code{<kreckel@@ginac.de>}.
74 Permission is granted to make and distribute verbatim copies of
75 this manual provided the copyright notice and this permission notice
76 are preserved on all copies.
78 Permission is granted to copy and distribute modified versions of this
79 manual under the conditions for verbatim copying, provided that the entire
80 resulting derived work is distributed under the terms of a permission
81 notice identical to this one.
83 Permission is granted to copy and distribute translations of this manual
84 into another language, under the above conditions for modified versions,
85 except that this permission notice may be stated in a translation approved
92 @node Top, Introduction, (dir), (dir)
95 @c * Introduction:: Introduction
101 * Ordinary number types::
102 * Functions on numbers::
106 * Symbolic data types::
107 * Univariate polynomials::
109 * Using the library::
113 --- The Detailed Node Listing ---
118 * Building the library::
119 * Installing the library::
128 Ordinary number types
131 * Floating-point numbers::
137 * Constructing numbers::
138 * Elementary functions::
139 * Elementary rational functions::
140 * Elementary complex functions::
142 * Rounding functions::
144 * Transcendental functions::
145 * Functions on integers::
146 * Functions on floating-point numbers::
147 * Conversion functions::
148 * Random number generators::
149 * Obfuscating operators::
153 * Constructing integers::
154 * Constructing rational numbers::
155 * Constructing floating-point numbers::
156 * Constructing complex numbers::
158 Transcendental functions
160 * Exponential and logarithmic functions::
161 * Trigonometric functions::
162 * Hyperbolic functions::
166 Functions on integers
168 * Logical functions::
169 * Number theoretic functions::
170 * Combinatorial functions::
174 * Conversion to floating-point numbers::
175 * Conversion to rational numbers::
179 * Internal and printed representation::
185 * Modular integer rings::
186 * Functions on modular integers::
193 Univariate polynomials
195 * Univariate polynomial rings::
196 * Functions on univariate polynomials::
197 * Special polynomials::
202 * Memory efficiency::
204 * Garbage collection::
211 * Debugging support::
216 * Floating-point underflow::
218 * Customizing the memory allocator::
221 @node Introduction, Installation, Top, Top
222 @comment node-name, next, previous, up
223 @chapter Introduction
226 CLN is a library for computations with all kinds of numbers.
227 It has a rich set of number classes:
231 Integers (with unlimited precision),
237 Floating-point numbers:
247 Long float (with unlimited precision),
254 Modular integers (integers modulo a fixed integer),
257 Univariate polynomials.
261 The subtypes of the complex numbers among these are exactly the
262 types of numbers known to the Common Lisp language. Therefore
263 @code{CLN} can be used for Common Lisp implementations, giving
264 @samp{CLN} another meaning: it becomes an abbreviation of
265 ``Common Lisp Numbers''.
268 The CLN package implements
272 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
273 comparisons, @dots{}),
276 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
279 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
280 functions and their inverse functions).
284 CLN is a C++ library. Using C++ as an implementation language provides
288 efficiency: it compiles to machine code,
290 type safety: the C++ compiler knows about the number types and complains
291 if, for example, you try to assign a float to an integer variable.
293 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
294 @code{==}, @dots{} operators as in C or C++.
298 CLN is memory efficient:
302 Small integers and short floats are immediate, not heap allocated.
304 Heap-allocated memory is reclaimed through an automatic, non-interruptive
309 CLN is speed efficient:
313 The kernel of CLN has been written in assembly language for some CPUs
314 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
316 On all CPUs, CLN uses the superefficient low-level routines from GNU
319 It uses Karatsuba multiplication, which is significantly faster
320 for large numbers than the standard multiplication algorithm.
322 For very large numbers (more than 12000 decimal digits), it uses
324 Sch{@"o}nhage-Strassen
329 multiplication, which is an asymptotically
330 optimal multiplication algorithm, for multiplication, division and
335 CLN aims at being easily integrated into larger software packages:
339 The garbage collection imposes no burden on the main application.
341 The library provides hooks for memory allocation and exceptions.
345 @node Installation, Ordinary number types, Introduction, Top
346 @chapter Installation
348 This section describes how to install the CLN package on your system.
353 * Building the library::
354 * Installing the library::
358 @node Prerequisites, Building the library, Installation, Installation
359 @section Prerequisites
367 @node C++ compiler, Make utility, Prerequisites, Prerequisites
368 @subsection C++ compiler
370 To build CLN, you need a C++ compiler.
371 Actually, you need GNU @code{g++ 2.7.0} or newer.
372 On HPPA, you need GNU @code{g++ 2.8.0} or newer.
373 I recommend GNU @code{egcs 1.1} or newer.
375 The following C++ features are used:
376 classes, member functions,
377 overloading of functions and operators,
378 constructors and destructors, inline, const,
379 multiple inheritance, templates.
381 The following C++ features are not used:
382 @code{new}, @code{delete}, virtual inheritance,
385 CLN relies on semi-automatic ordering of initializations
386 of static and global variables, a feature which I could
387 implement for GNU g++ only.
390 @comment cl_modules.h requires g++
391 Therefore nearly any C++ compiler will do.
393 The following C++ compilers are known to compile CLN:
396 GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
401 The following C++ compilers are known to be unusable for CLN:
404 On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
405 in lines containing @code{#if} or @code{#elif} preprocessor commands.
407 On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
408 in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
409 to have default constructors, and because it probably miscompiles the
410 integer multiplication routines.
412 On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
413 @code{short}s to @code{int}s by zero-extend.
417 On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
418 initializations will not work.
422 @node Make utility, Sed utility, C++ compiler, Prerequisites
423 @subsection Make utility
425 To build CLN, you also need to have GNU @code{make} installed.
427 @node Sed utility, , Make utility, Prerequisites
428 @subsection Sed utility
430 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
431 This is because the libtool script, which creates the CLN library, relies
432 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
436 @node Building the library, Installing the library, Prerequisites, Installation
437 @section Building the library
439 As with any autoconfiguring GNU software, installation is as easy as this:
447 If on your system, @samp{make} is not GNU @code{make}, you have to use
448 @samp{gmake} instead of @samp{make} above.
450 The @code{configure} command checks out some features of your system and
451 C++ compiler and builds the @code{Makefile}s. The @code{make} command
452 builds the library. This step may take 4 hours on an average workstation.
453 The @code{make check} runs some test to check that no important subroutine
454 has been miscompiled.
456 The @code{configure} command accepts options. To get a summary of them, try
462 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
464 You can specify the C compiler, the C++ compiler and their options through
465 the following environment variables when running @code{configure}:
469 Specifies the C compiler.
472 Flags to be given to the C compiler when compiling programs (not when linking).
475 Specifies the C++ compiler.
478 Flags to be given to the C++ compiler when compiling programs (not when linking).
484 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
485 $ CC="gcc -V 2.7.2" CFLAGS="-O -g" \
486 CXX="g++ -V 2.7.2" CXXFLAGS="-O -g" ./configure
487 $ CC="gcc -V 2.8.1" CFLAGS="-O -fno-exceptions" \
488 CXX="g++ -V 2.8.1" CXXFLAGS="-O -fno-exceptions" ./configure
489 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O2 -fno-exceptions" \
490 CXX="g++ -V egcs-2.91.60" CFLAGS="-O2 -fno-exceptions" ./configure
493 @comment cl_modules.h requires g++
494 You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
495 compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
498 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
499 $ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
502 On SGI Irix 5, if you wish not to use @code{g++}:
505 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
508 On SGI Irix 6, if you wish not to use @code{g++}:
511 $ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
512 ./configure --without-gmp
513 $ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
514 -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
515 ./configure --without-gmp
519 Note that for these environment variables to take effect, you have to set
520 them (assuming a Bourne-compatible shell) on the same line as the
521 @code{configure} command. If you made the settings in earlier shell
522 commands, you have to @code{export} the environment variables before
523 calling @code{configure}. In a @code{csh} shell, you have to use the
524 @samp{setenv} command for setting each of the environment variables.
526 On Linux, @code{g++} needs 15 MB to compile the tests. So you should better
527 have 17 MB swap space and 1 MB room in $TMPDIR.
529 If you use @code{g++} version 2.7.x, don't add @samp{-O2} to the CXXFLAGS,
530 because @samp{g++ -O} generates better code for CLN than @samp{g++ -O2}.
532 If you use @code{g++} version 2.8.x or egcs-2.91.x (a.k.a. egcs-1.1) or
533 gcc-2.95.x, I recommend adding @samp{-fno-exceptions} to the CXXFLAGS.
534 This will likely generate better code.
536 If you use @code{g++} version egcs-2.91.x (egcs-1.1) or gcc-2.95.x on Sparc,
537 add either @samp{-O} or @samp{-O2 -fno-schedule-insns} to the CXXFLAGS.
538 With full @samp{-O2}, @code{g++} miscompiles the division routines. Also, for
539 --enable-shared to work, you need egcs-1.1.2 or newer.
541 On MIPS (SGI Irix 6), pass option @code{--without-gmp} to configure. gmp does
542 not work when compiled in @samp{n32} binary format on Irix.
544 By default, only a static library is built. You can build CLN as a shared
545 library too, by calling @code{configure} with the option @samp{--enable-shared}.
546 To get it built as a shared library only, call @code{configure} with the options
547 @samp{--enable-shared --disable-static}.
549 If you use @code{g++} version egcs-2.91.x (egcs-1.1) on Sparc, you cannot
550 use @samp{--enable-shared} because @code{g++} would miscompile parts of the
554 @node Installing the library, Cleaning up, Building the library, Installation
555 @section Installing the library
557 As with any autoconfiguring GNU software, installation is as easy as this:
563 The @samp{make install} command installs the library and the include files
564 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
565 if you haven't specified a @code{--prefix} option to @code{configure}).
566 This step may require superuser privileges.
568 If you have already built the library and wish to install it, but didn't
569 specify @code{--prefix=@dots{}} at configure time, just re-run
570 @code{configure}, giving it the same options as the first time, plus
571 the @code{--prefix=@dots{}} option.
574 @node Cleaning up, , Installing the library, Installation
577 You can remove system-dependent files generated by @code{make} through
583 You can remove all files generated by @code{make}, thus reverting to a
584 virgin distribution of CLN, through
591 @node Ordinary number types, Functions on numbers, Installation, Top
592 @chapter Ordinary number types
594 CLN implements the following class hierarchy:
602 Real or complex number
611 +-------------------+-------------------+
613 Rational number Floating-point number
615 <cl_rational.h> <cl_float.h>
617 | +-------------+-------------+-------------+
619 cl_I Short-Float Single-Float Double-Float Long-Float
620 <cl_integer.h> cl_SF cl_FF cl_DF cl_LF
621 <cl_sfloat.h> <cl_ffloat.h> <cl_dfloat.h> <cl_lfloat.h>
624 The base class @code{cl_number} is an abstract base class.
625 It is not useful to declare a variable of this type except if you want
626 to completely disable compile-time type checking and use run-time type
629 The class @code{cl_N} comprises real and complex numbers. There is
630 no special class for complex numbers since complex numbers with imaginary
631 part @code{0} are automatically converted to real numbers.
633 The class @code{cl_R} comprises real numbers of different kinds. It is an
636 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
637 integers. There is no special class for non-integral rational numbers
638 since rational numbers with denominator @code{1} are automatically converted
641 The class @code{cl_F} implements floating-point approximations to real numbers.
642 It is an abstract class.
647 * Floating-point numbers::
652 @node Exact numbers, Floating-point numbers, Ordinary number types, Ordinary number types
653 @section Exact numbers
655 Some numbers are represented as exact numbers: there is no loss of information
656 when such a number is converted from its mathematical value to its internal
657 representation. On exact numbers, the elementary operations (@code{+},
658 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
661 In CLN, the exact numbers are:
665 rational numbers (including integers),
667 complex numbers whose real and imaginary parts are both rational numbers.
670 Rational numbers are always normalized to the form
671 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
672 are coprime integers and the denominator is positive. If the resulting
673 denominator is @code{1}, the rational number is converted to an integer.
675 Small integers (typically in the range @code{-2^30}@dots{}@code{2^30-1},
676 for 32-bit machines) are especially efficient, because they consume no heap
677 allocation. Otherwise the distinction between these immediate integers
678 (called ``fixnums'') and heap allocated integers (called ``bignums'')
679 is completely transparent.
682 @node Floating-point numbers, Complex numbers, Exact numbers, Ordinary number types
683 @section Floating-point numbers
685 Not all real numbers can be represented exactly. (There is an easy mathematical
686 proof for this: Only a countable set of numbers can be stored exactly in
687 a computer, even if one assumes that it has unlimited storage. But there
688 are uncountably many real numbers.) So some approximation is needed.
689 CLN implements ordinary floating-point numbers, with mantissa and exponent.
691 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
692 only return approximate results. For example, the value of the expression
693 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
694 @samp{0.7}. Rounding errors like this one are inevitable when computing
695 with floating-point numbers.
697 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
698 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
699 rule: It first computes the exact mathematical result and then returns the
700 floating-point number which is nearest to this. If two floating-point numbers
701 are equally distant from the ideal result, the one with a @code{0} in its least
702 significant mantissa bit is chosen.
704 Similarly, testing floating point numbers for equality @samp{x == y}
705 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
706 for some well-chosen @code{epsilon}.
708 Floating point numbers come in four flavors:
712 Short floats, type @code{cl_SF}.
713 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
714 and 17 mantissa bits (including the ``hidden'' bit).
715 They don't consume heap allocation.
718 Single floats, type @code{cl_FF}.
719 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
720 and 24 mantissa bits (including the ``hidden'' bit).
721 In CLN, they are represented as IEEE single-precision floating point numbers.
722 This corresponds closely to the C/C++ type @samp{float}.
725 Double floats, type @code{cl_DF}.
726 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
727 and 53 mantissa bits (including the ``hidden'' bit).
728 In CLN, they are represented as IEEE double-precision floating point numbers.
729 This corresponds closely to the C/C++ type @samp{double}.
732 Long floats, type @code{cl_LF}.
733 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
734 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
735 The precision of a long float is unlimited, but once created, a long float
736 has a fixed precision. (No ``lazy recomputation''.)
739 Of course, computations with long floats are more expensive than those
740 with smaller floating-point formats.
742 CLN does not implement features like NaNs, denormalized numbers and
743 gradual underflow. If the exponent range of some floating-point type
744 is too limited for your application, choose another floating-point type
745 with larger exponent range.
747 As a user of CLN, you can forget about the differences between the
748 four floating-point types and just declare all your floating-point
749 variables as being of type @code{cl_F}. This has the advantage that
750 when you change the precision of some computation (say, from @code{cl_DF}
751 to @code{cl_LF}), you don't have to change the code, only the precision
752 of the initial values. Also, many transcendental functions have been
753 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
754 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
755 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
756 the floating point contagion rule happened to change in the future.)
759 @node Complex numbers, Conversions, Floating-point numbers, Ordinary number types
760 @section Complex numbers
762 Complex numbers, as implemented by the class @code{cl_N}, have a real
763 part and an imaginary part, both real numbers. A complex number whose
764 imaginary part is the exact number @code{0} is automatically converted
767 Complex numbers can arise from real numbers alone, for example
768 through application of @code{sqrt} or transcendental functions.
771 @node Conversions, , Complex numbers, Ordinary number types
774 Conversions from any class to any its superclasses (``base classes'' in
775 C++ terminology) is done automatically.
777 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
778 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
779 @code{cl_N} and @code{cl_number}.
781 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
782 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
783 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
784 efficiency. Their range is therefore limited:
788 The conversion from @samp{int} works only if the argument is < 2^29 and > -2^29.
790 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
793 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
794 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
795 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
797 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
798 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
799 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
800 @samp{cl_I}, first convert it to an @samp{unsigned long}.
802 Conversions from the C built-in type @samp{float} are provided for the classes
803 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
805 Conversions from the C built-in type @samp{double} are provided for the classes
806 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
808 Conversions from @samp{const char *} are provided for the classes
809 @code{cl_I}, @code{cl_RA},
810 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
811 @code{cl_R}, @code{cl_N}.
812 The easiest way to specify a value which is outside of the range of the
813 C++ built-in types is therefore to specify it as a string, like this:
815 cl_I order_of_rubiks_cube_group = "43252003274489856000";
817 Note that this conversion is done at runtime, not at compile-time.
819 Conversions from @code{cl_I} to the C built-in types @samp{int},
820 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
824 @item int cl_I_to_int (const cl_I& x)
825 @itemx unsigned int cl_I_to_uint (const cl_I& x)
826 @itemx long cl_I_to_long (const cl_I& x)
827 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
828 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
829 representable in the range of @var{ctype}, a runtime error occurs.
832 Conversions from the classes @code{cl_I}, @code{cl_RA},
833 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
835 to the C built-in types @samp{float} and @samp{double} are provided through
839 @item float cl_float_approx (const @var{type}& x)
840 @itemx double cl_double_approx (const @var{type}& x)
841 Returns an approximation of @code{x} of C type @var{ctype}.
842 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
843 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
846 Conversions from any class to any of its subclasses (``derived classes'' in
847 C++ terminology) are not provided. Instead, you can assert and check
848 that a value belongs to a certain subclass, and return it as element of that
849 class, using the @samp{As} and @samp{The} macros.
850 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
851 @var{type} and returns it as such.
852 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
853 @var{type} and returns it as such. It is your responsibility to ensure
854 that this assumption is valid.
860 if (!(x >= 0)) abort();
861 cl_I ten_x = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
862 // In general, it would be a rational number.
867 @node Functions on numbers, Input/Output, Ordinary number types, Top
868 @chapter Functions on numbers
870 Each of the number classes declares its mathematical operations in the
871 corresponding include file. For example, if your code operates with
872 objects of type @code{cl_I}, it should @code{#include <cl_integer.h>}.
876 * Constructing numbers::
877 * Elementary functions::
878 * Elementary rational functions::
879 * Elementary complex functions::
881 * Rounding functions::
883 * Transcendental functions::
884 * Functions on integers::
885 * Functions on floating-point numbers::
886 * Conversion functions::
887 * Random number generators::
888 * Obfuscating operators::
891 @node Constructing numbers, Elementary functions, Functions on numbers, Functions on numbers
892 @section Constructing numbers
894 Here is how to create number objects ``from nothing''.
898 * Constructing integers::
899 * Constructing rational numbers::
900 * Constructing floating-point numbers::
901 * Constructing complex numbers::
904 @node Constructing integers, Constructing rational numbers, Constructing numbers, Constructing numbers
905 @subsection Constructing integers
907 @code{cl_I} objects are most easily constructed from C integers and from
908 strings. See @ref{Conversions}.
911 @node Constructing rational numbers, Constructing floating-point numbers, Constructing integers, Constructing numbers
912 @subsection Constructing rational numbers
914 @code{cl_RA} objects can be constructed from strings. The syntax
915 for rational numbers is described in @ref{Internal and printed representation}.
916 Another standard way to produce a rational number is through application
917 of @samp{operator /} or @samp{recip} on integers.
920 @node Constructing floating-point numbers, Constructing complex numbers, Constructing rational numbers, Constructing numbers
921 @subsection Constructing floating-point numbers
923 @code{cl_F} objects with low precision are most easily constructed from
924 C @samp{float} and @samp{double}. See @ref{Conversions}.
926 To construct a @code{cl_F} with high precision, you can use the conversion
927 from @samp{const char *}, but you have to specify the desired precision
928 within the string. (See @ref{Internal and printed representation}.)
931 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
933 will set @samp{e} to the given value, with a precision of 40 decimal digits.
935 The programmatic way to construct a @code{cl_F} with high precision is
936 through the @code{cl_float} conversion function, see
937 @ref{Conversion to floating-point numbers}. For example, to compute
938 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
939 and then apply the exponential function:
941 cl_float_format_t precision = cl_float_format(40);
942 cl_F e = exp(cl_float(1,precision));
946 @node Constructing complex numbers, , Constructing floating-point numbers, Constructing numbers
947 @subsection Constructing complex numbers
949 Non-real @code{cl_N} objects are normally constructed through the function
951 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
953 See @ref{Elementary complex functions}.
956 @node Elementary functions, Elementary rational functions, Constructing numbers, Functions on numbers
957 @section Elementary functions
959 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
960 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
961 defines the following operations:
964 @item @var{type} operator + (const @var{type}&, const @var{type}&)
967 @item @var{type} operator - (const @var{type}&, const @var{type}&)
970 @item @var{type} operator - (const @var{type}&)
971 Returns the negative of the argument.
973 @item @var{type} plus1 (const @var{type}& x)
974 Returns @code{x + 1}.
976 @item @var{type} minus1 (const @var{type}& x)
977 Returns @code{x - 1}.
979 @item @var{type} operator * (const @var{type}&, const @var{type}&)
982 @item @var{type} square (const @var{type}& x)
983 Returns @code{x * x}.
986 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
987 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
988 defines the following operations:
991 @item @var{type} operator / (const @var{type}&, const @var{type}&)
994 @item @var{type} recip (const @var{type}&)
995 Returns the reciprocal of the argument.
998 The class @code{cl_I} doesn't define a @samp{/} operation because
999 in the C/C++ language this operator, applied to integral types,
1000 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
1001 is implementation dependent). (@xref{Rounding functions})
1002 Instead, @code{cl_I} defines an ``exact quotient'' function:
1005 @item cl_I exquo (const cl_I& x, const cl_I& y)
1006 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
1009 The following exponentiation functions are defined:
1012 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
1013 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
1014 @code{y} must be > 0. Returns @code{x^y}.
1016 @item cl_RA expt (const cl_RA& x, const cl_I& y)
1017 @itemx cl_R expt (const cl_R& x, const cl_I& y)
1018 @itemx cl_N expt (const cl_N& x, const cl_I& y)
1022 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1023 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1024 defines the following operation:
1027 @item @var{type} abs (const @var{type}& x)
1028 Returns the absolute value of @code{x}.
1029 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
1032 The class @code{cl_N} implements this as follows:
1035 @item cl_R abs (const cl_N x)
1036 Returns the absolute value of @code{x}.
1039 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1040 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1041 defines the following operation:
1044 @item @var{type} signum (const @var{type}& x)
1045 Returns the sign of @code{x}, in the same number format as @code{x}.
1046 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
1047 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
1052 @node Elementary rational functions, Elementary complex functions, Elementary functions, Functions on numbers
1053 @section Elementary rational functions
1055 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
1058 @item cl_I numerator (const @var{type}& x)
1059 Returns the numerator of @code{x}.
1061 @item cl_I denominator (const @var{type}& x)
1062 Returns the denominator of @code{x}.
1065 The numerator and denominator of a rational number are normalized in such
1066 a way that they have no factor in common and the denominator is positive.
1069 @node Elementary complex functions, Comparisons, Elementary rational functions, Functions on numbers
1070 @section Elementary complex functions
1072 The class @code{cl_N} defines the following operation:
1075 @item cl_N complex (const cl_R& a, const cl_R& b)
1076 Returns the complex number @code{a+bi}, that is, the complex number with
1077 real part @code{a} and imaginary part @code{b}.
1080 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1083 @item cl_R realpart (const @var{type}& x)
1084 Returns the real part of @code{x}.
1086 @item cl_R imagpart (const @var{type}& x)
1087 Returns the imaginary part of @code{x}.
1089 @item @var{type} conjugate (const @var{type}& x)
1090 Returns the complex conjugate of @code{x}.
1093 We have the relations
1097 @code{x = complex(realpart(x), imagpart(x))}
1099 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1103 @node Comparisons, Rounding functions, Elementary complex functions, Functions on numbers
1104 @section Comparisons
1106 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1107 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1108 defines the following operations:
1111 @item bool operator == (const @var{type}&, const @var{type}&)
1112 @itemx bool operator != (const @var{type}&, const @var{type}&)
1113 Comparison, as in C and C++.
1115 @item uint32 cl_equal_hashcode (const @var{type}&)
1116 Returns a 32-bit hash code that is the same for any two numbers which are
1117 the same according to @code{==}. This hash code depends on the number's value,
1118 not its type or precision.
1120 @item cl_boolean zerop (const @var{type}& x)
1121 Compare against zero: @code{x == 0}
1124 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1125 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1126 defines the following operations:
1129 @item cl_signean cl_compare (const @var{type}& x, const @var{type}& y)
1130 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1131 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1133 @item bool operator <= (const @var{type}&, const @var{type}&)
1134 @itemx bool operator < (const @var{type}&, const @var{type}&)
1135 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1136 @itemx bool operator > (const @var{type}&, const @var{type}&)
1137 Comparison, as in C and C++.
1139 @item cl_boolean minusp (const @var{type}& x)
1140 Compare against zero: @code{x < 0}
1142 @item cl_boolean plusp (const @var{type}& x)
1143 Compare against zero: @code{x > 0}
1145 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1146 Return the maximum of @code{x} and @code{y}.
1148 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1149 Return the minimum of @code{x} and @code{y}.
1152 When a floating point number and a rational number are compared, the float
1153 is first converted to a rational number using the function @code{rational}.
1154 Since a floating point number actually represents an interval of real numbers,
1155 the result might be surprising.
1156 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1157 there is no floating point number whose value is exactly @code{1/3}.
1160 @node Rounding functions, Roots, Comparisons, Functions on numbers
1161 @section Rounding functions
1163 When a real number is to be converted to an integer, there is no ``best''
1164 rounding. The desired rounding function depends on the application.
1165 The Common Lisp and ISO Lisp standards offer four rounding functions:
1169 This is the largest integer <=@code{x}.
1172 This is the smallest integer >=@code{x}.
1175 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1178 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1179 integers, choose the even one.
1182 These functions have different advantages:
1184 @code{floor} and @code{ceiling} are translation invariant:
1185 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1186 for every @code{x} and every integer @code{n}.
1188 On the other hand, @code{truncate} and @code{round} are symmetric:
1189 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1190 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1191 down exactly as often as it rounds up.
1193 The functions are related like this:
1197 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1198 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1200 @code{truncate(x) = sign(x) * floor(abs(x))}
1203 Each of the classes @code{cl_R}, @code{cl_RA},
1204 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1205 defines the following operations:
1208 @item cl_I floor1 (const @var{type}& x)
1209 Returns @code{floor(x)}.
1210 @item cl_I ceiling1 (const @var{type}& x)
1211 Returns @code{ceiling(x)}.
1212 @item cl_I truncate1 (const @var{type}& x)
1213 Returns @code{truncate(x)}.
1214 @item cl_I round1 (const @var{type}& x)
1215 Returns @code{round(x)}.
1218 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1219 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1220 defines the following operations:
1223 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1224 Returns @code{floor(x/y)}.
1225 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1226 Returns @code{ceiling(x/y)}.
1227 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1228 Returns @code{truncate(x/y)}.
1229 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1230 Returns @code{round(x/y)}.
1233 These functions are called @samp{floor1}, @dots{} here instead of
1234 @samp{floor}, @dots{}, because on some systems, system dependent include
1235 files define @samp{floor} and @samp{ceiling} as macros.
1237 In many cases, one needs both the quotient and the remainder of a division.
1238 It is more efficient to compute both at the same time than to perform
1239 two divisions, one for quotient and the next one for the remainder.
1240 The following functions therefore return a structure containing both
1241 the quotient and the remainder. The suffix @samp{2} indicates the number
1242 of ``return values''. The remainder is defined as follows:
1246 for the computation of @code{quotient = floor(x)},
1247 @code{remainder = x - quotient},
1249 for the computation of @code{quotient = floor(x,y)},
1250 @code{remainder = x - quotient*y},
1253 and similarly for the other three operations.
1255 Each of the classes @code{cl_R}, @code{cl_RA},
1256 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1257 defines the following operations:
1260 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1261 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1262 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1263 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1264 @itemx @var{type}_div_t round2 (const @var{type}& x)
1267 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1268 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1269 defines the following operations:
1272 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1273 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1274 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1275 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1276 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1279 Sometimes, one wants the quotient as a floating-point number (of the
1280 same format as the argument, if the argument is a float) instead of as
1281 an integer. The prefix @samp{f} indicates this.
1284 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1285 defines the following operations:
1288 @item @var{type} ffloor (const @var{type}& x)
1289 @itemx @var{type} fceiling (const @var{type}& x)
1290 @itemx @var{type} ftruncate (const @var{type}& x)
1291 @itemx @var{type} fround (const @var{type}& x)
1294 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1296 The class @code{cl_R} defines the following operations:
1299 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1300 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1301 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1302 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1305 These functions also exist in versions which return both the quotient
1306 and the remainder. The suffix @samp{2} indicates this.
1309 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1310 defines the following operations:
1313 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1314 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1315 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1316 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1317 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1319 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1321 The class @code{cl_R} defines the following operations:
1324 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1325 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1326 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1327 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1328 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1331 Other applications need only the remainder of a division.
1332 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1333 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1334 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1338 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1340 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1343 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1344 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1345 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1347 The classes @code{cl_R}, @code{cl_I} define the following operations:
1350 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1351 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1355 @node Roots, Transcendental functions, Rounding functions, Functions on numbers
1358 Each of the classes @code{cl_R},
1359 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1360 defines the following operation:
1363 @item @var{type} sqrt (const @var{type}& x)
1364 @code{x} must be >= 0. This function returns the square root of @code{x},
1365 normalized to be >= 0. If @code{x} is the square of a rational number,
1366 @code{sqrt(x)} will be a rational number, else it will return a
1367 floating-point approximation.
1370 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1373 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1374 This tests whether @code{x} is a perfect square. If so, it returns true
1375 and the exact square root in @code{*root}, else it returns false.
1378 Furthermore, for integers, similarly:
1381 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1382 @code{x} should be >= 0. This function sets @code{*root} to
1383 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1384 the boolean value @code{(expt(*root,2) == x)}.
1387 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1388 define the following operation:
1391 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1392 @code{x} must be >= 0. @code{n} must be > 0.
1393 This tests whether @code{x} is an @code{n}th power of a rational number.
1394 If so, it returns true and the exact root in @code{*root}, else it returns
1398 The only square root function which accepts negative numbers is the one
1399 for class @code{cl_N}:
1402 @item cl_N sqrt (const cl_N& z)
1403 Returns the square root of @code{z}, as defined by the formula
1404 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1405 or to a complex number are done if necessary. The range of the result is the
1406 right half plane @code{realpart(sqrt(z)) >= 0}
1407 including the positive imaginary axis and 0, but excluding
1408 the negative imaginary axis.
1409 The result is an exact number only if @code{z} is an exact number.
1413 @node Transcendental functions, Functions on integers, Roots, Functions on numbers
1414 @section Transcendental functions
1417 The transcendental functions return an exact result if the argument
1418 is exact and the result is exact as well. Otherwise they must return
1419 inexact numbers even if the argument is exact.
1420 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1424 * Exponential and logarithmic functions::
1425 * Trigonometric functions::
1426 * Hyperbolic functions::
1431 @node Exponential and logarithmic functions, Trigonometric functions, Transcendental functions, Transcendental functions
1432 @subsection Exponential and logarithmic functions
1435 @item cl_R exp (const cl_R& x)
1436 @itemx cl_N exp (const cl_N& x)
1437 Returns the exponential function of @code{x}. This is @code{e^x} where
1438 @code{e} is the base of the natural logarithms. The range of the result
1439 is the entire complex plane excluding 0.
1441 @item cl_R ln (const cl_R& x)
1442 @code{x} must be > 0. Returns the (natural) logarithm of x.
1444 @item cl_N log (const cl_N& x)
1445 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1446 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1447 The range of the result is the strip in the complex plane
1448 @code{-pi < imagpart(log(x)) <= pi}.
1450 @item cl_R phase (const cl_N& x)
1451 Returns the angle part of @code{x} in its polar representation as a
1452 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1453 This is also the imaginary part of @code{log(x)}.
1454 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1455 The result will be an exact number only if @code{zerop(x)} or
1456 if @code{x} is real and positive.
1458 @item cl_R log (const cl_R& a, const cl_R& b)
1459 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1460 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1461 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1464 @item cl_N log (const cl_N& a, const cl_N& b)
1465 Returns the logarithm of @code{a} with respect to base @code{b}.
1466 @code{log(a,b) = log(a)/log(b)}.
1468 @item cl_N expt (const cl_N& x, const cl_N& y)
1469 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1472 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1475 @item cl_F cl_exp1 (cl_float_format_t f)
1476 Returns e as a float of format @code{f}.
1478 @item cl_F cl_exp1 (const cl_F& y)
1479 Returns e in the float format of @code{y}.
1481 @item cl_F cl_exp1 (void)
1482 Returns e as a float of format @code{cl_default_float_format}.
1486 @node Trigonometric functions, Hyperbolic functions, Exponential and logarithmic functions, Transcendental functions
1487 @subsection Trigonometric functions
1490 @item cl_R sin (const cl_R& x)
1491 Returns @code{sin(x)}. The range of the result is the interval
1492 @code{-1 <= sin(x) <= 1}.
1494 @item cl_N sin (const cl_N& z)
1495 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1497 @item cl_R cos (const cl_R& x)
1498 Returns @code{cos(x)}. The range of the result is the interval
1499 @code{-1 <= cos(x) <= 1}.
1501 @item cl_N cos (const cl_N& x)
1502 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1504 @item struct cl_cos_sin_t @{ cl_R cos; cl_R sin; @};
1505 @itemx cl_cos_sin_t cl_cos_sin (const cl_R& x)
1506 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1507 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1508 hold only approximately.
1510 @item cl_R tan (const cl_R& x)
1511 @itemx cl_N tan (const cl_N& x)
1512 Returns @code{tan(x) = sin(x)/cos(x)}.
1514 @item cl_N cis (const cl_R& x)
1515 @itemx cl_N cis (const cl_N& x)
1516 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1517 @code{e^(i*x) = cos(x) + i*sin(x)}.
1519 @item cl_N asin (const cl_N& z)
1520 Returns @code{arcsin(z)}. This is defined as
1521 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1522 @code{arcsin(-z) = -arcsin(z)}.
1523 The range of the result is the strip in the complex domain
1524 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1525 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1526 with @code{realpart = pi/2} and @code{imagpart > 0}.
1528 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1532 @item cl_N acos (const cl_N& z)
1533 Returns @code{arccos(z)}. This is defined as
1534 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1537 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1539 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1540 The range of the result is the strip in the complex domain
1541 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1542 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1543 with @code{realpart = pi} and @code{imagpart > 0}.
1545 Proof: This follows from the results about arcsin.
1548 @item cl_R atan (const cl_R& x, const cl_R& y)
1549 Returns the angle of the polar representation of the complex number
1550 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1551 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1552 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1553 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1554 with reversed order of arguments.
1556 @item cl_R atan (const cl_R& x)
1557 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1558 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1559 will be an exact number only if @code{x} is the exact @code{0}.
1561 @item cl_N atan (const cl_N& z)
1562 Returns @code{arctan(z)}. This is defined as
1563 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1564 @code{arctan(-z) = -arctan(z)}. The range of the result is
1565 the strip in the complex domain
1566 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1567 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1568 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1570 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1575 The constant pi = 3.14@dots{} is returned by the following functions:
1578 @item cl_F cl_pi (cl_float_format_t f)
1579 Returns pi as a float of format @code{f}.
1581 @item cl_F cl_pi (const cl_F& y)
1582 Returns pi in the float format of @code{y}.
1584 @item cl_F cl_pi (void)
1585 Returns pi as a float of format @code{cl_default_float_format}.
1589 @node Hyperbolic functions, Euler gamma, Trigonometric functions, Transcendental functions
1590 @subsection Hyperbolic functions
1593 @item cl_R sinh (const cl_R& x)
1594 Returns @code{sinh(x)}.
1596 @item cl_N sinh (const cl_N& z)
1597 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1599 @item cl_R cosh (const cl_R& x)
1600 Returns @code{cosh(x)}. The range of the result is the interval
1601 @code{cosh(x) >= 1}.
1603 @item cl_N cosh (const cl_N& z)
1604 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1606 @item struct cl_cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1607 @itemx cl_cosh_sinh_t cl_cosh_sinh (const cl_R& x)
1608 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1609 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1610 hold only approximately.
1612 @item cl_R tanh (const cl_R& x)
1613 @itemx cl_N tanh (const cl_N& x)
1614 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1616 @item cl_N asinh (const cl_N& z)
1617 Returns @code{arsinh(z)}. This is defined as
1618 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1619 @code{arsinh(-z) = -arsinh(z)}.
1621 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1622 Actually, z+sqrt(1+z^2) can never be real and <0, so
1623 -pi < imagpart(arsinh(z)) < pi.
1624 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1625 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1627 The range of the result is the strip in the complex domain
1628 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1629 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1630 with @code{imagpart = pi/2} and @code{realpart < 0}.
1632 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1633 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1634 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1635 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1636 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1637 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1638 If y >= 1, the imagpart is pi/2 and the realpart is
1639 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1642 Moreover, if z is in Range(sqrt),
1643 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1644 (for a proof, see file src/cl_C_asinh.cc).
1647 @item cl_N acosh (const cl_N& z)
1648 Returns @code{arcosh(z)}. This is defined as
1649 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1650 The range of the result is the half-strip in the complex domain
1651 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1652 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1654 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1655 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1656 If z is in Range(sqrt), we have
1657 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1658 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1660 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1661 and since the imagpart of both expressions is > -pi, <= pi
1662 ==> arcosh(z) = log(z+sqrt(z^2-1))
1663 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1664 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1665 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1666 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1667 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1669 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1670 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1671 = x^2 + y^2 + sqrt(u^2+v^2)
1676 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1677 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1678 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1679 Otherwise, -z is in Range(sqrt).
1680 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1681 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1682 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1683 and this has realpart > 0.
1684 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1685 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1686 has realpart = 0 and imagpart > 0.
1687 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1688 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1689 This has realpart >= 0 and imagpart = pi.
1692 @item cl_N atanh (const cl_N& z)
1693 Returns @code{artanh(z)}. This is defined as
1694 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1695 @code{artanh(-z) = -artanh(z)}. The range of the result is
1696 the strip in the complex domain
1697 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1698 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1699 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1701 Proof: Write z = x+iy. Examine
1702 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1704 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1705 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1706 |x| < 1 ==> imagpart = 0
1709 = (atan(1+x,y) - atan(1-x,-y))/2
1710 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1711 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1712 > (pi - pi/2 - pi/2 )/2 = 0
1713 and (1+x)/y > (1-x)/y
1714 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1715 ==> imagpart < pi/2.
1716 Hence 0 < imagpart < pi/2.
1718 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1723 @node Euler gamma, Riemann zeta, Hyperbolic functions, Transcendental functions
1724 @subsection Euler gamma
1726 Euler's constant C = 0.577@dots{} is returned by the following functions:
1729 @item cl_F cl_eulerconst (cl_float_format_t f)
1730 Returns Euler's constant as a float of format @code{f}.
1732 @item cl_F cl_eulerconst (const cl_F& y)
1733 Returns Euler's constant in the float format of @code{y}.
1735 @item cl_F cl_eulerconst (void)
1736 Returns Euler's constant as a float of format @code{cl_default_float_format}.
1739 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1742 @item cl_F cl_catalanconst (cl_float_format_t f)
1743 Returns Catalan's constant as a float of format @code{f}.
1745 @item cl_F cl_catalanconst (const cl_F& y)
1746 Returns Catalan's constant in the float format of @code{y}.
1748 @item cl_F cl_catalanconst (void)
1749 Returns Catalan's constant as a float of format @code{cl_default_float_format}.
1753 @node Riemann zeta, , Euler gamma, Transcendental functions
1754 @subsection Riemann zeta
1756 Riemann's zeta function at an integral point @code{s>1} is returned by the
1757 following functions:
1760 @item cl_F cl_zeta (int s, cl_float_format_t f)
1761 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1763 @item cl_F cl_zeta (int s, const cl_F& y)
1764 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1766 @item cl_F cl_zeta (int s)
1767 Returns Riemann's zeta function at @code{s} as a float of format
1768 @code{cl_default_float_format}.
1772 @node Functions on integers, Functions on floating-point numbers, Transcendental functions, Functions on numbers
1773 @section Functions on integers
1776 * Logical functions::
1777 * Number theoretic functions::
1778 * Combinatorial functions::
1781 @node Logical functions, Number theoretic functions, Functions on integers, Functions on integers
1782 @subsection Logical functions
1784 Integers, when viewed as in two's complement notation, can be thought as
1785 infinite bit strings where the bits' values eventually are constant.
1792 The logical operations view integers as such bit strings and operate
1793 on each of the bit positions in parallel.
1796 @item cl_I lognot (const cl_I& x)
1797 @itemx cl_I operator ~ (const cl_I& x)
1798 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1800 @item cl_I logand (const cl_I& x, const cl_I& y)
1801 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1802 Logical and, like @code{x & y} in C.
1804 @item cl_I logior (const cl_I& x, const cl_I& y)
1805 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1806 Logical (inclusive) or, like @code{x | y} in C.
1808 @item cl_I logxor (const cl_I& x, const cl_I& y)
1809 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1810 Exclusive or, like @code{x ^ y} in C.
1812 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1813 Bitwise equivalence, like @code{~(x ^ y)} in C.
1815 @item cl_I lognand (const cl_I& x, const cl_I& y)
1816 Bitwise not and, like @code{~(x & y)} in C.
1818 @item cl_I lognor (const cl_I& x, const cl_I& y)
1819 Bitwise not or, like @code{~(x | y)} in C.
1821 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1822 Logical and, complementing the first argument, like @code{~x & y} in C.
1824 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1825 Logical and, complementing the second argument, like @code{x & ~y} in C.
1827 @item cl_I logorc1 (const cl_I& x, const cl_I& y)
1828 Logical or, complementing the first argument, like @code{~x | y} in C.
1830 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1831 Logical or, complementing the second argument, like @code{x | ~y} in C.
1834 These operations are all available though the function
1836 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
1838 where @code{op} must have one of the 16 values (each one stands for a function
1839 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
1840 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
1841 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
1842 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
1843 @code{boole_orc1}, @code{boole_orc2}.
1845 Other functions that view integers as bit strings:
1848 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
1849 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
1850 @code{logand(x,y) != 0}.
1852 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
1853 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
1854 Bit 0 is the least significant bit.
1856 @item uintL logcount (const cl_I& x)
1857 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
1858 the number of zero bits in @code{x}, if @code{x} < 0.
1861 The following functions operate on intervals of bits in integers.
1864 struct cl_byte @{ uintL size; uintL position; @};
1866 represents the bit interval containing the bits
1867 @code{position}@dots{}@code{position+size-1} of an integer.
1868 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
1871 @item cl_I ldb (const cl_I& n, const cl_byte& b)
1872 extracts the bits of @code{n} described by the bit interval @code{b}
1873 and returns them as a nonnegative integer with @code{b.size} bits.
1875 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
1876 Returns true if some bit described by the bit interval @code{b} is set in
1879 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1880 Returns @code{n}, with the bits described by the bit interval @code{b}
1881 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
1882 @code{newbyte} are relevant.
1885 The functions @code{ldb} and @code{dpb} implicitly shift. The following
1886 functions are their counterparts without shifting:
1889 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
1890 returns an integer with the bits described by the bit interval @code{b}
1891 copied from the corresponding bits in @code{n}, the other bits zero.
1893 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1894 returns an integer where the bits described by the bit interval @code{b}
1895 come from @code{newbyte} and the other bits come from @code{n}.
1898 The following relations hold:
1902 @code{ldb (n, b) = mask_field(n, b) >> b.position},
1904 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
1906 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
1909 The following operations on integers as bit strings are efficient shortcuts
1910 for common arithmetic operations:
1913 @item cl_boolean oddp (const cl_I& x)
1914 Returns true if the least significant bit of @code{x} is 1. Equivalent to
1915 @code{mod(x,2) != 0}.
1917 @item cl_boolean evenp (const cl_I& x)
1918 Returns true if the least significant bit of @code{x} is 0. Equivalent to
1919 @code{mod(x,2) == 0}.
1921 @item cl_I operator << (const cl_I& x, const cl_I& n)
1922 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
1923 Equivalent to @code{x * expt(2,n)}.
1925 @item cl_I operator >> (const cl_I& x, const cl_I& n)
1926 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
1927 Bits shifted out to the right are thrown away.
1928 Equivalent to @code{floor(x / expt(2,n))}.
1930 @item cl_I ash (const cl_I& x, const cl_I& y)
1931 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
1932 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
1933 returns @code{floor(x * expt(2,y))}.
1935 @item uintL integer_length (const cl_I& x)
1936 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
1937 in two's complement notation. This is the smallest n >= 0 such that
1938 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
1941 @item uintL ord2 (const cl_I& x)
1942 @code{x} must be non-zero. This function returns the number of 0 bits at the
1943 right of @code{x} in two's complement notation. This is the largest n >= 0
1944 such that 2^n divides @code{x}.
1946 @item uintL power2p (const cl_I& x)
1947 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
1948 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
1949 (See also the function @code{logp}.)
1953 @node Number theoretic functions, Combinatorial functions, Logical functions, Functions on integers
1954 @subsection Number theoretic functions
1957 @item uint32 gcd (uint32 a, uint32 b)
1958 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
1959 This function returns the greatest common divisor of @code{a} and @code{b},
1960 normalized to be >= 0.
1962 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
1963 This function (``extended gcd'') returns the greatest common divisor @code{g} of
1964 @code{a} and @code{b} and at the same time the representation of @code{g}
1965 as an integral linear combination of @code{a} and @code{b}:
1966 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
1967 @code{u} and @code{v} will be normalized to be of smallest possible absolute
1968 value, in the following sense: If @code{a} and @code{b} are non-zero, and
1969 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
1970 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
1972 @item cl_I lcm (const cl_I& a, const cl_I& b)
1973 This function returns the least common multiple of @code{a} and @code{b},
1974 normalized to be >= 0.
1976 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
1977 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
1978 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
1979 rational number, this function returns true and sets *l = log(a,b), else
1984 @node Combinatorial functions, , Number theoretic functions, Functions on integers
1985 @subsection Combinatorial functions
1988 @item cl_I factorial (uintL n)
1989 @code{n} must be a small integer >= 0. This function returns the factorial
1990 @code{n}! = @code{1*2*@dots{}*n}.
1992 @item cl_I doublefactorial (uintL n)
1993 @code{n} must be a small integer >= 0. This function returns the
1994 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
1995 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
1997 @item cl_I binomial (uintL n, uintL k)
1998 @code{n} and @code{k} must be small integers >= 0. This function returns the
1999 binomial coefficient
2001 ${n \choose k} = {n! \over n! (n-k)!}$
2004 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2006 for 0 <= k <= n, 0 else.
2010 @node Functions on floating-point numbers, Conversion functions, Functions on integers, Functions on numbers
2011 @section Functions on floating-point numbers
2013 Recall that a floating-point number consists of a sign @code{s}, an
2014 exponent @code{e} and a mantissa @code{m}. The value of the number is
2015 @code{(-1)^s * 2^e * m}.
2018 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2019 defines the following operations.
2022 @item @var{type} scale_float (const @var{type}& x, sintL delta)
2023 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2024 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2025 because it copies @code{x} and modifies the exponent.
2028 The following functions provide an abstract interface to the underlying
2029 representation of floating-point numbers.
2032 @item sintL float_exponent (const @var{type}& x)
2033 Returns the exponent @code{e} of @code{x}.
2034 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2035 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2037 @item sintL float_radix (const @var{type}& x)
2038 Returns the base of the floating-point representation. This is always @code{2}.
2040 @item @var{type} float_sign (const @var{type}& x)
2041 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2042 @code{x} >= 0, -1 for @code{x} < 0.
2044 @item uintL float_digits (const @var{type}& x)
2045 Returns the number of mantissa bits in the floating-point representation
2046 of @code{x}, including the hidden bit. The value only depends on the type
2047 of @code{x}, not on its value.
2049 @item uintL float_precision (const @var{type}& x)
2050 Returns the number of significant mantissa bits in the floating-point
2051 representation of @code{x}. Since denormalized numbers are not supported,
2052 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2056 The complete internal representation of a float is encoded in the type
2057 @code{cl_decoded_float} (or @code{cl_decoded_sfloat}, @code{cl_decoded_ffloat},
2058 @code{cl_decoded_dfloat}, @code{cl_decoded_lfloat}, respectively), defined by
2060 struct cl_decoded_@var{type}float @{
2061 @var{type} mantissa; cl_I exponent; @var{type} sign;
2065 and returned by the function
2068 @item cl_decoded_@var{type}float decode_float (const @var{type}& x)
2069 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2070 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2071 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2072 @code{e} is the same as returned by the function @code{float_exponent}.
2075 A complete decoding in terms of integers is provided as type
2077 struct cl_idecoded_float @{
2078 cl_I mantissa; cl_I exponent; cl_I sign;
2081 by the following function:
2084 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2085 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2086 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2087 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2088 WARNING: The exponent @code{e} is not the same as the one returned by
2089 the functions @code{decode_float} and @code{float_exponent}.
2092 Some other function, implemented only for class @code{cl_F}:
2095 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2096 This returns a floating point number whose precision and absolute value
2097 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2098 zero, it is treated as positive. Same for @code{y}.
2102 @node Conversion functions, Random number generators, Functions on floating-point numbers, Functions on numbers
2103 @section Conversion functions
2106 * Conversion to floating-point numbers::
2107 * Conversion to rational numbers::
2110 @node Conversion to floating-point numbers, Conversion to rational numbers, Conversion functions, Conversion functions
2111 @subsection Conversion to floating-point numbers
2113 The type @code{cl_float_format_t} describes a floating-point format.
2116 @item cl_float_format_t cl_float_format (uintL n)
2117 Returns the smallest float format which guarantees at least @code{n}
2118 decimal digits in the mantissa (after the decimal point).
2120 @item cl_float_format_t cl_float_format (const cl_F& x)
2121 Returns the floating point format of @code{x}.
2123 @item cl_float_format_t cl_default_float_format
2124 Global variable: the default float format used when converting rational numbers
2128 To convert a real number to a float, each of the types
2129 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2130 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2131 defines the following operations:
2134 @item cl_F cl_float (const @var{type}&x, cl_float_format_t f)
2135 Returns @code{x} as a float of format @code{f}.
2136 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2137 Returns @code{x} in the float format of @code{y}.
2138 @item cl_F cl_float (const @var{type}&x)
2139 Returns @code{x} as a float of format @code{cl_default_float_format} if
2140 it is an exact number, or @code{x} itself if it is already a float.
2143 Of course, converting a number to a float can lose precision.
2145 Every floating-point format has some characteristic numbers:
2148 @item cl_F most_positive_float (cl_float_format_t f)
2149 Returns the largest (most positive) floating point number in float format @code{f}.
2151 @item cl_F most_negative_float (cl_float_format_t f)
2152 Returns the smallest (most negative) floating point number in float format @code{f}.
2154 @item cl_F least_positive_float (cl_float_format_t f)
2155 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2156 in float format @code{f}.
2158 @item cl_F least_negative_float (cl_float_format_t f)
2159 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2160 in float format @code{f}.
2162 @item cl_F float_epsilon (cl_float_format_t f)
2163 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2165 @item cl_F float_negative_epsilon (cl_float_format_t f)
2166 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2170 @node Conversion to rational numbers, , Conversion to floating-point numbers, Conversion functions
2171 @subsection Conversion to rational numbers
2173 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2174 defines the following operation:
2177 @item cl_RA rational (const @var{type}& x)
2178 Returns the value of @code{x} as an exact number. If @code{x} is already
2179 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2180 the value is a rational number whose denominator is a power of 2.
2183 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2187 @item cl_RA rationalize (const cl_R& x)
2188 If @code{x} is a floating-point number, it actually represents an interval
2189 of real numbers, and this function returns the rational number with
2190 smallest denominator (and smallest numerator, in magnitude)
2191 which lies in this interval.
2192 If @code{x} is already an exact number, this function returns @code{x}.
2195 If @code{x} is any float, one has
2199 @code{cl_float(rational(x),x) = x}
2201 @code{cl_float(rationalize(x),x) = x}
2205 @node Random number generators, Obfuscating operators, Conversion functions, Functions on numbers
2206 @section Random number generators
2209 A random generator is a machine which produces (pseudo-)random numbers.
2210 The include file @code{<cl_random.h>} defines a class @code{cl_random_state}
2211 which contains the state of a random generator. If you make a copy
2212 of the random number generator, the original one and the copy will produce
2213 the same sequence of random numbers.
2215 The following functions return (pseudo-)random numbers in different formats.
2216 Calling one of these modifies the state of the random number generator in
2217 a complicated but deterministic way.
2221 cl_random_state cl_default_random_state
2223 contains a default random number generator. It is used when the functions
2224 below are called without @code{cl_random_state} argument.
2227 @item uint32 random32 (cl_random_state& randomstate)
2228 @itemx uint32 random32 ()
2229 Returns a random unsigned 32-bit number. All bits are equally random.
2231 @item cl_I random_I (cl_random_state& randomstate, const cl_I& n)
2232 @itemx cl_I random_I (const cl_I& n)
2233 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2234 in the range @code{0 <= x < n}.
2236 @item cl_F random_F (cl_random_state& randomstate, const cl_F& n)
2237 @itemx cl_F random_F (const cl_F& n)
2238 @code{n} must be a float > 0. This function returns a random floating-point
2239 number of the same format as @code{n} in the range @code{0 <= x < n}.
2241 @item cl_R random_R (cl_random_state& randomstate, const cl_R& n)
2242 @itemx cl_R random_R (const cl_R& n)
2243 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2244 if @code{n} is a float.
2248 @node Obfuscating operators, , Random number generators, Functions on numbers
2249 @section Obfuscating operators
2251 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2252 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2253 are not available by default because their
2254 use tends to make programs unreadable. It is trivial to get away without
2255 them. However, if you feel that you absolutely need these operators
2256 to get happy, then add
2258 #define WANT_OBFUSCATING_OPERATORS
2260 to the beginning of your source files, before the inclusion of any CLN
2261 include files. This flag will enable the following operators:
2263 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2264 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2267 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2268 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2269 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2270 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2273 For the class @code{cl_I}:
2276 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2277 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2278 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2279 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2280 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2281 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2282 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2283 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2286 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2287 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2290 @item @var{type}& operator ++ (@var{type}& x)
2291 The prefix operator @code{++x}.
2293 @item void operator ++ (@var{type}& x, int)
2294 The postfix operator @code{x++}.
2296 @item @var{type}& operator -- (@var{type}& x)
2297 The prefix operator @code{--x}.
2299 @item void operator -- (@var{type}& x, int)
2300 The postfix operator @code{x--}.
2303 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2304 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2308 @node Input/Output, Rings, Functions on numbers, Top
2309 @chapter Input/Output
2312 * Internal and printed representation::
2314 * Output functions::
2317 @node Internal and printed representation, Input functions, Input/Output, Input/Output
2318 @section Internal and printed representation
2320 All computations deal with the internal representations of the numbers.
2322 Every number has an external representation as a sequence of ASCII characters.
2323 Several external representations may denote the same number, for example,
2324 "20.0" and "20.000".
2326 Converting an internal to an external representation is called ``printing'',
2327 converting an external to an internal representation is called ``reading''.
2328 In CLN, is it always true that conversion of an internal to an external
2329 representation and then back to an internal representation will yield the
2330 same internal representation. Symbolically: @code{read(print(x)) == x}.
2331 This is called ``print-read consistency''.
2333 Different types of numbers have different external representations (case
2338 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2339 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2340 for decimal integers
2341 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2343 @item Rational numbers
2344 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2345 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2348 @item Floating-point numbers
2349 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2350 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2351 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2352 of the form _@var{prec} may be appended. There must be at least
2353 one digit in the non-exponent part. The exponent has the syntax
2354 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2355 The exponent marker is
2359 @samp{s} for short-floats,
2361 @samp{f} for single-floats,
2363 @samp{d} for double-floats,
2365 @samp{L} for long-floats,
2368 or @samp{e}, which denotes a default float format. The precision specifying
2369 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2370 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2371 function @samp{cl_float_format}.
2373 @item Complex numbers
2374 External representation:
2377 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2378 if @var{imagpart} is negative, its printed representation begins with
2379 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2380 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2381 is rational and the rational number's base is >18, because the @samp{i}
2382 is then read as a digit.
2384 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2389 @node Input functions, Output functions, Internal and printed representation, Input/Output
2390 @section Input functions
2392 Including @code{<cl_io.h>} defines a type @code{cl_istream}, which is
2393 the type of the first argument to all input functions. Unless you build
2394 and use CLN with the macro CL_IO_STDIO being defined, @code{cl_istream}
2395 is the same as @code{istream&}.
2400 @code{cl_istream cl_stdin}
2402 contains the standard input stream.
2404 These are the simple input functions:
2407 @item int freadchar (cl_istream stream)
2408 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2409 if the end of stream was encountered or an error occurred.
2411 @item int funreadchar (cl_istream stream, int c)
2412 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2413 last @code{freadchar} operation on @code{stream}.
2416 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2417 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2418 defines, in @code{<cl_@var{type}_io.h>}, the following input function:
2421 @item cl_istream operator>> (cl_istream stream, @var{type}& result)
2422 Reads a number from @code{stream} and stores it in the @code{result}.
2425 The most flexible input functions, defined in @code{<cl_@var{type}_io.h>},
2429 @item cl_N read_complex (cl_istream stream, const cl_read_flags& flags)
2430 @itemx cl_R read_real (cl_istream stream, const cl_read_flags& flags)
2431 @itemx cl_F read_float (cl_istream stream, const cl_read_flags& flags)
2432 @itemx cl_RA read_rational (cl_istream stream, const cl_read_flags& flags)
2433 @itemx cl_I read_integer (cl_istream stream, const cl_read_flags& flags)
2434 Reads a number from @code{stream}. The @code{flags} are parameters which
2435 affect the input syntax. Whitespace before the number is silently skipped.
2437 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2438 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2439 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2440 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2441 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2442 Reads a number from a string in memory. The @code{flags} are parameters which
2443 affect the input syntax. The string starts at @code{string} and ends at
2444 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2445 @code{NULL}, denoting the entire string, i.e. equivalent to
2446 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2447 @code{NULL}, the string in memory must contain exactly one number and nothing
2448 more, else a fatal error will be signalled. If @code{end_of_parse}
2449 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2450 the last parsed character (i.e. @code{string_limit} if nothing came after
2451 the number). Whitespace is not allowed.
2454 The structure @code{cl_read_flags} contains the following fields:
2457 @item cl_read_syntax_t syntax
2458 The possible results of the read operation. Possible values are
2459 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2460 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2461 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2463 @item cl_read_lsyntax_t lsyntax
2464 Specifies the language-dependent syntax variant for the read operation.
2468 @item lsyntax_standard
2469 accept standard algebraic notation only, no complex numbers,
2470 @item lsyntax_algebraic
2471 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2472 @item lsyntax_commonlisp
2473 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2474 hexadecimal numbers,
2475 @code{#@var{base}R} for rational numbers in a given base,
2476 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2478 accept all of these extensions.
2481 @item unsigned int rational_base
2482 The base in which rational numbers are read.
2484 @item cl_float_format_t float_flags.default_float_format
2485 The float format used when reading floats with exponent marker @samp{e}.
2487 @item cl_float_format_t float_flags.default_lfloat_format
2488 The float format used when reading floats with exponent marker @samp{l}.
2490 @item cl_boolean float_flags.mantissa_dependent_float_format
2491 When this flag is true, floats specified with more digits than corresponding
2492 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2493 precision corresponding to their number of significant digits.
2497 @node Output functions, , Input functions, Input/Output
2498 @section Output functions
2500 Including @code{<cl_io.h>} defines a type @code{cl_ostream}, which is
2501 the type of the first argument to all output functions. Unless you build
2502 and use CLN with the macro CL_IO_STDIO being defined, @code{cl_ostream}
2503 is the same as @code{ostream&}.
2508 @code{cl_ostream cl_stdout}
2510 contains the standard output stream.
2515 @code{cl_ostream cl_stderr}
2517 contains the standard error output stream.
2519 These are the simple output functions:
2522 @item void fprintchar (cl_ostream stream, char c)
2523 Prints the character @code{x} literally on the @code{stream}.
2525 @item void fprint (cl_ostream stream, const char * string)
2526 Prints the @code{string} literally on the @code{stream}.
2528 @item void fprintdecimal (cl_ostream stream, int x)
2529 @itemx void fprintdecimal (cl_ostream stream, const cl_I& x)
2530 Prints the integer @code{x} in decimal on the @code{stream}.
2532 @item void fprintbinary (cl_ostream stream, const cl_I& x)
2533 Prints the integer @code{x} in binary (base 2, without prefix)
2534 on the @code{stream}.
2536 @item void fprintoctal (cl_ostream stream, const cl_I& x)
2537 Prints the integer @code{x} in octal (base 8, without prefix)
2538 on the @code{stream}.
2540 @item void fprinthexadecimal (cl_ostream stream, const cl_I& x)
2541 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2542 on the @code{stream}.
2545 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2546 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2547 defines, in @code{<cl_@var{type}_io.h>}, the following output functions:
2550 @item void fprint (cl_ostream stream, const @var{type}& x)
2551 @itemx cl_ostream operator<< (cl_ostream stream, const @var{type}& x)
2552 Prints the number @code{x} on the @code{stream}. The output may depend
2553 on the global printer settings in the variable @code{cl_default_print_flags}.
2554 The @code{ostream} flags and settings (flags, width and locale) are
2558 The most flexible output function, defined in @code{<cl_@var{type}_io.h>},
2561 void print_complex (cl_ostream stream, const cl_print_flags& flags,
2563 void print_real (cl_ostream stream, const cl_print_flags& flags,
2565 void print_float (cl_ostream stream, const cl_print_flags& flags,
2567 void print_rational (cl_ostream stream, const cl_print_flags& flags,
2569 void print_integer (cl_ostream stream, const cl_print_flags& flags,
2572 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2573 parameters which affect the output.
2575 The structure type @code{cl_print_flags} contains the following fields:
2578 @item unsigned int rational_base
2579 The base in which rational numbers are printed. Default is @code{10}.
2581 @item cl_boolean rational_readably
2582 If this flag is true, rational numbers are printed with radix specifiers in
2583 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2584 prefixes, trailing dot). Default is false.
2586 @item cl_boolean float_readably
2587 If this flag is true, type specific exponent markers have precedence over 'E'.
2590 @item cl_float_format_t default_float_format
2591 Floating point numbers of this format will be printed using the 'E' exponent
2592 marker. Default is @code{cl_float_format_ffloat}.
2594 @item cl_boolean complex_readably
2595 If this flag is true, complex numbers will be printed using the Common Lisp
2596 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2598 @item cl_string univpoly_varname
2599 Univariate polynomials with no explicit indeterminate name will be printed
2600 using this variable name. Default is @code{"x"}.
2603 The global variable @code{cl_default_print_flags} contains the default values,
2604 used by the function @code{fprint},
2607 @node Rings, Modular integers, Input/Output, Top
2610 CLN has a class of abstract rings.
2618 Rings can be compared for equality:
2621 @item bool operator== (const cl_ring&, const cl_ring&)
2622 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2623 These compare two rings for equality.
2626 Given a ring @code{R}, the following members can be used.
2629 @item void R->fprint (cl_ostream stream, const cl_ring_element& x)
2630 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2631 @itemx cl_ring_element R->zero ()
2632 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2633 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2634 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2635 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2636 @itemx cl_ring_element R->one ()
2637 @itemx cl_ring_element R->canonhom (const cl_I& x)
2638 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2639 @itemx cl_ring_element R->square (const cl_ring_element& x)
2640 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2643 The following rings are built-in.
2646 @item cl_null_ring cl_0_ring
2647 The null ring, containing only zero.
2649 @item cl_complex_ring cl_C_ring
2650 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2652 @item cl_real_ring cl_R_ring
2653 The ring of real numbers. This corresponds to the type @code{cl_R}.
2655 @item cl_rational_ring cl_RA_ring
2656 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2658 @item cl_integer_ring cl_I_ring
2659 The ring of integers. This corresponds to the type @code{cl_I}.
2662 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2663 @code{cl_RA_ring}, @code{cl_I_ring}:
2666 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2667 Tests whether the given number is an element of the number ring R.
2671 @node Modular integers, Symbolic data types, Rings, Top
2672 @chapter Modular integers
2675 * Modular integer rings::
2676 * Functions on modular integers::
2679 @node Modular integer rings, Functions on modular integers, Modular integers, Modular integers
2680 @section Modular integer rings
2682 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2683 The modulus is explicitly part of every modular integer. CLN doesn't
2684 allow you to (accidentally) mix elements of different modular rings,
2685 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2686 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2687 doesn't have generic types. So one has to live with runtime checks.)
2689 The class of modular integer rings is
2697 Modular integer ring
2702 and the class of all modular integers (elements of modular integer rings) is
2710 Modular integer rings are constructed using the function
2713 @item cl_modint_ring cl_find_modint_ring (const cl_I& N)
2714 This function returns the modular ring @samp{Z/NZ}. It takes care
2715 of finding out about special cases of @code{N}, like powers of two
2716 and odd numbers for which Montgomery multiplication will be a win,
2717 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2718 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2719 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2723 Modular integer rings can be compared for equality:
2726 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2727 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2728 These compare two modular integer rings for equality. Two different calls
2729 to @code{cl_find_modint_ring} with the same argument necessarily return the
2730 same ring because it is memoized in the cache table.
2733 @node Functions on modular integers, , Modular integer rings, Modular integers
2734 @section Functions on modular integers
2736 Given a modular integer ring @code{R}, the following members can be used.
2739 @item cl_I R->modulus
2740 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2742 @item cl_MI R->zero()
2743 This returns @code{0 mod N}.
2745 @item cl_MI R->one()
2746 This returns @code{1 mod N}.
2748 @item cl_MI R->canonhom (const cl_I& x)
2749 This returns @code{x mod N}.
2751 @item cl_I R->retract (const cl_MI& x)
2752 This is a partial inverse function to @code{R->canonhom}. It returns the
2753 standard representative (@code{>=0}, @code{<N}) of @code{x}.
2755 @item cl_MI R->random(cl_random_state& randomstate)
2756 @itemx cl_MI R->random()
2757 This returns a random integer modulo @code{N}.
2760 The following operations are defined on modular integers.
2763 @item cl_modint_ring x.ring ()
2764 Returns the ring to which the modular integer @code{x} belongs.
2766 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
2767 Returns the sum of two modular integers. One of the arguments may also be
2770 @item cl_MI operator- (const cl_MI&, const cl_MI&)
2771 Returns the difference of two modular integers. One of the arguments may also be
2774 @item cl_MI operator- (const cl_MI&)
2775 Returns the negative of a modular integer.
2777 @item cl_MI operator* (const cl_MI&, const cl_MI&)
2778 Returns the product of two modular integers. One of the arguments may also be
2781 @item cl_MI square (const cl_MI&)
2782 Returns the square of a modular integer.
2784 @item cl_MI recip (const cl_MI& x)
2785 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
2786 must be coprime to the modulus, otherwise an error message is issued.
2788 @item cl_MI div (const cl_MI& x, const cl_MI& y)
2789 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
2790 @code{y} must be coprime to the modulus, otherwise an error message is issued.
2792 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
2793 @code{y} must be > 0. Returns @code{x^y}.
2795 @item cl_MI expt (const cl_MI& x, const cl_I& y)
2796 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
2797 modulus, else an error message is issued.
2799 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
2800 Returns @code{x*2^y}.
2802 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
2803 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
2804 or an error message is issued.
2806 @item bool operator== (const cl_MI&, const cl_MI&)
2807 @itemx bool operator!= (const cl_MI&, const cl_MI&)
2808 Compares two modular integers, belonging to the same modular integer ring,
2811 @item cl_boolean zerop (const cl_MI& x)
2812 Returns true if @code{x} is @code{0 mod N}.
2815 The following output functions are defined (see also the chapter on
2819 @item void fprint (cl_ostream stream, const cl_MI& x)
2820 @itemx cl_ostream operator<< (cl_ostream stream, const cl_MI& x)
2821 Prints the modular integer @code{x} on the @code{stream}. The output may depend
2822 on the global printer settings in the variable @code{cl_default_print_flags}.
2826 @node Symbolic data types, Univariate polynomials, Modular integers, Top
2827 @chapter Symbolic data types
2829 CLN implements two symbolic (non-numeric) data types: strings and symbols.
2836 @node Strings, Symbols, Symbolic data types, Symbolic data types
2847 implements immutable strings.
2849 Strings are constructed through the following constructors:
2852 @item cl_string (const char * s)
2853 Returns an immutable copy of the (zero-terminated) C string @code{s}.
2855 @item cl_string (const char * ptr, unsigned long len)
2856 Returns an immutable copy of the @code{len} characters at
2857 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
2860 The following functions are available on strings:
2864 Assignment from @code{cl_string} and @code{const char *}.
2868 Returns the length of the string @code{s}.
2871 Returns the @code{i}th character of the string @code{s}.
2872 @code{i} must be in the range @code{0 <= i < s.length()}.
2874 @item bool equal (const cl_string& s1, const cl_string& s2)
2875 Compares two strings for equality. One of the arguments may also be a
2876 plain @code{const char *}.
2879 @node Symbols, , Strings, Symbolic data types
2882 Symbols are uniquified strings: all symbols with the same name are shared.
2883 This means that comparison of two symbols is fast (effectively just a pointer
2884 comparison), whereas comparison of two strings must in the worst case walk
2885 both strings until their end.
2886 Symbols are used, for example, as tags for properties, as names of variables
2887 in polynomial rings, etc.
2889 Symbols are constructed through the following constructor:
2892 @item cl_symbol (const cl_string& s)
2893 Looks up or creates a new symbol with a given name.
2896 The following operations are available on symbols:
2899 @item cl_string (const cl_symbol& sym)
2900 Conversion to @code{cl_string}: Returns the string which names the symbol
2903 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
2904 Compares two symbols for equality. This is very fast.
2908 @node Univariate polynomials, Internals, Symbolic data types, Top
2909 @chapter Univariate polynomials
2912 * Univariate polynomial rings::
2913 * Functions on univariate polynomials::
2914 * Special polynomials::
2917 @node Univariate polynomial rings, Functions on univariate polynomials, Univariate polynomials, Univariate polynomials
2918 @section Univariate polynomial rings
2920 CLN implements univariate polynomials (polynomials in one variable) over an
2921 arbitrary ring. The indeterminate variable may be either unnamed (and will be
2922 printed according to @code{cl_default_print_flags.univpoly_varname}, which
2923 defaults to @samp{x}) or carry a given name. The base ring and the
2924 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
2925 (accidentally) mix elements of different polynomial rings, e.g.
2926 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
2927 return a multivariate polynomial, but they are not yet implemented in CLN.)
2929 The classes of univariate polynomial rings are
2937 Univariate polynomial ring
2941 +----------------+-------------------+
2943 Complex polynomial ring | Modular integer polynomial ring
2944 cl_univpoly_complex_ring | cl_univpoly_modint_ring
2945 <cl_univpoly_complex.h> | <cl_univpoly_modint.h>
2949 Real polynomial ring |
2950 cl_univpoly_real_ring |
2951 <cl_univpoly_real.h> |
2955 Rational polynomial ring |
2956 cl_univpoly_rational_ring |
2957 <cl_univpoly_rational.h> |
2961 Integer polynomial ring
2962 cl_univpoly_integer_ring
2963 <cl_univpoly_integer.h>
2966 and the corresponding classes of univariate polynomials are
2969 Univariate polynomial
2973 +----------------+-------------------+
2975 Complex polynomial | Modular integer polynomial
2977 <cl_univpoly_complex.h> | <cl_univpoly_modint.h>
2983 <cl_univpoly_real.h> |
2987 Rational polynomial |
2989 <cl_univpoly_rational.h> |
2995 <cl_univpoly_integer.h>
2998 Univariate polynomial rings are constructed using the functions
3001 @item cl_univpoly_ring cl_find_univpoly_ring (const cl_ring& R)
3002 @itemx cl_univpoly_ring cl_find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3003 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3004 @code{R} may be an arbitrary ring. This function takes care of finding out
3005 about special cases of @code{R}, such as the rings of complex numbers,
3006 real numbers, rational numbers, integers, or modular integer rings.
3007 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3008 This ensures that two calls of this function with the same arguments will
3009 return the same polynomial ring.
3011 @item cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring& R)
3012 @itemx cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3013 @itemx cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring& R)
3014 @itemx cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3015 @itemx cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring& R)
3016 @itemx cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3017 @itemx cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring& R)
3018 @itemx cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3019 @itemx cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring& R)
3020 @itemx cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3021 These functions are equivalent to the general @code{cl_find_univpoly_ring},
3022 only the return type is more specific, according to the base ring's type.
3025 @node Functions on univariate polynomials, Special polynomials, Univariate polynomial rings, Univariate polynomials
3026 @section Functions on univariate polynomials
3028 Given a univariate polynomial ring @code{R}, the following members can be used.
3031 @item cl_ring R->basering()
3032 This returns the base ring, as passed to @samp{cl_find_univpoly_ring}.
3034 @item cl_UP R->zero()
3035 This returns @code{0 in R}, a polynomial of degree -1.
3037 @item cl_UP R->one()
3038 This returns @code{1 in R}, a polynomial of degree <= 0.
3040 @item cl_UP R->canonhom (const cl_I& x)
3041 This returns @code{x in R}, a polynomial of degree <= 0.
3043 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3044 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3047 @item cl_UP R->create (sintL degree)
3048 Creates a new polynomial with a given degree. The zero polynomial has degree
3049 @code{-1}. After creating the polynomial, you should put in the coefficients,
3050 using the @code{set_coeff} member function, and then call the @code{finalize}
3054 The following are the only destructive operations on univariate polynomials.
3057 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3058 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3059 After changing a polynomial and before applying any "normal" operation on it,
3060 you should call its @code{finalize} member function.
3062 @item void finalize (cl_UP& x)
3063 This function marks the endpoint of destructive modifications of a polynomial.
3064 It normalizes the internal representation so that subsequent computations have
3065 less overhead. Doing normal computations on unnormalized polynomials may
3066 produce wrong results or crash the program.
3069 The following operations are defined on univariate polynomials.
3072 @item cl_univpoly_ring x.ring ()
3073 Returns the ring to which the univariate polynomial @code{x} belongs.
3075 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3076 Returns the sum of two univariate polynomials.
3078 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3079 Returns the difference of two univariate polynomials.
3081 @item cl_UP operator- (const cl_UP&)
3082 Returns the negative of a univariate polynomial.
3084 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3085 Returns the product of two univariate polynomials. One of the arguments may
3086 also be a plain integer or an element of the base ring.
3088 @item cl_UP square (const cl_UP&)
3089 Returns the square of a univariate polynomial.
3091 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3092 @code{y} must be > 0. Returns @code{x^y}.
3094 @item bool operator== (const cl_UP&, const cl_UP&)
3095 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3096 Compares two univariate polynomials, belonging to the same univariate
3097 polynomial ring, for equality.
3099 @item cl_boolean zerop (const cl_UP& x)
3100 Returns true if @code{x} is @code{0 in R}.
3102 @item sintL degree (const cl_UP& x)
3103 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3105 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3106 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3108 @item cl_ring_element x (const cl_ring_element& y)
3109 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3110 then @samp{x(y)} returns the value of the substitution of @code{y} into
3113 @item cl_UP deriv (const cl_UP& x)
3114 Returns the derivative of the polynomial @code{x} with respect to the
3115 indeterminate @code{X}.
3118 The following output functions are defined (see also the chapter on
3122 @item void fprint (cl_ostream stream, const cl_UP& x)
3123 @itemx cl_ostream operator<< (cl_ostream stream, const cl_UP& x)
3124 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3125 depend on the global printer settings in the variable
3126 @code{cl_default_print_flags}.
3129 @node Special polynomials, , Functions on univariate polynomials, Univariate polynomials
3130 @section Special polynomials
3132 The following functions return special polynomials.
3135 @item cl_UP_I cl_tschebychev (sintL n)
3136 Returns the n-th Tchebychev polynomial (n >= 0).
3138 @item cl_UP_I cl_hermite (sintL n)
3139 Returns the n-th Hermite polynomial (n >= 0).
3141 @item cl_UP_RA cl_legendre (sintL n)
3142 Returns the n-th Legendre polynomial (n >= 0).
3144 @item cl_UP_I cl_laguerre (sintL n)
3145 Returns the n-th Laguerre polynomial (n >= 0).
3148 Information how to derive the differential equation satisfied by each
3149 of these polynomials from their definition can be found in the
3150 @code{doc/polynomial/} directory.
3153 @node Internals, Using the library, Univariate polynomials, Top
3158 * Memory efficiency::
3159 * Speed efficiency::
3160 * Garbage collection::
3163 @node Why C++ ?, Memory efficiency, Internals, Internals
3166 Using C++ as an implementation language provides
3170 Efficiency: It compiles to machine code.
3173 Portability: It runs on all platforms supporting a C++ compiler. Because
3174 of the availability of GNU C++, this includes all currently used 32-bit and
3175 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3178 Type safety: The C++ compilers knows about the number types and complains if,
3179 for example, you try to assign a float to an integer variable. However,
3180 a drawback is that C++ doesn't know about generic types, hence a restriction
3181 like that @code{operation+ (const cl_MI&, const cl_MI&)} requires that both
3182 arguments belong to the same modular ring cannot be expressed as a compile-time
3186 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3187 @code{=}, @code{==}, ... can be used in infix notation, which is more
3188 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3191 With these language features, there is no need for two separate languages,
3192 one for the implementation of the library and one in which the library's users
3193 can program. This means that a prototype implementation of an algorithm
3194 can be integrated into the library immediately after it has been tested and
3195 debugged. No need to rewrite it in a low-level language after having prototyped
3196 in a high-level language.
3199 @node Memory efficiency, Speed efficiency, Why C++ ?, Internals
3200 @section Memory efficiency
3202 In order to save memory allocations, CLN implements:
3206 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3209 Garbage collection: A reference counting mechanism makes sure that any
3210 number object's storage is freed immediately when the last reference to the
3213 Small integers are represented as immediate values instead of pointers
3214 to heap allocated storage. This means that integers @code{> -2^29},
3215 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3220 @node Speed efficiency, Garbage collection, Memory efficiency, Internals
3221 @section Speed efficiency
3223 Speed efficiency is obtained by the combination of the following tricks
3228 Small integers, being represented as immediate values, don't require
3229 memory access, just a couple of instructions for each elementary operation.
3231 The kernel of CLN has been written in assembly language for some CPUs
3232 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3234 On all CPUs, CLN uses the superefficient low-level routines from GNU
3237 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3238 algorithm, the Karatsuba multiplication, which is an
3249 For very large numbers (more than 12000 decimal digits), CLN uses
3251 Sch{@"o}nhage-Strassen
3256 multiplication, which is an asymptotically
3257 optimal multiplication algorithm.
3259 These fast multiplication algorithms also give improvements in the speed
3260 of division and radix conversion.
3264 @node Garbage collection, , Speed efficiency, Internals
3265 @section Garbage collection
3267 All the number classes are reference count classes: They only contain a pointer
3268 to an object in the heap. Upon construction, assignment and destruction of
3269 number objects, only the objects' reference count are manipulated.
3271 Memory occupied by number objects are automatically reclaimed as soon as
3272 their reference count drops to zero.
3274 For number rings, another strategy is implemented: There is a cache of,
3275 for example, the modular integer rings. A modular integer ring is destroyed
3276 only if its reference count dropped to zero and the cache is about to be
3277 resized. The effect of this strategy is that recently used rings remain
3278 cached, whereas undue memory consumption through cached rings is avoided.
3281 @node Using the library, Customizing, Internals, Top
3282 @chapter Using the library
3284 For the following discussion, we will assume that you have installed
3285 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3286 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3287 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3288 environment variables, or directly substitute the appropriate values.
3292 * Compiler options::
3295 * Debugging support::
3298 @node Compiler options, Include files, Using the library, Using the library
3299 @section Compiler options
3301 Until you have installed CLN in a public place, the following options are
3304 When you compile CLN application code, add the flags
3306 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3308 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3309 When you link CLN application code to form an executable, add the flags
3311 $CLN_TARGETDIR/src/libcln.a
3313 to the C/C++ compiler's command line (@code{make} variable LIBS).
3315 If you did a @code{make install}, the include files are installed in a
3316 public directory (normally @code{/usr/local/include}), hence you don't
3317 need special flags for compiling. The library has been installed to a
3318 public directory as well (normally @code{/usr/local/lib}), hence when
3319 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3322 @node Include files, An Example, Compiler options, Using the library
3323 @section Include files
3325 Here is a summary of the include files and their contents.
3329 General definitions, reference counting, garbage collection.
3331 The class cl_number.
3332 @item <cl_complex.h>
3333 Functions for class cl_N, the complex numbers.
3335 Functions for class cl_R, the real numbers.
3337 Functions for class cl_F, the floats.
3339 Functions for class cl_SF, the short-floats.
3341 Functions for class cl_FF, the single-floats.
3343 Functions for class cl_DF, the double-floats.
3345 Functions for class cl_LF, the long-floats.
3346 @item <cl_rational.h>
3347 Functions for class cl_RA, the rational numbers.
3348 @item <cl_integer.h>
3349 Functions for class cl_I, the integers.
3352 @item <cl_complex_io.h>
3353 Input/Output for class cl_N, the complex numbers.
3354 @item <cl_real_io.h>
3355 Input/Output for class cl_R, the real numbers.
3356 @item <cl_float_io.h>
3357 Input/Output for class cl_F, the floats.
3358 @item <cl_sfloat_io.h>
3359 Input/Output for class cl_SF, the short-floats.
3360 @item <cl_ffloat_io.h>
3361 Input/Output for class cl_FF, the single-floats.
3362 @item <cl_dfloat_io.h>
3363 Input/Output for class cl_DF, the double-floats.
3364 @item <cl_lfloat_io.h>
3365 Input/Output for class cl_LF, the long-floats.
3366 @item <cl_rational_io.h>
3367 Input/Output for class cl_RA, the rational numbers.
3368 @item <cl_integer_io.h>
3369 Input/Output for class cl_I, the integers.
3371 Flags for customizing input operations.
3373 Flags for customizing output operations.
3375 @code{cl_malloc_hook}, @code{cl_free_hook}.
3378 @item <cl_condition.h>
3379 Conditions/exceptions.
3384 @item <cl_proplist.h>
3388 @item <cl_null_ring.h>
3390 @item <cl_complex_ring.h>
3391 The ring of complex numbers.
3392 @item <cl_real_ring.h>
3393 The ring of real numbers.
3394 @item <cl_rational_ring.h>
3395 The ring of rational numbers.
3396 @item <cl_integer_ring.h>
3397 The ring of integers.
3398 @item <cl_numtheory.h>
3399 Number threory functions.
3400 @item <cl_modinteger.h>
3406 @item <cl_GV_number.h>
3407 General vectors over cl_number.
3408 @item <cl_GV_complex.h>
3409 General vectors over cl_N.
3410 @item <cl_GV_real.h>
3411 General vectors over cl_R.
3412 @item <cl_GV_rational.h>
3413 General vectors over cl_RA.
3414 @item <cl_GV_integer.h>
3415 General vectors over cl_I.
3416 @item <cl_GV_modinteger.h>
3417 General vectors of modular integers.
3420 @item <cl_SV_number.h>
3421 Simple vectors over cl_number.
3422 @item <cl_SV_complex.h>
3423 Simple vectors over cl_N.
3424 @item <cl_SV_real.h>
3425 Simple vectors over cl_R.
3426 @item <cl_SV_rational.h>
3427 Simple vectors over cl_RA.
3428 @item <cl_SV_integer.h>
3429 Simple vectors over cl_I.
3430 @item <cl_SV_ringelt.h>
3431 Simple vectors of general ring elements.
3432 @item <cl_univpoly.h>
3433 Univariate polynomials.
3434 @item <cl_univpoly_integer.h>
3435 Univariate polynomials over the integers.
3436 @item <cl_univpoly_rational.h>
3437 Univariate polynomials over the rational numbers.
3438 @item <cl_univpoly_real.h>
3439 Univariate polynomials over the real numbers.
3440 @item <cl_univpoly_complex.h>
3441 Univariate polynomials over the complex numbers.
3442 @item <cl_univpoly_modint.h>
3443 Univariate polynomials over modular integer rings.
3447 Includes all of the above.
3451 @node An Example, Debugging support, Include files, Using the library
3454 A function which computes the nth Fibonacci number can be written as follows.
3457 #include <cl_integer.h>
3458 #include <cl_real.h>
3460 // Returns F_n, computed as the nearest integer to
3461 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3462 const cl_I fibonacci (int n)
3464 // Need a precision of ((1+sqrt(5))/2)^-n.
3465 cl_float_format_t prec = cl_float_format((int)(0.208987641*n+5));
3466 cl_R sqrt5 = sqrt(cl_float(5,prec));
3467 cl_R phi = (1+sqrt5)/2;
3468 return round1( expt(phi,n)/sqrt5 );
3472 Let's explain what is going on in detail.
3474 The include file @code{<cl_integer.h>} is necessary because the type
3475 @code{cl_I} is used in the function, and the include file @code{<cl_real.h>}
3476 is needed for the type @code{cl_R} and the floating point number functions.
3477 The order of the include files does not matter.
3479 Then comes the function declaration. The argument is an @code{int}, the
3480 result an integer. The return type is defined as @samp{const cl_I}, not
3481 simply @samp{cl_I}, because that allows the compiler to detect typos like
3482 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3483 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3484 number). We use the most specialized possible return type because functions
3485 which call @samp{fibonacci} will be able to profit from the compiler's type
3486 analysis: Adding two integers is slightly more efficient than adding the
3487 same objects declared as complex numbers, because it needs less type
3488 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3489 the size of the resulting executable program.
3491 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3492 integer. In order to get a correct result, the absolute error should be less
3493 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3494 To this end, the first line computes a floating point precision for sqrt(5)
3497 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3498 number and than taking the square root. The converse, first taking the square
3499 root of 5, and then converting to the desired precision, would not work in
3500 CLN: The square root would be computed to a default precision (normally
3501 single-float precision), and the following conversion could not help about
3502 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3503 system and does not represent sqrt(5) in a non-numeric way.
3505 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3506 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3507 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3508 @code{cl_N} because a @samp{round1} does not exist for general complex
3511 When the function returns, all the local variables in the function are
3512 automatically reclaimed (garbage collected). Only the result survives and
3513 gets passed to the caller.
3516 @node Debugging support, , An Example, Using the library
3517 @section Debugging support
3519 When debugging a CLN application with GNU @code{gdb}, two facilities are
3520 available from the library:
3523 @item The library does type checks, range checks, consistency checks at
3524 many places. When one of these fails, the function @code{cl_abort()} is
3525 called. Its default implementation is to perform an @code{exit(1)}, so
3526 you won't have a core dump. But for debugging, it is best to set a
3527 breakpoint at this function:
3529 (gdb) break cl_abort
3531 When this breakpoint is hit, look at the stack's backtrace:
3536 @item The debugger's normal @code{print} command doesn't know about
3537 CLN's types and therefore prints mostly useless hexadecimal addresses.
3538 CLN offers a function @code{cl_print}, callable from the debugger,
3539 for printing number objects. In order to get this function, you have
3540 to define the macro @samp{CL_DEBUG} and then include all the header files
3541 for which you want @code{cl_print} debugging support. For example:
3544 #include <cl_string.h>
3546 Now, if you have in your program a variable @code{cl_string s}, and
3547 inspect it under @code{gdb}, the output may look like this:
3550 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3551 word = 134568800@}@}, @}
3552 (gdb) call cl_print(s)
3556 Note that the output of @code{cl_print} goes to the program's error output,
3557 not to gdb's standard output.
3559 Note, however, that the above facility does not work with all CLN types,
3560 only with number objects and similar. Therefore CLN offers a member function
3561 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3562 is needed for this member function to be implemented. Under @code{gdb},
3563 you call it like this:
3566 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3567 word = 134568800@}@}, @}
3568 (gdb) call s.debug_print()
3571 >call ($1).debug_print()
3576 Unfortunately, this feature does not seem to work under all circumstances.
3580 @node Customizing, Index, Using the library, Top
3581 @chapter Customizing
3585 * Floating-point underflow::
3587 * Customizing the memory allocator::
3590 @node Error handling, Floating-point underflow, Customizing, Customizing
3591 @section Error handling
3593 When a fatal error occurs, an error message is output to the standard error
3594 output stream, and the function @code{cl_abort} is called. The default
3595 version of this function (provided in the library) terminates the application.
3596 To catch such a fatal error, you need to define the function @code{cl_abort}
3597 yourself, with the prototype
3599 #include <cl_abort.h>
3600 void cl_abort (void);
3602 This function must not return control to its caller.
3605 @node Floating-point underflow, Customizing I/O, Error handling, Customizing
3606 @section Floating-point underflow
3608 Floating point underflow denotes the situation when a floating-point number
3609 is to be created which is so close to @code{0} that its exponent is too
3610 low to be represented internally. By default, this causes a fatal error.
3611 If you set the global variable
3613 cl_boolean cl_inhibit_floating_point_underflow
3615 to @code{cl_true}, the error will be inhibited, and a floating-point zero
3616 will be generated instead.
3617 The default value of @code{cl_inhibit_floating_point_underflow} is
3621 @node Customizing I/O, Customizing the memory allocator, Floating-point underflow, Customizing
3622 @section Customizing I/O
3624 The output of the function @code{fprint} may be customized by changing the
3625 value of the global variable @code{cl_default_print_flags}.
3628 @node Customizing the memory allocator, , Customizing I/O, Customizing
3629 @section Customizing the memory allocator
3631 Every memory allocation of CLN is done through the function pointer
3632 @code{cl_malloc_hook}. Freeing of this memory is done through the function
3633 pointer @code{cl_free_hook}. The default versions of these functions,
3634 provided in the library, call @code{malloc} and @code{free} and check
3635 the @code{malloc} result against @code{NULL}.
3636 If you want to provide another memory allocator, you need to define
3637 the variables @code{cl_malloc_hook} and @code{cl_free_hook} yourself,
3640 #include <cl_malloc.h>
3641 void* (*cl_malloc_hook) (size_t size) = @dots{};
3642 void (*cl_free_hook) (void* ptr) = @dots{};
3644 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
3646 It is not possible to change the memory allocator at runtime, because
3647 it is already called at program startup by the constructors of some
3655 @node Index, , Customizing, Top
3661 @c Table of contents