1 \input texinfo @c -*-texinfo-*-
4 @settitle CLN, a Class Library for Numbers
5 @c @setchapternewpage off
10 @c I hate putting "@noindent" in front of every paragraph.
16 * CLN: (cln). Class Library for Numbers (C++).
21 @c Don't need the other types of indices.
32 This file documents @sc{cln}, a Class Library for Numbers.
34 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
35 Richard B. Kreckel, @code{<kreckel@@ginac.de>}.
37 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004.
38 Copyright (C) Richard B. Kreckel 2000, 2001, 2002, 2003, 2004.
40 Permission is granted to make and distribute verbatim copies of
41 this manual provided the copyright notice and this permission notice
42 are preserved on all copies.
45 Permission is granted to process this file through TeX and print the
46 results, provided the printed document carries copying permission
47 notice identical to this one except for the removal of this paragraph
48 (this paragraph not being relevant to the printed manual).
51 Permission is granted to copy and distribute modified versions of this
52 manual under the conditions for verbatim copying, provided that the entire
53 resulting derived work is distributed under the terms of a permission
54 notice identical to this one.
56 Permission is granted to copy and distribute translations of this manual
57 into another language, under the above conditions for modified versions,
58 except that this permission notice may be stated in a translation approved
64 @c prevent ugly black rectangles on overfull hbox lines:
67 @title CLN, a Class Library for Numbers
69 @author by Bruno Haible
71 @vskip 0pt plus 1filll
72 Copyright @copyright{} Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004.
74 Copyright @copyright{} Richard Kreckel 2000, 2001, 2002, 2003, 2004.
77 Published by Bruno Haible, @code{<haible@@clisp.cons.org>} and
78 Richard Kreckel, @code{<kreckel@@ginac.de>}.
80 Permission is granted to make and distribute verbatim copies of
81 this manual provided the copyright notice and this permission notice
82 are preserved on all copies.
84 Permission is granted to copy and distribute modified versions of this
85 manual under the conditions for verbatim copying, provided that the entire
86 resulting derived work is distributed under the terms of a permission
87 notice identical to this one.
89 Permission is granted to copy and distribute translations of this manual
90 into another language, under the above conditions for modified versions,
91 except that this permission notice may be stated in a translation approved
102 @node Top, Introduction, (dir), (dir)
105 @c * Introduction:: Introduction
109 @node Introduction, Top, Top, Top
110 @comment node-name, next, previous, up
111 @chapter Introduction
114 CLN is a library for computations with all kinds of numbers.
115 It has a rich set of number classes:
119 Integers (with unlimited precision),
125 Floating-point numbers:
135 Long float (with unlimited precision),
142 Modular integers (integers modulo a fixed integer),
145 Univariate polynomials.
149 The subtypes of the complex numbers among these are exactly the
150 types of numbers known to the Common Lisp language. Therefore
151 @code{CLN} can be used for Common Lisp implementations, giving
152 @samp{CLN} another meaning: it becomes an abbreviation of
153 ``Common Lisp Numbers''.
156 The CLN package implements
160 Elementary functions (@code{+}, @code{-}, @code{*}, @code{/}, @code{sqrt},
161 comparisons, @dots{}),
164 Logical functions (logical @code{and}, @code{or}, @code{not}, @dots{}),
167 Transcendental functions (exponential, logarithmic, trigonometric, hyperbolic
168 functions and their inverse functions).
172 CLN is a C++ library. Using C++ as an implementation language provides
176 efficiency: it compiles to machine code,
178 type safety: the C++ compiler knows about the number types and complains
179 if, for example, you try to assign a float to an integer variable.
181 algebraic syntax: You can use the @code{+}, @code{-}, @code{*}, @code{=},
182 @code{==}, @dots{} operators as in C or C++.
186 CLN is memory efficient:
190 Small integers and short floats are immediate, not heap allocated.
192 Heap-allocated memory is reclaimed through an automatic, non-interruptive
197 CLN is speed efficient:
201 The kernel of CLN has been written in assembly language for some CPUs
202 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
205 On all CPUs, CLN may be configured to use the superefficient low-level
206 routines from GNU GMP version 3.
208 It uses Karatsuba multiplication, which is significantly faster
209 for large numbers than the standard multiplication algorithm.
211 For very large numbers (more than 12000 decimal digits), it uses
213 Sch{@"o}nhage-Strassen
214 @cindex Sch{@"o}nhage-Strassen multiplication
218 @cindex Schnhage-Strassen multiplication
220 multiplication, which is an asymptotically optimal multiplication
221 algorithm, for multiplication, division and radix conversion.
225 CLN aims at being easily integrated into larger software packages:
229 The garbage collection imposes no burden on the main application.
231 The library provides hooks for memory allocation and exceptions.
234 All non-macro identifiers are hidden in namespace @code{cln} in
235 order to avoid name clashes.
239 @chapter Installation
241 This section describes how to install the CLN package on your system.
244 @section Prerequisites
246 @subsection C++ compiler
248 To build CLN, you need a C++ compiler.
249 Actually, you need GNU @code{g++ 2.95} or newer.
251 The following C++ features are used:
252 classes, member functions, overloading of functions and operators,
253 constructors and destructors, inline, const, multiple inheritance,
254 templates and namespaces.
256 The following C++ features are not used:
257 @code{new}, @code{delete}, virtual inheritance, exceptions.
259 CLN relies on semi-automatic ordering of initializations
260 of static and global variables, a feature which I could
261 implement for GNU g++ only.
264 @comment cl_modules.h requires g++
265 Therefore nearly any C++ compiler will do.
267 The following C++ compilers are known to compile CLN:
270 GNU @code{g++ 2.7.0}, @code{g++ 2.7.2}
275 The following C++ compilers are known to be unusable for CLN:
278 On SunOS 4, @code{CC 2.1}, because it doesn't grok @code{//} comments
279 in lines containing @code{#if} or @code{#elif} preprocessor commands.
281 On AIX 3.2.5, @code{xlC}, because it doesn't grok the template syntax
282 in @code{cl_SV.h} and @code{cl_GV.h}, because it forces most class types
283 to have default constructors, and because it probably miscompiles the
284 integer multiplication routines.
286 On AIX 4.1.4.0, @code{xlC}, because when optimizing, it sometimes converts
287 @code{short}s to @code{int}s by zero-extend.
291 On HPPA, GNU @code{g++ 2.7.x}, because the semi-automatic ordering of
292 initializations will not work.
296 @subsection Make utility
299 To build CLN, you also need to have GNU @code{make} installed.
301 Only GNU @code{make} 3.77 is unusable for CLN; other versions work fine.
303 @subsection Sed utility
306 To build CLN on HP-UX, you also need to have GNU @code{sed} installed.
307 This is because the libtool script, which creates the CLN library, relies
308 on @code{sed}, and the vendor's @code{sed} utility on these systems is too
312 @section Building the library
314 As with any autoconfiguring GNU software, installation is as easy as this:
322 If on your system, @samp{make} is not GNU @code{make}, you have to use
323 @samp{gmake} instead of @samp{make} above.
325 The @code{configure} command checks out some features of your system and
326 C++ compiler and builds the @code{Makefile}s. The @code{make} command
327 builds the library. This step may take about an hour on an average workstation.
328 The @code{make check} runs some test to check that no important subroutine
329 has been miscompiled.
331 The @code{configure} command accepts options. To get a summary of them, try
337 Some of the options are explained in detail in the @samp{INSTALL.generic} file.
339 You can specify the C compiler, the C++ compiler and their options through
340 the following environment variables when running @code{configure}:
344 Specifies the C compiler.
347 Flags to be given to the C compiler when compiling programs (not when linking).
350 Specifies the C++ compiler.
353 Flags to be given to the C++ compiler when compiling programs (not when linking).
359 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
360 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O -g" \
361 CXX="g++ -V egcs-2.91.60" CXXFLAGS="-O -g" ./configure
362 $ CC="gcc -V 2.95.2" CFLAGS="-O2 -fno-exceptions" \
363 CXX="g++ -V 2.95.2" CFLAGS="-O2 -fno-exceptions" ./configure
364 $ CC="gcc -V 3.0.4" CFLAGS="-O2 -finline-limit=1000 -fno-exceptions" \
365 CXX="g++ -V 3.0.4" CFLAGS="-O2 -finline-limit=1000 -fno-exceptions" \
369 @comment cl_modules.h requires g++
370 You should not mix GNU and non-GNU compilers. So, if @code{CXX} is a non-GNU
371 compiler, @code{CC} should be set to a non-GNU compiler as well. Examples:
374 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O" ./configure
375 $ CC="gcc -V 2.7.0" CFLAGS="-g" CXX="g++ -V 2.7.0" CXXFLAGS="-g" ./configure
378 On SGI Irix 5, if you wish not to use @code{g++}:
381 $ CC="cc" CFLAGS="-O" CXX="CC" CXXFLAGS="-O -Olimit 16000" ./configure
384 On SGI Irix 6, if you wish not to use @code{g++}:
387 $ CC="cc -32" CFLAGS="-O" CXX="CC -32" CXXFLAGS="-O -Olimit 34000" \
388 ./configure --without-gmp
389 $ CC="cc -n32" CFLAGS="-O" CXX="CC -n32" CXXFLAGS="-O \
390 -OPT:const_copy_limit=32400 -OPT:global_limit=32400 -OPT:fprop_limit=4000" \
391 ./configure --without-gmp
395 Note that for these environment variables to take effect, you have to set
396 them (assuming a Bourne-compatible shell) on the same line as the
397 @code{configure} command. If you made the settings in earlier shell
398 commands, you have to @code{export} the environment variables before
399 calling @code{configure}. In a @code{csh} shell, you have to use the
400 @samp{setenv} command for setting each of the environment variables.
402 Currently CLN works only with the GNU @code{g++} compiler, and only in
403 optimizing mode. So you should specify at least @code{-O} in the CXXFLAGS,
404 or no CXXFLAGS at all. (If CXXFLAGS is not set, CLN will use @code{-O}.)
406 If you use @code{g++} 3.0.x or 3.1, I recommend adding
407 @samp{-finline-limit=1000} to the CXXFLAGS. This is essential for good code.
409 If you use @code{g++} gcc-2.95.x or gcc-3.x , I recommend adding
410 @samp{-fno-exceptions} to the CXXFLAGS. This will likely generate better code.
412 If you use @code{g++} from gcc-3.0.4 or older on Sparc, add either
413 @samp{-O}, @samp{-O1} or @samp{-O2 -fno-schedule-insns} to the
414 CXXFLAGS. With full @samp{-O2}, @code{g++} miscompiles the division
415 routines. If you use @code{g++} older than 2.95.3 on Sparc you should
416 also specify @samp{--disable-shared} because of bad code produced in the
417 shared library. Also, do not use gcc-3.0 on Sparc for compiling CLN, it
420 If you use @code{g++} on OSF/1 or Tru64 using gcc-2.95.x, you should
421 specify @samp{--disable-shared} because of linker problems with
422 duplicate symbols in shared libraries. If you use @code{g++} from
423 gcc-3.0.n, with n larger than 1, you should @emph{not} add
424 @samp{-fno-exceptions} to the CXXFLAGS, since that will generate wrong
425 code (gcc-3.1 is okay again, as is gcc-3.0).
427 Also, please do not compile CLN with @code{g++} using the @code{-O3}
428 optimization level. This leads to inferior code quality.
430 If you use @code{g++} from gcc-3.1, it will need 235 MB of virtual memory.
431 You might need some swap space if your machine doesn't have 512 MB of RAM.
433 By default, both a shared and a static library are built. You can build
434 CLN as a static (or shared) library only, by calling @code{configure} with
435 the option @samp{--disable-shared} (or @samp{--disable-static}). While
436 shared libraries are usually more convenient to use, they may not work
437 on all architectures. Try disabling them if you run into linker
438 problems. Also, they are generally somewhat slower than static
439 libraries so runtime-critical applications should be linked statically.
441 If you are compiling on a 64-bit machine with 32-bit userland, you
442 might have to specify that explicitly while configuring the library.
443 For instance, the popular x86_64 architecture can host a 32-bit x86
444 operating system and toolchain on top of a 64-bit kernel. In such a
445 situation, you must explicitly tell configure @emph{not} to assume a
448 $ ./configure --build=i686-pc-linux-gnu
450 If you forget about this, the build will fail because @code{uname -m}
451 will set x86_64 which conflicts with what the compiler knows.
453 If you use @code{g++} from gcc-3.1 with option @samp{-g}, you will need
454 some disk space: 335 MB for building as both a shared and a static library,
455 or 130 MB when building as a shared library only.
458 @subsection Using the GNU MP Library
461 Starting with version 1.1, CLN may be configured to make use of a
462 preinstalled @code{gmp} library. Please make sure that you have at
463 least @code{gmp} version 3.0 installed since earlier versions are
464 unsupported and likely not to work. Enabling this feature by calling
465 @code{configure} with the option @samp{--with-gmp} is known to be quite
466 a boost for CLN's performance.
468 If you have installed the @code{gmp} library and its header file in
469 some place where your compiler cannot find it by default, you must help
470 @code{configure} by setting @code{CPPFLAGS} and @code{LDFLAGS}. Here is
474 $ CC="gcc" CFLAGS="-O2" CXX="g++" CXXFLAGS="-O2 -fno-exceptions" \
475 CPPFLAGS="-I/opt/gmp/include" LDFLAGS="-L/opt/gmp/lib" ./configure --with-gmp
479 @section Installing the library
482 As with any autoconfiguring GNU software, installation is as easy as this:
488 The @samp{make install} command installs the library and the include files
489 into public places (@file{/usr/local/lib/} and @file{/usr/local/include/},
490 if you haven't specified a @code{--prefix} option to @code{configure}).
491 This step may require superuser privileges.
493 If you have already built the library and wish to install it, but didn't
494 specify @code{--prefix=@dots{}} at configure time, just re-run
495 @code{configure}, giving it the same options as the first time, plus
496 the @code{--prefix=@dots{}} option.
501 You can remove system-dependent files generated by @code{make} through
507 You can remove all files generated by @code{make}, thus reverting to a
508 virgin distribution of CLN, through
515 @chapter Ordinary number types
517 CLN implements the following class hierarchy:
525 Real or complex number
534 +-------------------+-------------------+
536 Rational number Floating-point number
538 <cln/rational.h> <cln/float.h>
540 | +--------------+--------------+--------------+
542 cl_I Short-Float Single-Float Double-Float Long-Float
543 <cln/integer.h> cl_SF cl_FF cl_DF cl_LF
544 <cln/sfloat.h> <cln/ffloat.h> <cln/dfloat.h> <cln/lfloat.h>
547 @cindex @code{cl_number}
548 @cindex abstract class
549 The base class @code{cl_number} is an abstract base class.
550 It is not useful to declare a variable of this type except if you want
551 to completely disable compile-time type checking and use run-time type
556 @cindex complex number
557 The class @code{cl_N} comprises real and complex numbers. There is
558 no special class for complex numbers since complex numbers with imaginary
559 part @code{0} are automatically converted to real numbers.
562 The class @code{cl_R} comprises real numbers of different kinds. It is an
566 @cindex rational number
568 The class @code{cl_RA} comprises exact real numbers: rational numbers, including
569 integers. There is no special class for non-integral rational numbers
570 since rational numbers with denominator @code{1} are automatically converted
574 The class @code{cl_F} implements floating-point approximations to real numbers.
575 It is an abstract class.
578 @section Exact numbers
581 Some numbers are represented as exact numbers: there is no loss of information
582 when such a number is converted from its mathematical value to its internal
583 representation. On exact numbers, the elementary operations (@code{+},
584 @code{-}, @code{*}, @code{/}, comparisons, @dots{}) compute the completely
587 In CLN, the exact numbers are:
591 rational numbers (including integers),
593 complex numbers whose real and imaginary parts are both rational numbers.
596 Rational numbers are always normalized to the form
597 @code{@var{numerator}/@var{denominator}} where the numerator and denominator
598 are coprime integers and the denominator is positive. If the resulting
599 denominator is @code{1}, the rational number is converted to an integer.
601 @cindex immediate numbers
602 Small integers (typically in the range @code{-2^29}@dots{}@code{2^29-1},
603 for 32-bit machines) are especially efficient, because they consume no heap
604 allocation. Otherwise the distinction between these immediate integers
605 (called ``fixnums'') and heap allocated integers (called ``bignums'')
606 is completely transparent.
609 @section Floating-point numbers
610 @cindex floating-point number
612 Not all real numbers can be represented exactly. (There is an easy mathematical
613 proof for this: Only a countable set of numbers can be stored exactly in
614 a computer, even if one assumes that it has unlimited storage. But there
615 are uncountably many real numbers.) So some approximation is needed.
616 CLN implements ordinary floating-point numbers, with mantissa and exponent.
618 @cindex rounding error
619 The elementary operations (@code{+}, @code{-}, @code{*}, @code{/}, @dots{})
620 only return approximate results. For example, the value of the expression
621 @code{(cl_F) 0.3 + (cl_F) 0.4} prints as @samp{0.70000005}, not as
622 @samp{0.7}. Rounding errors like this one are inevitable when computing
623 with floating-point numbers.
625 Nevertheless, CLN rounds the floating-point results of the operations @code{+},
626 @code{-}, @code{*}, @code{/}, @code{sqrt} according to the ``round-to-even''
627 rule: It first computes the exact mathematical result and then returns the
628 floating-point number which is nearest to this. If two floating-point numbers
629 are equally distant from the ideal result, the one with a @code{0} in its least
630 significant mantissa bit is chosen.
632 Similarly, testing floating point numbers for equality @samp{x == y}
633 is gambling with random errors. Better check for @samp{abs(x - y) < epsilon}
634 for some well-chosen @code{epsilon}.
636 Floating point numbers come in four flavors:
641 Short floats, type @code{cl_SF}.
642 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
643 and 17 mantissa bits (including the ``hidden'' bit).
644 They don't consume heap allocation.
648 Single floats, type @code{cl_FF}.
649 They have 1 sign bit, 8 exponent bits (including the exponent's sign),
650 and 24 mantissa bits (including the ``hidden'' bit).
651 In CLN, they are represented as IEEE single-precision floating point numbers.
652 This corresponds closely to the C/C++ type @samp{float}.
656 Double floats, type @code{cl_DF}.
657 They have 1 sign bit, 11 exponent bits (including the exponent's sign),
658 and 53 mantissa bits (including the ``hidden'' bit).
659 In CLN, they are represented as IEEE double-precision floating point numbers.
660 This corresponds closely to the C/C++ type @samp{double}.
664 Long floats, type @code{cl_LF}.
665 They have 1 sign bit, 32 exponent bits (including the exponent's sign),
666 and n mantissa bits (including the ``hidden'' bit), where n >= 64.
667 The precision of a long float is unlimited, but once created, a long float
668 has a fixed precision. (No ``lazy recomputation''.)
671 Of course, computations with long floats are more expensive than those
672 with smaller floating-point formats.
674 CLN does not implement features like NaNs, denormalized numbers and
675 gradual underflow. If the exponent range of some floating-point type
676 is too limited for your application, choose another floating-point type
677 with larger exponent range.
680 As a user of CLN, you can forget about the differences between the
681 four floating-point types and just declare all your floating-point
682 variables as being of type @code{cl_F}. This has the advantage that
683 when you change the precision of some computation (say, from @code{cl_DF}
684 to @code{cl_LF}), you don't have to change the code, only the precision
685 of the initial values. Also, many transcendental functions have been
686 declared as returning a @code{cl_F} when the argument is a @code{cl_F},
687 but such declarations are missing for the types @code{cl_SF}, @code{cl_FF},
688 @code{cl_DF}, @code{cl_LF}. (Such declarations would be wrong if
689 the floating point contagion rule happened to change in the future.)
692 @section Complex numbers
693 @cindex complex number
695 Complex numbers, as implemented by the class @code{cl_N}, have a real
696 part and an imaginary part, both real numbers. A complex number whose
697 imaginary part is the exact number @code{0} is automatically converted
700 Complex numbers can arise from real numbers alone, for example
701 through application of @code{sqrt} or transcendental functions.
707 Conversions from any class to any its superclasses (``base classes'' in
708 C++ terminology) is done automatically.
710 Conversions from the C built-in types @samp{long} and @samp{unsigned long}
711 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
712 @code{cl_N} and @code{cl_number}.
714 Conversions from the C built-in types @samp{int} and @samp{unsigned int}
715 are provided for the classes @code{cl_I}, @code{cl_RA}, @code{cl_R},
716 @code{cl_N} and @code{cl_number}. However, these conversions emphasize
717 efficiency. Their range is therefore limited:
721 The conversion from @samp{int} works only if the argument is < 2^29 and > -2^29.
723 The conversion from @samp{unsigned int} works only if the argument is < 2^29.
726 In a declaration like @samp{cl_I x = 10;} the C++ compiler is able to
727 do the conversion of @code{10} from @samp{int} to @samp{cl_I} at compile time
728 already. On the other hand, code like @samp{cl_I x = 1000000000;} is
730 So, if you want to be sure that an @samp{int} whose magnitude is not guaranteed
731 to be < 2^29 is correctly converted to a @samp{cl_I}, first convert it to a
732 @samp{long}. Similarly, if a large @samp{unsigned int} is to be converted to a
733 @samp{cl_I}, first convert it to an @samp{unsigned long}.
735 Conversions from the C built-in type @samp{float} are provided for the classes
736 @code{cl_FF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
738 Conversions from the C built-in type @samp{double} are provided for the classes
739 @code{cl_DF}, @code{cl_F}, @code{cl_R}, @code{cl_N} and @code{cl_number}.
741 Conversions from @samp{const char *} are provided for the classes
742 @code{cl_I}, @code{cl_RA},
743 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F},
744 @code{cl_R}, @code{cl_N}.
745 The easiest way to specify a value which is outside of the range of the
746 C++ built-in types is therefore to specify it as a string, like this:
749 cl_I order_of_rubiks_cube_group = "43252003274489856000";
751 Note that this conversion is done at runtime, not at compile-time.
753 Conversions from @code{cl_I} to the C built-in types @samp{int},
754 @samp{unsigned int}, @samp{long}, @samp{unsigned long} are provided through
758 @item int cl_I_to_int (const cl_I& x)
759 @cindex @code{cl_I_to_int ()}
760 @itemx unsigned int cl_I_to_uint (const cl_I& x)
761 @cindex @code{cl_I_to_uint ()}
762 @itemx long cl_I_to_long (const cl_I& x)
763 @cindex @code{cl_I_to_long ()}
764 @itemx unsigned long cl_I_to_ulong (const cl_I& x)
765 @cindex @code{cl_I_to_ulong ()}
766 Returns @code{x} as element of the C type @var{ctype}. If @code{x} is not
767 representable in the range of @var{ctype}, a runtime error occurs.
770 Conversions from the classes @code{cl_I}, @code{cl_RA},
771 @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}, @code{cl_F} and
773 to the C built-in types @samp{float} and @samp{double} are provided through
777 @item float float_approx (const @var{type}& x)
778 @cindex @code{float_approx ()}
779 @itemx double double_approx (const @var{type}& x)
780 @cindex @code{double_approx ()}
781 Returns an approximation of @code{x} of C type @var{ctype}.
782 If @code{abs(x)} is too close to 0 (underflow), 0 is returned.
783 If @code{abs(x)} is too large (overflow), an IEEE infinity is returned.
786 Conversions from any class to any of its subclasses (``derived classes'' in
787 C++ terminology) are not provided. Instead, you can assert and check
788 that a value belongs to a certain subclass, and return it as element of that
789 class, using the @samp{As} and @samp{The} macros.
791 @cindex @code{As()()}
792 @code{As(@var{type})(@var{value})} checks that @var{value} belongs to
793 @var{type} and returns it as such.
794 @cindex @code{The()()}
795 @code{The(@var{type})(@var{value})} assumes that @var{value} belongs to
796 @var{type} and returns it as such. It is your responsibility to ensure
797 that this assumption is valid. Since macros and namespaces don't go
798 together well, there is an equivalent to @samp{The}: the template
806 if (!(x >= 0)) abort();
807 cl_I ten_x_a = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
808 // In general, it would be a rational number.
809 cl_I ten_x_b = the<cl_I>(expt(10,x)); // The same as above.
814 @chapter Functions on numbers
816 Each of the number classes declares its mathematical operations in the
817 corresponding include file. For example, if your code operates with
818 objects of type @code{cl_I}, it should @code{#include <cln/integer.h>}.
821 @section Constructing numbers
823 Here is how to create number objects ``from nothing''.
826 @subsection Constructing integers
828 @code{cl_I} objects are most easily constructed from C integers and from
829 strings. See @ref{Conversions}.
832 @subsection Constructing rational numbers
834 @code{cl_RA} objects can be constructed from strings. The syntax
835 for rational numbers is described in @ref{Internal and printed representation}.
836 Another standard way to produce a rational number is through application
837 of @samp{operator /} or @samp{recip} on integers.
840 @subsection Constructing floating-point numbers
842 @code{cl_F} objects with low precision are most easily constructed from
843 C @samp{float} and @samp{double}. See @ref{Conversions}.
845 To construct a @code{cl_F} with high precision, you can use the conversion
846 from @samp{const char *}, but you have to specify the desired precision
847 within the string. (See @ref{Internal and printed representation}.)
850 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
852 will set @samp{e} to the given value, with a precision of 40 decimal digits.
854 The programmatic way to construct a @code{cl_F} with high precision is
855 through the @code{cl_float} conversion function, see
856 @ref{Conversion to floating-point numbers}. For example, to compute
857 @code{e} to 40 decimal places, first construct 1.0 to 40 decimal places
858 and then apply the exponential function:
860 float_format_t precision = float_format(40);
861 cl_F e = exp(cl_float(1,precision));
865 @subsection Constructing complex numbers
867 Non-real @code{cl_N} objects are normally constructed through the function
869 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
871 See @ref{Elementary complex functions}.
874 @section Elementary functions
876 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
877 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
878 defines the following operations:
881 @item @var{type} operator + (const @var{type}&, const @var{type}&)
882 @cindex @code{operator + ()}
885 @item @var{type} operator - (const @var{type}&, const @var{type}&)
886 @cindex @code{operator - ()}
889 @item @var{type} operator - (const @var{type}&)
890 Returns the negative of the argument.
892 @item @var{type} plus1 (const @var{type}& x)
893 @cindex @code{plus1 ()}
894 Returns @code{x + 1}.
896 @item @var{type} minus1 (const @var{type}& x)
897 @cindex @code{minus1 ()}
898 Returns @code{x - 1}.
900 @item @var{type} operator * (const @var{type}&, const @var{type}&)
901 @cindex @code{operator * ()}
904 @item @var{type} square (const @var{type}& x)
905 @cindex @code{square ()}
906 Returns @code{x * x}.
909 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
910 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
911 defines the following operations:
914 @item @var{type} operator / (const @var{type}&, const @var{type}&)
915 @cindex @code{operator / ()}
918 @item @var{type} recip (const @var{type}&)
919 @cindex @code{recip ()}
920 Returns the reciprocal of the argument.
923 The class @code{cl_I} doesn't define a @samp{/} operation because
924 in the C/C++ language this operator, applied to integral types,
925 denotes the @samp{floor} or @samp{truncate} operation (which one of these,
926 is implementation dependent). (@xref{Rounding functions}.)
927 Instead, @code{cl_I} defines an ``exact quotient'' function:
930 @item cl_I exquo (const cl_I& x, const cl_I& y)
931 @cindex @code{exquo ()}
932 Checks that @code{y} divides @code{x}, and returns the quotient @code{x}/@code{y}.
935 The following exponentiation functions are defined:
938 @item cl_I expt_pos (const cl_I& x, const cl_I& y)
939 @cindex @code{expt_pos ()}
940 @itemx cl_RA expt_pos (const cl_RA& x, const cl_I& y)
941 @code{y} must be > 0. Returns @code{x^y}.
943 @item cl_RA expt (const cl_RA& x, const cl_I& y)
944 @cindex @code{expt ()}
945 @itemx cl_R expt (const cl_R& x, const cl_I& y)
946 @itemx cl_N expt (const cl_N& x, const cl_I& y)
950 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
951 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
952 defines the following operation:
955 @item @var{type} abs (const @var{type}& x)
956 @cindex @code{abs ()}
957 Returns the absolute value of @code{x}.
958 This is @code{x} if @code{x >= 0}, and @code{-x} if @code{x <= 0}.
961 The class @code{cl_N} implements this as follows:
964 @item cl_R abs (const cl_N x)
965 Returns the absolute value of @code{x}.
968 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
969 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
970 defines the following operation:
973 @item @var{type} signum (const @var{type}& x)
974 @cindex @code{signum ()}
975 Returns the sign of @code{x}, in the same number format as @code{x}.
976 This is defined as @code{x / abs(x)} if @code{x} is non-zero, and
977 @code{x} if @code{x} is zero. If @code{x} is real, the value is either
982 @section Elementary rational functions
984 Each of the classes @code{cl_RA}, @code{cl_I} defines the following operations:
987 @item cl_I numerator (const @var{type}& x)
988 @cindex @code{numerator ()}
989 Returns the numerator of @code{x}.
991 @item cl_I denominator (const @var{type}& x)
992 @cindex @code{denominator ()}
993 Returns the denominator of @code{x}.
996 The numerator and denominator of a rational number are normalized in such
997 a way that they have no factor in common and the denominator is positive.
1000 @section Elementary complex functions
1002 The class @code{cl_N} defines the following operation:
1005 @item cl_N complex (const cl_R& a, const cl_R& b)
1006 @cindex @code{complex ()}
1007 Returns the complex number @code{a+bi}, that is, the complex number with
1008 real part @code{a} and imaginary part @code{b}.
1011 Each of the classes @code{cl_N}, @code{cl_R} defines the following operations:
1014 @item cl_R realpart (const @var{type}& x)
1015 @cindex @code{realpart ()}
1016 Returns the real part of @code{x}.
1018 @item cl_R imagpart (const @var{type}& x)
1019 @cindex @code{imagpart ()}
1020 Returns the imaginary part of @code{x}.
1022 @item @var{type} conjugate (const @var{type}& x)
1023 @cindex @code{conjugate ()}
1024 Returns the complex conjugate of @code{x}.
1027 We have the relations
1031 @code{x = complex(realpart(x), imagpart(x))}
1033 @code{conjugate(x) = complex(realpart(x), -imagpart(x))}
1037 @section Comparisons
1040 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
1041 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1042 defines the following operations:
1045 @item bool operator == (const @var{type}&, const @var{type}&)
1046 @cindex @code{operator == ()}
1047 @itemx bool operator != (const @var{type}&, const @var{type}&)
1048 @cindex @code{operator != ()}
1049 Comparison, as in C and C++.
1051 @item uint32 equal_hashcode (const @var{type}&)
1052 @cindex @code{equal_hashcode ()}
1053 Returns a 32-bit hash code that is the same for any two numbers which are
1054 the same according to @code{==}. This hash code depends on the number's value,
1055 not its type or precision.
1057 @item cl_boolean zerop (const @var{type}& x)
1058 @cindex @code{zerop ()}
1059 Compare against zero: @code{x == 0}
1062 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1063 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1064 defines the following operations:
1067 @item cl_signean compare (const @var{type}& x, const @var{type}& y)
1068 @cindex @code{compare ()}
1069 Compares @code{x} and @code{y}. Returns +1 if @code{x}>@code{y},
1070 -1 if @code{x}<@code{y}, 0 if @code{x}=@code{y}.
1072 @item bool operator <= (const @var{type}&, const @var{type}&)
1073 @cindex @code{operator <= ()}
1074 @itemx bool operator < (const @var{type}&, const @var{type}&)
1075 @cindex @code{operator < ()}
1076 @itemx bool operator >= (const @var{type}&, const @var{type}&)
1077 @cindex @code{operator >= ()}
1078 @itemx bool operator > (const @var{type}&, const @var{type}&)
1079 @cindex @code{operator > ()}
1080 Comparison, as in C and C++.
1082 @item cl_boolean minusp (const @var{type}& x)
1083 @cindex @code{minusp ()}
1084 Compare against zero: @code{x < 0}
1086 @item cl_boolean plusp (const @var{type}& x)
1087 @cindex @code{plusp ()}
1088 Compare against zero: @code{x > 0}
1090 @item @var{type} max (const @var{type}& x, const @var{type}& y)
1091 @cindex @code{max ()}
1092 Return the maximum of @code{x} and @code{y}.
1094 @item @var{type} min (const @var{type}& x, const @var{type}& y)
1095 @cindex @code{min ()}
1096 Return the minimum of @code{x} and @code{y}.
1099 When a floating point number and a rational number are compared, the float
1100 is first converted to a rational number using the function @code{rational}.
1101 Since a floating point number actually represents an interval of real numbers,
1102 the result might be surprising.
1103 For example, @code{(cl_F)(cl_R)"1/3" == (cl_R)"1/3"} returns false because
1104 there is no floating point number whose value is exactly @code{1/3}.
1107 @section Rounding functions
1110 When a real number is to be converted to an integer, there is no ``best''
1111 rounding. The desired rounding function depends on the application.
1112 The Common Lisp and ISO Lisp standards offer four rounding functions:
1116 This is the largest integer <=@code{x}.
1119 This is the smallest integer >=@code{x}.
1122 Among the integers between 0 and @code{x} (inclusive) the one nearest to @code{x}.
1125 The integer nearest to @code{x}. If @code{x} is exactly halfway between two
1126 integers, choose the even one.
1129 These functions have different advantages:
1131 @code{floor} and @code{ceiling} are translation invariant:
1132 @code{floor(x+n) = floor(x) + n} and @code{ceiling(x+n) = ceiling(x) + n}
1133 for every @code{x} and every integer @code{n}.
1135 On the other hand, @code{truncate} and @code{round} are symmetric:
1136 @code{truncate(-x) = -truncate(x)} and @code{round(-x) = -round(x)},
1137 and furthermore @code{round} is unbiased: on the ``average'', it rounds
1138 down exactly as often as it rounds up.
1140 The functions are related like this:
1144 @code{ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1}
1145 for rational numbers @code{m/n} (@code{m}, @code{n} integers, @code{n}>0), and
1147 @code{truncate(x) = sign(x) * floor(abs(x))}
1150 Each of the classes @code{cl_R}, @code{cl_RA},
1151 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1152 defines the following operations:
1155 @item cl_I floor1 (const @var{type}& x)
1156 @cindex @code{floor1 ()}
1157 Returns @code{floor(x)}.
1158 @item cl_I ceiling1 (const @var{type}& x)
1159 @cindex @code{ceiling1 ()}
1160 Returns @code{ceiling(x)}.
1161 @item cl_I truncate1 (const @var{type}& x)
1162 @cindex @code{truncate1 ()}
1163 Returns @code{truncate(x)}.
1164 @item cl_I round1 (const @var{type}& x)
1165 @cindex @code{round1 ()}
1166 Returns @code{round(x)}.
1169 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_I},
1170 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1171 defines the following operations:
1174 @item cl_I floor1 (const @var{type}& x, const @var{type}& y)
1175 Returns @code{floor(x/y)}.
1176 @item cl_I ceiling1 (const @var{type}& x, const @var{type}& y)
1177 Returns @code{ceiling(x/y)}.
1178 @item cl_I truncate1 (const @var{type}& x, const @var{type}& y)
1179 Returns @code{truncate(x/y)}.
1180 @item cl_I round1 (const @var{type}& x, const @var{type}& y)
1181 Returns @code{round(x/y)}.
1184 These functions are called @samp{floor1}, @dots{} here instead of
1185 @samp{floor}, @dots{}, because on some systems, system dependent include
1186 files define @samp{floor} and @samp{ceiling} as macros.
1188 In many cases, one needs both the quotient and the remainder of a division.
1189 It is more efficient to compute both at the same time than to perform
1190 two divisions, one for quotient and the next one for the remainder.
1191 The following functions therefore return a structure containing both
1192 the quotient and the remainder. The suffix @samp{2} indicates the number
1193 of ``return values''. The remainder is defined as follows:
1197 for the computation of @code{quotient = floor(x)},
1198 @code{remainder = x - quotient},
1200 for the computation of @code{quotient = floor(x,y)},
1201 @code{remainder = x - quotient*y},
1204 and similarly for the other three operations.
1206 Each of the classes @code{cl_R}, @code{cl_RA},
1207 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1208 defines the following operations:
1211 @item struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1212 @itemx @var{type}_div_t floor2 (const @var{type}& x)
1213 @itemx @var{type}_div_t ceiling2 (const @var{type}& x)
1214 @itemx @var{type}_div_t truncate2 (const @var{type}& x)
1215 @itemx @var{type}_div_t round2 (const @var{type}& 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 struct @var{type}_div_t @{ cl_I quotient; @var{type} remainder; @};
1224 @itemx @var{type}_div_t floor2 (const @var{type}& x, const @var{type}& y)
1225 @cindex @code{floor2 ()}
1226 @itemx @var{type}_div_t ceiling2 (const @var{type}& x, const @var{type}& y)
1227 @cindex @code{ceiling2 ()}
1228 @itemx @var{type}_div_t truncate2 (const @var{type}& x, const @var{type}& y)
1229 @cindex @code{truncate2 ()}
1230 @itemx @var{type}_div_t round2 (const @var{type}& x, const @var{type}& y)
1231 @cindex @code{round2 ()}
1234 Sometimes, one wants the quotient as a floating-point number (of the
1235 same format as the argument, if the argument is a float) instead of as
1236 an integer. The prefix @samp{f} indicates this.
1239 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1240 defines the following operations:
1243 @item @var{type} ffloor (const @var{type}& x)
1244 @cindex @code{ffloor ()}
1245 @itemx @var{type} fceiling (const @var{type}& x)
1246 @cindex @code{fceiling ()}
1247 @itemx @var{type} ftruncate (const @var{type}& x)
1248 @cindex @code{ftruncate ()}
1249 @itemx @var{type} fround (const @var{type}& x)
1250 @cindex @code{fround ()}
1253 and similarly for class @code{cl_R}, but with return type @code{cl_F}.
1255 The class @code{cl_R} defines the following operations:
1258 @item cl_F ffloor (const @var{type}& x, const @var{type}& y)
1259 @itemx cl_F fceiling (const @var{type}& x, const @var{type}& y)
1260 @itemx cl_F ftruncate (const @var{type}& x, const @var{type}& y)
1261 @itemx cl_F fround (const @var{type}& x, const @var{type}& y)
1264 These functions also exist in versions which return both the quotient
1265 and the remainder. The suffix @samp{2} indicates this.
1268 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1269 defines the following operations:
1270 @cindex @code{cl_F_fdiv_t}
1271 @cindex @code{cl_SF_fdiv_t}
1272 @cindex @code{cl_FF_fdiv_t}
1273 @cindex @code{cl_DF_fdiv_t}
1274 @cindex @code{cl_LF_fdiv_t}
1277 @item struct @var{type}_fdiv_t @{ @var{type} quotient; @var{type} remainder; @};
1278 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x)
1279 @cindex @code{ffloor2 ()}
1280 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x)
1281 @cindex @code{fceiling2 ()}
1282 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x)
1283 @cindex @code{ftruncate2 ()}
1284 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x)
1285 @cindex @code{fround2 ()}
1287 and similarly for class @code{cl_R}, but with quotient type @code{cl_F}.
1288 @cindex @code{cl_R_fdiv_t}
1290 The class @code{cl_R} defines the following operations:
1293 @item struct @var{type}_fdiv_t @{ cl_F quotient; cl_R remainder; @};
1294 @itemx @var{type}_fdiv_t ffloor2 (const @var{type}& x, const @var{type}& y)
1295 @itemx @var{type}_fdiv_t fceiling2 (const @var{type}& x, const @var{type}& y)
1296 @itemx @var{type}_fdiv_t ftruncate2 (const @var{type}& x, const @var{type}& y)
1297 @itemx @var{type}_fdiv_t fround2 (const @var{type}& x, const @var{type}& y)
1300 Other applications need only the remainder of a division.
1301 The remainder of @samp{floor} and @samp{ffloor} is called @samp{mod}
1302 (abbreviation of ``modulo''). The remainder @samp{truncate} and
1303 @samp{ftruncate} is called @samp{rem} (abbreviation of ``remainder'').
1307 @code{mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y}
1309 @code{rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y}
1312 If @code{x} and @code{y} are both >= 0, @code{mod(x,y) = rem(x,y) >= 0}.
1313 In general, @code{mod(x,y)} has the sign of @code{y} or is zero,
1314 and @code{rem(x,y)} has the sign of @code{x} or is zero.
1316 The classes @code{cl_R}, @code{cl_I} define the following operations:
1319 @item @var{type} mod (const @var{type}& x, const @var{type}& y)
1320 @cindex @code{mod ()}
1321 @itemx @var{type} rem (const @var{type}& x, const @var{type}& y)
1322 @cindex @code{rem ()}
1328 Each of the classes @code{cl_R},
1329 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
1330 defines the following operation:
1333 @item @var{type} sqrt (const @var{type}& x)
1334 @cindex @code{sqrt ()}
1335 @code{x} must be >= 0. This function returns the square root of @code{x},
1336 normalized to be >= 0. If @code{x} is the square of a rational number,
1337 @code{sqrt(x)} will be a rational number, else it will return a
1338 floating-point approximation.
1341 The classes @code{cl_RA}, @code{cl_I} define the following operation:
1344 @item cl_boolean sqrtp (const @var{type}& x, @var{type}* root)
1345 @cindex @code{sqrtp ()}
1346 This tests whether @code{x} is a perfect square. If so, it returns true
1347 and the exact square root in @code{*root}, else it returns false.
1350 Furthermore, for integers, similarly:
1353 @item cl_boolean isqrt (const @var{type}& x, @var{type}* root)
1354 @cindex @code{isqrt ()}
1355 @code{x} should be >= 0. This function sets @code{*root} to
1356 @code{floor(sqrt(x))} and returns the same value as @code{sqrtp}:
1357 the boolean value @code{(expt(*root,2) == x)}.
1360 For @code{n}th roots, the classes @code{cl_RA}, @code{cl_I}
1361 define the following operation:
1364 @item cl_boolean rootp (const @var{type}& x, const cl_I& n, @var{type}* root)
1365 @cindex @code{rootp ()}
1366 @code{x} must be >= 0. @code{n} must be > 0.
1367 This tests whether @code{x} is an @code{n}th power of a rational number.
1368 If so, it returns true and the exact root in @code{*root}, else it returns
1372 The only square root function which accepts negative numbers is the one
1373 for class @code{cl_N}:
1376 @item cl_N sqrt (const cl_N& z)
1377 @cindex @code{sqrt ()}
1378 Returns the square root of @code{z}, as defined by the formula
1379 @code{sqrt(z) = exp(log(z)/2)}. Conversion to a floating-point type
1380 or to a complex number are done if necessary. The range of the result is the
1381 right half plane @code{realpart(sqrt(z)) >= 0}
1382 including the positive imaginary axis and 0, but excluding
1383 the negative imaginary axis.
1384 The result is an exact number only if @code{z} is an exact number.
1388 @section Transcendental functions
1389 @cindex transcendental functions
1391 The transcendental functions return an exact result if the argument
1392 is exact and the result is exact as well. Otherwise they must return
1393 inexact numbers even if the argument is exact.
1394 For example, @code{cos(0) = 1} returns the rational number @code{1}.
1397 @subsection Exponential and logarithmic functions
1400 @item cl_R exp (const cl_R& x)
1401 @cindex @code{exp ()}
1402 @itemx cl_N exp (const cl_N& x)
1403 Returns the exponential function of @code{x}. This is @code{e^x} where
1404 @code{e} is the base of the natural logarithms. The range of the result
1405 is the entire complex plane excluding 0.
1407 @item cl_R ln (const cl_R& x)
1408 @cindex @code{ln ()}
1409 @code{x} must be > 0. Returns the (natural) logarithm of x.
1411 @item cl_N log (const cl_N& x)
1412 @cindex @code{log ()}
1413 Returns the (natural) logarithm of x. If @code{x} is real and positive,
1414 this is @code{ln(x)}. In general, @code{log(x) = log(abs(x)) + i*phase(x)}.
1415 The range of the result is the strip in the complex plane
1416 @code{-pi < imagpart(log(x)) <= pi}.
1418 @item cl_R phase (const cl_N& x)
1419 @cindex @code{phase ()}
1420 Returns the angle part of @code{x} in its polar representation as a
1421 complex number. That is, @code{phase(x) = atan(realpart(x),imagpart(x))}.
1422 This is also the imaginary part of @code{log(x)}.
1423 The range of the result is the interval @code{-pi < phase(x) <= pi}.
1424 The result will be an exact number only if @code{zerop(x)} or
1425 if @code{x} is real and positive.
1427 @item cl_R log (const cl_R& a, const cl_R& b)
1428 @code{a} and @code{b} must be > 0. Returns the logarithm of @code{a} with
1429 respect to base @code{b}. @code{log(a,b) = ln(a)/ln(b)}.
1430 The result can be exact only if @code{a = 1} or if @code{a} and @code{b}
1433 @item cl_N log (const cl_N& a, const cl_N& b)
1434 Returns the logarithm of @code{a} with respect to base @code{b}.
1435 @code{log(a,b) = log(a)/log(b)}.
1437 @item cl_N expt (const cl_N& x, const cl_N& y)
1438 @cindex @code{expt ()}
1439 Exponentiation: Returns @code{x^y = exp(y*log(x))}.
1442 The constant e = exp(1) = 2.71828@dots{} is returned by the following functions:
1445 @item cl_F exp1 (float_format_t f)
1446 @cindex @code{exp1 ()}
1447 Returns e as a float of format @code{f}.
1449 @item cl_F exp1 (const cl_F& y)
1450 Returns e in the float format of @code{y}.
1452 @item cl_F exp1 (void)
1453 Returns e as a float of format @code{default_float_format}.
1457 @subsection Trigonometric functions
1460 @item cl_R sin (const cl_R& x)
1461 @cindex @code{sin ()}
1462 Returns @code{sin(x)}. The range of the result is the interval
1463 @code{-1 <= sin(x) <= 1}.
1465 @item cl_N sin (const cl_N& z)
1466 Returns @code{sin(z)}. The range of the result is the entire complex plane.
1468 @item cl_R cos (const cl_R& x)
1469 @cindex @code{cos ()}
1470 Returns @code{cos(x)}. The range of the result is the interval
1471 @code{-1 <= cos(x) <= 1}.
1473 @item cl_N cos (const cl_N& x)
1474 Returns @code{cos(z)}. The range of the result is the entire complex plane.
1476 @item struct cos_sin_t @{ cl_R cos; cl_R sin; @};
1477 @cindex @code{cos_sin_t}
1478 @itemx cos_sin_t cos_sin (const cl_R& x)
1479 Returns both @code{sin(x)} and @code{cos(x)}. This is more efficient than
1480 @cindex @code{cos_sin ()}
1481 computing them separately. The relation @code{cos^2 + sin^2 = 1} will
1482 hold only approximately.
1484 @item cl_R tan (const cl_R& x)
1485 @cindex @code{tan ()}
1486 @itemx cl_N tan (const cl_N& x)
1487 Returns @code{tan(x) = sin(x)/cos(x)}.
1489 @item cl_N cis (const cl_R& x)
1490 @cindex @code{cis ()}
1491 @itemx cl_N cis (const cl_N& x)
1492 Returns @code{exp(i*x)}. The name @samp{cis} means ``cos + i sin'', because
1493 @code{e^(i*x) = cos(x) + i*sin(x)}.
1496 @cindex @code{asin ()}
1497 @item cl_N asin (const cl_N& z)
1498 Returns @code{arcsin(z)}. This is defined as
1499 @code{arcsin(z) = log(iz+sqrt(1-z^2))/i} and satisfies
1500 @code{arcsin(-z) = -arcsin(z)}.
1501 The range of the result is the strip in the complex domain
1502 @code{-pi/2 <= realpart(arcsin(z)) <= pi/2}, excluding the numbers
1503 with @code{realpart = -pi/2} and @code{imagpart < 0} and the numbers
1504 with @code{realpart = pi/2} and @code{imagpart > 0}.
1506 Proof: This follows from arcsin(z) = arsinh(iz)/i and the corresponding
1510 @item cl_N acos (const cl_N& z)
1511 @cindex @code{acos ()}
1512 Returns @code{arccos(z)}. This is defined as
1513 @code{arccos(z) = pi/2 - arcsin(z) = log(z+i*sqrt(1-z^2))/i}
1516 @code{arccos(z) = 2*log(sqrt((1+z)/2)+i*sqrt((1-z)/2))/i}
1518 and satisfies @code{arccos(-z) = pi - arccos(z)}.
1519 The range of the result is the strip in the complex domain
1520 @code{0 <= realpart(arcsin(z)) <= pi}, excluding the numbers
1521 with @code{realpart = 0} and @code{imagpart < 0} and the numbers
1522 with @code{realpart = pi} and @code{imagpart > 0}.
1524 Proof: This follows from the results about arcsin.
1528 @cindex @code{atan ()}
1529 @item cl_R atan (const cl_R& x, const cl_R& y)
1530 Returns the angle of the polar representation of the complex number
1531 @code{x+iy}. This is @code{atan(y/x)} if @code{x>0}. The range of
1532 the result is the interval @code{-pi < atan(x,y) <= pi}. The result will
1533 be an exact number only if @code{x > 0} and @code{y} is the exact @code{0}.
1534 WARNING: In Common Lisp, this function is called as @code{(atan y x)},
1535 with reversed order of arguments.
1537 @item cl_R atan (const cl_R& x)
1538 Returns @code{arctan(x)}. This is the same as @code{atan(1,x)}. The range
1539 of the result is the interval @code{-pi/2 < atan(x) < pi/2}. The result
1540 will be an exact number only if @code{x} is the exact @code{0}.
1542 @item cl_N atan (const cl_N& z)
1543 Returns @code{arctan(z)}. This is defined as
1544 @code{arctan(z) = (log(1+iz)-log(1-iz)) / 2i} and satisfies
1545 @code{arctan(-z) = -arctan(z)}. The range of the result is
1546 the strip in the complex domain
1547 @code{-pi/2 <= realpart(arctan(z)) <= pi/2}, excluding the numbers
1548 with @code{realpart = -pi/2} and @code{imagpart >= 0} and the numbers
1549 with @code{realpart = pi/2} and @code{imagpart <= 0}.
1551 Proof: arctan(z) = artanh(iz)/i, we know the range of the artanh function.
1557 @cindex Archimedes' constant
1558 Archimedes' constant pi = 3.14@dots{} is returned by the following functions:
1561 @item cl_F pi (float_format_t f)
1562 @cindex @code{pi ()}
1563 Returns pi as a float of format @code{f}.
1565 @item cl_F pi (const cl_F& y)
1566 Returns pi in the float format of @code{y}.
1568 @item cl_F pi (void)
1569 Returns pi as a float of format @code{default_float_format}.
1573 @subsection Hyperbolic functions
1576 @item cl_R sinh (const cl_R& x)
1577 @cindex @code{sinh ()}
1578 Returns @code{sinh(x)}.
1580 @item cl_N sinh (const cl_N& z)
1581 Returns @code{sinh(z)}. The range of the result is the entire complex plane.
1583 @item cl_R cosh (const cl_R& x)
1584 @cindex @code{cosh ()}
1585 Returns @code{cosh(x)}. The range of the result is the interval
1586 @code{cosh(x) >= 1}.
1588 @item cl_N cosh (const cl_N& z)
1589 Returns @code{cosh(z)}. The range of the result is the entire complex plane.
1591 @item struct cosh_sinh_t @{ cl_R cosh; cl_R sinh; @};
1592 @cindex @code{cosh_sinh_t}
1593 @itemx cosh_sinh_t cosh_sinh (const cl_R& x)
1594 @cindex @code{cosh_sinh ()}
1595 Returns both @code{sinh(x)} and @code{cosh(x)}. This is more efficient than
1596 computing them separately. The relation @code{cosh^2 - sinh^2 = 1} will
1597 hold only approximately.
1599 @item cl_R tanh (const cl_R& x)
1600 @cindex @code{tanh ()}
1601 @itemx cl_N tanh (const cl_N& x)
1602 Returns @code{tanh(x) = sinh(x)/cosh(x)}.
1604 @item cl_N asinh (const cl_N& z)
1605 @cindex @code{asinh ()}
1606 Returns @code{arsinh(z)}. This is defined as
1607 @code{arsinh(z) = log(z+sqrt(1+z^2))} and satisfies
1608 @code{arsinh(-z) = -arsinh(z)}.
1610 Proof: Knowing the range of log, we know -pi < imagpart(arsinh(z)) <= pi.
1611 Actually, z+sqrt(1+z^2) can never be real and <0, so
1612 -pi < imagpart(arsinh(z)) < pi.
1613 We have (z+sqrt(1+z^2))*(-z+sqrt(1+(-z)^2)) = (1+z^2)-z^2 = 1, hence the
1614 logs of both factors sum up to 0 mod 2*pi*i, hence to 0.
1616 The range of the result is the strip in the complex domain
1617 @code{-pi/2 <= imagpart(arsinh(z)) <= pi/2}, excluding the numbers
1618 with @code{imagpart = -pi/2} and @code{realpart > 0} and the numbers
1619 with @code{imagpart = pi/2} and @code{realpart < 0}.
1621 Proof: Write z = x+iy. Because of arsinh(-z) = -arsinh(z), we may assume
1622 that z is in Range(sqrt), that is, x>=0 and, if x=0, then y>=0.
1623 If x > 0, then Re(z+sqrt(1+z^2)) = x + Re(sqrt(1+z^2)) >= x > 0,
1624 so -pi/2 < imagpart(log(z+sqrt(1+z^2))) < pi/2.
1625 If x = 0 and y >= 0, arsinh(z) = log(i*y+sqrt(1-y^2)).
1626 If y <= 1, the realpart is 0 and the imagpart is >= 0 and <= pi/2.
1627 If y >= 1, the imagpart is pi/2 and the realpart is
1628 log(y+sqrt(y^2-1)) >= log(y) >= 0.
1631 Moreover, if z is in Range(sqrt),
1632 log(sqrt(1+z^2)+z) = 2 artanh(z/(1+sqrt(1+z^2)))
1633 (for a proof, see file src/cl_C_asinh.cc).
1636 @item cl_N acosh (const cl_N& z)
1637 @cindex @code{acosh ()}
1638 Returns @code{arcosh(z)}. This is defined as
1639 @code{arcosh(z) = 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))}.
1640 The range of the result is the half-strip in the complex domain
1641 @code{-pi < imagpart(arcosh(z)) <= pi, realpart(arcosh(z)) >= 0},
1642 excluding the numbers with @code{realpart = 0} and @code{-pi < imagpart < 0}.
1644 Proof: sqrt((z+1)/2) and sqrt((z-1)/2)) lie in Range(sqrt), hence does
1645 their sum, hence its log has an imagpart <= pi/2 and > -pi/2.
1646 If z is in Range(sqrt), we have
1647 sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1)
1648 ==> (sqrt((z+1)/2)+sqrt((z-1)/2))^2 = (z+1)/2 + sqrt(z^2-1) + (z-1)/2
1650 ==> arcosh(z) = log(z+sqrt(z^2-1)) mod 2*pi*i
1651 and since the imagpart of both expressions is > -pi, <= pi
1652 ==> arcosh(z) = log(z+sqrt(z^2-1))
1653 To prove that the realpart of this is >= 0, write z = x+iy with x>=0,
1654 z^2-1 = u+iv with u = x^2-y^2-1, v = 2xy,
1655 sqrt(z^2-1) = p+iq with p = sqrt((sqrt(u^2+v^2)+u)/2) >= 0,
1656 q = sqrt((sqrt(u^2+v^2)-u)/2) * sign(v),
1657 then |z+sqrt(z^2-1)|^2 = |x+iy + p+iq|^2
1659 = x^2 + 2xp + p^2 + y^2 + 2yq + q^2
1660 >= x^2 + p^2 + y^2 + q^2 (since x>=0, p>=0, yq>=0)
1661 = x^2 + y^2 + sqrt(u^2+v^2)
1666 hence realpart(log(z+sqrt(z^2-1))) = log(|z+sqrt(z^2-1)|) >= 0.
1667 Equality holds only if y = 0 and u <= 0, i.e. 0 <= x < 1.
1668 In this case arcosh(z) = log(x+i*sqrt(1-x^2)) has imagpart >=0.
1669 Otherwise, -z is in Range(sqrt).
1670 If y != 0, sqrt((z+1)/2) = i^sign(y) * sqrt((-z-1)/2),
1671 sqrt((z-1)/2) = i^sign(y) * sqrt((-z+1)/2),
1672 hence arcosh(z) = sign(y)*pi/2*i + arcosh(-z),
1673 and this has realpart > 0.
1674 If y = 0 and -1<=x<=0, we still have sqrt(z+1)*sqrt(z-1) = sqrt(z^2-1),
1675 ==> arcosh(z) = log(z+sqrt(z^2-1)) = log(x+i*sqrt(1-x^2))
1676 has realpart = 0 and imagpart > 0.
1677 If y = 0 and x<=-1, however, sqrt(z+1)*sqrt(z-1) = - sqrt(z^2-1),
1678 ==> arcosh(z) = log(z-sqrt(z^2-1)) = pi*i + arcosh(-z).
1679 This has realpart >= 0 and imagpart = pi.
1682 @item cl_N atanh (const cl_N& z)
1683 @cindex @code{atanh ()}
1684 Returns @code{artanh(z)}. This is defined as
1685 @code{artanh(z) = (log(1+z)-log(1-z)) / 2} and satisfies
1686 @code{artanh(-z) = -artanh(z)}. The range of the result is
1687 the strip in the complex domain
1688 @code{-pi/2 <= imagpart(artanh(z)) <= pi/2}, excluding the numbers
1689 with @code{imagpart = -pi/2} and @code{realpart <= 0} and the numbers
1690 with @code{imagpart = pi/2} and @code{realpart >= 0}.
1692 Proof: Write z = x+iy. Examine
1693 imagpart(artanh(z)) = (atan(1+x,y) - atan(1-x,-y))/2.
1695 x > 1 ==> imagpart = -pi/2, realpart = 1/2 log((x+1)/(x-1)) > 0,
1696 x < -1 ==> imagpart = pi/2, realpart = 1/2 log((-x-1)/(-x+1)) < 0,
1697 |x| < 1 ==> imagpart = 0
1700 = (atan(1+x,y) - atan(1-x,-y))/2
1701 = ((pi/2 - atan((1+x)/y)) - (-pi/2 - atan((1-x)/-y)))/2
1702 = (pi - atan((1+x)/y) - atan((1-x)/y))/2
1703 > (pi - pi/2 - pi/2 )/2 = 0
1704 and (1+x)/y > (1-x)/y
1705 ==> atan((1+x)/y) > atan((-1+x)/y) = - atan((1-x)/y)
1706 ==> imagpart < pi/2.
1707 Hence 0 < imagpart < pi/2.
1709 By artanh(z) = -artanh(-z) and case 2, -pi/2 < imagpart < 0.
1714 @subsection Euler gamma
1715 @cindex Euler's constant
1717 Euler's constant C = 0.577@dots{} is returned by the following functions:
1720 @item cl_F eulerconst (float_format_t f)
1721 @cindex @code{eulerconst ()}
1722 Returns Euler's constant as a float of format @code{f}.
1724 @item cl_F eulerconst (const cl_F& y)
1725 Returns Euler's constant in the float format of @code{y}.
1727 @item cl_F eulerconst (void)
1728 Returns Euler's constant as a float of format @code{default_float_format}.
1731 Catalan's constant G = 0.915@dots{} is returned by the following functions:
1732 @cindex Catalan's constant
1735 @item cl_F catalanconst (float_format_t f)
1736 @cindex @code{catalanconst ()}
1737 Returns Catalan's constant as a float of format @code{f}.
1739 @item cl_F catalanconst (const cl_F& y)
1740 Returns Catalan's constant in the float format of @code{y}.
1742 @item cl_F catalanconst (void)
1743 Returns Catalan's constant as a float of format @code{default_float_format}.
1747 @subsection Riemann zeta
1748 @cindex Riemann's zeta
1750 Riemann's zeta function at an integral point @code{s>1} is returned by the
1751 following functions:
1754 @item cl_F zeta (int s, float_format_t f)
1755 @cindex @code{zeta ()}
1756 Returns Riemann's zeta function at @code{s} as a float of format @code{f}.
1758 @item cl_F zeta (int s, const cl_F& y)
1759 Returns Riemann's zeta function at @code{s} in the float format of @code{y}.
1761 @item cl_F zeta (int s)
1762 Returns Riemann's zeta function at @code{s} as a float of format
1763 @code{default_float_format}.
1767 @section Functions on integers
1769 @subsection Logical functions
1771 Integers, when viewed as in two's complement notation, can be thought as
1772 infinite bit strings where the bits' values eventually are constant.
1779 The logical operations view integers as such bit strings and operate
1780 on each of the bit positions in parallel.
1783 @item cl_I lognot (const cl_I& x)
1784 @cindex @code{lognot ()}
1785 @itemx cl_I operator ~ (const cl_I& x)
1786 @cindex @code{operator ~ ()}
1787 Logical not, like @code{~x} in C. This is the same as @code{-1-x}.
1789 @item cl_I logand (const cl_I& x, const cl_I& y)
1790 @cindex @code{logand ()}
1791 @itemx cl_I operator & (const cl_I& x, const cl_I& y)
1792 @cindex @code{operator & ()}
1793 Logical and, like @code{x & y} in C.
1795 @item cl_I logior (const cl_I& x, const cl_I& y)
1796 @cindex @code{logior ()}
1797 @itemx cl_I operator | (const cl_I& x, const cl_I& y)
1798 @cindex @code{operator | ()}
1799 Logical (inclusive) or, like @code{x | y} in C.
1801 @item cl_I logxor (const cl_I& x, const cl_I& y)
1802 @cindex @code{logxor ()}
1803 @itemx cl_I operator ^ (const cl_I& x, const cl_I& y)
1804 @cindex @code{operator ^ ()}
1805 Exclusive or, like @code{x ^ y} in C.
1807 @item cl_I logeqv (const cl_I& x, const cl_I& y)
1808 @cindex @code{logeqv ()}
1809 Bitwise equivalence, like @code{~(x ^ y)} in C.
1811 @item cl_I lognand (const cl_I& x, const cl_I& y)
1812 @cindex @code{lognand ()}
1813 Bitwise not and, like @code{~(x & y)} in C.
1815 @item cl_I lognor (const cl_I& x, const cl_I& y)
1816 @cindex @code{lognor ()}
1817 Bitwise not or, like @code{~(x | y)} in C.
1819 @item cl_I logandc1 (const cl_I& x, const cl_I& y)
1820 @cindex @code{logandc1 ()}
1821 Logical and, complementing the first argument, like @code{~x & y} in C.
1823 @item cl_I logandc2 (const cl_I& x, const cl_I& y)
1824 @cindex @code{logandc2 ()}
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 @cindex @code{logorc1 ()}
1829 Logical or, complementing the first argument, like @code{~x | y} in C.
1831 @item cl_I logorc2 (const cl_I& x, const cl_I& y)
1832 @cindex @code{logorc2 ()}
1833 Logical or, complementing the second argument, like @code{x | ~y} in C.
1836 These operations are all available though the function
1838 @item cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)
1839 @cindex @code{boole ()}
1841 where @code{op} must have one of the 16 values (each one stands for a function
1842 which combines two bits into one bit): @code{boole_clr}, @code{boole_set},
1843 @code{boole_1}, @code{boole_2}, @code{boole_c1}, @code{boole_c2},
1844 @code{boole_and}, @code{boole_ior}, @code{boole_xor}, @code{boole_eqv},
1845 @code{boole_nand}, @code{boole_nor}, @code{boole_andc1}, @code{boole_andc2},
1846 @code{boole_orc1}, @code{boole_orc2}.
1847 @cindex @code{boole_clr}
1848 @cindex @code{boole_set}
1849 @cindex @code{boole_1}
1850 @cindex @code{boole_2}
1851 @cindex @code{boole_c1}
1852 @cindex @code{boole_c2}
1853 @cindex @code{boole_and}
1854 @cindex @code{boole_xor}
1855 @cindex @code{boole_eqv}
1856 @cindex @code{boole_nand}
1857 @cindex @code{boole_nor}
1858 @cindex @code{boole_andc1}
1859 @cindex @code{boole_andc2}
1860 @cindex @code{boole_orc1}
1861 @cindex @code{boole_orc2}
1864 Other functions that view integers as bit strings:
1867 @item cl_boolean logtest (const cl_I& x, const cl_I& y)
1868 @cindex @code{logtest ()}
1869 Returns true if some bit is set in both @code{x} and @code{y}, i.e. if
1870 @code{logand(x,y) != 0}.
1872 @item cl_boolean logbitp (const cl_I& n, const cl_I& x)
1873 @cindex @code{logbitp ()}
1874 Returns true if the @code{n}th bit (from the right) of @code{x} is set.
1875 Bit 0 is the least significant bit.
1877 @item uintL logcount (const cl_I& x)
1878 @cindex @code{logcount ()}
1879 Returns the number of one bits in @code{x}, if @code{x} >= 0, or
1880 the number of zero bits in @code{x}, if @code{x} < 0.
1883 The following functions operate on intervals of bits in integers.
1886 struct cl_byte @{ uintL size; uintL position; @};
1888 @cindex @code{cl_byte}
1889 represents the bit interval containing the bits
1890 @code{position}@dots{}@code{position+size-1} of an integer.
1891 The constructor @code{cl_byte(size,position)} constructs a @code{cl_byte}.
1894 @item cl_I ldb (const cl_I& n, const cl_byte& b)
1895 @cindex @code{ldb ()}
1896 extracts the bits of @code{n} described by the bit interval @code{b}
1897 and returns them as a nonnegative integer with @code{b.size} bits.
1899 @item cl_boolean ldb_test (const cl_I& n, const cl_byte& b)
1900 @cindex @code{ldb_test ()}
1901 Returns true if some bit described by the bit interval @code{b} is set in
1904 @item cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1905 @cindex @code{dpb ()}
1906 Returns @code{n}, with the bits described by the bit interval @code{b}
1907 replaced by @code{newbyte}. Only the lowest @code{b.size} bits of
1908 @code{newbyte} are relevant.
1911 The functions @code{ldb} and @code{dpb} implicitly shift. The following
1912 functions are their counterparts without shifting:
1915 @item cl_I mask_field (const cl_I& n, const cl_byte& b)
1916 @cindex @code{mask_field ()}
1917 returns an integer with the bits described by the bit interval @code{b}
1918 copied from the corresponding bits in @code{n}, the other bits zero.
1920 @item cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)
1921 @cindex @code{deposit_field ()}
1922 returns an integer where the bits described by the bit interval @code{b}
1923 come from @code{newbyte} and the other bits come from @code{n}.
1926 The following relations hold:
1930 @code{ldb (n, b) = mask_field(n, b) >> b.position},
1932 @code{dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n, b)},
1934 @code{deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^ mask_field(new_byte,b)}.
1937 The following operations on integers as bit strings are efficient shortcuts
1938 for common arithmetic operations:
1941 @item cl_boolean oddp (const cl_I& x)
1942 @cindex @code{oddp ()}
1943 Returns true if the least significant bit of @code{x} is 1. Equivalent to
1944 @code{mod(x,2) != 0}.
1946 @item cl_boolean evenp (const cl_I& x)
1947 @cindex @code{evenp ()}
1948 Returns true if the least significant bit of @code{x} is 0. Equivalent to
1949 @code{mod(x,2) == 0}.
1951 @item cl_I operator << (const cl_I& x, const cl_I& n)
1952 @cindex @code{operator << ()}
1953 Shifts @code{x} by @code{n} bits to the left. @code{n} should be >=0.
1954 Equivalent to @code{x * expt(2,n)}.
1956 @item cl_I operator >> (const cl_I& x, const cl_I& n)
1957 @cindex @code{operator >> ()}
1958 Shifts @code{x} by @code{n} bits to the right. @code{n} should be >=0.
1959 Bits shifted out to the right are thrown away.
1960 Equivalent to @code{floor(x / expt(2,n))}.
1962 @item cl_I ash (const cl_I& x, const cl_I& y)
1963 @cindex @code{ash ()}
1964 Shifts @code{x} by @code{y} bits to the left (if @code{y}>=0) or
1965 by @code{-y} bits to the right (if @code{y}<=0). In other words, this
1966 returns @code{floor(x * expt(2,y))}.
1968 @item uintL integer_length (const cl_I& x)
1969 @cindex @code{integer_length ()}
1970 Returns the number of bits (excluding the sign bit) needed to represent @code{x}
1971 in two's complement notation. This is the smallest n >= 0 such that
1972 -2^n <= x < 2^n. If x > 0, this is the unique n > 0 such that
1975 @item uintL ord2 (const cl_I& x)
1976 @cindex @code{ord2 ()}
1977 @code{x} must be non-zero. This function returns the number of 0 bits at the
1978 right of @code{x} in two's complement notation. This is the largest n >= 0
1979 such that 2^n divides @code{x}.
1981 @item uintL power2p (const cl_I& x)
1982 @cindex @code{power2p ()}
1983 @code{x} must be > 0. This function checks whether @code{x} is a power of 2.
1984 If @code{x} = 2^(n-1), it returns n. Else it returns 0.
1985 (See also the function @code{logp}.)
1989 @subsection Number theoretic functions
1992 @item uint32 gcd (uint32 a, uint32 b)
1993 @cindex @code{gcd ()}
1994 @itemx cl_I gcd (const cl_I& a, const cl_I& b)
1995 This function returns the greatest common divisor of @code{a} and @code{b},
1996 normalized to be >= 0.
1998 @item cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)
1999 @cindex @code{xgcd ()}
2000 This function (``extended gcd'') returns the greatest common divisor @code{g} of
2001 @code{a} and @code{b} and at the same time the representation of @code{g}
2002 as an integral linear combination of @code{a} and @code{b}:
2003 @code{u} and @code{v} with @code{u*a+v*b = g}, @code{g} >= 0.
2004 @code{u} and @code{v} will be normalized to be of smallest possible absolute
2005 value, in the following sense: If @code{a} and @code{b} are non-zero, and
2006 @code{abs(a) != abs(b)}, @code{u} and @code{v} will satisfy the inequalities
2007 @code{abs(u) <= abs(b)/(2*g)}, @code{abs(v) <= abs(a)/(2*g)}.
2009 @item cl_I lcm (const cl_I& a, const cl_I& b)
2010 @cindex @code{lcm ()}
2011 This function returns the least common multiple of @code{a} and @code{b},
2012 normalized to be >= 0.
2014 @item cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)
2015 @cindex @code{logp ()}
2016 @itemx cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)
2017 @code{a} must be > 0. @code{b} must be >0 and != 1. If log(a,b) is
2018 rational number, this function returns true and sets *l = log(a,b), else
2021 @item int jacobi (sint32 a, sint32 b)
2022 @cindex @code{jacobi()}
2023 @itemx int jacobi (const cl_I& a, const cl_I& b)
2024 Returns the Jacobi symbol
2026 $\left({a\over b}\right)$,
2031 @code{a,b} must be integers, @code{b>0} and odd. The result is 0
2034 @item cl_boolean isprobprime (const cl_I& n)
2036 @cindex @code{isprobprime()}
2037 Returns true if @code{n} is a small prime or passes the Miller-Rabin
2038 primality test. The probability of a false positive is 1:10^30.
2040 @item cl_I nextprobprime (const cl_R& x)
2041 @cindex @code{nextprobprime()}
2042 Returns the smallest probable prime >=@code{x}.
2046 @subsection Combinatorial functions
2049 @item cl_I factorial (uintL n)
2050 @cindex @code{factorial ()}
2051 @code{n} must be a small integer >= 0. This function returns the factorial
2052 @code{n}! = @code{1*2*@dots{}*n}.
2054 @item cl_I doublefactorial (uintL n)
2055 @cindex @code{doublefactorial ()}
2056 @code{n} must be a small integer >= 0. This function returns the
2057 doublefactorial @code{n}!! = @code{1*3*@dots{}*n} or
2058 @code{n}!! = @code{2*4*@dots{}*n}, respectively.
2060 @item cl_I binomial (uintL n, uintL k)
2061 @cindex @code{binomial ()}
2062 @code{n} and @code{k} must be small integers >= 0. This function returns the
2063 binomial coefficient
2065 ${n \choose k} = {n! \over n! (n-k)!}$
2068 (@code{n} choose @code{k}) = @code{n}! / @code{k}! @code{(n-k)}!
2070 for 0 <= k <= n, 0 else.
2074 @section Functions on floating-point numbers
2076 Recall that a floating-point number consists of a sign @code{s}, an
2077 exponent @code{e} and a mantissa @code{m}. The value of the number is
2078 @code{(-1)^s * 2^e * m}.
2081 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2082 defines the following operations.
2085 @item @var{type} scale_float (const @var{type}& x, sintL delta)
2086 @cindex @code{scale_float ()}
2087 @itemx @var{type} scale_float (const @var{type}& x, const cl_I& delta)
2088 Returns @code{x*2^delta}. This is more efficient than an explicit multiplication
2089 because it copies @code{x} and modifies the exponent.
2092 The following functions provide an abstract interface to the underlying
2093 representation of floating-point numbers.
2096 @item sintL float_exponent (const @var{type}& x)
2097 @cindex @code{float_exponent ()}
2098 Returns the exponent @code{e} of @code{x}.
2099 For @code{x = 0.0}, this is 0. For @code{x} non-zero, this is the unique
2100 integer with @code{2^(e-1) <= abs(x) < 2^e}.
2102 @item sintL float_radix (const @var{type}& x)
2103 @cindex @code{float_radix ()}
2104 Returns the base of the floating-point representation. This is always @code{2}.
2106 @item @var{type} float_sign (const @var{type}& x)
2107 @cindex @code{float_sign ()}
2108 Returns the sign @code{s} of @code{x} as a float. The value is 1 for
2109 @code{x} >= 0, -1 for @code{x} < 0.
2111 @item uintL float_digits (const @var{type}& x)
2112 @cindex @code{float_digits ()}
2113 Returns the number of mantissa bits in the floating-point representation
2114 of @code{x}, including the hidden bit. The value only depends on the type
2115 of @code{x}, not on its value.
2117 @item uintL float_precision (const @var{type}& x)
2118 @cindex @code{float_precision ()}
2119 Returns the number of significant mantissa bits in the floating-point
2120 representation of @code{x}. Since denormalized numbers are not supported,
2121 this is the same as @code{float_digits(x)} if @code{x} is non-zero, and
2125 The complete internal representation of a float is encoded in the type
2126 @cindex @code{decoded_float}
2127 @cindex @code{decoded_sfloat}
2128 @cindex @code{decoded_ffloat}
2129 @cindex @code{decoded_dfloat}
2130 @cindex @code{decoded_lfloat}
2131 @code{decoded_float} (or @code{decoded_sfloat}, @code{decoded_ffloat},
2132 @code{decoded_dfloat}, @code{decoded_lfloat}, respectively), defined by
2134 struct decoded_@var{type}float @{
2135 @var{type} mantissa; cl_I exponent; @var{type} sign;
2139 and returned by the function
2142 @item decoded_@var{type}float decode_float (const @var{type}& x)
2143 @cindex @code{decode_float ()}
2144 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2145 @code{x = (-1)^s * 2^e * m} and @code{0.5 <= m < 1.0}. For @code{x} = 0,
2146 it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2147 @code{e} is the same as returned by the function @code{float_exponent}.
2150 A complete decoding in terms of integers is provided as type
2151 @cindex @code{cl_idecoded_float}
2153 struct cl_idecoded_float @{
2154 cl_I mantissa; cl_I exponent; cl_I sign;
2157 by the following function:
2160 @item cl_idecoded_float integer_decode_float (const @var{type}& x)
2161 @cindex @code{integer_decode_float ()}
2162 For @code{x} non-zero, this returns @code{(-1)^s}, @code{e}, @code{m} with
2163 @code{x = (-1)^s * 2^e * m} and @code{m} an integer with @code{float_digits(x)}
2164 bits. For @code{x} = 0, it returns @code{(-1)^s}=1, @code{e}=0, @code{m}=0.
2165 WARNING: The exponent @code{e} is not the same as the one returned by
2166 the functions @code{decode_float} and @code{float_exponent}.
2169 Some other function, implemented only for class @code{cl_F}:
2172 @item cl_F float_sign (const cl_F& x, const cl_F& y)
2173 @cindex @code{float_sign ()}
2174 This returns a floating point number whose precision and absolute value
2175 is that of @code{y} and whose sign is that of @code{x}. If @code{x} is
2176 zero, it is treated as positive. Same for @code{y}.
2180 @section Conversion functions
2183 @subsection Conversion to floating-point numbers
2185 The type @code{float_format_t} describes a floating-point format.
2186 @cindex @code{float_format_t}
2189 @item float_format_t float_format (uintL n)
2190 @cindex @code{float_format ()}
2191 Returns the smallest float format which guarantees at least @code{n}
2192 decimal digits in the mantissa (after the decimal point).
2194 @item float_format_t float_format (const cl_F& x)
2195 Returns the floating point format of @code{x}.
2197 @item float_format_t default_float_format
2198 @cindex @code{default_float_format}
2199 Global variable: the default float format used when converting rational numbers
2203 To convert a real number to a float, each of the types
2204 @code{cl_R}, @code{cl_F}, @code{cl_I}, @code{cl_RA},
2205 @code{int}, @code{unsigned int}, @code{float}, @code{double}
2206 defines the following operations:
2209 @item cl_F cl_float (const @var{type}&x, float_format_t f)
2210 @cindex @code{cl_float ()}
2211 Returns @code{x} as a float of format @code{f}.
2212 @item cl_F cl_float (const @var{type}&x, const cl_F& y)
2213 Returns @code{x} in the float format of @code{y}.
2214 @item cl_F cl_float (const @var{type}&x)
2215 Returns @code{x} as a float of format @code{default_float_format} if
2216 it is an exact number, or @code{x} itself if it is already a float.
2219 Of course, converting a number to a float can lose precision.
2221 Every floating-point format has some characteristic numbers:
2224 @item cl_F most_positive_float (float_format_t f)
2225 @cindex @code{most_positive_float ()}
2226 Returns the largest (most positive) floating point number in float format @code{f}.
2228 @item cl_F most_negative_float (float_format_t f)
2229 @cindex @code{most_negative_float ()}
2230 Returns the smallest (most negative) floating point number in float format @code{f}.
2232 @item cl_F least_positive_float (float_format_t f)
2233 @cindex @code{least_positive_float ()}
2234 Returns the least positive floating point number (i.e. > 0 but closest to 0)
2235 in float format @code{f}.
2237 @item cl_F least_negative_float (float_format_t f)
2238 @cindex @code{least_negative_float ()}
2239 Returns the least negative floating point number (i.e. < 0 but closest to 0)
2240 in float format @code{f}.
2242 @item cl_F float_epsilon (float_format_t f)
2243 @cindex @code{float_epsilon ()}
2244 Returns the smallest floating point number e > 0 such that @code{1+e != 1}.
2246 @item cl_F float_negative_epsilon (float_format_t f)
2247 @cindex @code{float_negative_epsilon ()}
2248 Returns the smallest floating point number e > 0 such that @code{1-e != 1}.
2252 @subsection Conversion to rational numbers
2254 Each of the classes @code{cl_R}, @code{cl_RA}, @code{cl_F}
2255 defines the following operation:
2258 @item cl_RA rational (const @var{type}& x)
2259 @cindex @code{rational ()}
2260 Returns the value of @code{x} as an exact number. If @code{x} is already
2261 an exact number, this is @code{x}. If @code{x} is a floating-point number,
2262 the value is a rational number whose denominator is a power of 2.
2265 In order to convert back, say, @code{(cl_F)(cl_R)"1/3"} to @code{1/3}, there is
2269 @item cl_RA rationalize (const cl_R& x)
2270 @cindex @code{rationalize ()}
2271 If @code{x} is a floating-point number, it actually represents an interval
2272 of real numbers, and this function returns the rational number with
2273 smallest denominator (and smallest numerator, in magnitude)
2274 which lies in this interval.
2275 If @code{x} is already an exact number, this function returns @code{x}.
2278 If @code{x} is any float, one has
2282 @code{cl_float(rational(x),x) = x}
2284 @code{cl_float(rationalize(x),x) = x}
2288 @section Random number generators
2291 A random generator is a machine which produces (pseudo-)random numbers.
2292 The include file @code{<cln/random.h>} defines a class @code{random_state}
2293 which contains the state of a random generator. If you make a copy
2294 of the random number generator, the original one and the copy will produce
2295 the same sequence of random numbers.
2297 The following functions return (pseudo-)random numbers in different formats.
2298 Calling one of these modifies the state of the random number generator in
2299 a complicated but deterministic way.
2302 @cindex @code{random_state}
2303 @cindex @code{default_random_state}
2305 random_state default_random_state
2307 contains a default random number generator. It is used when the functions
2308 below are called without @code{random_state} argument.
2311 @item uint32 random32 (random_state& randomstate)
2312 @itemx uint32 random32 ()
2313 @cindex @code{random32 ()}
2314 Returns a random unsigned 32-bit number. All bits are equally random.
2316 @item cl_I random_I (random_state& randomstate, const cl_I& n)
2317 @itemx cl_I random_I (const cl_I& n)
2318 @cindex @code{random_I ()}
2319 @code{n} must be an integer > 0. This function returns a random integer @code{x}
2320 in the range @code{0 <= x < n}.
2322 @item cl_F random_F (random_state& randomstate, const cl_F& n)
2323 @itemx cl_F random_F (const cl_F& n)
2324 @cindex @code{random_F ()}
2325 @code{n} must be a float > 0. This function returns a random floating-point
2326 number of the same format as @code{n} in the range @code{0 <= x < n}.
2328 @item cl_R random_R (random_state& randomstate, const cl_R& n)
2329 @itemx cl_R random_R (const cl_R& n)
2330 @cindex @code{random_R ()}
2331 Behaves like @code{random_I} if @code{n} is an integer and like @code{random_F}
2332 if @code{n} is a float.
2336 @section Obfuscating operators
2337 @cindex modifying operators
2339 The modifying C/C++ operators @code{+=}, @code{-=}, @code{*=}, @code{/=},
2340 @code{&=}, @code{|=}, @code{^=}, @code{<<=}, @code{>>=}
2341 are not available by default because their
2342 use tends to make programs unreadable. It is trivial to get away without
2343 them. However, if you feel that you absolutely need these operators
2344 to get happy, then add
2346 #define WANT_OBFUSCATING_OPERATORS
2348 @cindex @code{WANT_OBFUSCATING_OPERATORS}
2349 to the beginning of your source files, before the inclusion of any CLN
2350 include files. This flag will enable the following operators:
2352 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA},
2353 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2356 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2357 @cindex @code{operator += ()}
2358 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2359 @cindex @code{operator -= ()}
2360 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2361 @cindex @code{operator *= ()}
2362 @itemx @var{type}& operator /= (@var{type}&, const @var{type}&)
2363 @cindex @code{operator /= ()}
2366 For the class @code{cl_I}:
2369 @item @var{type}& operator += (@var{type}&, const @var{type}&)
2370 @itemx @var{type}& operator -= (@var{type}&, const @var{type}&)
2371 @itemx @var{type}& operator *= (@var{type}&, const @var{type}&)
2372 @itemx @var{type}& operator &= (@var{type}&, const @var{type}&)
2373 @cindex @code{operator &= ()}
2374 @itemx @var{type}& operator |= (@var{type}&, const @var{type}&)
2375 @cindex @code{operator |= ()}
2376 @itemx @var{type}& operator ^= (@var{type}&, const @var{type}&)
2377 @cindex @code{operator ^= ()}
2378 @itemx @var{type}& operator <<= (@var{type}&, const @var{type}&)
2379 @cindex @code{operator <<= ()}
2380 @itemx @var{type}& operator >>= (@var{type}&, const @var{type}&)
2381 @cindex @code{operator >>= ()}
2384 For the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2385 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}:
2388 @item @var{type}& operator ++ (@var{type}& x)
2389 @cindex @code{operator ++ ()}
2390 The prefix operator @code{++x}.
2392 @item void operator ++ (@var{type}& x, int)
2393 The postfix operator @code{x++}.
2395 @item @var{type}& operator -- (@var{type}& x)
2396 @cindex @code{operator -- ()}
2397 The prefix operator @code{--x}.
2399 @item void operator -- (@var{type}& x, int)
2400 The postfix operator @code{x--}.
2403 Note that by using these obfuscating operators, you wouldn't gain efficiency:
2404 In CLN @samp{x += y;} is exactly the same as @samp{x = x+y;}, not more
2408 @chapter Input/Output
2409 @cindex Input/Output
2411 @section Internal and printed representation
2412 @cindex representation
2414 All computations deal with the internal representations of the numbers.
2416 Every number has an external representation as a sequence of ASCII characters.
2417 Several external representations may denote the same number, for example,
2418 "20.0" and "20.000".
2420 Converting an internal to an external representation is called ``printing'',
2422 converting an external to an internal representation is called ``reading''.
2424 In CLN, it is always true that conversion of an internal to an external
2425 representation and then back to an internal representation will yield the
2426 same internal representation. Symbolically: @code{read(print(x)) == x}.
2427 This is called ``print-read consistency''.
2429 Different types of numbers have different external representations (case
2434 External representation: @var{sign}@{@var{digit}@}+. The reader also accepts the
2435 Common Lisp syntaxes @var{sign}@{@var{digit}@}+@code{.} with a trailing dot
2436 for decimal integers
2437 and the @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes.
2439 @item Rational numbers
2440 External representation: @var{sign}@{@var{digit}@}+@code{/}@{@var{digit}@}+.
2441 The @code{#@var{n}R}, @code{#b}, @code{#o}, @code{#x} prefixes are allowed
2444 @item Floating-point numbers
2445 External representation: @var{sign}@{@var{digit}@}*@var{exponent} or
2446 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}*@var{exponent} or
2447 @var{sign}@{@var{digit}@}*@code{.}@{@var{digit}@}+. A precision specifier
2448 of the form _@var{prec} may be appended. There must be at least
2449 one digit in the non-exponent part. The exponent has the syntax
2450 @var{expmarker} @var{expsign} @{@var{digit}@}+.
2451 The exponent marker is
2455 @samp{s} for short-floats,
2457 @samp{f} for single-floats,
2459 @samp{d} for double-floats,
2461 @samp{L} for long-floats,
2464 or @samp{e}, which denotes a default float format. The precision specifying
2465 suffix has the syntax _@var{prec} where @var{prec} denotes the number of
2466 valid mantissa digits (in decimal, excluding leading zeroes), cf. also
2467 function @samp{float_format}.
2469 @item Complex numbers
2470 External representation:
2473 In algebraic notation: @code{@var{realpart}+@var{imagpart}i}. Of course,
2474 if @var{imagpart} is negative, its printed representation begins with
2475 a @samp{-}, and the @samp{+} between @var{realpart} and @var{imagpart}
2476 may be omitted. Note that this notation cannot be used when the @var{imagpart}
2477 is rational and the rational number's base is >18, because the @samp{i}
2478 is then read as a digit.
2480 In Common Lisp notation: @code{#C(@var{realpart} @var{imagpart})}.
2485 @section Input functions
2487 Including @code{<cln/io.h>} defines a number of simple input functions
2488 that read from @code{std::istream&}:
2491 @item int freadchar (std::istream& stream)
2492 Reads a character from @code{stream}. Returns @code{cl_EOF} (not a @samp{char}!)
2493 if the end of stream was encountered or an error occurred.
2495 @item int funreadchar (std::istream& stream, int c)
2496 Puts back @code{c} onto @code{stream}. @code{c} must be the result of the
2497 last @code{freadchar} operation on @code{stream}.
2500 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2501 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2502 defines, in @code{<cln/@var{type}_io.h>}, the following input function:
2505 @item std::istream& operator>> (std::istream& stream, @var{type}& result)
2506 Reads a number from @code{stream} and stores it in the @code{result}.
2509 The most flexible input functions, defined in @code{<cln/@var{type}_io.h>},
2513 @item cl_N read_complex (std::istream& stream, const cl_read_flags& flags)
2514 @itemx cl_R read_real (std::istream& stream, const cl_read_flags& flags)
2515 @itemx cl_F read_float (std::istream& stream, const cl_read_flags& flags)
2516 @itemx cl_RA read_rational (std::istream& stream, const cl_read_flags& flags)
2517 @itemx cl_I read_integer (std::istream& stream, const cl_read_flags& flags)
2518 Reads a number from @code{stream}. The @code{flags} are parameters which
2519 affect the input syntax. Whitespace before the number is silently skipped.
2521 @item cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2522 @itemx cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2523 @itemx cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2524 @itemx cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2525 @itemx cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)
2526 Reads a number from a string in memory. The @code{flags} are parameters which
2527 affect the input syntax. The string starts at @code{string} and ends at
2528 @code{string_limit} (exclusive limit). @code{string_limit} may also be
2529 @code{NULL}, denoting the entire string, i.e. equivalent to
2530 @code{string_limit = string + strlen(string)}. If @code{end_of_parse} is
2531 @code{NULL}, the string in memory must contain exactly one number and nothing
2532 more, else a fatal error will be signalled. If @code{end_of_parse}
2533 is not @code{NULL}, @code{*end_of_parse} will be assigned a pointer past
2534 the last parsed character (i.e. @code{string_limit} if nothing came after
2535 the number). Whitespace is not allowed.
2538 The structure @code{cl_read_flags} contains the following fields:
2541 @item cl_read_syntax_t syntax
2542 The possible results of the read operation. Possible values are
2543 @code{syntax_number}, @code{syntax_real}, @code{syntax_rational},
2544 @code{syntax_integer}, @code{syntax_float}, @code{syntax_sfloat},
2545 @code{syntax_ffloat}, @code{syntax_dfloat}, @code{syntax_lfloat}.
2547 @item cl_read_lsyntax_t lsyntax
2548 Specifies the language-dependent syntax variant for the read operation.
2552 @item lsyntax_standard
2553 accept standard algebraic notation only, no complex numbers,
2554 @item lsyntax_algebraic
2555 accept the algebraic notation @code{@var{x}+@var{y}i} for complex numbers,
2556 @item lsyntax_commonlisp
2557 accept the @code{#b}, @code{#o}, @code{#x} syntaxes for binary, octal,
2558 hexadecimal numbers,
2559 @code{#@var{base}R} for rational numbers in a given base,
2560 @code{#c(@var{realpart} @var{imagpart})} for complex numbers,
2562 accept all of these extensions.
2565 @item unsigned int rational_base
2566 The base in which rational numbers are read.
2568 @item float_format_t float_flags.default_float_format
2569 The float format used when reading floats with exponent marker @samp{e}.
2571 @item float_format_t float_flags.default_lfloat_format
2572 The float format used when reading floats with exponent marker @samp{l}.
2574 @item cl_boolean float_flags.mantissa_dependent_float_format
2575 When this flag is true, floats specified with more digits than corresponding
2576 to the exponent marker they contain, but without @var{_nnn} suffix, will get a
2577 precision corresponding to their number of significant digits.
2581 @section Output functions
2583 Including @code{<cln/io.h>} defines a number of simple output functions
2584 that write to @code{std::ostream&}:
2587 @item void fprintchar (std::ostream& stream, char c)
2588 Prints the character @code{x} literally on the @code{stream}.
2590 @item void fprint (std::ostream& stream, const char * string)
2591 Prints the @code{string} literally on the @code{stream}.
2593 @item void fprintdecimal (std::ostream& stream, int x)
2594 @itemx void fprintdecimal (std::ostream& stream, const cl_I& x)
2595 Prints the integer @code{x} in decimal on the @code{stream}.
2597 @item void fprintbinary (std::ostream& stream, const cl_I& x)
2598 Prints the integer @code{x} in binary (base 2, without prefix)
2599 on the @code{stream}.
2601 @item void fprintoctal (std::ostream& stream, const cl_I& x)
2602 Prints the integer @code{x} in octal (base 8, without prefix)
2603 on the @code{stream}.
2605 @item void fprinthexadecimal (std::ostream& stream, const cl_I& x)
2606 Prints the integer @code{x} in hexadecimal (base 16, without prefix)
2607 on the @code{stream}.
2610 Each of the classes @code{cl_N}, @code{cl_R}, @code{cl_RA}, @code{cl_I},
2611 @code{cl_F}, @code{cl_SF}, @code{cl_FF}, @code{cl_DF}, @code{cl_LF}
2612 defines, in @code{<cln/@var{type}_io.h>}, the following output functions:
2615 @item void fprint (std::ostream& stream, const @var{type}& x)
2616 @itemx std::ostream& operator<< (std::ostream& stream, const @var{type}& x)
2617 Prints the number @code{x} on the @code{stream}. The output may depend
2618 on the global printer settings in the variable @code{default_print_flags}.
2619 The @code{ostream} flags and settings (flags, width and locale) are
2623 The most flexible output function, defined in @code{<cln/@var{type}_io.h>},
2626 void print_complex (std::ostream& stream, const cl_print_flags& flags,
2628 void print_real (std::ostream& stream, const cl_print_flags& flags,
2630 void print_float (std::ostream& stream, const cl_print_flags& flags,
2632 void print_rational (std::ostream& stream, const cl_print_flags& flags,
2634 void print_integer (std::ostream& stream, const cl_print_flags& flags,
2637 Prints the number @code{x} on the @code{stream}. The @code{flags} are
2638 parameters which affect the output.
2640 The structure type @code{cl_print_flags} contains the following fields:
2643 @item unsigned int rational_base
2644 The base in which rational numbers are printed. Default is @code{10}.
2646 @item cl_boolean rational_readably
2647 If this flag is true, rational numbers are printed with radix specifiers in
2648 Common Lisp syntax (@code{#@var{n}R} or @code{#b} or @code{#o} or @code{#x}
2649 prefixes, trailing dot). Default is false.
2651 @item cl_boolean float_readably
2652 If this flag is true, type specific exponent markers have precedence over 'E'.
2655 @item float_format_t default_float_format
2656 Floating point numbers of this format will be printed using the 'E' exponent
2657 marker. Default is @code{float_format_ffloat}.
2659 @item cl_boolean complex_readably
2660 If this flag is true, complex numbers will be printed using the Common Lisp
2661 syntax @code{#C(@var{realpart} @var{imagpart})}. Default is false.
2663 @item cl_string univpoly_varname
2664 Univariate polynomials with no explicit indeterminate name will be printed
2665 using this variable name. Default is @code{"x"}.
2668 The global variable @code{default_print_flags} contains the default values,
2669 used by the function @code{fprint}.
2674 CLN has a class of abstract rings.
2682 Rings can be compared for equality:
2685 @item bool operator== (const cl_ring&, const cl_ring&)
2686 @itemx bool operator!= (const cl_ring&, const cl_ring&)
2687 These compare two rings for equality.
2690 Given a ring @code{R}, the following members can be used.
2693 @item void R->fprint (std::ostream& stream, const cl_ring_element& x)
2694 @cindex @code{fprint ()}
2695 @itemx cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)
2696 @cindex @code{equal ()}
2697 @itemx cl_ring_element R->zero ()
2698 @cindex @code{zero ()}
2699 @itemx cl_boolean R->zerop (const cl_ring_element& x)
2700 @cindex @code{zerop ()}
2701 @itemx cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)
2702 @cindex @code{plus ()}
2703 @itemx cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)
2704 @cindex @code{minus ()}
2705 @itemx cl_ring_element R->uminus (const cl_ring_element& x)
2706 @cindex @code{uminus ()}
2707 @itemx cl_ring_element R->one ()
2708 @cindex @code{one ()}
2709 @itemx cl_ring_element R->canonhom (const cl_I& x)
2710 @cindex @code{canonhom ()}
2711 @itemx cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)
2712 @cindex @code{mul ()}
2713 @itemx cl_ring_element R->square (const cl_ring_element& x)
2714 @cindex @code{square ()}
2715 @itemx cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)
2716 @cindex @code{expt_pos ()}
2719 The following rings are built-in.
2722 @item cl_null_ring cl_0_ring
2723 The null ring, containing only zero.
2725 @item cl_complex_ring cl_C_ring
2726 The ring of complex numbers. This corresponds to the type @code{cl_N}.
2728 @item cl_real_ring cl_R_ring
2729 The ring of real numbers. This corresponds to the type @code{cl_R}.
2731 @item cl_rational_ring cl_RA_ring
2732 The ring of rational numbers. This corresponds to the type @code{cl_RA}.
2734 @item cl_integer_ring cl_I_ring
2735 The ring of integers. This corresponds to the type @code{cl_I}.
2738 Type tests can be performed for any of @code{cl_C_ring}, @code{cl_R_ring},
2739 @code{cl_RA_ring}, @code{cl_I_ring}:
2742 @item cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
2743 @cindex @code{instanceof ()}
2744 Tests whether the given number is an element of the number ring R.
2748 @chapter Modular integers
2749 @cindex modular integer
2751 @section Modular integer rings
2754 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2755 The modulus is explicitly part of every modular integer. CLN doesn't
2756 allow you to (accidentally) mix elements of different modular rings,
2757 e.g. @code{(3 mod 4) + (2 mod 5)} will result in a runtime error.
2758 (Ideally one would imagine a generic data type @code{cl_MI(N)}, but C++
2759 doesn't have generic types. So one has to live with runtime checks.)
2761 The class of modular integer rings is
2769 Modular integer ring
2773 @cindex @code{cl_modint_ring}
2775 and the class of all modular integers (elements of modular integer rings) is
2783 Modular integer rings are constructed using the function
2786 @item cl_modint_ring find_modint_ring (const cl_I& N)
2787 @cindex @code{find_modint_ring ()}
2788 This function returns the modular ring @samp{Z/NZ}. It takes care
2789 of finding out about special cases of @code{N}, like powers of two
2790 and odd numbers for which Montgomery multiplication will be a win,
2791 @cindex Montgomery multiplication
2792 and precomputes any necessary auxiliary data for computing modulo @code{N}.
2793 There is a cache table of rings, indexed by @code{N} (or, more precisely,
2794 by @code{abs(N)}). This ensures that the precomputation costs are reduced
2798 Modular integer rings can be compared for equality:
2801 @item bool operator== (const cl_modint_ring&, const cl_modint_ring&)
2802 @cindex @code{operator == ()}
2803 @itemx bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
2804 @cindex @code{operator != ()}
2805 These compare two modular integer rings for equality. Two different calls
2806 to @code{find_modint_ring} with the same argument necessarily return the
2807 same ring because it is memoized in the cache table.
2810 @section Functions on modular integers
2812 Given a modular integer ring @code{R}, the following members can be used.
2815 @item cl_I R->modulus
2816 @cindex @code{modulus}
2817 This is the ring's modulus, normalized to be nonnegative: @code{abs(N)}.
2819 @item cl_MI R->zero()
2820 @cindex @code{zero ()}
2821 This returns @code{0 mod N}.
2823 @item cl_MI R->one()
2824 @cindex @code{one ()}
2825 This returns @code{1 mod N}.
2827 @item cl_MI R->canonhom (const cl_I& x)
2828 @cindex @code{canonhom ()}
2829 This returns @code{x mod N}.
2831 @item cl_I R->retract (const cl_MI& x)
2832 @cindex @code{retract ()}
2833 This is a partial inverse function to @code{R->canonhom}. It returns the
2834 standard representative (@code{>=0}, @code{<N}) of @code{x}.
2836 @item cl_MI R->random(random_state& randomstate)
2837 @itemx cl_MI R->random()
2838 @cindex @code{random ()}
2839 This returns a random integer modulo @code{N}.
2842 The following operations are defined on modular integers.
2845 @item cl_modint_ring x.ring ()
2846 @cindex @code{ring ()}
2847 Returns the ring to which the modular integer @code{x} belongs.
2849 @item cl_MI operator+ (const cl_MI&, const cl_MI&)
2850 @cindex @code{operator + ()}
2851 Returns the sum of two modular integers. One of the arguments may also
2854 @item cl_MI operator- (const cl_MI&, const cl_MI&)
2855 @cindex @code{operator - ()}
2856 Returns the difference of two modular integers. One of the arguments may also
2859 @item cl_MI operator- (const cl_MI&)
2860 Returns the negative of a modular integer.
2862 @item cl_MI operator* (const cl_MI&, const cl_MI&)
2863 @cindex @code{operator * ()}
2864 Returns the product of two modular integers. One of the arguments may also
2867 @item cl_MI square (const cl_MI&)
2868 @cindex @code{square ()}
2869 Returns the square of a modular integer.
2871 @item cl_MI recip (const cl_MI& x)
2872 @cindex @code{recip ()}
2873 Returns the reciprocal @code{x^-1} of a modular integer @code{x}. @code{x}
2874 must be coprime to the modulus, otherwise an error message is issued.
2876 @item cl_MI div (const cl_MI& x, const cl_MI& y)
2877 @cindex @code{div ()}
2878 Returns the quotient @code{x*y^-1} of two modular integers @code{x}, @code{y}.
2879 @code{y} must be coprime to the modulus, otherwise an error message is issued.
2881 @item cl_MI expt_pos (const cl_MI& x, const cl_I& y)
2882 @cindex @code{expt_pos ()}
2883 @code{y} must be > 0. Returns @code{x^y}.
2885 @item cl_MI expt (const cl_MI& x, const cl_I& y)
2886 @cindex @code{expt ()}
2887 Returns @code{x^y}. If @code{y} is negative, @code{x} must be coprime to the
2888 modulus, else an error message is issued.
2890 @item cl_MI operator<< (const cl_MI& x, const cl_I& y)
2891 @cindex @code{operator << ()}
2892 Returns @code{x*2^y}.
2894 @item cl_MI operator>> (const cl_MI& x, const cl_I& y)
2895 @cindex @code{operator >> ()}
2896 Returns @code{x*2^-y}. When @code{y} is positive, the modulus must be odd,
2897 or an error message is issued.
2899 @item bool operator== (const cl_MI&, const cl_MI&)
2900 @cindex @code{operator == ()}
2901 @itemx bool operator!= (const cl_MI&, const cl_MI&)
2902 @cindex @code{operator != ()}
2903 Compares two modular integers, belonging to the same modular integer ring,
2906 @item cl_boolean zerop (const cl_MI& x)
2907 @cindex @code{zerop ()}
2908 Returns true if @code{x} is @code{0 mod N}.
2911 The following output functions are defined (see also the chapter on
2915 @item void fprint (std::ostream& stream, const cl_MI& x)
2916 @cindex @code{fprint ()}
2917 @itemx std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
2918 @cindex @code{operator << ()}
2919 Prints the modular integer @code{x} on the @code{stream}. The output may depend
2920 on the global printer settings in the variable @code{default_print_flags}.
2924 @chapter Symbolic data types
2925 @cindex symbolic type
2927 CLN implements two symbolic (non-numeric) data types: strings and symbols.
2931 @cindex @code{cl_string}
2941 implements immutable strings.
2943 Strings are constructed through the following constructors:
2946 @item cl_string (const char * s)
2947 Returns an immutable copy of the (zero-terminated) C string @code{s}.
2949 @item cl_string (const char * ptr, unsigned long len)
2950 Returns an immutable copy of the @code{len} characters at
2951 @code{ptr[0]}, @dots{}, @code{ptr[len-1]}. NUL characters are allowed.
2954 The following functions are available on strings:
2958 Assignment from @code{cl_string} and @code{const char *}.
2961 @cindex @code{length ()}
2963 @cindex @code{strlen ()}
2964 Returns the length of the string @code{s}.
2967 @cindex @code{operator [] ()}
2968 Returns the @code{i}th character of the string @code{s}.
2969 @code{i} must be in the range @code{0 <= i < s.length()}.
2971 @item bool equal (const cl_string& s1, const cl_string& s2)
2972 @cindex @code{equal ()}
2973 Compares two strings for equality. One of the arguments may also be a
2974 plain @code{const char *}.
2979 @cindex @code{cl_symbol}
2981 Symbols are uniquified strings: all symbols with the same name are shared.
2982 This means that comparison of two symbols is fast (effectively just a pointer
2983 comparison), whereas comparison of two strings must in the worst case walk
2984 both strings until their end.
2985 Symbols are used, for example, as tags for properties, as names of variables
2986 in polynomial rings, etc.
2988 Symbols are constructed through the following constructor:
2991 @item cl_symbol (const cl_string& s)
2992 Looks up or creates a new symbol with a given name.
2995 The following operations are available on symbols:
2998 @item cl_string (const cl_symbol& sym)
2999 Conversion to @code{cl_string}: Returns the string which names the symbol
3002 @item bool equal (const cl_symbol& sym1, const cl_symbol& sym2)
3003 @cindex @code{equal ()}
3004 Compares two symbols for equality. This is very fast.
3008 @chapter Univariate polynomials
3010 @cindex univariate polynomial
3012 @section Univariate polynomial rings
3014 CLN implements univariate polynomials (polynomials in one variable) over an
3015 arbitrary ring. The indeterminate variable may be either unnamed (and will be
3016 printed according to @code{default_print_flags.univpoly_varname}, which
3017 defaults to @samp{x}) or carry a given name. The base ring and the
3018 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
3019 (accidentally) mix elements of different polynomial rings, e.g.
3020 @code{(a^2+1) * (b^3-1)} will result in a runtime error. (Ideally this should
3021 return a multivariate polynomial, but they are not yet implemented in CLN.)
3023 The classes of univariate polynomial rings are
3031 Univariate polynomial ring
3035 +----------------+-------------------+
3037 Complex polynomial ring | Modular integer polynomial ring
3038 cl_univpoly_complex_ring | cl_univpoly_modint_ring
3039 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3043 Real polynomial ring |
3044 cl_univpoly_real_ring |
3045 <cln/univpoly_real.h> |
3049 Rational polynomial ring |
3050 cl_univpoly_rational_ring |
3051 <cln/univpoly_rational.h> |
3055 Integer polynomial ring
3056 cl_univpoly_integer_ring
3057 <cln/univpoly_integer.h>
3060 and the corresponding classes of univariate polynomials are
3063 Univariate polynomial
3067 +----------------+-------------------+
3069 Complex polynomial | Modular integer polynomial
3071 <cln/univpoly_complex.h> | <cln/univpoly_modint.h>
3077 <cln/univpoly_real.h> |
3081 Rational polynomial |
3083 <cln/univpoly_rational.h> |
3089 <cln/univpoly_integer.h>
3092 Univariate polynomial rings are constructed using the functions
3095 @item cl_univpoly_ring find_univpoly_ring (const cl_ring& R)
3096 @itemx cl_univpoly_ring find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)
3097 This function returns the polynomial ring @samp{R[X]}, unnamed or named.
3098 @code{R} may be an arbitrary ring. This function takes care of finding out
3099 about special cases of @code{R}, such as the rings of complex numbers,
3100 real numbers, rational numbers, integers, or modular integer rings.
3101 There is a cache table of rings, indexed by @code{R} and @code{varname}.
3102 This ensures that two calls of this function with the same arguments will
3103 return the same polynomial ring.
3105 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R)
3106 @cindex @code{find_univpoly_ring ()}
3107 @itemx cl_univpoly_complex_ring find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)
3108 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R)
3109 @itemx cl_univpoly_real_ring find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)
3110 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R)
3111 @itemx cl_univpoly_rational_ring find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)
3112 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R)
3113 @itemx cl_univpoly_integer_ring find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)
3114 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R)
3115 @itemx cl_univpoly_modint_ring find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)
3116 These functions are equivalent to the general @code{find_univpoly_ring},
3117 only the return type is more specific, according to the base ring's type.
3120 @section Functions on univariate polynomials
3122 Given a univariate polynomial ring @code{R}, the following members can be used.
3125 @item cl_ring R->basering()
3126 @cindex @code{basering ()}
3127 This returns the base ring, as passed to @samp{find_univpoly_ring}.
3129 @item cl_UP R->zero()
3130 @cindex @code{zero ()}
3131 This returns @code{0 in R}, a polynomial of degree -1.
3133 @item cl_UP R->one()
3134 @cindex @code{one ()}
3135 This returns @code{1 in R}, a polynomial of degree == 0.
3137 @item cl_UP R->canonhom (const cl_I& x)
3138 @cindex @code{canonhom ()}
3139 This returns @code{x in R}, a polynomial of degree <= 0.
3141 @item cl_UP R->monomial (const cl_ring_element& x, uintL e)
3142 @cindex @code{monomial ()}
3143 This returns a sparse polynomial: @code{x * X^e}, where @code{X} is the
3146 @item cl_UP R->create (sintL degree)
3147 @cindex @code{create ()}
3148 Creates a new polynomial with a given degree. The zero polynomial has degree
3149 @code{-1}. After creating the polynomial, you should put in the coefficients,
3150 using the @code{set_coeff} member function, and then call the @code{finalize}
3154 The following are the only destructive operations on univariate polynomials.
3157 @item void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)
3158 @cindex @code{set_coeff ()}
3159 This changes the coefficient of @code{X^index} in @code{x} to be @code{y}.
3160 After changing a polynomial and before applying any "normal" operation on it,
3161 you should call its @code{finalize} member function.
3163 @item void finalize (cl_UP& x)
3164 @cindex @code{finalize ()}
3165 This function marks the endpoint of destructive modifications of a polynomial.
3166 It normalizes the internal representation so that subsequent computations have
3167 less overhead. Doing normal computations on unnormalized polynomials may
3168 produce wrong results or crash the program.
3171 The following operations are defined on univariate polynomials.
3174 @item cl_univpoly_ring x.ring ()
3175 @cindex @code{ring ()}
3176 Returns the ring to which the univariate polynomial @code{x} belongs.
3178 @item cl_UP operator+ (const cl_UP&, const cl_UP&)
3179 @cindex @code{operator + ()}
3180 Returns the sum of two univariate polynomials.
3182 @item cl_UP operator- (const cl_UP&, const cl_UP&)
3183 @cindex @code{operator - ()}
3184 Returns the difference of two univariate polynomials.
3186 @item cl_UP operator- (const cl_UP&)
3187 Returns the negative of a univariate polynomial.
3189 @item cl_UP operator* (const cl_UP&, const cl_UP&)
3190 @cindex @code{operator * ()}
3191 Returns the product of two univariate polynomials. One of the arguments may
3192 also be a plain integer or an element of the base ring.
3194 @item cl_UP square (const cl_UP&)
3195 @cindex @code{square ()}
3196 Returns the square of a univariate polynomial.
3198 @item cl_UP expt_pos (const cl_UP& x, const cl_I& y)
3199 @cindex @code{expt_pos ()}
3200 @code{y} must be > 0. Returns @code{x^y}.
3202 @item bool operator== (const cl_UP&, const cl_UP&)
3203 @cindex @code{operator == ()}
3204 @itemx bool operator!= (const cl_UP&, const cl_UP&)
3205 @cindex @code{operator != ()}
3206 Compares two univariate polynomials, belonging to the same univariate
3207 polynomial ring, for equality.
3209 @item cl_boolean zerop (const cl_UP& x)
3210 @cindex @code{zerop ()}
3211 Returns true if @code{x} is @code{0 in R}.
3213 @item sintL degree (const cl_UP& x)
3214 @cindex @code{degree ()}
3215 Returns the degree of the polynomial. The zero polynomial has degree @code{-1}.
3217 @item sintL ldegree (const cl_UP& x)
3218 @cindex @code{degree ()}
3219 Returns the low degree of the polynomial. This is the degree of the first
3220 non-vanishing polynomial coefficient. The zero polynomial has ldegree @code{-1}.
3222 @item cl_ring_element coeff (const cl_UP& x, uintL index)
3223 @cindex @code{coeff ()}
3224 Returns the coefficient of @code{X^index} in the polynomial @code{x}.
3226 @item cl_ring_element x (const cl_ring_element& y)
3227 @cindex @code{operator () ()}
3228 Evaluation: If @code{x} is a polynomial and @code{y} belongs to the base ring,
3229 then @samp{x(y)} returns the value of the substitution of @code{y} into
3232 @item cl_UP deriv (const cl_UP& x)
3233 @cindex @code{deriv ()}
3234 Returns the derivative of the polynomial @code{x} with respect to the
3235 indeterminate @code{X}.
3238 The following output functions are defined (see also the chapter on
3242 @item void fprint (std::ostream& stream, const cl_UP& x)
3243 @cindex @code{fprint ()}
3244 @itemx std::ostream& operator<< (std::ostream& stream, const cl_UP& x)
3245 @cindex @code{operator << ()}
3246 Prints the univariate polynomial @code{x} on the @code{stream}. The output may
3247 depend on the global printer settings in the variable
3248 @code{default_print_flags}.
3251 @section Special polynomials
3253 The following functions return special polynomials.
3256 @item cl_UP_I tschebychev (sintL n)
3257 @cindex @code{tschebychev ()}
3258 @cindex Chebyshev polynomial
3259 Returns the n-th Chebyshev polynomial (n >= 0).
3261 @item cl_UP_I hermite (sintL n)
3262 @cindex @code{hermite ()}
3263 @cindex Hermite polynomial
3264 Returns the n-th Hermite polynomial (n >= 0).
3266 @item cl_UP_RA legendre (sintL n)
3267 @cindex @code{legendre ()}
3268 @cindex Legende polynomial
3269 Returns the n-th Legendre polynomial (n >= 0).
3271 @item cl_UP_I laguerre (sintL n)
3272 @cindex @code{laguerre ()}
3273 @cindex Laguerre polynomial
3274 Returns the n-th Laguerre polynomial (n >= 0).
3277 Information how to derive the differential equation satisfied by each
3278 of these polynomials from their definition can be found in the
3279 @code{doc/polynomial/} directory.
3287 Using C++ as an implementation language provides
3291 Efficiency: It compiles to machine code.
3295 Portability: It runs on all platforms supporting a C++ compiler. Because
3296 of the availability of GNU C++, this includes all currently used 32-bit and
3297 64-bit platforms, independently of the quality of the vendor's C++ compiler.
3300 Type safety: The C++ compilers knows about the number types and complains if,
3301 for example, you try to assign a float to an integer variable. However,
3302 a drawback is that C++ doesn't know about generic types, hence a restriction
3303 like that @code{operator+ (const cl_MI&, const cl_MI&)} requires that both
3304 arguments belong to the same modular ring cannot be expressed as a compile-time
3308 Algebraic syntax: The elementary operations @code{+}, @code{-}, @code{*},
3309 @code{=}, @code{==}, ... can be used in infix notation, which is more
3310 convenient than Lisp notation @samp{(+ x y)} or C notation @samp{add(x,y,&z)}.
3313 With these language features, there is no need for two separate languages,
3314 one for the implementation of the library and one in which the library's users
3315 can program. This means that a prototype implementation of an algorithm
3316 can be integrated into the library immediately after it has been tested and
3317 debugged. No need to rewrite it in a low-level language after having prototyped
3318 in a high-level language.
3321 @section Memory efficiency
3323 In order to save memory allocations, CLN implements:
3327 Object sharing: An operation like @code{x+0} returns @code{x} without copying
3330 @cindex garbage collection
3331 @cindex reference counting
3332 Garbage collection: A reference counting mechanism makes sure that any
3333 number object's storage is freed immediately when the last reference to the
3336 @cindex immediate numbers
3337 Small integers are represented as immediate values instead of pointers
3338 to heap allocated storage. This means that integers @code{> -2^29},
3339 @code{< 2^29} don't consume heap memory, unless they were explicitly allocated
3344 @section Speed efficiency
3346 Speed efficiency is obtained by the combination of the following tricks
3351 Small integers, being represented as immediate values, don't require
3352 memory access, just a couple of instructions for each elementary operation.
3354 The kernel of CLN has been written in assembly language for some CPUs
3355 (@code{i386}, @code{m68k}, @code{sparc}, @code{mips}, @code{arm}).
3357 On all CPUs, CLN may be configured to use the superefficient low-level
3358 routines from GNU GMP version 3.
3360 For large numbers, CLN uses, instead of the standard @code{O(N^2)}
3361 algorithm, the Karatsuba multiplication, which is an
3372 For very large numbers (more than 12000 decimal digits), CLN uses
3374 Sch{@"o}nhage-Strassen
3375 @cindex Sch{@"o}nhage-Strassen multiplication
3379 @cindex Schnhage-Strassen multiplication
3381 multiplication, which is an asymptotically optimal multiplication
3384 These fast multiplication algorithms also give improvements in the speed
3385 of division and radix conversion.
3389 @section Garbage collection
3390 @cindex garbage collection
3392 All the number classes are reference count classes: They only contain a pointer
3393 to an object in the heap. Upon construction, assignment and destruction of
3394 number objects, only the objects' reference count are manipulated.
3396 Memory occupied by number objects are automatically reclaimed as soon as
3397 their reference count drops to zero.
3399 For number rings, another strategy is implemented: There is a cache of,
3400 for example, the modular integer rings. A modular integer ring is destroyed
3401 only if its reference count dropped to zero and the cache is about to be
3402 resized. The effect of this strategy is that recently used rings remain
3403 cached, whereas undue memory consumption through cached rings is avoided.
3406 @chapter Using the library
3408 For the following discussion, we will assume that you have installed
3409 the CLN source in @code{$CLN_DIR} and built it in @code{$CLN_TARGETDIR}.
3410 For example, for me it's @code{CLN_DIR="$HOME/cln"} and
3411 @code{CLN_TARGETDIR="$HOME/cln/linuxelf"}. You might define these as
3412 environment variables, or directly substitute the appropriate values.
3415 @section Compiler options
3416 @cindex compiler options
3418 Until you have installed CLN in a public place, the following options are
3421 When you compile CLN application code, add the flags
3423 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
3425 to the C++ compiler's command line (@code{make} variable CFLAGS or CXXFLAGS).
3426 When you link CLN application code to form an executable, add the flags
3428 $CLN_TARGETDIR/src/libcln.a
3430 to the C/C++ compiler's command line (@code{make} variable LIBS).
3432 If you did a @code{make install}, the include files are installed in a
3433 public directory (normally @code{/usr/local/include}), hence you don't
3434 need special flags for compiling. The library has been installed to a
3435 public directory as well (normally @code{/usr/local/lib}), hence when
3436 linking a CLN application it is sufficient to give the flag @code{-lcln}.
3438 Since CLN version 1.1, there are two tools to make the creation of
3439 software packages that use CLN easier:
3442 @cindex @code{cln-config}
3443 @code{cln-config} is a shell script that you can use to determine the
3444 compiler and linker command line options required to compile and link a
3445 program with CLN. Start it with @code{--help} to learn about its options
3446 or consult the manpage that comes with it.
3448 @cindex @code{AC_PATH_CLN}
3449 @code{AC_PATH_CLN} is for packages configured using GNU automake.
3452 @code{AC_PATH_CLN([@var{MIN-VERSION}, [@var{ACTION-IF-FOUND} [, @var{ACTION-IF-NOT-FOUND}]]])}
3454 This macro determines the location of CLN using @code{cln-config}, which
3455 is either found in the user's path, or from the environment variable
3456 @code{CLN_CONFIG}. It tests the installed libraries to make sure that
3457 their version is not earlier than @var{MIN-VERSION} (a default version
3458 will be used if not specified). If the required version was found, sets
3459 the @env{CLN_CPPFLAGS} and the @env{CLN_LIBS} variables. This
3460 macro is in the file @file{cln.m4} which is installed in
3461 @file{$datadir/aclocal}. Note that if automake was installed with a
3462 different @samp{--prefix} than CLN, you will either have to manually
3463 move @file{cln.m4} to automake's @file{$datadir/aclocal}, or give
3464 aclocal the @samp{-I} option when running it. Here is a possible example
3465 to be included in your package's @file{configure.ac}:
3467 AC_PATH_CLN(1.1.0, [
3468 LIBS="$LIBS $CLN_LIBS"
3469 CPPFLAGS="$CPPFLAGS $CLN_CPPFLAGS"
3470 ], AC_MSG_ERROR([No suitable installed version of CLN could be found.]))
3475 @section Compatibility to old CLN versions
3477 @cindex compatibility
3479 As of CLN version 1.1 all non-macro identifiers were hidden in namespace
3480 @code{cln} in order to avoid potential name clashes with other C++
3481 libraries. If you have an old application, you will have to manually
3482 port it to the new scheme. The following principles will help during
3486 All headers are now in a separate subdirectory. Instead of including
3487 @code{cl_}@var{something}@code{.h}, include
3488 @code{cln/}@var{something}@code{.h} now.
3490 All public identifiers (typenames and functions) have lost their
3491 @code{cl_} prefix. Exceptions are all the typenames of number types,
3492 (cl_N, cl_I, cl_MI, @dots{}), rings, symbolic types (cl_string,
3493 cl_symbol) and polynomials (cl_UP_@var{type}). (This is because their
3494 names would not be mnemonic enough once the namespace @code{cln} is
3495 imported. Even in a namespace we favor @code{cl_N} over @code{N}.)
3497 All public @emph{functions} that had by a @code{cl_} in their name still
3498 carry that @code{cl_} if it is intrinsic part of a typename (as in
3499 @code{cl_I_to_int ()}).
3501 When developing other libraries, please keep in mind not to import the
3502 namespace @code{cln} in one of your public header files by saying
3503 @code{using namespace cln;}. This would propagate to other applications
3504 and can cause name clashes there.
3507 @section Include files
3508 @cindex include files
3509 @cindex header files
3511 Here is a summary of the include files and their contents.
3514 @item <cln/object.h>
3515 General definitions, reference counting, garbage collection.
3516 @item <cln/number.h>
3517 The class cl_number.
3518 @item <cln/complex.h>
3519 Functions for class cl_N, the complex numbers.
3521 Functions for class cl_R, the real numbers.
3523 Functions for class cl_F, the floats.
3524 @item <cln/sfloat.h>
3525 Functions for class cl_SF, the short-floats.
3526 @item <cln/ffloat.h>
3527 Functions for class cl_FF, the single-floats.
3528 @item <cln/dfloat.h>
3529 Functions for class cl_DF, the double-floats.
3530 @item <cln/lfloat.h>
3531 Functions for class cl_LF, the long-floats.
3532 @item <cln/rational.h>
3533 Functions for class cl_RA, the rational numbers.
3534 @item <cln/integer.h>
3535 Functions for class cl_I, the integers.
3538 @item <cln/complex_io.h>
3539 Input/Output for class cl_N, the complex numbers.
3540 @item <cln/real_io.h>
3541 Input/Output for class cl_R, the real numbers.
3542 @item <cln/float_io.h>
3543 Input/Output for class cl_F, the floats.
3544 @item <cln/sfloat_io.h>
3545 Input/Output for class cl_SF, the short-floats.
3546 @item <cln/ffloat_io.h>
3547 Input/Output for class cl_FF, the single-floats.
3548 @item <cln/dfloat_io.h>
3549 Input/Output for class cl_DF, the double-floats.
3550 @item <cln/lfloat_io.h>
3551 Input/Output for class cl_LF, the long-floats.
3552 @item <cln/rational_io.h>
3553 Input/Output for class cl_RA, the rational numbers.
3554 @item <cln/integer_io.h>
3555 Input/Output for class cl_I, the integers.
3557 Flags for customizing input operations.
3558 @item <cln/output.h>
3559 Flags for customizing output operations.
3560 @item <cln/malloc.h>
3561 @code{malloc_hook}, @code{free_hook}.
3564 @item <cln/condition.h>
3565 Conditions/exceptions.
3566 @item <cln/string.h>
3568 @item <cln/symbol.h>
3570 @item <cln/proplist.h>
3574 @item <cln/null_ring.h>
3576 @item <cln/complex_ring.h>
3577 The ring of complex numbers.
3578 @item <cln/real_ring.h>
3579 The ring of real numbers.
3580 @item <cln/rational_ring.h>
3581 The ring of rational numbers.
3582 @item <cln/integer_ring.h>
3583 The ring of integers.
3584 @item <cln/numtheory.h>
3585 Number threory functions.
3586 @item <cln/modinteger.h>
3592 @item <cln/GV_number.h>
3593 General vectors over cl_number.
3594 @item <cln/GV_complex.h>
3595 General vectors over cl_N.
3596 @item <cln/GV_real.h>
3597 General vectors over cl_R.
3598 @item <cln/GV_rational.h>
3599 General vectors over cl_RA.
3600 @item <cln/GV_integer.h>
3601 General vectors over cl_I.
3602 @item <cln/GV_modinteger.h>
3603 General vectors of modular integers.
3606 @item <cln/SV_number.h>
3607 Simple vectors over cl_number.
3608 @item <cln/SV_complex.h>
3609 Simple vectors over cl_N.
3610 @item <cln/SV_real.h>
3611 Simple vectors over cl_R.
3612 @item <cln/SV_rational.h>
3613 Simple vectors over cl_RA.
3614 @item <cln/SV_integer.h>
3615 Simple vectors over cl_I.
3616 @item <cln/SV_ringelt.h>
3617 Simple vectors of general ring elements.
3618 @item <cln/univpoly.h>
3619 Univariate polynomials.
3620 @item <cln/univpoly_integer.h>
3621 Univariate polynomials over the integers.
3622 @item <cln/univpoly_rational.h>
3623 Univariate polynomials over the rational numbers.
3624 @item <cln/univpoly_real.h>
3625 Univariate polynomials over the real numbers.
3626 @item <cln/univpoly_complex.h>
3627 Univariate polynomials over the complex numbers.
3628 @item <cln/univpoly_modint.h>
3629 Univariate polynomials over modular integer rings.
3630 @item <cln/timing.h>
3633 Includes all of the above.
3639 A function which computes the nth Fibonacci number can be written as follows.
3640 @cindex Fibonacci number
3643 #include <cln/integer.h>
3644 #include <cln/real.h>
3645 using namespace cln;
3647 // Returns F_n, computed as the nearest integer to
3648 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3649 const cl_I fibonacci (int n)
3651 // Need a precision of ((1+sqrt(5))/2)^-n.
3652 float_format_t prec = float_format((int)(0.208987641*n+5));
3653 cl_R sqrt5 = sqrt(cl_float(5,prec));
3654 cl_R phi = (1+sqrt5)/2;
3655 return round1( expt(phi,n)/sqrt5 );
3659 Let's explain what is going on in detail.
3661 The include file @code{<cln/integer.h>} is necessary because the type
3662 @code{cl_I} is used in the function, and the include file @code{<cln/real.h>}
3663 is needed for the type @code{cl_R} and the floating point number functions.
3664 The order of the include files does not matter. In order not to write
3665 out @code{cln::}@var{foo} in this simple example we can safely import
3666 the whole namespace @code{cln}.
3668 Then comes the function declaration. The argument is an @code{int}, the
3669 result an integer. The return type is defined as @samp{const cl_I}, not
3670 simply @samp{cl_I}, because that allows the compiler to detect typos like
3671 @samp{fibonacci(n) = 100}. It would be possible to declare the return
3672 type as @code{const cl_R} (real number) or even @code{const cl_N} (complex
3673 number). We use the most specialized possible return type because functions
3674 which call @samp{fibonacci} will be able to profit from the compiler's type
3675 analysis: Adding two integers is slightly more efficient than adding the
3676 same objects declared as complex numbers, because it needs less type
3677 dispatch. Also, when linking to CLN as a non-shared library, this minimizes
3678 the size of the resulting executable program.
3680 The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest
3681 integer. In order to get a correct result, the absolute error should be less
3682 than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)).
3683 To this end, the first line computes a floating point precision for sqrt(5)
3686 Then sqrt(5) is computed by first converting the integer 5 to a floating point
3687 number and than taking the square root. The converse, first taking the square
3688 root of 5, and then converting to the desired precision, would not work in
3689 CLN: The square root would be computed to a default precision (normally
3690 single-float precision), and the following conversion could not help about
3691 the lacking accuracy. This is because CLN is not a symbolic computer algebra
3692 system and does not represent sqrt(5) in a non-numeric way.
3694 The type @code{cl_R} for sqrt5 and, in the following line, phi is the only
3695 possible choice. You cannot write @code{cl_F} because the C++ compiler can
3696 only infer that @code{cl_float(5,prec)} is a real number. You cannot write
3697 @code{cl_N} because a @samp{round1} does not exist for general complex
3700 When the function returns, all the local variables in the function are
3701 automatically reclaimed (garbage collected). Only the result survives and
3702 gets passed to the caller.
3704 The file @code{fibonacci.cc} in the subdirectory @code{examples}
3705 contains this implementation together with an even faster algorithm.
3707 @section Debugging support
3710 When debugging a CLN application with GNU @code{gdb}, two facilities are
3711 available from the library:
3714 @item The library does type checks, range checks, consistency checks at
3715 many places. When one of these fails, the function @code{cl_abort()} is
3716 called. Its default implementation is to perform an @code{exit(1)}, so
3717 you won't have a core dump. But for debugging, it is best to set a
3718 breakpoint at this function:
3720 (gdb) break cl_abort
3722 When this breakpoint is hit, look at the stack's backtrace:
3727 @item The debugger's normal @code{print} command doesn't know about
3728 CLN's types and therefore prints mostly useless hexadecimal addresses.
3729 CLN offers a function @code{cl_print}, callable from the debugger,
3730 for printing number objects. In order to get this function, you have
3731 to define the macro @samp{CL_DEBUG} and then include all the header files
3732 for which you want @code{cl_print} debugging support. For example:
3733 @cindex @code{CL_DEBUG}
3736 #include <cln/string.h>
3738 Now, if you have in your program a variable @code{cl_string s}, and
3739 inspect it under @code{gdb}, the output may look like this:
3742 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3743 word = 134568800@}@}, @}
3744 (gdb) call cl_print(s)
3748 Note that the output of @code{cl_print} goes to the program's error output,
3749 not to gdb's standard output.
3751 Note, however, that the above facility does not work with all CLN types,
3752 only with number objects and similar. Therefore CLN offers a member function
3753 @code{debug_print()} on all CLN types. The same macro @samp{CL_DEBUG}
3754 is needed for this member function to be implemented. Under @code{gdb},
3755 you call it like this:
3756 @cindex @code{debug_print ()}
3759 $7 = @{<cl_gcpointer> = @{ = @{pointer = 0x8055b60, heappointer = 0x8055b60,
3760 word = 134568800@}@}, @}
3761 (gdb) call s.debug_print()
3764 >call ($1).debug_print()
3769 Unfortunately, this feature does not seem to work under all circumstances.
3773 @chapter Customizing
3776 @section Error handling
3778 When a fatal error occurs, an error message is output to the standard error
3779 output stream, and the function @code{cl_abort} is called. The default
3780 version of this function (provided in the library) terminates the application.
3781 To catch such a fatal error, you need to define the function @code{cl_abort}
3782 yourself, with the prototype
3784 #include <cln/abort.h>
3785 void cl_abort (void);
3787 @cindex @code{cl_abort ()}
3788 This function must not return control to its caller.
3791 @section Floating-point underflow
3794 Floating point underflow denotes the situation when a floating-point number
3795 is to be created which is so close to @code{0} that its exponent is too
3796 low to be represented internally. By default, this causes a fatal error.
3797 If you set the global variable
3799 cl_boolean cl_inhibit_floating_point_underflow
3801 to @code{cl_true}, the error will be inhibited, and a floating-point zero
3802 will be generated instead. The default value of
3803 @code{cl_inhibit_floating_point_underflow} is @code{cl_false}.
3806 @section Customizing I/O
3808 The output of the function @code{fprint} may be customized by changing the
3809 value of the global variable @code{default_print_flags}.
3810 @cindex @code{default_print_flags}
3813 @section Customizing the memory allocator
3815 Every memory allocation of CLN is done through the function pointer
3816 @code{malloc_hook}. Freeing of this memory is done through the function
3817 pointer @code{free_hook}. The default versions of these functions,
3818 provided in the library, call @code{malloc} and @code{free} and check
3819 the @code{malloc} result against @code{NULL}.
3820 If you want to provide another memory allocator, you need to define
3821 the variables @code{malloc_hook} and @code{free_hook} yourself,
3824 #include <cln/malloc.h>
3826 void* (*malloc_hook) (size_t size) = @dots{};
3827 void (*free_hook) (void* ptr) = @dots{};
3830 @cindex @code{malloc_hook ()}
3831 @cindex @code{free_hook ()}
3832 The @code{cl_malloc_hook} function must not return a @code{NULL} pointer.
3834 It is not possible to change the memory allocator at runtime, because
3835 it is already called at program startup by the constructors of some