1 This is Info file cln.info, produced by Makeinfo version 1.68 from the
4 This file documents CLN, a Class Library for Numbers.
6 Published by Bruno Haible, `<haible@clisp.cons.org>' and Richard
7 Kreckel, `<kreckel@ginac.de>'.
9 Copyright (C) Bruno Haible 1995, 1996, 1997, 1998, 1999, 2000.
11 Permission is granted to make and distribute verbatim copies of this
12 manual provided the copyright notice and this permission notice are
13 preserved on all copies.
15 Permission is granted to copy and distribute modified versions of this
16 manual under the conditions for verbatim copying, provided that the
17 entire resulting derived work is distributed under the terms of a
18 permission notice identical to this one.
20 Permission is granted to copy and distribute translations of this manual
21 into another language, under the above conditions for modified versions,
22 except that this permission notice may be stated in a translation
23 approved by the author.
26 File: cln.info, Node: Top, Next: Introduction, Prev: (dir), Up: (dir)
32 * Ordinary number types::
33 * Functions on numbers::
37 * Symbolic data types::
38 * Univariate polynomials::
44 -- The Detailed Node Listing --
49 * Building the library::
50 * Installing the library::
62 * Floating-point numbers::
68 * Constructing numbers::
69 * Elementary functions::
70 * Elementary rational functions::
71 * Elementary complex functions::
73 * Rounding functions::
75 * Transcendental functions::
76 * Functions on integers::
77 * Functions on floating-point numbers::
78 * Conversion functions::
79 * Random number generators::
80 * Obfuscating operators::
84 * Constructing integers::
85 * Constructing rational numbers::
86 * Constructing floating-point numbers::
87 * Constructing complex numbers::
89 Transcendental functions
91 * Exponential and logarithmic functions::
92 * Trigonometric functions::
93 * Hyperbolic functions::
100 * Number theoretic functions::
101 * Combinatorial functions::
105 * Conversion to floating-point numbers::
106 * Conversion to rational numbers::
110 * Internal and printed representation::
116 * Modular integer rings::
117 * Functions on modular integers::
124 Univariate polynomials
126 * Univariate polynomial rings::
127 * Functions on univariate polynomials::
128 * Special polynomials::
133 * Memory efficiency::
135 * Garbage collection::
142 * Debugging support::
147 * Floating-point underflow::
149 * Customizing the memory allocator::
152 File: cln.info, Node: Introduction, Next: Installation, Prev: Top, Up: Top
157 CLN is a library for computations with all kinds of numbers. It has a
158 rich set of number classes:
160 * Integers (with unlimited precision),
164 * Floating-point numbers:
172 - Long float (with unlimited precision),
176 * Modular integers (integers modulo a fixed integer),
178 * Univariate polynomials.
180 The subtypes of the complex numbers among these are exactly the types
181 of numbers known to the Common Lisp language. Therefore `CLN' can be
182 used for Common Lisp implementations, giving `CLN' another meaning: it
183 becomes an abbreviation of "Common Lisp Numbers".
185 The CLN package implements
187 * Elementary functions (`+', `-', `*', `/', `sqrt', comparisons,
190 * Logical functions (logical `and', `or', `not', ...),
192 * Transcendental functions (exponential, logarithmic, trigonometric,
193 hyperbolic functions and their inverse functions).
195 CLN is a C++ library. Using C++ as an implementation language provides
197 * efficiency: it compiles to machine code,
199 * type safety: the C++ compiler knows about the number types and
200 complains if, for example, you try to assign a float to an integer
203 * algebraic syntax: You can use the `+', `-', `*', `=', `==', ...
204 operators as in C or C++.
206 CLN is memory efficient:
208 * Small integers and short floats are immediate, not heap allocated.
210 * Heap-allocated memory is reclaimed through an automatic,
211 non-interruptive garbage collection.
213 CLN is speed efficient:
215 * The kernel of CLN has been written in assembly language for some
216 CPUs (`i386', `m68k', `sparc', `mips', `arm').
218 * On all CPUs, CLN uses the superefficient low-level routines from
221 * It uses Karatsuba multiplication, which is significantly faster
222 for large numbers than the standard multiplication algorithm.
224 * For very large numbers (more than 12000 decimal digits), it uses
225 Schönhage-Strassen multiplication, which is an asymptotically
226 optimal multiplication algorithm, for multiplication, division and
229 CLN aims at being easily integrated into larger software packages:
231 * The garbage collection imposes no burden on the main application.
233 * The library provides hooks for memory allocation and exceptions.
236 File: cln.info, Node: Installation, Next: Ordinary number types, Prev: Introduction, Up: Top
241 This section describes how to install the CLN package on your system.
246 * Building the library::
247 * Installing the library::
251 File: cln.info, Node: Prerequisites, Next: Building the library, Prev: Installation, Up: Installation
263 File: cln.info, Node: C++ compiler, Next: Make utility, Prev: Prerequisites, Up: Prerequisites
268 To build CLN, you need a C++ compiler. Actually, you need GNU `g++
269 2.7.0' or newer. On HPPA, you need GNU `g++ 2.8.0' or newer. I
270 recommend GNU `egcs 1.1' or newer.
272 The following C++ features are used: classes, member functions,
273 overloading of functions and operators, constructors and destructors,
274 inline, const, multiple inheritance, templates.
276 The following C++ features are not used: `new', `delete', virtual
277 inheritance, exceptions.
279 CLN relies on semi-automatic ordering of initializations of static and
280 global variables, a feature which I could implement for GNU g++ only.
283 File: cln.info, Node: Make utility, Next: Sed utility, Prev: C++ compiler, Up: Prerequisites
288 To build CLN, you also need to have GNU `make' installed.
291 File: cln.info, Node: Sed utility, Prev: Make utility, Up: Prerequisites
296 To build CLN on HP-UX, you also need to have GNU `sed' installed. This
297 is because the libtool script, which creates the CLN library, relies on
298 `sed', and the vendor's `sed' utility on these systems is too limited.
301 File: cln.info, Node: Building the library, Next: Installing the library, Prev: Prerequisites, Up: Installation
306 As with any autoconfiguring GNU software, installation is as easy as
313 If on your system, `make' is not GNU `make', you have to use `gmake'
314 instead of `make' above.
316 The `configure' command checks out some features of your system and C++
317 compiler and builds the `Makefile's. The `make' command builds the
318 library. This step may take 4 hours on an average workstation. The
319 `make check' runs some test to check that no important subroutine has
322 The `configure' command accepts options. To get a summary of them, try
326 Some of the options are explained in detail in the `INSTALL.generic'
329 You can specify the C compiler, the C++ compiler and their options
330 through the following environment variables when running `configure':
333 Specifies the C compiler.
336 Flags to be given to the C compiler when compiling programs (not
340 Specifies the C++ compiler.
343 Flags to be given to the C++ compiler when compiling programs (not
348 $ CC="gcc" CFLAGS="-O" CXX="g++" CXXFLAGS="-O" ./configure
349 $ CC="gcc -V 2.7.2" CFLAGS="-O -g" \
350 CXX="g++ -V 2.7.2" CXXFLAGS="-O -g" ./configure
351 $ CC="gcc -V 2.8.1" CFLAGS="-O -fno-exceptions" \
352 CXX="g++ -V 2.8.1" CXXFLAGS="-O -fno-exceptions" ./configure
353 $ CC="gcc -V egcs-2.91.60" CFLAGS="-O2 -fno-exceptions" \
354 CXX="g++ -V egcs-2.91.60" CFLAGS="-O2 -fno-exceptions" ./configure
356 Note that for these environment variables to take effect, you have to
357 set them (assuming a Bourne-compatible shell) on the same line as the
358 `configure' command. If you made the settings in earlier shell
359 commands, you have to `export' the environment variables before calling
360 `configure'. In a `csh' shell, you have to use the `setenv' command for
361 setting each of the environment variables.
363 On Linux, `g++' needs 15 MB to compile the tests. So you should better
364 have 17 MB swap space and 1 MB room in $TMPDIR.
366 If you use `g++' version 2.7.x, don't add `-O2' to the CXXFLAGS,
367 because `g++ -O' generates better code for CLN than `g++ -O2'.
369 If you use `g++' version 2.8.x or egcs-2.91.x (a.k.a. egcs-1.1) or
370 gcc-2.95.x, I recommend adding `-fno-exceptions' to the CXXFLAGS. This
371 will likely generate better code.
373 If you use `g++' version egcs-2.91.x (egcs-1.1) or gcc-2.95.x on Sparc,
374 add either `-O' or `-O2 -fno-schedule-insns' to the CXXFLAGS. With
375 full `-O2', `g++' miscompiles the division routines. Also, for
376 -enable-shared to work, you need egcs-1.1.2 or newer.
378 On MIPS (SGI Irix 6), pass option `--without-gmp' to configure. gmp does
379 not work when compiled in `n32' binary format on Irix.
381 By default, only a static library is built. You can build CLN as a
382 shared library too, by calling `configure' with the option
383 `--enable-shared'. To get it built as a shared library only, call
384 `configure' with the options `--enable-shared --disable-static'.
386 If you use `g++' version egcs-2.91.x (egcs-1.1) on Sparc, you cannot
387 use `--enable-shared' because `g++' would miscompile parts of the
391 File: cln.info, Node: Installing the library, Next: Cleaning up, Prev: Building the library, Up: Installation
393 Installing the library
394 ======================
396 As with any autoconfiguring GNU software, installation is as easy as
401 The `make install' command installs the library and the include files
402 into public places (`/usr/local/lib/' and `/usr/local/include/', if you
403 haven't specified a `--prefix' option to `configure'). This step may
404 require superuser privileges.
406 If you have already built the library and wish to install it, but didn't
407 specify `--prefix=...' at configure time, just re-run `configure',
408 giving it the same options as the first time, plus the `--prefix=...'
412 File: cln.info, Node: Cleaning up, Prev: Installing the library, Up: Installation
417 You can remove system-dependent files generated by `make' through
421 You can remove all files generated by `make', thus reverting to a
422 virgin distribution of CLN, through
427 File: cln.info, Node: Ordinary number types, Next: Functions on numbers, Prev: Installation, Up: Top
429 Ordinary number types
430 *********************
432 CLN implements the following class hierarchy:
439 Real or complex number
448 +-------------------+-------------------+
450 Rational number Floating-point number
452 <cl_rational.h> <cl_float.h>
454 | +-------------+-------------+-------------+
456 cl_I Short-Float Single-Float Double-Float Long-Float
457 <cl_integer.h> cl_SF cl_FF cl_DF cl_LF
458 <cl_sfloat.h> <cl_ffloat.h> <cl_dfloat.h> <cl_lfloat.h>
460 The base class `cl_number' is an abstract base class. It is not useful
461 to declare a variable of this type except if you want to completely
462 disable compile-time type checking and use run-time type checking
465 The class `cl_N' comprises real and complex numbers. There is no
466 special class for complex numbers since complex numbers with imaginary
467 part `0' are automatically converted to real numbers.
469 The class `cl_R' comprises real numbers of different kinds. It is an
472 The class `cl_RA' comprises exact real numbers: rational numbers,
473 including integers. There is no special class for non-integral rational
474 numbers since rational numbers with denominator `1' are automatically
475 converted to integers.
477 The class `cl_F' implements floating-point approximations to real
478 numbers. It is an abstract class.
483 * Floating-point numbers::
488 File: cln.info, Node: Exact numbers, Next: Floating-point numbers, Prev: Ordinary number types, Up: Ordinary number types
493 Some numbers are represented as exact numbers: there is no loss of
494 information when such a number is converted from its mathematical value
495 to its internal representation. On exact numbers, the elementary
496 operations (`+', `-', `*', `/', comparisons, ...) compute the completely
499 In CLN, the exact numbers are:
501 * rational numbers (including integers),
503 * complex numbers whose real and imaginary parts are both rational
506 Rational numbers are always normalized to the form
507 `NUMERATOR/DENOMINATOR' where the numerator and denominator are coprime
508 integers and the denominator is positive. If the resulting denominator
509 is `1', the rational number is converted to an integer.
511 Small integers (typically in the range `-2^30'...`2^30-1', for 32-bit
512 machines) are especially efficient, because they consume no heap
513 allocation. Otherwise the distinction between these immediate integers
514 (called "fixnums") and heap allocated integers (called "bignums") is
515 completely transparent.
518 File: cln.info, Node: Floating-point numbers, Next: Complex numbers, Prev: Exact numbers, Up: Ordinary number types
520 Floating-point numbers
521 ======================
523 Not all real numbers can be represented exactly. (There is an easy
524 mathematical proof for this: Only a countable set of numbers can be
525 stored exactly in a computer, even if one assumes that it has unlimited
526 storage. But there are uncountably many real numbers.) So some
527 approximation is needed. CLN implements ordinary floating-point
528 numbers, with mantissa and exponent.
530 The elementary operations (`+', `-', `*', `/', ...) only return
531 approximate results. For example, the value of the expression `(cl_F)
532 0.3 + (cl_F) 0.4' prints as `0.70000005', not as `0.7'. Rounding errors
533 like this one are inevitable when computing with floating-point numbers.
535 Nevertheless, CLN rounds the floating-point results of the operations
536 `+', `-', `*', `/', `sqrt' according to the "round-to-even" rule: It
537 first computes the exact mathematical result and then returns the
538 floating-point number which is nearest to this. If two floating-point
539 numbers are equally distant from the ideal result, the one with a `0'
540 in its least significant mantissa bit is chosen.
542 Similarly, testing floating point numbers for equality `x == y' is
543 gambling with random errors. Better check for `abs(x - y) < epsilon'
544 for some well-chosen `epsilon'.
546 Floating point numbers come in four flavors:
548 * Short floats, type `cl_SF'. They have 1 sign bit, 8 exponent bits
549 (including the exponent's sign), and 17 mantissa bits (including
550 the "hidden" bit). They don't consume heap allocation.
552 * Single floats, type `cl_FF'. They have 1 sign bit, 8 exponent
553 bits (including the exponent's sign), and 24 mantissa bits
554 (including the "hidden" bit). In CLN, they are represented as
555 IEEE single-precision floating point numbers. This corresponds
556 closely to the C/C++ type `float'.
558 * Double floats, type `cl_DF'. They have 1 sign bit, 11 exponent
559 bits (including the exponent's sign), and 53 mantissa bits
560 (including the "hidden" bit). In CLN, they are represented as
561 IEEE double-precision floating point numbers. This corresponds
562 closely to the C/C++ type `double'.
564 * Long floats, type `cl_LF'. They have 1 sign bit, 32 exponent bits
565 (including the exponent's sign), and n mantissa bits (including
566 the "hidden" bit), where n >= 64. The precision of a long float
567 is unlimited, but once created, a long float has a fixed
568 precision. (No "lazy recomputation".)
570 Of course, computations with long floats are more expensive than those
571 with smaller floating-point formats.
573 CLN does not implement features like NaNs, denormalized numbers and
574 gradual underflow. If the exponent range of some floating-point type is
575 too limited for your application, choose another floating-point type
576 with larger exponent range.
578 As a user of CLN, you can forget about the differences between the four
579 floating-point types and just declare all your floating-point variables
580 as being of type `cl_F'. This has the advantage that when you change
581 the precision of some computation (say, from `cl_DF' to `cl_LF'), you
582 don't have to change the code, only the precision of the initial
583 values. Also, many transcendental functions have been declared as
584 returning a `cl_F' when the argument is a `cl_F', but such declarations
585 are missing for the types `cl_SF', `cl_FF', `cl_DF', `cl_LF'. (Such
586 declarations would be wrong if the floating point contagion rule
587 happened to change in the future.)
590 File: cln.info, Node: Complex numbers, Next: Conversions, Prev: Floating-point numbers, Up: Ordinary number types
595 Complex numbers, as implemented by the class `cl_N', have a real part
596 and an imaginary part, both real numbers. A complex number whose
597 imaginary part is the exact number `0' is automatically converted to a
600 Complex numbers can arise from real numbers alone, for example through
601 application of `sqrt' or transcendental functions.
604 File: cln.info, Node: Conversions, Prev: Complex numbers, Up: Ordinary number types
609 Conversions from any class to any its superclasses ("base classes" in
610 C++ terminology) is done automatically.
612 Conversions from the C built-in types `long' and `unsigned long' are
613 provided for the classes `cl_I', `cl_RA', `cl_R', `cl_N' and
616 Conversions from the C built-in types `int' and `unsigned int' are
617 provided for the classes `cl_I', `cl_RA', `cl_R', `cl_N' and
618 `cl_number'. However, these conversions emphasize efficiency. Their
619 range is therefore limited:
621 - The conversion from `int' works only if the argument is < 2^29 and
624 - The conversion from `unsigned int' works only if the argument is <
627 In a declaration like `cl_I x = 10;' the C++ compiler is able to do the
628 conversion of `10' from `int' to `cl_I' at compile time already. On the
629 other hand, code like `cl_I x = 1000000000;' is in error. So, if you
630 want to be sure that an `int' whose magnitude is not guaranteed to be <
631 2^29 is correctly converted to a `cl_I', first convert it to a `long'.
632 Similarly, if a large `unsigned int' is to be converted to a `cl_I',
633 first convert it to an `unsigned long'.
635 Conversions from the C built-in type `float' are provided for the
636 classes `cl_FF', `cl_F', `cl_R', `cl_N' and `cl_number'.
638 Conversions from the C built-in type `double' are provided for the
639 classes `cl_DF', `cl_F', `cl_R', `cl_N' and `cl_number'.
641 Conversions from `const char *' are provided for the classes `cl_I',
642 `cl_RA', `cl_SF', `cl_FF', `cl_DF', `cl_LF', `cl_F', `cl_R', `cl_N'.
643 The easiest way to specify a value which is outside of the range of the
644 C++ built-in types is therefore to specify it as a string, like this:
645 cl_I order_of_rubiks_cube_group = "43252003274489856000";
646 Note that this conversion is done at runtime, not at compile-time.
648 Conversions from `cl_I' to the C built-in types `int', `unsigned int',
649 `long', `unsigned long' are provided through the functions
651 `int cl_I_to_int (const cl_I& x)'
652 `unsigned int cl_I_to_uint (const cl_I& x)'
653 `long cl_I_to_long (const cl_I& x)'
654 `unsigned long cl_I_to_ulong (const cl_I& x)'
655 Returns `x' as element of the C type CTYPE. If `x' is not
656 representable in the range of CTYPE, a runtime error occurs.
658 Conversions from the classes `cl_I', `cl_RA', `cl_SF', `cl_FF',
659 `cl_DF', `cl_LF', `cl_F' and `cl_R' to the C built-in types `float' and
660 `double' are provided through the functions
662 `float cl_float_approx (const TYPE& x)'
663 `double cl_double_approx (const TYPE& x)'
664 Returns an approximation of `x' of C type CTYPE. If `abs(x)' is
665 too close to 0 (underflow), 0 is returned. If `abs(x)' is too
666 large (overflow), an IEEE infinity is returned.
668 Conversions from any class to any of its subclasses ("derived classes"
669 in C++ terminology) are not provided. Instead, you can assert and check
670 that a value belongs to a certain subclass, and return it as element of
671 that class, using the `As' and `The' macros. `As(TYPE)(VALUE)' checks
672 that VALUE belongs to TYPE and returns it as such. `The(TYPE)(VALUE)'
673 assumes that VALUE belongs to TYPE and returns it as such. It is your
674 responsibility to ensure that this assumption is valid. Example:
677 if (!(x >= 0)) abort();
678 cl_I ten_x = The(cl_I)(expt(10,x)); // If x >= 0, 10^x is an integer.
679 // In general, it would be a rational number.
682 File: cln.info, Node: Functions on numbers, Next: Input/Output, Prev: Ordinary number types, Up: Top
687 Each of the number classes declares its mathematical operations in the
688 corresponding include file. For example, if your code operates with
689 objects of type `cl_I', it should `#include <cl_integer.h>'.
693 * Constructing numbers::
694 * Elementary functions::
695 * Elementary rational functions::
696 * Elementary complex functions::
698 * Rounding functions::
700 * Transcendental functions::
701 * Functions on integers::
702 * Functions on floating-point numbers::
703 * Conversion functions::
704 * Random number generators::
705 * Obfuscating operators::
708 File: cln.info, Node: Constructing numbers, Next: Elementary functions, Prev: Functions on numbers, Up: Functions on numbers
713 Here is how to create number objects "from nothing".
717 * Constructing integers::
718 * Constructing rational numbers::
719 * Constructing floating-point numbers::
720 * Constructing complex numbers::
723 File: cln.info, Node: Constructing integers, Next: Constructing rational numbers, Prev: Constructing numbers, Up: Constructing numbers
725 Constructing integers
726 ---------------------
728 `cl_I' objects are most easily constructed from C integers and from
729 strings. See *Note Conversions::.
732 File: cln.info, Node: Constructing rational numbers, Next: Constructing floating-point numbers, Prev: Constructing integers, Up: Constructing numbers
734 Constructing rational numbers
735 -----------------------------
737 `cl_RA' objects can be constructed from strings. The syntax for
738 rational numbers is described in *Note Internal and printed
739 representation::. Another standard way to produce a rational number is
740 through application of `operator /' or `recip' on integers.
743 File: cln.info, Node: Constructing floating-point numbers, Next: Constructing complex numbers, Prev: Constructing rational numbers, Up: Constructing numbers
745 Constructing floating-point numbers
746 -----------------------------------
748 `cl_F' objects with low precision are most easily constructed from C
749 `float' and `double'. See *Note Conversions::.
751 To construct a `cl_F' with high precision, you can use the conversion
752 from `const char *', but you have to specify the desired precision
753 within the string. (See *Note Internal and printed representation::.)
755 cl_F e = "0.271828182845904523536028747135266249775724709369996e+1_40";
756 will set `e' to the given value, with a precision of 40 decimal digits.
758 The programmatic way to construct a `cl_F' with high precision is
759 through the `cl_float' conversion function, see *Note Conversion to
760 floating-point numbers::. For example, to compute `e' to 40 decimal
761 places, first construct 1.0 to 40 decimal places and then apply the
762 exponential function:
763 cl_float_format_t precision = cl_float_format(40);
764 cl_F e = exp(cl_float(1,precision));
767 File: cln.info, Node: Constructing complex numbers, Prev: Constructing floating-point numbers, Up: Constructing numbers
769 Constructing complex numbers
770 ----------------------------
772 Non-real `cl_N' objects are normally constructed through the function
773 cl_N complex (const cl_R& realpart, const cl_R& imagpart)
774 See *Note Elementary complex functions::.
777 File: cln.info, Node: Elementary functions, Next: Elementary rational functions, Prev: Constructing numbers, Up: Functions on numbers
782 Each of the classes `cl_N', `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF',
783 `cl_FF', `cl_DF', `cl_LF' defines the following operations:
785 `TYPE operator + (const TYPE&, const TYPE&)'
788 `TYPE operator - (const TYPE&, const TYPE&)'
791 `TYPE operator - (const TYPE&)'
792 Returns the negative of the argument.
794 `TYPE plus1 (const TYPE& x)'
797 `TYPE minus1 (const TYPE& x)'
800 `TYPE operator * (const TYPE&, const TYPE&)'
803 `TYPE square (const TYPE& x)'
806 Each of the classes `cl_N', `cl_R', `cl_RA', `cl_F', `cl_SF', `cl_FF',
807 `cl_DF', `cl_LF' defines the following operations:
809 `TYPE operator / (const TYPE&, const TYPE&)'
812 `TYPE recip (const TYPE&)'
813 Returns the reciprocal of the argument.
815 The class `cl_I' doesn't define a `/' operation because in the C/C++
816 language this operator, applied to integral types, denotes the `floor'
817 or `truncate' operation (which one of these, is implementation
818 dependent). (*Note Rounding functions::) Instead, `cl_I' defines an
819 "exact quotient" function:
821 `cl_I exquo (const cl_I& x, const cl_I& y)'
822 Checks that `y' divides `x', and returns the quotient `x'/`y'.
824 The following exponentiation functions are defined:
826 `cl_I expt_pos (const cl_I& x, const cl_I& y)'
827 `cl_RA expt_pos (const cl_RA& x, const cl_I& y)'
828 `y' must be > 0. Returns `x^y'.
830 `cl_RA expt (const cl_RA& x, const cl_I& y)'
831 `cl_R expt (const cl_R& x, const cl_I& y)'
832 `cl_N expt (const cl_N& x, const cl_I& y)'
835 Each of the classes `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF', `cl_FF',
836 `cl_DF', `cl_LF' defines the following operation:
838 `TYPE abs (const TYPE& x)'
839 Returns the absolute value of `x'. This is `x' if `x >= 0', and
842 The class `cl_N' implements this as follows:
844 `cl_R abs (const cl_N x)'
845 Returns the absolute value of `x'.
847 Each of the classes `cl_N', `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF',
848 `cl_FF', `cl_DF', `cl_LF' defines the following operation:
850 `TYPE signum (const TYPE& x)'
851 Returns the sign of `x', in the same number format as `x'. This
852 is defined as `x / abs(x)' if `x' is non-zero, and `x' if `x' is
853 zero. If `x' is real, the value is either 0 or 1 or -1.
856 File: cln.info, Node: Elementary rational functions, Next: Elementary complex functions, Prev: Elementary functions, Up: Functions on numbers
858 Elementary rational functions
859 =============================
861 Each of the classes `cl_RA', `cl_I' defines the following operations:
863 `cl_I numerator (const TYPE& x)'
864 Returns the numerator of `x'.
866 `cl_I denominator (const TYPE& x)'
867 Returns the denominator of `x'.
869 The numerator and denominator of a rational number are normalized in
870 such a way that they have no factor in common and the denominator is
874 File: cln.info, Node: Elementary complex functions, Next: Comparisons, Prev: Elementary rational functions, Up: Functions on numbers
876 Elementary complex functions
877 ============================
879 The class `cl_N' defines the following operation:
881 `cl_N complex (const cl_R& a, const cl_R& b)'
882 Returns the complex number `a+bi', that is, the complex number with
883 real part `a' and imaginary part `b'.
885 Each of the classes `cl_N', `cl_R' defines the following operations:
887 `cl_R realpart (const TYPE& x)'
888 Returns the real part of `x'.
890 `cl_R imagpart (const TYPE& x)'
891 Returns the imaginary part of `x'.
893 `TYPE conjugate (const TYPE& x)'
894 Returns the complex conjugate of `x'.
896 We have the relations
898 `x = complex(realpart(x), imagpart(x))'
900 `conjugate(x) = complex(realpart(x), -imagpart(x))'
903 File: cln.info, Node: Comparisons, Next: Rounding functions, Prev: Elementary complex functions, Up: Functions on numbers
908 Each of the classes `cl_N', `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF',
909 `cl_FF', `cl_DF', `cl_LF' defines the following operations:
911 `bool operator == (const TYPE&, const TYPE&)'
912 `bool operator != (const TYPE&, const TYPE&)'
913 Comparison, as in C and C++.
915 `uint32 cl_equal_hashcode (const TYPE&)'
916 Returns a 32-bit hash code that is the same for any two numbers
917 which are the same according to `=='. This hash code depends on
918 the number's value, not its type or precision.
920 `cl_boolean zerop (const TYPE& x)'
921 Compare against zero: `x == 0'
923 Each of the classes `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF', `cl_FF',
924 `cl_DF', `cl_LF' defines the following operations:
926 `cl_signean cl_compare (const TYPE& x, const TYPE& y)'
927 Compares `x' and `y'. Returns +1 if `x'>`y', -1 if `x'<`y', 0 if
930 `bool operator <= (const TYPE&, const TYPE&)'
931 `bool operator < (const TYPE&, const TYPE&)'
932 `bool operator >= (const TYPE&, const TYPE&)'
933 `bool operator > (const TYPE&, const TYPE&)'
934 Comparison, as in C and C++.
936 `cl_boolean minusp (const TYPE& x)'
937 Compare against zero: `x < 0'
939 `cl_boolean plusp (const TYPE& x)'
940 Compare against zero: `x > 0'
942 `TYPE max (const TYPE& x, const TYPE& y)'
943 Return the maximum of `x' and `y'.
945 `TYPE min (const TYPE& x, const TYPE& y)'
946 Return the minimum of `x' and `y'.
948 When a floating point number and a rational number are compared, the
949 float is first converted to a rational number using the function
950 `rational'. Since a floating point number actually represents an
951 interval of real numbers, the result might be surprising. For example,
952 `(cl_F)(cl_R)"1/3" == (cl_R)"1/3"' returns false because there is no
953 floating point number whose value is exactly `1/3'.
956 File: cln.info, Node: Rounding functions, Next: Roots, Prev: Comparisons, Up: Functions on numbers
961 When a real number is to be converted to an integer, there is no "best"
962 rounding. The desired rounding function depends on the application.
963 The Common Lisp and ISO Lisp standards offer four rounding functions:
966 This is the largest integer <=`x'.
969 This is the smallest integer >=`x'.
972 Among the integers between 0 and `x' (inclusive) the one nearest
976 The integer nearest to `x'. If `x' is exactly halfway between two
977 integers, choose the even one.
979 These functions have different advantages:
981 `floor' and `ceiling' are translation invariant: `floor(x+n) = floor(x)
982 + n' and `ceiling(x+n) = ceiling(x) + n' for every `x' and every
985 On the other hand, `truncate' and `round' are symmetric: `truncate(-x)
986 = -truncate(x)' and `round(-x) = -round(x)', and furthermore `round' is
987 unbiased: on the "average", it rounds down exactly as often as it
990 The functions are related like this:
992 `ceiling(m/n) = floor((m+n-1)/n) = floor((m-1)/n)+1' for rational
993 numbers `m/n' (`m', `n' integers, `n'>0), and
995 `truncate(x) = sign(x) * floor(abs(x))'
997 Each of the classes `cl_R', `cl_RA', `cl_F', `cl_SF', `cl_FF', `cl_DF',
998 `cl_LF' defines the following operations:
1000 `cl_I floor1 (const TYPE& x)'
1003 `cl_I ceiling1 (const TYPE& x)'
1004 Returns `ceiling(x)'.
1006 `cl_I truncate1 (const TYPE& x)'
1007 Returns `truncate(x)'.
1009 `cl_I round1 (const TYPE& x)'
1012 Each of the classes `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF', `cl_FF',
1013 `cl_DF', `cl_LF' defines the following operations:
1015 `cl_I floor1 (const TYPE& x, const TYPE& y)'
1016 Returns `floor(x/y)'.
1018 `cl_I ceiling1 (const TYPE& x, const TYPE& y)'
1019 Returns `ceiling(x/y)'.
1021 `cl_I truncate1 (const TYPE& x, const TYPE& y)'
1022 Returns `truncate(x/y)'.
1024 `cl_I round1 (const TYPE& x, const TYPE& y)'
1025 Returns `round(x/y)'.
1027 These functions are called `floor1', ... here instead of `floor', ...,
1028 because on some systems, system dependent include files define `floor'
1029 and `ceiling' as macros.
1031 In many cases, one needs both the quotient and the remainder of a
1032 division. It is more efficient to compute both at the same time than
1033 to perform two divisions, one for quotient and the next one for the
1034 remainder. The following functions therefore return a structure
1035 containing both the quotient and the remainder. The suffix `2'
1036 indicates the number of "return values". The remainder is defined as
1039 * for the computation of `quotient = floor(x)', `remainder = x -
1042 * for the computation of `quotient = floor(x,y)', `remainder = x -
1045 and similarly for the other three operations.
1047 Each of the classes `cl_R', `cl_RA', `cl_F', `cl_SF', `cl_FF', `cl_DF',
1048 `cl_LF' defines the following operations:
1050 `struct TYPE_div_t { cl_I quotient; TYPE remainder; };'
1051 `TYPE_div_t floor2 (const TYPE& x)'
1052 `TYPE_div_t ceiling2 (const TYPE& x)'
1053 `TYPE_div_t truncate2 (const TYPE& x)'
1054 `TYPE_div_t round2 (const TYPE& x)'
1055 Each of the classes `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF', `cl_FF',
1056 `cl_DF', `cl_LF' defines the following operations:
1058 `struct TYPE_div_t { cl_I quotient; TYPE remainder; };'
1059 `TYPE_div_t floor2 (const TYPE& x, const TYPE& y)'
1060 `TYPE_div_t ceiling2 (const TYPE& x, const TYPE& y)'
1061 `TYPE_div_t truncate2 (const TYPE& x, const TYPE& y)'
1062 `TYPE_div_t round2 (const TYPE& x, const TYPE& y)'
1063 Sometimes, one wants the quotient as a floating-point number (of the
1064 same format as the argument, if the argument is a float) instead of as
1065 an integer. The prefix `f' indicates this.
1067 Each of the classes `cl_F', `cl_SF', `cl_FF', `cl_DF', `cl_LF' defines
1068 the following operations:
1070 `TYPE ffloor (const TYPE& x)'
1071 `TYPE fceiling (const TYPE& x)'
1072 `TYPE ftruncate (const TYPE& x)'
1073 `TYPE fround (const TYPE& x)'
1074 and similarly for class `cl_R', but with return type `cl_F'.
1076 The class `cl_R' defines the following operations:
1078 `cl_F ffloor (const TYPE& x, const TYPE& y)'
1079 `cl_F fceiling (const TYPE& x, const TYPE& y)'
1080 `cl_F ftruncate (const TYPE& x, const TYPE& y)'
1081 `cl_F fround (const TYPE& x, const TYPE& y)'
1082 These functions also exist in versions which return both the quotient
1083 and the remainder. The suffix `2' indicates this.
1085 Each of the classes `cl_F', `cl_SF', `cl_FF', `cl_DF', `cl_LF' defines
1086 the following operations:
1088 `struct TYPE_fdiv_t { TYPE quotient; TYPE remainder; };'
1089 `TYPE_fdiv_t ffloor2 (const TYPE& x)'
1090 `TYPE_fdiv_t fceiling2 (const TYPE& x)'
1091 `TYPE_fdiv_t ftruncate2 (const TYPE& x)'
1092 `TYPE_fdiv_t fround2 (const TYPE& x)'
1093 and similarly for class `cl_R', but with quotient type `cl_F'.
1095 The class `cl_R' defines the following operations:
1097 `struct TYPE_fdiv_t { cl_F quotient; cl_R remainder; };'
1098 `TYPE_fdiv_t ffloor2 (const TYPE& x, const TYPE& y)'
1099 `TYPE_fdiv_t fceiling2 (const TYPE& x, const TYPE& y)'
1100 `TYPE_fdiv_t ftruncate2 (const TYPE& x, const TYPE& y)'
1101 `TYPE_fdiv_t fround2 (const TYPE& x, const TYPE& y)'
1102 Other applications need only the remainder of a division. The
1103 remainder of `floor' and `ffloor' is called `mod' (abbreviation of
1104 "modulo"). The remainder `truncate' and `ftruncate' is called `rem'
1105 (abbreviation of "remainder").
1107 * `mod(x,y) = floor2(x,y).remainder = x - floor(x/y)*y'
1109 * `rem(x,y) = truncate2(x,y).remainder = x - truncate(x/y)*y'
1111 If `x' and `y' are both >= 0, `mod(x,y) = rem(x,y) >= 0'. In general,
1112 `mod(x,y)' has the sign of `y' or is zero, and `rem(x,y)' has the sign
1115 The classes `cl_R', `cl_I' define the following operations:
1117 `TYPE mod (const TYPE& x, const TYPE& y)'
1118 `TYPE rem (const TYPE& x, const TYPE& y)'
1120 File: cln.info, Node: Roots, Next: Transcendental functions, Prev: Rounding functions, Up: Functions on numbers
1125 Each of the classes `cl_R', `cl_F', `cl_SF', `cl_FF', `cl_DF', `cl_LF'
1126 defines the following operation:
1128 `TYPE sqrt (const TYPE& x)'
1129 `x' must be >= 0. This function returns the square root of `x',
1130 normalized to be >= 0. If `x' is the square of a rational number,
1131 `sqrt(x)' will be a rational number, else it will return a
1132 floating-point approximation.
1134 The classes `cl_RA', `cl_I' define the following operation:
1136 `cl_boolean sqrtp (const TYPE& x, TYPE* root)'
1137 This tests whether `x' is a perfect square. If so, it returns true
1138 and the exact square root in `*root', else it returns false.
1140 Furthermore, for integers, similarly:
1142 `cl_boolean isqrt (const TYPE& x, TYPE* root)'
1143 `x' should be >= 0. This function sets `*root' to `floor(sqrt(x))'
1144 and returns the same value as `sqrtp': the boolean value
1145 `(expt(*root,2) == x)'.
1147 For `n'th roots, the classes `cl_RA', `cl_I' define the following
1150 `cl_boolean rootp (const TYPE& x, const cl_I& n, TYPE* root)'
1151 `x' must be >= 0. `n' must be > 0. This tests whether `x' is an
1152 `n'th power of a rational number. If so, it returns true and the
1153 exact root in `*root', else it returns false.
1155 The only square root function which accepts negative numbers is the one
1158 `cl_N sqrt (const cl_N& z)'
1159 Returns the square root of `z', as defined by the formula `sqrt(z)
1160 = exp(log(z)/2)'. Conversion to a floating-point type or to a
1161 complex number are done if necessary. The range of the result is
1162 the right half plane `realpart(sqrt(z)) >= 0' including the
1163 positive imaginary axis and 0, but excluding the negative
1164 imaginary axis. The result is an exact number only if `z' is an
1168 File: cln.info, Node: Transcendental functions, Next: Functions on integers, Prev: Roots, Up: Functions on numbers
1170 Transcendental functions
1171 ========================
1173 The transcendental functions return an exact result if the argument is
1174 exact and the result is exact as well. Otherwise they must return
1175 inexact numbers even if the argument is exact. For example, `cos(0) =
1176 1' returns the rational number `1'.
1180 * Exponential and logarithmic functions::
1181 * Trigonometric functions::
1182 * Hyperbolic functions::
1187 File: cln.info, Node: Exponential and logarithmic functions, Next: Trigonometric functions, Prev: Transcendental functions, Up: Transcendental functions
1189 Exponential and logarithmic functions
1190 -------------------------------------
1192 `cl_R exp (const cl_R& x)'
1193 `cl_N exp (const cl_N& x)'
1194 Returns the exponential function of `x'. This is `e^x' where `e'
1195 is the base of the natural logarithms. The range of the result is
1196 the entire complex plane excluding 0.
1198 `cl_R ln (const cl_R& x)'
1199 `x' must be > 0. Returns the (natural) logarithm of x.
1201 `cl_N log (const cl_N& x)'
1202 Returns the (natural) logarithm of x. If `x' is real and positive,
1203 this is `ln(x)'. In general, `log(x) = log(abs(x)) + i*phase(x)'.
1204 The range of the result is the strip in the complex plane `-pi <
1205 imagpart(log(x)) <= pi'.
1207 `cl_R phase (const cl_N& x)'
1208 Returns the angle part of `x' in its polar representation as a
1209 complex number. That is, `phase(x) =
1210 atan(realpart(x),imagpart(x))'. This is also the imaginary part
1211 of `log(x)'. The range of the result is the interval `-pi <
1212 phase(x) <= pi'. The result will be an exact number only if
1213 `zerop(x)' or if `x' is real and positive.
1215 `cl_R log (const cl_R& a, const cl_R& b)'
1216 `a' and `b' must be > 0. Returns the logarithm of `a' with respect
1217 to base `b'. `log(a,b) = ln(a)/ln(b)'. The result can be exact
1218 only if `a = 1' or if `a' and `b' are both rational.
1220 `cl_N log (const cl_N& a, const cl_N& b)'
1221 Returns the logarithm of `a' with respect to base `b'. `log(a,b)
1224 `cl_N expt (const cl_N& x, const cl_N& y)'
1225 Exponentiation: Returns `x^y = exp(y*log(x))'.
1227 The constant e = exp(1) = 2.71828... is returned by the following
1230 `cl_F cl_exp1 (cl_float_format_t f)'
1231 Returns e as a float of format `f'.
1233 `cl_F cl_exp1 (const cl_F& y)'
1234 Returns e in the float format of `y'.
1236 `cl_F cl_exp1 (void)'
1237 Returns e as a float of format `cl_default_float_format'.
1240 File: cln.info, Node: Trigonometric functions, Next: Hyperbolic functions, Prev: Exponential and logarithmic functions, Up: Transcendental functions
1242 Trigonometric functions
1243 -----------------------
1245 `cl_R sin (const cl_R& x)'
1246 Returns `sin(x)'. The range of the result is the interval `-1 <=
1249 `cl_N sin (const cl_N& z)'
1250 Returns `sin(z)'. The range of the result is the entire complex
1253 `cl_R cos (const cl_R& x)'
1254 Returns `cos(x)'. The range of the result is the interval `-1 <=
1257 `cl_N cos (const cl_N& x)'
1258 Returns `cos(z)'. The range of the result is the entire complex
1261 `struct cl_cos_sin_t { cl_R cos; cl_R sin; };'
1262 `cl_cos_sin_t cl_cos_sin (const cl_R& x)'
1263 Returns both `sin(x)' and `cos(x)'. This is more efficient than
1264 computing them separately. The relation `cos^2 + sin^2 = 1' will
1265 hold only approximately.
1267 `cl_R tan (const cl_R& x)'
1268 `cl_N tan (const cl_N& x)'
1269 Returns `tan(x) = sin(x)/cos(x)'.
1271 `cl_N cis (const cl_R& x)'
1272 `cl_N cis (const cl_N& x)'
1273 Returns `exp(i*x)'. The name `cis' means "cos + i sin", because
1274 `e^(i*x) = cos(x) + i*sin(x)'.
1276 `cl_N asin (const cl_N& z)'
1277 Returns `arcsin(z)'. This is defined as `arcsin(z) =
1278 log(iz+sqrt(1-z^2))/i' and satisfies `arcsin(-z) = -arcsin(z)'.
1279 The range of the result is the strip in the complex domain `-pi/2
1280 <= realpart(arcsin(z)) <= pi/2', excluding the numbers with
1281 `realpart = -pi/2' and `imagpart < 0' and the numbers with
1282 `realpart = pi/2' and `imagpart > 0'.
1284 `cl_N acos (const cl_N& z)'
1285 Returns `arccos(z)'. This is defined as `arccos(z) = pi/2 -
1286 arcsin(z) = log(z+i*sqrt(1-z^2))/i' and satisfies `arccos(-z) = pi
1287 - arccos(z)'. The range of the result is the strip in the complex
1288 domain `0 <= realpart(arcsin(z)) <= pi', excluding the numbers
1289 with `realpart = 0' and `imagpart < 0' and the numbers with
1290 `realpart = pi' and `imagpart > 0'.
1292 `cl_R atan (const cl_R& x, const cl_R& y)'
1293 Returns the angle of the polar representation of the complex number
1294 `x+iy'. This is `atan(y/x)' if `x>0'. The range of the result is
1295 the interval `-pi < atan(x,y) <= pi'. The result will be an exact
1296 number only if `x > 0' and `y' is the exact `0'. WARNING: In
1297 Common Lisp, this function is called as `(atan y x)', with
1298 reversed order of arguments.
1300 `cl_R atan (const cl_R& x)'
1301 Returns `arctan(x)'. This is the same as `atan(1,x)'. The range of
1302 the result is the interval `-pi/2 < atan(x) < pi/2'. The result
1303 will be an exact number only if `x' is the exact `0'.
1305 `cl_N atan (const cl_N& z)'
1306 Returns `arctan(z)'. This is defined as `arctan(z) =
1307 (log(1+iz)-log(1-iz)) / 2i' and satisfies `arctan(-z) =
1308 -arctan(z)'. The range of the result is the strip in the complex
1309 domain `-pi/2 <= realpart(arctan(z)) <= pi/2', excluding the
1310 numbers with `realpart = -pi/2' and `imagpart >= 0' and the numbers
1311 with `realpart = pi/2' and `imagpart <= 0'.
1313 The constant pi = 3.14... is returned by the following functions:
1315 `cl_F cl_pi (cl_float_format_t f)'
1316 Returns pi as a float of format `f'.
1318 `cl_F cl_pi (const cl_F& y)'
1319 Returns pi in the float format of `y'.
1322 Returns pi as a float of format `cl_default_float_format'.
1325 File: cln.info, Node: Hyperbolic functions, Next: Euler gamma, Prev: Trigonometric functions, Up: Transcendental functions
1327 Hyperbolic functions
1328 --------------------
1330 `cl_R sinh (const cl_R& x)'
1333 `cl_N sinh (const cl_N& z)'
1334 Returns `sinh(z)'. The range of the result is the entire complex
1337 `cl_R cosh (const cl_R& x)'
1338 Returns `cosh(x)'. The range of the result is the interval
1341 `cl_N cosh (const cl_N& z)'
1342 Returns `cosh(z)'. The range of the result is the entire complex
1345 `struct cl_cosh_sinh_t { cl_R cosh; cl_R sinh; };'
1346 `cl_cosh_sinh_t cl_cosh_sinh (const cl_R& x)'
1347 Returns both `sinh(x)' and `cosh(x)'. This is more efficient than
1348 computing them separately. The relation `cosh^2 - sinh^2 = 1' will
1349 hold only approximately.
1351 `cl_R tanh (const cl_R& x)'
1352 `cl_N tanh (const cl_N& x)'
1353 Returns `tanh(x) = sinh(x)/cosh(x)'.
1355 `cl_N asinh (const cl_N& z)'
1356 Returns `arsinh(z)'. This is defined as `arsinh(z) =
1357 log(z+sqrt(1+z^2))' and satisfies `arsinh(-z) = -arsinh(z)'. The
1358 range of the result is the strip in the complex domain `-pi/2 <=
1359 imagpart(arsinh(z)) <= pi/2', excluding the numbers with `imagpart
1360 = -pi/2' and `realpart > 0' and the numbers with `imagpart = pi/2'
1363 `cl_N acosh (const cl_N& z)'
1364 Returns `arcosh(z)'. This is defined as `arcosh(z) =
1365 2*log(sqrt((z+1)/2)+sqrt((z-1)/2))'. The range of the result is
1366 the half-strip in the complex domain `-pi < imagpart(arcosh(z)) <=
1367 pi, realpart(arcosh(z)) >= 0', excluding the numbers with
1368 `realpart = 0' and `-pi < imagpart < 0'.
1370 `cl_N atanh (const cl_N& z)'
1371 Returns `artanh(z)'. This is defined as `artanh(z) =
1372 (log(1+z)-log(1-z)) / 2' and satisfies `artanh(-z) = -artanh(z)'.
1373 The range of the result is the strip in the complex domain `-pi/2
1374 <= imagpart(artanh(z)) <= pi/2', excluding the numbers with
1375 `imagpart = -pi/2' and `realpart <= 0' and the numbers with
1376 `imagpart = pi/2' and `realpart >= 0'.
1379 File: cln.info, Node: Euler gamma, Next: Riemann zeta, Prev: Hyperbolic functions, Up: Transcendental functions
1384 Euler's constant C = 0.577... is returned by the following functions:
1386 `cl_F cl_eulerconst (cl_float_format_t f)'
1387 Returns Euler's constant as a float of format `f'.
1389 `cl_F cl_eulerconst (const cl_F& y)'
1390 Returns Euler's constant in the float format of `y'.
1392 `cl_F cl_eulerconst (void)'
1393 Returns Euler's constant as a float of format
1394 `cl_default_float_format'.
1396 Catalan's constant G = 0.915... is returned by the following functions:
1398 `cl_F cl_catalanconst (cl_float_format_t f)'
1399 Returns Catalan's constant as a float of format `f'.
1401 `cl_F cl_catalanconst (const cl_F& y)'
1402 Returns Catalan's constant in the float format of `y'.
1404 `cl_F cl_catalanconst (void)'
1405 Returns Catalan's constant as a float of format
1406 `cl_default_float_format'.
1409 File: cln.info, Node: Riemann zeta, Prev: Euler gamma, Up: Transcendental functions
1414 Riemann's zeta function at an integral point `s>1' is returned by the
1415 following functions:
1417 `cl_F cl_zeta (int s, cl_float_format_t f)'
1418 Returns Riemann's zeta function at `s' as a float of format `f'.
1420 `cl_F cl_zeta (int s, const cl_F& y)'
1421 Returns Riemann's zeta function at `s' in the float format of `y'.
1423 `cl_F cl_zeta (int s)'
1424 Returns Riemann's zeta function at `s' as a float of format
1425 `cl_default_float_format'.
1428 File: cln.info, Node: Functions on integers, Next: Functions on floating-point numbers, Prev: Transcendental functions, Up: Functions on numbers
1430 Functions on integers
1431 =====================
1435 * Logical functions::
1436 * Number theoretic functions::
1437 * Combinatorial functions::
1440 File: cln.info, Node: Logical functions, Next: Number theoretic functions, Prev: Functions on integers, Up: Functions on integers
1445 Integers, when viewed as in two's complement notation, can be thought as
1446 infinite bit strings where the bits' values eventually are constant.
1451 The logical operations view integers as such bit strings and operate on
1452 each of the bit positions in parallel.
1454 `cl_I lognot (const cl_I& x)'
1455 `cl_I operator ~ (const cl_I& x)'
1456 Logical not, like `~x' in C. This is the same as `-1-x'.
1458 `cl_I logand (const cl_I& x, const cl_I& y)'
1459 `cl_I operator & (const cl_I& x, const cl_I& y)'
1460 Logical and, like `x & y' in C.
1462 `cl_I logior (const cl_I& x, const cl_I& y)'
1463 `cl_I operator | (const cl_I& x, const cl_I& y)'
1464 Logical (inclusive) or, like `x | y' in C.
1466 `cl_I logxor (const cl_I& x, const cl_I& y)'
1467 `cl_I operator ^ (const cl_I& x, const cl_I& y)'
1468 Exclusive or, like `x ^ y' in C.
1470 `cl_I logeqv (const cl_I& x, const cl_I& y)'
1471 Bitwise equivalence, like `~(x ^ y)' in C.
1473 `cl_I lognand (const cl_I& x, const cl_I& y)'
1474 Bitwise not and, like `~(x & y)' in C.
1476 `cl_I lognor (const cl_I& x, const cl_I& y)'
1477 Bitwise not or, like `~(x | y)' in C.
1479 `cl_I logandc1 (const cl_I& x, const cl_I& y)'
1480 Logical and, complementing the first argument, like `~x & y' in C.
1482 `cl_I logandc2 (const cl_I& x, const cl_I& y)'
1483 Logical and, complementing the second argument, like `x & ~y' in C.
1485 `cl_I logorc1 (const cl_I& x, const cl_I& y)'
1486 Logical or, complementing the first argument, like `~x | y' in C.
1488 `cl_I logorc2 (const cl_I& x, const cl_I& y)'
1489 Logical or, complementing the second argument, like `x | ~y' in C.
1491 These operations are all available though the function
1492 `cl_I boole (cl_boole op, const cl_I& x, const cl_I& y)'
1493 where `op' must have one of the 16 values (each one stands for a
1494 function which combines two bits into one bit): `boole_clr',
1495 `boole_set', `boole_1', `boole_2', `boole_c1', `boole_c2', `boole_and',
1496 `boole_ior', `boole_xor', `boole_eqv', `boole_nand', `boole_nor',
1497 `boole_andc1', `boole_andc2', `boole_orc1', `boole_orc2'.
1499 Other functions that view integers as bit strings:
1501 `cl_boolean logtest (const cl_I& x, const cl_I& y)'
1502 Returns true if some bit is set in both `x' and `y', i.e. if
1505 `cl_boolean logbitp (const cl_I& n, const cl_I& x)'
1506 Returns true if the `n'th bit (from the right) of `x' is set. Bit
1507 0 is the least significant bit.
1509 `uintL logcount (const cl_I& x)'
1510 Returns the number of one bits in `x', if `x' >= 0, or the number
1511 of zero bits in `x', if `x' < 0.
1513 The following functions operate on intervals of bits in integers. The
1515 struct cl_byte { uintL size; uintL position; };
1516 represents the bit interval containing the bits
1517 `position'...`position+size-1' of an integer. The constructor
1518 `cl_byte(size,position)' constructs a `cl_byte'.
1520 `cl_I ldb (const cl_I& n, const cl_byte& b)'
1521 extracts the bits of `n' described by the bit interval `b' and
1522 returns them as a nonnegative integer with `b.size' bits.
1524 `cl_boolean ldb_test (const cl_I& n, const cl_byte& b)'
1525 Returns true if some bit described by the bit interval `b' is set
1528 `cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b)'
1529 Returns `n', with the bits described by the bit interval `b'
1530 replaced by `newbyte'. Only the lowest `b.size' bits of `newbyte'
1533 The functions `ldb' and `dpb' implicitly shift. The following functions
1534 are their counterparts without shifting:
1536 `cl_I mask_field (const cl_I& n, const cl_byte& b)'
1537 returns an integer with the bits described by the bit interval `b'
1538 copied from the corresponding bits in `n', the other bits zero.
1540 `cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b)'
1541 returns an integer where the bits described by the bit interval `b'
1542 come from `newbyte' and the other bits come from `n'.
1544 The following relations hold:
1546 `ldb (n, b) = mask_field(n, b) >> b.position',
1548 `dpb (newbyte, n, b) = deposit_field (newbyte << b.position, n,
1551 `deposit_field(newbyte,n,b) = n ^ mask_field(n,b) ^
1552 mask_field(new_byte,b)'.
1554 The following operations on integers as bit strings are efficient
1555 shortcuts for common arithmetic operations:
1557 `cl_boolean oddp (const cl_I& x)'
1558 Returns true if the least significant bit of `x' is 1. Equivalent
1561 `cl_boolean evenp (const cl_I& x)'
1562 Returns true if the least significant bit of `x' is 0. Equivalent
1565 `cl_I operator << (const cl_I& x, const cl_I& n)'
1566 Shifts `x' by `n' bits to the left. `n' should be >=0. Equivalent
1569 `cl_I operator >> (const cl_I& x, const cl_I& n)'
1570 Shifts `x' by `n' bits to the right. `n' should be >=0. Bits
1571 shifted out to the right are thrown away. Equivalent to `floor(x
1574 `cl_I ash (const cl_I& x, const cl_I& y)'
1575 Shifts `x' by `y' bits to the left (if `y'>=0) or by `-y' bits to
1576 the right (if `y'<=0). In other words, this returns `floor(x *
1579 `uintL integer_length (const cl_I& x)'
1580 Returns the number of bits (excluding the sign bit) needed to
1581 represent `x' in two's complement notation. This is the smallest n
1582 >= 0 such that -2^n <= x < 2^n. If x > 0, this is the unique n > 0
1583 such that 2^(n-1) <= x < 2^n.
1585 `uintL ord2 (const cl_I& x)'
1586 `x' must be non-zero. This function returns the number of 0 bits
1587 at the right of `x' in two's complement notation. This is the
1588 largest n >= 0 such that 2^n divides `x'.
1590 `uintL power2p (const cl_I& x)'
1591 `x' must be > 0. This function checks whether `x' is a power of 2.
1592 If `x' = 2^(n-1), it returns n. Else it returns 0. (See also the
1596 File: cln.info, Node: Number theoretic functions, Next: Combinatorial functions, Prev: Logical functions, Up: Functions on integers
1598 Number theoretic functions
1599 --------------------------
1601 `uint32 gcd (uint32 a, uint32 b)'
1602 `cl_I gcd (const cl_I& a, const cl_I& b)'
1603 This function returns the greatest common divisor of `a' and `b',
1604 normalized to be >= 0.
1606 `cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)'
1607 This function ("extended gcd") returns the greatest common divisor
1608 `g' of `a' and `b' and at the same time the representation of `g'
1609 as an integral linear combination of `a' and `b': `u' and `v' with
1610 `u*a+v*b = g', `g' >= 0. `u' and `v' will be normalized to be of
1611 smallest possible absolute value, in the following sense: If `a'
1612 and `b' are non-zero, and `abs(a) != abs(b)', `u' and `v' will
1613 satisfy the inequalities `abs(u) <= abs(b)/(2*g)', `abs(v) <=
1616 `cl_I lcm (const cl_I& a, const cl_I& b)'
1617 This function returns the least common multiple of `a' and `b',
1618 normalized to be >= 0.
1620 `cl_boolean logp (const cl_I& a, const cl_I& b, cl_RA* l)'
1621 `cl_boolean logp (const cl_RA& a, const cl_RA& b, cl_RA* l)'
1622 `a' must be > 0. `b' must be >0 and != 1. If log(a,b) is rational
1623 number, this function returns true and sets *l = log(a,b), else it
1627 File: cln.info, Node: Combinatorial functions, Prev: Number theoretic functions, Up: Functions on integers
1629 Combinatorial functions
1630 -----------------------
1632 `cl_I factorial (uintL n)'
1633 `n' must be a small integer >= 0. This function returns the
1634 factorial `n'! = `1*2*...*n'.
1636 `cl_I doublefactorial (uintL n)'
1637 `n' must be a small integer >= 0. This function returns the
1638 doublefactorial `n'!! = `1*3*...*n' or `n'!! = `2*4*...*n',
1641 `cl_I binomial (uintL n, uintL k)'
1642 `n' and `k' must be small integers >= 0. This function returns the
1643 binomial coefficient (`n' choose `k') = `n'! / `k'! `(n-k)'! for
1644 0 <= k <= n, 0 else.
1647 File: cln.info, Node: Functions on floating-point numbers, Next: Conversion functions, Prev: Functions on integers, Up: Functions on numbers
1649 Functions on floating-point numbers
1650 ===================================
1652 Recall that a floating-point number consists of a sign `s', an exponent
1653 `e' and a mantissa `m'. The value of the number is `(-1)^s * 2^e * m'.
1655 Each of the classes `cl_F', `cl_SF', `cl_FF', `cl_DF', `cl_LF' defines
1656 the following operations.
1658 `TYPE scale_float (const TYPE& x, sintL delta)'
1659 `TYPE scale_float (const TYPE& x, const cl_I& delta)'
1660 Returns `x*2^delta'. This is more efficient than an explicit
1661 multiplication because it copies `x' and modifies the exponent.
1663 The following functions provide an abstract interface to the underlying
1664 representation of floating-point numbers.
1666 `sintL float_exponent (const TYPE& x)'
1667 Returns the exponent `e' of `x'. For `x = 0.0', this is 0. For
1668 `x' non-zero, this is the unique integer with `2^(e-1) <= abs(x) <
1671 `sintL float_radix (const TYPE& x)'
1672 Returns the base of the floating-point representation. This is
1675 `TYPE float_sign (const TYPE& x)'
1676 Returns the sign `s' of `x' as a float. The value is 1 for `x' >=
1679 `uintL float_digits (const TYPE& x)'
1680 Returns the number of mantissa bits in the floating-point
1681 representation of `x', including the hidden bit. The value only
1682 depends on the type of `x', not on its value.
1684 `uintL float_precision (const TYPE& x)'
1685 Returns the number of significant mantissa bits in the
1686 floating-point representation of `x'. Since denormalized numbers
1687 are not supported, this is the same as `float_digits(x)' if `x' is
1688 non-zero, and 0 if `x' = 0.
1690 The complete internal representation of a float is encoded in the type
1691 `cl_decoded_float' (or `cl_decoded_sfloat', `cl_decoded_ffloat',
1692 `cl_decoded_dfloat', `cl_decoded_lfloat', respectively), defined by
1693 struct cl_decoded_TYPEfloat {
1694 TYPE mantissa; cl_I exponent; TYPE sign;
1697 and returned by the function
1699 `cl_decoded_TYPEfloat decode_float (const TYPE& x)'
1700 For `x' non-zero, this returns `(-1)^s', `e', `m' with `x = (-1)^s
1701 * 2^e * m' and `0.5 <= m < 1.0'. For `x' = 0, it returns
1702 `(-1)^s'=1, `e'=0, `m'=0. `e' is the same as returned by the
1703 function `float_exponent'.
1705 A complete decoding in terms of integers is provided as type
1706 struct cl_idecoded_float {
1707 cl_I mantissa; cl_I exponent; cl_I sign;
1709 by the following function:
1711 `cl_idecoded_float integer_decode_float (const TYPE& x)'
1712 For `x' non-zero, this returns `(-1)^s', `e', `m' with `x = (-1)^s
1713 * 2^e * m' and `m' an integer with `float_digits(x)' bits. For `x'
1714 = 0, it returns `(-1)^s'=1, `e'=0, `m'=0. WARNING: The exponent
1715 `e' is not the same as the one returned by the functions
1716 `decode_float' and `float_exponent'.
1718 Some other function, implemented only for class `cl_F':
1720 `cl_F float_sign (const cl_F& x, const cl_F& y)'
1721 This returns a floating point number whose precision and absolute
1722 value is that of `y' and whose sign is that of `x'. If `x' is
1723 zero, it is treated as positive. Same for `y'.
1726 File: cln.info, Node: Conversion functions, Next: Random number generators, Prev: Functions on floating-point numbers, Up: Functions on numbers
1728 Conversion functions
1729 ====================
1733 * Conversion to floating-point numbers::
1734 * Conversion to rational numbers::
1737 File: cln.info, Node: Conversion to floating-point numbers, Next: Conversion to rational numbers, Prev: Conversion functions, Up: Conversion functions
1739 Conversion to floating-point numbers
1740 ------------------------------------
1742 The type `cl_float_format_t' describes a floating-point format.
1744 `cl_float_format_t cl_float_format (uintL n)'
1745 Returns the smallest float format which guarantees at least `n'
1746 decimal digits in the mantissa (after the decimal point).
1748 `cl_float_format_t cl_float_format (const cl_F& x)'
1749 Returns the floating point format of `x'.
1751 `cl_float_format_t cl_default_float_format'
1752 Global variable: the default float format used when converting
1753 rational numbers to floats.
1755 To convert a real number to a float, each of the types `cl_R', `cl_F',
1756 `cl_I', `cl_RA', `int', `unsigned int', `float', `double' defines the
1757 following operations:
1759 `cl_F cl_float (const TYPE&x, cl_float_format_t f)'
1760 Returns `x' as a float of format `f'.
1762 `cl_F cl_float (const TYPE&x, const cl_F& y)'
1763 Returns `x' in the float format of `y'.
1765 `cl_F cl_float (const TYPE&x)'
1766 Returns `x' as a float of format `cl_default_float_format' if it
1767 is an exact number, or `x' itself if it is already a float.
1769 Of course, converting a number to a float can lose precision.
1771 Every floating-point format has some characteristic numbers:
1773 `cl_F most_positive_float (cl_float_format_t f)'
1774 Returns the largest (most positive) floating point number in float
1777 `cl_F most_negative_float (cl_float_format_t f)'
1778 Returns the smallest (most negative) floating point number in
1781 `cl_F least_positive_float (cl_float_format_t f)'
1782 Returns the least positive floating point number (i.e. > 0 but
1783 closest to 0) in float format `f'.
1785 `cl_F least_negative_float (cl_float_format_t f)'
1786 Returns the least negative floating point number (i.e. < 0 but
1787 closest to 0) in float format `f'.
1789 `cl_F float_epsilon (cl_float_format_t f)'
1790 Returns the smallest floating point number e > 0 such that `1+e !=
1793 `cl_F float_negative_epsilon (cl_float_format_t f)'
1794 Returns the smallest floating point number e > 0 such that `1-e !=
1798 File: cln.info, Node: Conversion to rational numbers, Prev: Conversion to floating-point numbers, Up: Conversion functions
1800 Conversion to rational numbers
1801 ------------------------------
1803 Each of the classes `cl_R', `cl_RA', `cl_F' defines the following
1806 `cl_RA rational (const TYPE& x)'
1807 Returns the value of `x' as an exact number. If `x' is already an
1808 exact number, this is `x'. If `x' is a floating-point number, the
1809 value is a rational number whose denominator is a power of 2.
1811 In order to convert back, say, `(cl_F)(cl_R)"1/3"' to `1/3', there is
1814 `cl_RA rationalize (const cl_R& x)'
1815 If `x' is a floating-point number, it actually represents an
1816 interval of real numbers, and this function returns the rational
1817 number with smallest denominator (and smallest numerator, in
1818 magnitude) which lies in this interval. If `x' is already an
1819 exact number, this function returns `x'.
1821 If `x' is any float, one has
1823 `cl_float(rational(x),x) = x'
1825 `cl_float(rationalize(x),x) = x'
1828 File: cln.info, Node: Random number generators, Next: Obfuscating operators, Prev: Conversion functions, Up: Functions on numbers
1830 Random number generators
1831 ========================
1833 A random generator is a machine which produces (pseudo-)random numbers.
1834 The include file `<cl_random.h>' defines a class `cl_random_state'
1835 which contains the state of a random generator. If you make a copy of
1836 the random number generator, the original one and the copy will produce
1837 the same sequence of random numbers.
1839 The following functions return (pseudo-)random numbers in different
1840 formats. Calling one of these modifies the state of the random number
1841 generator in a complicated but deterministic way.
1844 cl_random_state cl_default_random_state
1845 contains a default random number generator. It is used when the
1846 functions below are called without `cl_random_state' argument.
1848 `uint32 random32 (cl_random_state& randomstate)'
1849 `uint32 random32 ()'
1850 Returns a random unsigned 32-bit number. All bits are equally
1853 `cl_I random_I (cl_random_state& randomstate, const cl_I& n)'
1854 `cl_I random_I (const cl_I& n)'
1855 `n' must be an integer > 0. This function returns a random integer
1856 `x' in the range `0 <= x < n'.
1858 `cl_F random_F (cl_random_state& randomstate, const cl_F& n)'
1859 `cl_F random_F (const cl_F& n)'
1860 `n' must be a float > 0. This function returns a random
1861 floating-point number of the same format as `n' in the range `0 <=
1864 `cl_R random_R (cl_random_state& randomstate, const cl_R& n)'
1865 `cl_R random_R (const cl_R& n)'
1866 Behaves like `random_I' if `n' is an integer and like `random_F'
1870 File: cln.info, Node: Obfuscating operators, Prev: Random number generators, Up: Functions on numbers
1872 Obfuscating operators
1873 =====================
1875 The modifying C/C++ operators `+=', `-=', `*=', `/=', `&=', `|=', `^=',
1876 `<<=', `>>=' are not available by default because their use tends to
1877 make programs unreadable. It is trivial to get away without them.
1878 However, if you feel that you absolutely need these operators to get
1880 #define WANT_OBFUSCATING_OPERATORS
1881 to the beginning of your source files, before the inclusion of any CLN
1882 include files. This flag will enable the following operators:
1884 For the classes `cl_N', `cl_R', `cl_RA', `cl_F', `cl_SF', `cl_FF',
1887 `TYPE& operator += (TYPE&, const TYPE&)'
1888 `TYPE& operator -= (TYPE&, const TYPE&)'
1889 `TYPE& operator *= (TYPE&, const TYPE&)'
1890 `TYPE& operator /= (TYPE&, const TYPE&)'
1891 For the class `cl_I':
1893 `TYPE& operator += (TYPE&, const TYPE&)'
1894 `TYPE& operator -= (TYPE&, const TYPE&)'
1895 `TYPE& operator *= (TYPE&, const TYPE&)'
1896 `TYPE& operator &= (TYPE&, const TYPE&)'
1897 `TYPE& operator |= (TYPE&, const TYPE&)'
1898 `TYPE& operator ^= (TYPE&, const TYPE&)'
1899 `TYPE& operator <<= (TYPE&, const TYPE&)'
1900 `TYPE& operator >>= (TYPE&, const TYPE&)'
1901 For the classes `cl_N', `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF',
1902 `cl_FF', `cl_DF', `cl_LF':
1904 `TYPE& operator ++ (TYPE& x)'
1905 The prefix operator `++x'.
1907 `void operator ++ (TYPE& x, int)'
1908 The postfix operator `x++'.
1910 `TYPE& operator -- (TYPE& x)'
1911 The prefix operator `--x'.
1913 `void operator -- (TYPE& x, int)'
1914 The postfix operator `x--'.
1916 Note that by using these obfuscating operators, you wouldn't gain
1917 efficiency: In CLN `x += y;' is exactly the same as `x = x+y;', not
1921 File: cln.info, Node: Input/Output, Next: Rings, Prev: Functions on numbers, Up: Top
1928 * Internal and printed representation::
1930 * Output functions::
1933 File: cln.info, Node: Internal and printed representation, Next: Input functions, Prev: Input/Output, Up: Input/Output
1935 Internal and printed representation
1936 ===================================
1938 All computations deal with the internal representations of the numbers.
1940 Every number has an external representation as a sequence of ASCII
1941 characters. Several external representations may denote the same
1942 number, for example, "20.0" and "20.000".
1944 Converting an internal to an external representation is called
1945 "printing", converting an external to an internal representation is
1946 called "reading". In CLN, is it always true that conversion of an
1947 internal to an external representation and then back to an internal
1948 representation will yield the same internal representation.
1949 Symbolically: `read(print(x)) == x'. This is called "print-read
1952 Different types of numbers have different external representations (case
1956 External representation: SIGN{DIGIT}+. The reader also accepts the
1957 Common Lisp syntaxes SIGN{DIGIT}+`.' with a trailing dot for
1958 decimal integers and the `#NR', `#b', `#o', `#x' prefixes.
1961 External representation: SIGN{DIGIT}+`/'{DIGIT}+. The `#NR',
1962 `#b', `#o', `#x' prefixes are allowed here as well.
1964 Floating-point numbers
1965 External representation: SIGN{DIGIT}*EXPONENT or
1966 SIGN{DIGIT}*`.'{DIGIT}*EXPONENT or SIGN{DIGIT}*`.'{DIGIT}+. A
1967 precision specifier of the form _PREC may be appended. There must
1968 be at least one digit in the non-exponent part. The exponent has
1969 the syntax EXPMARKER EXPSIGN {DIGIT}+. The exponent marker is
1971 `s' for short-floats,
1973 `f' for single-floats,
1975 `d' for double-floats,
1977 `L' for long-floats,
1979 or `e', which denotes a default float format. The precision
1980 specifying suffix has the syntax _PREC where PREC denotes the
1981 number of valid mantissa digits (in decimal, excluding leading
1982 zeroes), cf. also function `cl_float_format'.
1985 External representation:
1986 In algebraic notation: `REALPART+IMAGPARTi'. Of course, if
1987 IMAGPART is negative, its printed representation begins with
1988 a `-', and the `+' between REALPART and IMAGPART may be
1989 omitted. Note that this notation cannot be used when the
1990 IMAGPART is rational and the rational number's base is >18,
1991 because the `i' is then read as a digit.
1993 In Common Lisp notation: `#C(REALPART IMAGPART)'.
1996 File: cln.info, Node: Input functions, Next: Output functions, Prev: Internal and printed representation, Up: Input/Output
2001 Including `<cl_io.h>' defines a type `cl_istream', which is the type of
2002 the first argument to all input functions. Unless you build and use CLN
2003 with the macro CL_IO_STDIO being defined, `cl_istream' is the same as
2007 `cl_istream cl_stdin' contains the standard input stream.
2009 These are the simple input functions:
2011 `int freadchar (cl_istream stream)'
2012 Reads a character from `stream'. Returns `cl_EOF' (not a `char'!)
2013 if the end of stream was encountered or an error occurred.
2015 `int funreadchar (cl_istream stream, int c)'
2016 Puts back `c' onto `stream'. `c' must be the result of the last
2017 `freadchar' operation on `stream'.
2019 Each of the classes `cl_N', `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF',
2020 `cl_FF', `cl_DF', `cl_LF' defines, in `<cl_TYPE_io.h>', the following
2023 `cl_istream operator>> (cl_istream stream, TYPE& result)'
2024 Reads a number from `stream' and stores it in the `result'.
2026 The most flexible input functions, defined in `<cl_TYPE_io.h>', are the
2029 `cl_N read_complex (cl_istream stream, const cl_read_flags& flags)'
2030 `cl_R read_real (cl_istream stream, const cl_read_flags& flags)'
2031 `cl_F read_float (cl_istream stream, const cl_read_flags& flags)'
2032 `cl_RA read_rational (cl_istream stream, const cl_read_flags& flags)'
2033 `cl_I read_integer (cl_istream stream, const cl_read_flags& flags)'
2034 Reads a number from `stream'. The `flags' are parameters which
2035 affect the input syntax. Whitespace before the number is silently
2038 `cl_N read_complex (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)'
2039 `cl_R read_real (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)'
2040 `cl_F read_float (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)'
2041 `cl_RA read_rational (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)'
2042 `cl_I read_integer (const cl_read_flags& flags, const char * string, const char * string_limit, const char * * end_of_parse)'
2043 Reads a number from a string in memory. The `flags' are parameters
2044 which affect the input syntax. The string starts at `string' and
2045 ends at `string_limit' (exclusive limit). `string_limit' may also
2046 be `NULL', denoting the entire string, i.e. equivalent to
2047 `string_limit = string + strlen(string)'. If `end_of_parse' is
2048 `NULL', the string in memory must contain exactly one number and
2049 nothing more, else a fatal error will be signalled. If
2050 `end_of_parse' is not `NULL', `*end_of_parse' will be assigned a
2051 pointer past the last parsed character (i.e. `string_limit' if
2052 nothing came after the number). Whitespace is not allowed.
2054 The structure `cl_read_flags' contains the following fields:
2056 `cl_read_syntax_t syntax'
2057 The possible results of the read operation. Possible values are
2058 `syntax_number', `syntax_real', `syntax_rational',
2059 `syntax_integer', `syntax_float', `syntax_sfloat',
2060 `syntax_ffloat', `syntax_dfloat', `syntax_lfloat'.
2062 `cl_read_lsyntax_t lsyntax'
2063 Specifies the language-dependent syntax variant for the read
2064 operation. Possible values are
2067 accept standard algebraic notation only, no complex numbers,
2070 accept the algebraic notation `X+Yi' for complex numbers,
2072 `lsyntax_commonlisp'
2073 accept the `#b', `#o', `#x' syntaxes for binary, octal,
2074 hexadecimal numbers, `#BASER' for rational numbers in a given
2075 base, `#c(REALPART IMAGPART)' for complex numbers,
2078 accept all of these extensions.
2080 `unsigned int rational_base'
2081 The base in which rational numbers are read.
2083 `cl_float_format_t float_flags.default_float_format'
2084 The float format used when reading floats with exponent marker `e'.
2086 `cl_float_format_t float_flags.default_lfloat_format'
2087 The float format used when reading floats with exponent marker `l'.
2089 `cl_boolean float_flags.mantissa_dependent_float_format'
2090 When this flag is true, floats specified with more digits than
2091 corresponding to the exponent marker they contain, but without
2092 _NNN suffix, will get a precision corresponding to their number of
2096 File: cln.info, Node: Output functions, Prev: Input functions, Up: Input/Output
2101 Including `<cl_io.h>' defines a type `cl_ostream', which is the type of
2102 the first argument to all output functions. Unless you build and use
2103 CLN with the macro CL_IO_STDIO being defined, `cl_ostream' is the same
2107 `cl_ostream cl_stdout' contains the standard output stream.
2110 `cl_ostream cl_stderr' contains the standard error output stream.
2112 These are the simple output functions:
2114 `void fprintchar (cl_ostream stream, char c)'
2115 Prints the character `x' literally on the `stream'.
2117 `void fprint (cl_ostream stream, const char * string)'
2118 Prints the `string' literally on the `stream'.
2120 `void fprintdecimal (cl_ostream stream, int x)'
2121 `void fprintdecimal (cl_ostream stream, const cl_I& x)'
2122 Prints the integer `x' in decimal on the `stream'.
2124 `void fprintbinary (cl_ostream stream, const cl_I& x)'
2125 Prints the integer `x' in binary (base 2, without prefix) on the
2128 `void fprintoctal (cl_ostream stream, const cl_I& x)'
2129 Prints the integer `x' in octal (base 8, without prefix) on the
2132 `void fprinthexadecimal (cl_ostream stream, const cl_I& x)'
2133 Prints the integer `x' in hexadecimal (base 16, without prefix) on
2136 Each of the classes `cl_N', `cl_R', `cl_RA', `cl_I', `cl_F', `cl_SF',
2137 `cl_FF', `cl_DF', `cl_LF' defines, in `<cl_TYPE_io.h>', the following
2140 `void fprint (cl_ostream stream, const TYPE& x)'
2141 `cl_ostream operator<< (cl_ostream stream, const TYPE& x)'
2142 Prints the number `x' on the `stream'. The output may depend on
2143 the global printer settings in the variable
2144 `cl_default_print_flags'. The `ostream' flags and settings
2145 (flags, width and locale) are ignored.
2147 The most flexible output function, defined in `<cl_TYPE_io.h>', are the
2149 void print_complex (cl_ostream stream, const cl_print_flags& flags,
2151 void print_real (cl_ostream stream, const cl_print_flags& flags,
2153 void print_float (cl_ostream stream, const cl_print_flags& flags,
2155 void print_rational (cl_ostream stream, const cl_print_flags& flags,
2157 void print_integer (cl_ostream stream, const cl_print_flags& flags,
2159 Prints the number `x' on the `stream'. The `flags' are parameters which
2162 The structure type `cl_print_flags' contains the following fields:
2164 `unsigned int rational_base'
2165 The base in which rational numbers are printed. Default is `10'.
2167 `cl_boolean rational_readably'
2168 If this flag is true, rational numbers are printed with radix
2169 specifiers in Common Lisp syntax (`#NR' or `#b' or `#o' or `#x'
2170 prefixes, trailing dot). Default is false.
2172 `cl_boolean float_readably'
2173 If this flag is true, type specific exponent markers have
2174 precedence over 'E'. Default is false.
2176 `cl_float_format_t default_float_format'
2177 Floating point numbers of this format will be printed using the
2178 'E' exponent marker. Default is `cl_float_format_ffloat'.
2180 `cl_boolean complex_readably'
2181 If this flag is true, complex numbers will be printed using the
2182 Common Lisp syntax `#C(REALPART IMAGPART)'. Default is false.
2184 `cl_string univpoly_varname'
2185 Univariate polynomials with no explicit indeterminate name will be
2186 printed using this variable name. Default is `"x"'.
2188 The global variable `cl_default_print_flags' contains the default
2189 values, used by the function `fprint',
2192 File: cln.info, Node: Rings, Next: Modular integers, Prev: Input/Output, Up: Top
2197 CLN has a class of abstract rings.
2203 Rings can be compared for equality:
2205 `bool operator== (const cl_ring&, const cl_ring&)'
2206 `bool operator!= (const cl_ring&, const cl_ring&)'
2207 These compare two rings for equality.
2209 Given a ring `R', the following members can be used.
2211 `void R->fprint (cl_ostream stream, const cl_ring_element& x)'
2212 `cl_boolean R->equal (const cl_ring_element& x, const cl_ring_element& y)'
2213 `cl_ring_element R->zero ()'
2214 `cl_boolean R->zerop (const cl_ring_element& x)'
2215 `cl_ring_element R->plus (const cl_ring_element& x, const cl_ring_element& y)'
2216 `cl_ring_element R->minus (const cl_ring_element& x, const cl_ring_element& y)'
2217 `cl_ring_element R->uminus (const cl_ring_element& x)'
2218 `cl_ring_element R->one ()'
2219 `cl_ring_element R->canonhom (const cl_I& x)'
2220 `cl_ring_element R->mul (const cl_ring_element& x, const cl_ring_element& y)'
2221 `cl_ring_element R->square (const cl_ring_element& x)'
2222 `cl_ring_element R->expt_pos (const cl_ring_element& x, const cl_I& y)'
2223 The following rings are built-in.
2225 `cl_null_ring cl_0_ring'
2226 The null ring, containing only zero.
2228 `cl_complex_ring cl_C_ring'
2229 The ring of complex numbers. This corresponds to the type `cl_N'.
2231 `cl_real_ring cl_R_ring'
2232 The ring of real numbers. This corresponds to the type `cl_R'.
2234 `cl_rational_ring cl_RA_ring'
2235 The ring of rational numbers. This corresponds to the type `cl_RA'.
2237 `cl_integer_ring cl_I_ring'
2238 The ring of integers. This corresponds to the type `cl_I'.
2240 Type tests can be performed for any of `cl_C_ring', `cl_R_ring',
2241 `cl_RA_ring', `cl_I_ring':
2243 `cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)'
2244 Tests whether the given number is an element of the number ring R.
2247 File: cln.info, Node: Modular integers, Next: Symbolic data types, Prev: Rings, Up: Top
2254 * Modular integer rings::
2255 * Functions on modular integers::
2258 File: cln.info, Node: Modular integer rings, Next: Functions on modular integers, Prev: Modular integers, Up: Modular integers
2260 Modular integer rings
2261 =====================
2263 CLN implements modular integers, i.e. integers modulo a fixed integer N.
2264 The modulus is explicitly part of every modular integer. CLN doesn't
2265 allow you to (accidentally) mix elements of different modular rings,
2266 e.g. `(3 mod 4) + (2 mod 5)' will result in a runtime error. (Ideally
2267 one would imagine a generic data type `cl_MI(N)', but C++ doesn't have
2268 generic types. So one has to live with runtime checks.)
2270 The class of modular integer rings is
2277 Modular integer ring
2281 and the class of all modular integers (elements of modular integer
2288 Modular integer rings are constructed using the function
2290 `cl_modint_ring cl_find_modint_ring (const cl_I& N)'
2291 This function returns the modular ring `Z/NZ'. It takes care of
2292 finding out about special cases of `N', like powers of two and odd
2293 numbers for which Montgomery multiplication will be a win, and
2294 precomputes any necessary auxiliary data for computing modulo `N'.
2295 There is a cache table of rings, indexed by `N' (or, more
2296 precisely, by `abs(N)'). This ensures that the precomputation
2297 costs are reduced to a minimum.
2299 Modular integer rings can be compared for equality:
2301 `bool operator== (const cl_modint_ring&, const cl_modint_ring&)'
2302 `bool operator!= (const cl_modint_ring&, const cl_modint_ring&)'
2303 These compare two modular integer rings for equality. Two
2304 different calls to `cl_find_modint_ring' with the same argument
2305 necessarily return the same ring because it is memoized in the
2309 File: cln.info, Node: Functions on modular integers, Prev: Modular integer rings, Up: Modular integers
2311 Functions on modular integers
2312 =============================
2314 Given a modular integer ring `R', the following members can be used.
2317 This is the ring's modulus, normalized to be nonnegative: `abs(N)'.
2320 This returns `0 mod N'.
2323 This returns `1 mod N'.
2325 `cl_MI R->canonhom (const cl_I& x)'
2326 This returns `x mod N'.
2328 `cl_I R->retract (const cl_MI& x)'
2329 This is a partial inverse function to `R->canonhom'. It returns the
2330 standard representative (`>=0', `<N') of `x'.
2332 `cl_MI R->random(cl_random_state& randomstate)'
2334 This returns a random integer modulo `N'.
2336 The following operations are defined on modular integers.
2338 `cl_modint_ring x.ring ()'
2339 Returns the ring to which the modular integer `x' belongs.
2341 `cl_MI operator+ (const cl_MI&, const cl_MI&)'
2342 Returns the sum of two modular integers. One of the arguments may
2343 also be a plain integer.
2345 `cl_MI operator- (const cl_MI&, const cl_MI&)'
2346 Returns the difference of two modular integers. One of the
2347 arguments may also be a plain integer.
2349 `cl_MI operator- (const cl_MI&)'
2350 Returns the negative of a modular integer.
2352 `cl_MI operator* (const cl_MI&, const cl_MI&)'
2353 Returns the product of two modular integers. One of the arguments
2354 may also be a plain integer.
2356 `cl_MI square (const cl_MI&)'
2357 Returns the square of a modular integer.
2359 `cl_MI recip (const cl_MI& x)'
2360 Returns the reciprocal `x^-1' of a modular integer `x'. `x' must
2361 be coprime to the modulus, otherwise an error message is issued.
2363 `cl_MI div (const cl_MI& x, const cl_MI& y)'
2364 Returns the quotient `x*y^-1' of two modular integers `x', `y'.
2365 `y' must be coprime to the modulus, otherwise an error message is
2368 `cl_MI expt_pos (const cl_MI& x, const cl_I& y)'
2369 `y' must be > 0. Returns `x^y'.
2371 `cl_MI expt (const cl_MI& x, const cl_I& y)'
2372 Returns `x^y'. If `y' is negative, `x' must be coprime to the
2373 modulus, else an error message is issued.
2375 `cl_MI operator<< (const cl_MI& x, const cl_I& y)'
2378 `cl_MI operator>> (const cl_MI& x, const cl_I& y)'
2379 Returns `x*2^-y'. When `y' is positive, the modulus must be odd,
2380 or an error message is issued.
2382 `bool operator== (const cl_MI&, const cl_MI&)'
2383 `bool operator!= (const cl_MI&, const cl_MI&)'
2384 Compares two modular integers, belonging to the same modular
2385 integer ring, for equality.
2387 `cl_boolean zerop (const cl_MI& x)'
2388 Returns true if `x' is `0 mod N'.
2390 The following output functions are defined (see also the chapter on
2393 `void fprint (cl_ostream stream, const cl_MI& x)'
2394 `cl_ostream operator<< (cl_ostream stream, const cl_MI& x)'
2395 Prints the modular integer `x' on the `stream'. The output may
2396 depend on the global printer settings in the variable
2397 `cl_default_print_flags'.
2400 File: cln.info, Node: Symbolic data types, Next: Univariate polynomials, Prev: Modular integers, Up: Top
2405 CLN implements two symbolic (non-numeric) data types: strings and
2414 File: cln.info, Node: Strings, Next: Symbols, Prev: Symbolic data types, Up: Symbolic data types
2425 implements immutable strings.
2427 Strings are constructed through the following constructors:
2429 `cl_string (const char * s)'
2430 Returns an immutable copy of the (zero-terminated) C string `s'.
2432 `cl_string (const char * ptr, unsigned long len)'
2433 Returns an immutable copy of the `len' characters at `ptr[0]',
2434 ..., `ptr[len-1]'. NUL characters are allowed.
2436 The following functions are available on strings:
2439 Assignment from `cl_string' and `const char *'.
2443 Returns the length of the string `s'.
2446 Returns the `i'th character of the string `s'. `i' must be in the
2447 range `0 <= i < s.length()'.
2449 `bool equal (const cl_string& s1, const cl_string& s2)'
2450 Compares two strings for equality. One of the arguments may also
2451 be a plain `const char *'.
2454 File: cln.info, Node: Symbols, Prev: Strings, Up: Symbolic data types
2459 Symbols are uniquified strings: all symbols with the same name are
2460 shared. This means that comparison of two symbols is fast (effectively
2461 just a pointer comparison), whereas comparison of two strings must in
2462 the worst case walk both strings until their end. Symbols are used,
2463 for example, as tags for properties, as names of variables in
2464 polynomial rings, etc.
2466 Symbols are constructed through the following constructor:
2468 `cl_symbol (const cl_string& s)'
2469 Looks up or creates a new symbol with a given name.
2471 The following operations are available on symbols:
2473 `cl_string (const cl_symbol& sym)'
2474 Conversion to `cl_string': Returns the string which names the
2477 `bool equal (const cl_symbol& sym1, const cl_symbol& sym2)'
2478 Compares two symbols for equality. This is very fast.
2481 File: cln.info, Node: Univariate polynomials, Next: Internals, Prev: Symbolic data types, Up: Top
2483 Univariate polynomials
2484 **********************
2488 * Univariate polynomial rings::
2489 * Functions on univariate polynomials::
2490 * Special polynomials::
2493 File: cln.info, Node: Univariate polynomial rings, Next: Functions on univariate polynomials, Prev: Univariate polynomials, Up: Univariate polynomials
2495 Univariate polynomial rings
2496 ===========================
2498 CLN implements univariate polynomials (polynomials in one variable)
2499 over an arbitrary ring. The indeterminate variable may be either
2500 unnamed (and will be printed according to
2501 `cl_default_print_flags.univpoly_varname', which defaults to `x') or
2502 carry a given name. The base ring and the indeterminate are explicitly
2503 part of every polynomial. CLN doesn't allow you to (accidentally) mix
2504 elements of different polynomial rings, e.g. `(a^2+1) * (b^3-1)' will
2505 result in a runtime error. (Ideally this should return a multivariate
2506 polynomial, but they are not yet implemented in CLN.)
2508 The classes of univariate polynomial rings are
2515 Univariate polynomial ring
2519 +----------------+-------------------+
2521 Complex polynomial ring | Modular integer polynomial ring
2522 cl_univpoly_complex_ring | cl_univpoly_modint_ring
2523 <cl_univpoly_complex.h> | <cl_univpoly_modint.h>
2527 Real polynomial ring |
2528 cl_univpoly_real_ring |
2529 <cl_univpoly_real.h> |
2533 Rational polynomial ring |
2534 cl_univpoly_rational_ring |
2535 <cl_univpoly_rational.h> |
2539 Integer polynomial ring
2540 cl_univpoly_integer_ring
2541 <cl_univpoly_integer.h>
2543 and the corresponding classes of univariate polynomials are
2545 Univariate polynomial
2549 +----------------+-------------------+
2551 Complex polynomial | Modular integer polynomial
2553 <cl_univpoly_complex.h> | <cl_univpoly_modint.h>
2559 <cl_univpoly_real.h> |
2563 Rational polynomial |
2565 <cl_univpoly_rational.h> |
2571 <cl_univpoly_integer.h>
2573 Univariate polynomial rings are constructed using the functions
2575 `cl_univpoly_ring cl_find_univpoly_ring (const cl_ring& R)'
2576 `cl_univpoly_ring cl_find_univpoly_ring (const cl_ring& R, const cl_symbol& varname)'
2577 This function returns the polynomial ring `R[X]', unnamed or named.
2578 `R' may be an arbitrary ring. This function takes care of finding
2579 out about special cases of `R', such as the rings of complex
2580 numbers, real numbers, rational numbers, integers, or modular
2581 integer rings. There is a cache table of rings, indexed by `R'
2582 and `varname'. This ensures that two calls of this function with
2583 the same arguments will return the same polynomial ring.
2585 `cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring& R)'
2586 `cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring& R, const cl_symbol& varname)'
2587 `cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring& R)'
2588 `cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring& R, const cl_symbol& varname)'
2589 `cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring& R)'
2590 `cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring& R, const cl_symbol& varname)'
2591 `cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring& R)'
2592 `cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring& R, const cl_symbol& varname)'
2593 `cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring& R)'
2594 `cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring& R, const cl_symbol& varname)'
2595 These functions are equivalent to the general
2596 `cl_find_univpoly_ring', only the return type is more specific,
2597 according to the base ring's type.
2600 File: cln.info, Node: Functions on univariate polynomials, Next: Special polynomials, Prev: Univariate polynomial rings, Up: Univariate polynomials
2602 Functions on univariate polynomials
2603 ===================================
2605 Given a univariate polynomial ring `R', the following members can be
2608 `cl_ring R->basering()'
2609 This returns the base ring, as passed to `cl_find_univpoly_ring'.
2612 This returns `0 in R', a polynomial of degree -1.
2615 This returns `1 in R', a polynomial of degree <= 0.
2617 `cl_UP R->canonhom (const cl_I& x)'
2618 This returns `x in R', a polynomial of degree <= 0.
2620 `cl_UP R->monomial (const cl_ring_element& x, uintL e)'
2621 This returns a sparse polynomial: `x * X^e', where `X' is the
2624 `cl_UP R->create (sintL degree)'
2625 Creates a new polynomial with a given degree. The zero polynomial
2626 has degree `-1'. After creating the polynomial, you should put in
2627 the coefficients, using the `set_coeff' member function, and then
2628 call the `finalize' member function.
2630 The following are the only destructive operations on univariate
2633 `void set_coeff (cl_UP& x, uintL index, const cl_ring_element& y)'
2634 This changes the coefficient of `X^index' in `x' to be `y'. After
2635 changing a polynomial and before applying any "normal" operation
2636 on it, you should call its `finalize' member function.
2638 `void finalize (cl_UP& x)'
2639 This function marks the endpoint of destructive modifications of a
2640 polynomial. It normalizes the internal representation so that
2641 subsequent computations have less overhead. Doing normal
2642 computations on unnormalized polynomials may produce wrong results
2643 or crash the program.
2645 The following operations are defined on univariate polynomials.
2647 `cl_univpoly_ring x.ring ()'
2648 Returns the ring to which the univariate polynomial `x' belongs.
2650 `cl_UP operator+ (const cl_UP&, const cl_UP&)'
2651 Returns the sum of two univariate polynomials.
2653 `cl_UP operator- (const cl_UP&, const cl_UP&)'
2654 Returns the difference of two univariate polynomials.
2656 `cl_UP operator- (const cl_UP&)'
2657 Returns the negative of a univariate polynomial.
2659 `cl_UP operator* (const cl_UP&, const cl_UP&)'
2660 Returns the product of two univariate polynomials. One of the
2661 arguments may also be a plain integer or an element of the base
2664 `cl_UP square (const cl_UP&)'
2665 Returns the square of a univariate polynomial.
2667 `cl_UP expt_pos (const cl_UP& x, const cl_I& y)'
2668 `y' must be > 0. Returns `x^y'.
2670 `bool operator== (const cl_UP&, const cl_UP&)'
2671 `bool operator!= (const cl_UP&, const cl_UP&)'
2672 Compares two univariate polynomials, belonging to the same
2673 univariate polynomial ring, for equality.
2675 `cl_boolean zerop (const cl_UP& x)'
2676 Returns true if `x' is `0 in R'.
2678 `sintL degree (const cl_UP& x)'
2679 Returns the degree of the polynomial. The zero polynomial has
2682 `cl_ring_element coeff (const cl_UP& x, uintL index)'
2683 Returns the coefficient of `X^index' in the polynomial `x'.
2685 `cl_ring_element x (const cl_ring_element& y)'
2686 Evaluation: If `x' is a polynomial and `y' belongs to the base
2687 ring, then `x(y)' returns the value of the substitution of `y' into
2690 `cl_UP deriv (const cl_UP& x)'
2691 Returns the derivative of the polynomial `x' with respect to the
2694 The following output functions are defined (see also the chapter on
2697 `void fprint (cl_ostream stream, const cl_UP& x)'
2698 `cl_ostream operator<< (cl_ostream stream, const cl_UP& x)'
2699 Prints the univariate polynomial `x' on the `stream'. The output
2700 may depend on the global printer settings in the variable
2701 `cl_default_print_flags'.
2704 File: cln.info, Node: Special polynomials, Prev: Functions on univariate polynomials, Up: Univariate polynomials
2709 The following functions return special polynomials.
2711 `cl_UP_I cl_tschebychev (sintL n)'
2712 Returns the n-th Tchebychev polynomial (n >= 0).
2714 `cl_UP_I cl_hermite (sintL n)'
2715 Returns the n-th Hermite polynomial (n >= 0).
2717 `cl_UP_RA cl_legendre (sintL n)'
2718 Returns the n-th Legendre polynomial (n >= 0).
2720 `cl_UP_I cl_laguerre (sintL n)'
2721 Returns the n-th Laguerre polynomial (n >= 0).
2723 Information how to derive the differential equation satisfied by each
2724 of these polynomials from their definition can be found in the
2725 `doc/polynomial/' directory.
2728 File: cln.info, Node: Internals, Next: Using the library, Prev: Univariate polynomials, Up: Top
2736 * Memory efficiency::
2737 * Speed efficiency::
2738 * Garbage collection::
2741 File: cln.info, Node: Why C++ ?, Next: Memory efficiency, Prev: Internals, Up: Internals
2746 Using C++ as an implementation language provides
2748 * Efficiency: It compiles to machine code.
2750 * Portability: It runs on all platforms supporting a C++ compiler.
2751 Because of the availability of GNU C++, this includes all
2752 currently used 32-bit and 64-bit platforms, independently of the
2753 quality of the vendor's C++ compiler.
2755 * Type safety: The C++ compilers knows about the number types and
2756 complains if, for example, you try to assign a float to an integer
2757 variable. However, a drawback is that C++ doesn't know about
2758 generic types, hence a restriction like that `operation+ (const
2759 cl_MI&, const cl_MI&)' requires that both arguments belong to the
2760 same modular ring cannot be expressed as a compile-time
2763 * Algebraic syntax: The elementary operations `+', `-', `*', `=',
2764 `==', ... can be used in infix notation, which is more convenient
2765 than Lisp notation `(+ x y)' or C notation `add(x,y,&z)'.
2767 With these language features, there is no need for two separate
2768 languages, one for the implementation of the library and one in which
2769 the library's users can program. This means that a prototype
2770 implementation of an algorithm can be integrated into the library
2771 immediately after it has been tested and debugged. No need to rewrite
2772 it in a low-level language after having prototyped in a high-level
2776 File: cln.info, Node: Memory efficiency, Next: Speed efficiency, Prev: Why C++ ?, Up: Internals
2781 In order to save memory allocations, CLN implements:
2783 * Object sharing: An operation like `x+0' returns `x' without copying
2786 * Garbage collection: A reference counting mechanism makes sure that
2787 any number object's storage is freed immediately when the last
2788 reference to the object is gone.
2790 * Small integers are represented as immediate values instead of
2791 pointers to heap allocated storage. This means that integers `>
2792 -2^29', `< 2^29' don't consume heap memory, unless they were
2793 explicitly allocated on the heap.
2796 File: cln.info, Node: Speed efficiency, Next: Garbage collection, Prev: Memory efficiency, Up: Internals
2801 Speed efficiency is obtained by the combination of the following tricks
2804 * Small integers, being represented as immediate values, don't
2805 require memory access, just a couple of instructions for each
2806 elementary operation.
2808 * The kernel of CLN has been written in assembly language for some
2809 CPUs (`i386', `m68k', `sparc', `mips', `arm').
2811 * On all CPUs, CLN uses the superefficient low-level routines from
2814 * For large numbers, CLN uses, instead of the standard `O(N^2)'
2815 algorithm, the Karatsuba multiplication, which is an `O(N^1.6)'
2818 * For very large numbers (more than 12000 decimal digits), CLN uses
2819 Schönhage-Strassen multiplication, which is an asymptotically
2820 optimal multiplication algorithm.
2822 * These fast multiplication algorithms also give improvements in the
2823 speed of division and radix conversion.
2826 File: cln.info, Node: Garbage collection, Prev: Speed efficiency, Up: Internals
2831 All the number classes are reference count classes: They only contain a
2832 pointer to an object in the heap. Upon construction, assignment and
2833 destruction of number objects, only the objects' reference count are
2836 Memory occupied by number objects are automatically reclaimed as soon as
2837 their reference count drops to zero.
2839 For number rings, another strategy is implemented: There is a cache of,
2840 for example, the modular integer rings. A modular integer ring is
2841 destroyed only if its reference count dropped to zero and the cache is
2842 about to be resized. The effect of this strategy is that recently used
2843 rings remain cached, whereas undue memory consumption through cached
2847 File: cln.info, Node: Using the library, Next: Customizing, Prev: Internals, Up: Top
2852 For the following discussion, we will assume that you have installed
2853 the CLN source in `$CLN_DIR' and built it in `$CLN_TARGETDIR'. For
2854 example, for me it's `CLN_DIR="$HOME/cln"' and
2855 `CLN_TARGETDIR="$HOME/cln/linuxelf"'. You might define these as
2856 environment variables, or directly substitute the appropriate values.
2860 * Compiler options::
2863 * Debugging support::
2866 File: cln.info, Node: Compiler options, Next: Include files, Prev: Using the library, Up: Using the library
2871 Until you have installed CLN in a public place, the following options
2874 When you compile CLN application code, add the flags
2875 -I$CLN_DIR/include -I$CLN_TARGETDIR/include
2876 to the C++ compiler's command line (`make' variable CFLAGS or CXXFLAGS).
2877 When you link CLN application code to form an executable, add the flags
2878 $CLN_TARGETDIR/src/libcln.a
2879 to the C/C++ compiler's command line (`make' variable LIBS).
2881 If you did a `make install', the include files are installed in a
2882 public directory (normally `/usr/local/include'), hence you don't need
2883 special flags for compiling. The library has been installed to a public
2884 directory as well (normally `/usr/local/lib'), hence when linking a CLN
2885 application it is sufficient to give the flag `-lcln'.
2888 File: cln.info, Node: Include files, Next: An Example, Prev: Compiler options, Up: Using the library
2893 Here is a summary of the include files and their contents.
2896 General definitions, reference counting, garbage collection.
2899 The class cl_number.
2902 Functions for class cl_N, the complex numbers.
2905 Functions for class cl_R, the real numbers.
2908 Functions for class cl_F, the floats.
2911 Functions for class cl_SF, the short-floats.
2914 Functions for class cl_FF, the single-floats.
2917 Functions for class cl_DF, the double-floats.
2920 Functions for class cl_LF, the long-floats.
2923 Functions for class cl_RA, the rational numbers.
2926 Functions for class cl_I, the integers.
2932 Input/Output for class cl_N, the complex numbers.
2935 Input/Output for class cl_R, the real numbers.
2938 Input/Output for class cl_F, the floats.
2941 Input/Output for class cl_SF, the short-floats.
2944 Input/Output for class cl_FF, the single-floats.
2947 Input/Output for class cl_DF, the double-floats.
2950 Input/Output for class cl_LF, the long-floats.
2952 `<cl_rational_io.h>'
2953 Input/Output for class cl_RA, the rational numbers.
2956 Input/Output for class cl_I, the integers.
2959 Flags for customizing input operations.
2962 Flags for customizing output operations.
2965 `cl_malloc_hook', `cl_free_hook'.
2971 Conditions/exceptions.
2988 `<cl_complex_ring.h>'
2989 The ring of complex numbers.
2992 The ring of real numbers.
2994 `<cl_rational_ring.h>'
2995 The ring of rational numbers.
2997 `<cl_integer_ring.h>'
2998 The ring of integers.
3001 Number threory functions.
3013 General vectors over cl_number.
3016 General vectors over cl_N.
3019 General vectors over cl_R.
3021 `<cl_GV_rational.h>'
3022 General vectors over cl_RA.
3025 General vectors over cl_I.
3027 `<cl_GV_modinteger.h>'
3028 General vectors of modular integers.
3034 Simple vectors over cl_number.
3037 Simple vectors over cl_N.
3040 Simple vectors over cl_R.
3042 `<cl_SV_rational.h>'
3043 Simple vectors over cl_RA.
3046 Simple vectors over cl_I.
3049 Simple vectors of general ring elements.
3052 Univariate polynomials.
3054 `<cl_univpoly_integer.h>'
3055 Univariate polynomials over the integers.
3057 `<cl_univpoly_rational.h>'
3058 Univariate polynomials over the rational numbers.
3060 `<cl_univpoly_real.h>'
3061 Univariate polynomials over the real numbers.
3063 `<cl_univpoly_complex.h>'
3064 Univariate polynomials over the complex numbers.
3066 `<cl_univpoly_modint.h>'
3067 Univariate polynomials over modular integer rings.
3073 Includes all of the above.
3076 File: cln.info, Node: An Example, Next: Debugging support, Prev: Include files, Up: Using the library
3081 A function which computes the nth Fibonacci number can be written as
3084 #include <cl_integer.h>
3085 #include <cl_real.h>
3087 // Returns F_n, computed as the nearest integer to
3088 // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0.
3089 const cl_I fibonacci (int n)
3091 // Need a precision of ((1+sqrt(5))/2)^-n.
3092 cl_float_format_t prec = cl_float_format((int)(0.208987641*n+5));
3093 cl_R sqrt5 = sqrt(cl_float(5,prec));
3094 cl_R phi = (1+sqrt5)/2;
3095 return round1( expt(phi,n)/sqrt5 );
3098 Let's explain what is going on in detail.
3100 The include file `<cl_integer.h>' is necessary because the type `cl_I'
3101 is used in the function, and the include file `<cl_real.h>' is needed
3102 for the type `cl_R' and the floating point number functions. The order
3103 of the include files does not matter.
3105 Then comes the function declaration. The argument is an `int', the
3106 result an integer. The return type is defined as `const cl_I', not
3107 simply `cl_I', because that allows the compiler to detect typos like
3108 `fibonacci(n) = 100'. It would be possible to declare the return type
3109 as `const cl_R' (real number) or even `const cl_N' (complex number). We
3110 use the most specialized possible return type because functions which
3111 call `fibonacci' will be able to profit from the compiler's type
3112 analysis: Adding two integers is slightly more efficient than adding the
3113 same objects declared as complex numbers, because it needs less type
3114 dispatch. Also, when linking to CLN as a non-shared library, this
3115 minimizes the size of the resulting executable program.
3117 The result will be computed as expt(phi,n)/sqrt(5), rounded to the
3118 nearest integer. In order to get a correct result, the absolute error
3119 should be less than 1/2, i.e. the relative error should be less than
3120 sqrt(5)/(2*expt(phi,n)). To this end, the first line computes a
3121 floating point precision for sqrt(5) and phi.
3123 Then sqrt(5) is computed by first converting the integer 5 to a
3124 floating point number and than taking the square root. The converse,
3125 first taking the square root of 5, and then converting to the desired
3126 precision, would not work in CLN: The square root would be computed to
3127 a default precision (normally single-float precision), and the
3128 following conversion could not help about the lacking accuracy. This is
3129 because CLN is not a symbolic computer algebra system and does not
3130 represent sqrt(5) in a non-numeric way.
3132 The type `cl_R' for sqrt5 and, in the following line, phi is the only
3133 possible choice. You cannot write `cl_F' because the C++ compiler can
3134 only infer that `cl_float(5,prec)' is a real number. You cannot write
3135 `cl_N' because a `round1' does not exist for general complex numbers.
3137 When the function returns, all the local variables in the function are
3138 automatically reclaimed (garbage collected). Only the result survives
3139 and gets passed to the caller.
3142 File: cln.info, Node: Debugging support, Prev: An Example, Up: Using the library
3147 When debugging a CLN application with GNU `gdb', two facilities are
3148 available from the library:
3150 * The library does type checks, range checks, consistency checks at
3151 many places. When one of these fails, the function `cl_abort()' is
3152 called. Its default implementation is to perform an `exit(1)', so
3153 you won't have a core dump. But for debugging, it is best to set a
3154 breakpoint at this function:
3155 (gdb) break cl_abort
3156 When this breakpoint is hit, look at the stack's backtrace:
3159 * The debugger's normal `print' command doesn't know about CLN's
3160 types and therefore prints mostly useless hexadecimal addresses.
3161 CLN offers a function `cl_print', callable from the debugger, for
3162 printing number objects. In order to get this function, you have
3163 to define the macro `CL_DEBUG' and then include all the header
3164 files for which you want `cl_print' debugging support. For example:
3166 #include <cl_string.h>
3167 Now, if you have in your program a variable `cl_string s', and
3168 inspect it under `gdb', the output may look like this:
3170 $7 = {<cl_gcpointer> = { = {pointer = 0x8055b60, heappointer = 0x8055b60,
3171 word = 134568800}}, }
3172 (gdb) call cl_print(s)
3175 Note that the output of `cl_print' goes to the program's error
3176 output, not to gdb's standard output.
3178 Note, however, that the above facility does not work with all CLN
3179 types, only with number objects and similar. Therefore CLN offers
3180 a member function `debug_print()' on all CLN types. The same macro
3181 `CL_DEBUG' is needed for this member function to be implemented.
3182 Under `gdb', you call it like this:
3184 $7 = {<cl_gcpointer> = { = {pointer = 0x8055b60, heappointer = 0x8055b60,
3185 word = 134568800}}, }
3186 (gdb) call s.debug_print()
3189 >call ($1).debug_print()
3193 Unfortunately, this feature does not seem to work under all
3197 File: cln.info, Node: Customizing, Next: Index, Prev: Using the library, Up: Top
3205 * Floating-point underflow::
3207 * Customizing the memory allocator::
3210 File: cln.info, Node: Error handling, Next: Floating-point underflow, Prev: Customizing, Up: Customizing
3215 When a fatal error occurs, an error message is output to the standard
3216 error output stream, and the function `cl_abort' is called. The default
3217 version of this function (provided in the library) terminates the
3218 application. To catch such a fatal error, you need to define the
3219 function `cl_abort' yourself, with the prototype
3220 #include <cl_abort.h>
3221 void cl_abort (void);
3222 This function must not return control to its caller.
3225 File: cln.info, Node: Floating-point underflow, Next: Customizing I/O, Prev: Error handling, Up: Customizing
3227 Floating-point underflow
3228 ========================
3230 Floating point underflow denotes the situation when a floating-point
3231 number is to be created which is so close to `0' that its exponent is
3232 too low to be represented internally. By default, this causes a fatal
3233 error. If you set the global variable
3234 cl_boolean cl_inhibit_floating_point_underflow
3235 to `cl_true', the error will be inhibited, and a floating-point zero
3236 will be generated instead. The default value of
3237 `cl_inhibit_floating_point_underflow' is `cl_false'.
3240 File: cln.info, Node: Customizing I/O, Next: Customizing the memory allocator, Prev: Floating-point underflow, Up: Customizing
3245 The output of the function `fprint' may be customized by changing the
3246 value of the global variable `cl_default_print_flags'.
3249 File: cln.info, Node: Customizing the memory allocator, Prev: Customizing I/O, Up: Customizing
3251 Customizing the memory allocator
3252 ================================
3254 Every memory allocation of CLN is done through the function pointer
3255 `cl_malloc_hook'. Freeing of this memory is done through the function
3256 pointer `cl_free_hook'. The default versions of these functions,
3257 provided in the library, call `malloc' and `free' and check the
3258 `malloc' result against `NULL'. If you want to provide another memory
3259 allocator, you need to define the variables `cl_malloc_hook' and
3260 `cl_free_hook' yourself, like this:
3261 #include <cl_malloc.h>
3262 void* (*cl_malloc_hook) (size_t size) = ...;
3263 void (*cl_free_hook) (void* ptr) = ...;
3264 The `cl_malloc_hook' function must not return a `NULL' pointer.
3266 It is not possible to change the memory allocator at runtime, because
3267 it is already called at program startup by the constructors of some
3271 File: cln.info, Node: Index, Prev: Customizing, Up: Top
3281 Node: Introduction
\7f3124
3282 Node: Installation
\7f5626
3283 Node: Prerequisites
\7f5920
3284 Node: C++ compiler
\7f6118
3285 Node: Make utility
\7f6833
3286 Node: Sed utility
\7f7019
3287 Node: Building the library
\7f7339
3288 Node: Installing the library
\7f10650
3289 Node: Cleaning up
\7f11373
3290 Node: Ordinary number types
\7f11698
3291 Node: Exact numbers
\7f14045
3292 Node: Floating-point numbers
\7f15210
3293 Node: Complex numbers
\7f18789
3294 Node: Conversions
\7f19286
3295 Node: Functions on numbers
\7f22752
3296 Node: Constructing numbers
\7f23455
3297 Node: Constructing integers
\7f23827
3298 Node: Constructing rational numbers
\7f24117
3299 Node: Constructing floating-point numbers
\7f24592
3300 Node: Constructing complex numbers
\7f25712
3301 Node: Elementary functions
\7f26076
3302 Node: Elementary rational functions
\7f28543
3303 Node: Elementary complex functions
\7f29115
3304 Node: Comparisons
\7f29943
3305 Node: Rounding functions
\7f31842
3307 Node: Transcendental functions
\7f39500
3308 Node: Exponential and logarithmic functions
\7f40056
3309 Node: Trigonometric functions
\7f42073
3310 Node: Hyperbolic functions
\7f45416
3311 Node: Euler gamma
\7f47489
3312 Node: Riemann zeta
\7f48405
3313 Node: Functions on integers
\7f48961
3314 Node: Logical functions
\7f49249
3315 Node: Number theoretic functions
\7f55202
3316 Node: Combinatorial functions
\7f56569
3317 Node: Functions on floating-point numbers
\7f57247
3318 Node: Conversion functions
\7f60478
3319 Node: Conversion to floating-point numbers
\7f60758
3320 Node: Conversion to rational numbers
\7f62981
3321 Node: Random number generators
\7f64035
3322 Node: Obfuscating operators
\7f65709
3323 Node: Input/Output
\7f67439
3324 Node: Internal and printed representation
\7f67649
3325 Node: Input functions
\7f70191
3326 Node: Output functions
\7f74742
3328 Node: Modular integers
\7f80402
3329 Node: Modular integer rings
\7f80602
3330 Node: Functions on modular integers
\7f82692
3331 Node: Symbolic data types
\7f85702
3332 Node: Strings
\7f85965
3333 Node: Symbols
\7f87030
3334 Node: Univariate polynomials
\7f87932
3335 Node: Univariate polynomial rings
\7f88190
3336 Node: Functions on univariate polynomials
\7f93144
3337 Node: Special polynomials
\7f96925
3338 Node: Internals
\7f97645
3339 Node: Why C++ ?
\7f97859
3340 Node: Memory efficiency
\7f99360
3341 Node: Speed efficiency
\7f100058
3342 Node: Garbage collection
\7f101122
3343 Node: Using the library
\7f101949
3344 Node: Compiler options
\7f102483
3345 Node: Include files
\7f103401
3346 Node: An Example
\7f107042
3347 Node: Debugging support
\7f110067
3348 Node: Customizing
\7f112417
3349 Node: Error handling
\7f112645
3350 Node: Floating-point underflow
\7f113219
3351 Node: Customizing I/O
\7f113858
3352 Node: Customizing the memory allocator
\7f114151
3353 Node: Index
\7f115108