PIOLOGIE
Manual
An Exact Arithmetic Library in C++
Version 1.3
December 13, 1999
Copyright © 1996-2000 by HiPiLib
Contents
1 Introduction
2 Trademarks Used in this Manual
3 License
3.1 Warranty
3.2 Single User
License
3.3 Server License
4 Quality
5 Editions
5.1 Demo Edition
5.2 Scientific
Edition
5.3 Professional
Edition
5.4 Enterprise
Edition
6 Build the PIOLOGIE
Library
6.1 Registration
Key
6.2 Supported
Processors
6.3 Supported
Compilers
6.4 Supported
Operating Systems
6.5 Compiler
Flags
7 Contact
7.1 Getting the
Latest Version
7.2 Reporting
Bugs
8 PIOLOGIE Revision
History
9 Natural Numbers: Natural(natural.h)
9.1 Basic Operations
9.1.1
Constructors
9.1.2
Assignments
9.2 Arithmetical
Operations
9.2.1
Addition (both arguments of the same type)
9.2.2
Addition (mixed mode expression)
9.2.3
Subtraction (both arguments of the same type)
9.2.4
Subtraction (mixed mode expression)
9.2.5
Multiplication (both arguments of the same type)
9.2.6
Multiplication (mixed mode expression)
9.2.7
Division (both arguments of the same type)
9.2.8
Division (mixed mode expression)
9.3 Bit Operations
9.3.1
Shifting
9.3.2
Both arguments of the same type
9.3.3
Mixed mode expression
9.4 Comparisons
9.4.1
Both arguments of the same type
9.4.2
Mixed mode expression
9.5 Input/Output
9.5.1
Decimal
9.5.2
Internal Representation
9.6 Functions
9.6.1
Basic Functions
9.6.2
Absolute Value Functions
9.6.3
Division Functions
9.6.4
Exponentiation Functions
9.6.5
Root Functions
9.6.6
Logarithmical Functions
9.6.7
Bit Manipulation Functions
9.6.8
Random Numbers
9.6.9
Conversions
9.6.10
Greatest Common Divisor
10 Integers: Integer(integer.h)
10.1 Basic Operations
10.1.1
Constructors
10.1.2
Assignments
10.2 Arithmetical
Operations
10.2.1
Addition (both arguments of the same type
10.2.2
Addition (mixed mode expression
10.2.3
Subtraction (both arguments of the same type)
10.2.4
Subtraction (mixed mode expression)
10.2.5
Multiplication (both arguments of the same type)
10.2.6
Multiplication (mixed mode expression)
10.2.7
Division (both arguments of the same type)
10.2.8
Division (mixed mode expression)
10.3 Bit Operations
10.3.1
Shifting
10.3.2
Both arguments of the same type
10.3.3
Mixed mode expression
10.4 Comparisons
10.4.1
Both arguments of the same type
10.4.2
Mixed mode expression
10.5 Input/Output
10.5.1
Decimal
10.5.2
Internal Representation
10.6 Functions
10.6.1
Basic Functions
10.6.2
Absolute Value Functions
10.6.3
Division Functions
10.6.4
Exponentiation Functions
10.6.5
Root Functions
10.6.6
Logarithmical Functions
10.6.7
Bit Manipulation Functions
10.6.8
Random Numbers
10.6.9
Conversions
10.6.10
Greatest Common Divisor
11 Rational Numbers: Rational(rational.h)
11.1 Basic Operations
11.1.1
Constructors
11.1.2
Selectors
11.1.3
Assignments
11.2 Arithmetical
Operations
11.2.1
Addition (both arguments of the same type
11.2.2
Subtraction (both arguments of the same type)
11.2.3
Multiplication (both arguments of the same type)
11.2.4
Division (both arguments of the same type)
11.3 Bit Operations
11.3.1
Shifting
11.4 Comparisons
11.4.1
Both arguments of the same type
11.4.2
Mixed mode expression
11.5 Input/Output
11.5.1
Decimal
11.5.2
Internal Representation
11.6 Functions
11.6.1
Basic Functions
11.6.2
Absolute Value Functions
11.6.3
Inversion Function
11.6.4
Exponentiation Functions
11.6.5
Integer Functions
11.6.6
Random Numbers
11.6.7
Conversions
12 Modular Arithmetic (modulo.h)
12.1 Exponentiation
12.2 Modular
Inverse
12.3 Modular
Square Root
12.4 Chinese
Remainder Theorem
13 Number Theory (nmbrthry.h)
13.1 Combinatorics
13.2 Fibonacci
Numbers
13.3 Primes
13.3.1
Constructor
13.3.2
Functions
13.4 Primality
Tests
13.5 Factorization
13.6 Number-Theoretic
Functions
13.7 Pell's
Equation
13.8 Jacobi
Symbol
14 Mathematical Constants (pi.h)
14.1 p
14.2 Öa
14.3 z(3)
14.4 exp(1)
14.5 ln(a)
14.6 g
15 Optimization
1 Introduction
PIOLOGIE is a
highly optimized C++ library for arbitrary precision arithmetic,
operating on natural, integer and rational numbers. The efficiency of the
algorithms in theory and practice and the implementation in ANSI-C++
according to newest knowledge are the fundamental features of this library.
Moreover the arithmetic is portable on all systems and independent of all
compilers, because it uses only one basic type, so that programs could
be written in a high-level language versus assembler without significant
loss of speed. The library is easy to use, because it uses overloading
mechanism of C++ and allows to write expressions in a conventional
mathematical form and does not require complex usage scenarios.
We do not support functions for arithmetical operations. We use a template
technique to hand over the arguments to the next operation. This template
technique does not use unnecessary copying, allocating and freeing of memory
and is as fast as simple function callings.
Additionally, as further advantage, special operator-combinations can
be optimized internally. For more details concerning this point see section
15.
The PIOLOGIE
package contains
-
Arithmetical operations (+, -, *, /, %, +=, etc.)
-
Bit operations (<<, >>, &, |, ^, <<=, etc.)
-
Comparisons (==, !=, <, >, <=, >=)
-
Input/Output streams
-
Functions: absolute value, division, exponentiation, root calculations,
random number generation, radix conversion, etc.
It compiles to machine code.
The major algorithmical improvements of PIOLOGIE
are
-
It can be used as a 8, 16, 32 and 64 bit based arithmetic, i.e. it is flexible
and portable for every known processor.
-
There is no limit for the size of numbers till 68,719,476,736 bits for
a 32 bit based arithmetic.
-
Every inner loop are carefully optimized for every size of numbers, e.g.
the inner loop of the addition algorithm was detailed analysed on many
compilers and processors with the result that the C++ implementation
of PIOLOGIE is
as fast as the best possible inner loop in assembler on machines today.
-
It was extensively tested for more than 100,000 CPU hours under more than
19 different compilers, processors and operating systems. High quality
checks are evaluated.
-
An iterative implementation of the Karatsuba multiplication, which is significantly
faster as the standard multiplication algorithm for numbers with only more
than 256 bits.
-
Schönhage-Strassen multiplication, which is an asymptotically optimal
algorithm, e.g. for multiplication, division, square root and radix conversion.
-
PIOLOGIE uses
an enhance template technique to extract and optimize an algebraic expression
at compile time for combinations of arguments, e.g. squaring costs about
two thirds of multiplication time.
2 Trademarks Used in this Manual
The following terms are trademarks of other companies:
Adobe, the Adobe logo, Acrobat, the Acrobat logo, Acrobat Reader, and
PostScript are trademarks of Adobe Systems Inc.
AIX, OS/2 and OS/390 are trademarks of International Business Machines
Corp. IBM is a registered trademark of International Business Machines
Corp.
Apogee is a trademark of Apogee Software, Inc.
Borland is a trademark of Inprise Corp.
DEC is a trademark of Compaq.
EDG is a trademark of Edison Design Group, Inc.
HP-UX is a trademark of Hewlett-Packard Company.
Intel and Pentium are registered trademarks of Intel Corp.
IRIX is a registered trademark of Silicon Graphics, Inc. in the United
States; which is either a trademark or a registered trademark in all other
countries where it is used. SGI indicates a trademark of Silicon Graphics,
Inc. that is not registered in the United States.
KAI is a trademark of Kuck & Associates, Inc.
Microsoft, Windows and Windows NT are registered trademarks of Microsoft
Corporation.
Sun Visual WorkShop, Solaris and SunOS are registered trademarks of
Sun Microsystems, Inc. in the United States and other countries.
UNIX is a registered trademark of UNIX System Laboratories, Inc.
Watcom is a registered trademark of Sybase, Inc.
Other company, products and services names may be trademarks or services
marks of others.
3 License
The term commercial use means any use of the PIOLOGIE
library by a firm, a commercial company or a government institution. Any
commercial use of PIOLOGIE
requires a license which is given out by HiPiLib at www.hipilib.de.
Redistributing your copy of PIOLOGIE
to a third party is not allowed.
A license for the installation and use of PIOLOGIE
is always given for one machine. Installing or copying the software to
another machine is not allowed.
A student edition are freely available for research and educational
under the GNU GENERAL PUBLIC LICENSE.
3.1 Warranty
This software is distributed in the hope that it will be useful but WITHOUT
ANY WARRANTY. The author(s) do not accept responsibility to anyone for
the consequences of using it or for whether it serves any particular purpose
or works at all. No warranty is made about the software or its performance.
This software is made available AS IS, and is distributed without warranty
of any kind, either expressed or implied.
In no event will the author(s) or their institutions be liable to you
for damages, including lost profits, lost money, or other special, incidental
or consequential damages arising out of or in connection with the use or
inability to use (including but not limited to loss of data or data being
rendered inaccurate or losses sustained by third parties or a failure of
the program to operate as documented) the program, even if you have been
advised of the possibility of such damages, or for any claim by any other
party, whether in an action of contract, negligence, or other tortious
action.
All the Software License Agreements of HiPiLib are governed by the laws
of Germany.
3.2 Single User License
PIOLOGIE is installed
and used on one single machine, which may not be used as a server.
3.3 Server License
PIOLOGIE is installed
and used on one server machine and there is no limit on the number of clients.
When buying any kind of license, you have the right to install and to develop
your own programs using PIOLOGIE.
You are also allowed to sell the binaries of your own programs that have
been compiled using PIOLOGIE.
This license is only allowed for the enterprise edition.
4 Quality
Quality is the highest goal of HiPiLib's philosophy. Thus, we offer only
products which have undergone - in some cases during some years - and passed
special tests. Everything is done to meet the highest expectations. On
the HiPiLib homepage you'll find references and links to scientific sites
which deal with our products. If our promise is not enough for you, you
are invited to read what others write about us.
Our philosophy of quality includes permanent control and improvement
of our libraries and corresponding programs. Every user - and of course
every interested person - can tell us about experiences, bugs, proposals
of improvement, etc. As a countermove to that, we try to keep you up to
date with latest developments and of course with our products.
5 Editions
PIOLOGIE is available
in several different editions, as listed below. Each of this editions is
connected with a special license agreement. Those agreements differ in
the possibility of commercial use of PIOLOGIE
library elements which are contained in the package, validity of registration,
and so on. The editions can partly be downloaded, others are sent after
a license was bought.
The following elements can be downloaded after sending registration
infos to HiPiLib: modulo, nmbrthry, pi, Manual, config.*, test.cpp Registration
key with limited validity.
5.1 Demo Edition
A Demo Edition of PIOLOGIE
is freely available at
www.hipilib.de. This edition can be used
without a license, but not for commercial purposes. For the Demo Edition
you need a special registration key. This key is as well freely available
on the homepage, but it - unlike the registration key of the Professional
Edition - excludes commercial use. The registration key of the Demo Edition
is only valid for a given period of time.
The Demo Edition of PIOLOGIE
is a fixed library, dependent on processor, compiler, and operating system
you choose. The Demo Edition has full functionality. Also, it includes
only Limited support. A fixed lib (for a processor, compiler, operating
system) available from web after sending registration infos which require
a registration key.
5.2 Scientific Edition
The Scientific Edition of PIOLOGIE
consists of the zipped source code. PIOLOGIE
is free for non-commercial purposes. This includes using PIOLOGIE
for research in schools, universities or similar academic organizations.
The usage is only allowed under GNU General Public License. The source
codes config.*, makefile, digit, natural, integer, rational are included
in this edition. The free files listed below are not included and have
to be downloaded separately. This edition includes limited support.
5.3 Professional Edition
The Professional Edition of PIOLOGIE
consists of a static library. It is dependent on processor, compiler, and
operating system you choose. After sending us these informations, you can
download a demo version of PIOLOGIE.
You get a registration key with unlimited validity under our Commercial
License Agreement. The Professional Edition is free for commercial usage.
It includes full support under our support conditions.
5.4 Enterprise Edition
The Enterprise Edition of PIOLOGIE
is a complete collection of static libraries and source codes. It is free
for commercial usage under the Commercial License Agreement. No registration
key is required. Manual, developer documentation, and all supplement programs
included. Full support under our support conditions.
6 Build the PIOLOGIE
Library
The following steps are necessary to build the PIOLOGIE
library in command line modus:
-
If your compiler does not have a make or nmake tool,
you can install GNU make which is for example available by anonymous
ftp from
prep.ai.mit.edu
-
Unpack the sources of PIOLOGIE,
where ``xxx" denotes the current version number. All files will be unpacked
into the directory called piologie.
-
For UNIX extract the source files by executing
% gzip -d piologie-xxx.tar.gz
% tar xvf piologie-xxx.tar
-
For Windows or OS/2 unzip the file piologie-xxx.zip into a directory.
-
In the created directory named piologie the following files should
at least exists:
-
Scientific Edition:
| config* |
configuration files for different compilers |
| digit.cpp |
the implementation file for digit operations |
| digit.h |
the included file for digit operations |
| integer.cpp |
the implementation file for integer operations |
| integer.h |
the included file for integer operations |
| makefile |
builds the library for different operating systems |
| manual.html |
contains information about PIOLOGIE
in html format |
| natural.cpp |
the implementation file for natural operations |
| natural.h |
the included file for natural operations |
| rational.cpp |
the implementation file for rational operations |
| rational.h |
the included file for rational operations |
-
Enterprise Edition:
| check.cpp |
program to check the PIOLOGIE
arithmetic |
| config* |
configuration files for different compilers |
| digit.cpp |
the implementation file for digit operations |
| digit.h |
the include file for digit operations |
| doc/ |
holds the manual and the developer documentation1
in the formats PDF, PS and HTML. |
| integer.cpp |
the implementation file for integer operations |
| integer.h |
the included file for integer operations |
| lib/ |
holds optimal generated libraries for different processors, compilers
and operating systems. These libraries include the arithmetic PIOLOGIE,
the Number Theory package, and files for calculation of constants. |
| makefile |
builds the library for different operating systems |
| manual.html |
contains information about PIOLOGIE
in html format |
| modulo.h |
the included file for the modular arithmetic |
| natural.cpp |
the implementation file for natural operations |
| natural.h |
the included file for natural operations |
| nmbrthry.cpp |
the implementation file for the Number Theory package |
| nmbrthry.h |
the included file for the Number Theory package |
| pi.cpp |
the implementation file for calculation of constants |
| pi.h |
the included file for calculation of constants |
| rational.cpp |
the implementation file for rational operations |
| rational.h |
the included file for rational operations |
| test.cpp |
little test program |
-
Configure your compiler if you have a not supported compiler (see section
5.3).
There is a configuration file, called config which you might need
to edit just a little, e.g. specify the compiler name.
The default settings are the GNU compiler 2.8.0 g++. In fact,
if you are using this compiler, you should not have to edit the file config
at all.
-
If you are in the directory piologie and you have one of the supported
compilers, type
| make ap |
for Apogee C++ 3.0, |
| make borland |
for Borland C++ 5.0, |
| make dec |
for Digital C++ 5.0, |
| make edg |
for Edison Design Group C++ front end 2.33, |
| make gnu |
for GNU C++ 2.6.1 - 2.7.2, |
| make gnu28 |
for GNU C++ 2.8.0 - 2.8.1, EGCS 1.1 |
| make gnu_mips4 |
for GNU C++ 2.7.2, SGI MIPS R8000, |
| make gnu_sparc |
for GNU C++ 2.7.2, SUN SuperSPARC, |
| make gnu28_sparc |
for GNU C++ 2.8.0, EGCS 1.1, SUN SuperSPARC, |
| make hp |
for HP C++ A.10.22, |
| make hpa |
for HP aC++ A.01.00, |
| make kai |
for KAI C++ 3.2, |
| make i386_ibm |
for IBM VisualAge C++ 3.0 on OS/2, |
| make os390 |
for IBM C++ on OS/390, |
| make ppc_ibm |
for IBM CSet++ on AIX 3.1.1, |
| make sgi |
for SGI MIPSpro C++ 7.1, |
| make sgi_8000 |
for SGI MIPSpro C++ 7.1 on MIPS R8000, |
| make sun |
for SUN WorkShop C++ 4.2, |
| make visual |
for Microsoft Visual C++ 5.0 - 6.0, |
| make watcom |
for Watcom C++ 11.0 |
to build the library (e.g. piologie.a under UNIX or piologie.lib
under Windows). Otherwise, adjust the settings for your own compiler in
the file config before calling make.
-
If you also build the little test program test.cpp2,
you can test the successful build of PIOLOGIE
if it generates the following output (e.g. Pentium II 266 MHz with Microsoft
Visual C++ 6.0, Microsoft Windows NT 4.0):
C:\piologie> test
fib1 time [s] = 1.221, (385053125)
fib2 time [s] = 1.322, (938800000)
sqrt time [s] = 3.886, (652162098)
mul time [s] = 1.091, (750000000)
sqr time [s] = 1.643, (0)
div time [s] = 1.071, (986328126)
pi time [s] = 1.182
6.1 Registration Key
There are different kinds of registration keys, corresponding to the Editions
of PIOLOGIE. Limited
Registration Key: This key is directly available on the HiPiLib homepage.
After filling out the download form, you get a key for the Demo Edition.
This key is valid for only a limited period.
Unlimited Registration Key: After buying the license for the Professional
Edition, you get a registration key for this edition. The validity of this
key is unlimited.
For registration key details please consult the section with the different
editions, or the HiPiLib homepage.
You can use your registration key in the following way:
extern const char* PIOLOGIE_KEY = "6RC0XK6PFQNVEQ6C2AHH6S Piologie
V1.3 Example";
(this key here is not valid).
6.2 Supported Processors
-
80486, Intel Pentium, Intel PentiumPro, Intel Pentium II/III,
-
DEC alpha,
-
HP PA,
-
IBM RS6000, IBM Power2, IBM PowerPC, IBM 9021-982, IBM S/390 G3/G4/G5/G6
-
SGI MIPS R4000/R4600/R5000/R8000/R10000,
-
SUN SuperSPARC, SUN UltraSPARC, SUN UltraSPARC II
6.3 Supported Compilers
-
Apogee C++ 3.0,
-
Borland C++ 5.02,
-
Digital C++ 5.0,
-
Edison Design Group C++ front end 2.33,
-
GNU C++ 2.6.1 - 2.8.1,
-
HP C++ A.10.22, HP aC++ A.01.00,
-
IBM CSet++ for AIX 3.1.1, IBM Visual Age C++ 3.0, IBM
C++ 3.6/3.6.5
-
KAI C++ 3.2,
-
Microsoft Visual C++ 5.0 - 6.0,
-
SGI MIPSpro C++ 7.1,
-
SUN WorkShop C++ 4.2 - 5.0,
-
Watcom C++ 10.6 - 11.0
6.4 Supported Operating Systems
-
SunOS,
-
SUN Solaris,
-
SGI Irix,
-
HP-UX,
-
IBM AIX,
-
Digital Unix,
-
Linux,
-
IBM OS/2,
-
IBM OS/390,
-
Microsoft Windows NT/95,
-
DOS32
6.5 Compiler Flags
| Flag: |
Meaning: |
| _Old_STD_ |
use not the newest C++ standard |
| STATIC_VS_INLINE |
some compilers have problems with inline |
| DEFINE_VS_CONST |
some compilers have problems with const |
| _DigitAsm_ |
use assembler whenever it is possible |
| _Piologie_Debug_ |
Debug modus for assert (developement only) |
| _Unknown_Apogee_Bug_ |
an unknown bug with Apogee compiler and inlining |
7 Contact
For whatever suggestions, questions, criticism, and praise you have concerning
the HiPiLib
products, please Contact HiPiLib.
HiPiLib
tries to answer all questions as fast as possible, and we hope to meet
your expectations.
7.1 Getting the Latest Version
To be always up to date with the latest developments of PIOLOGIE,
you can either visit the HiPiLib
homepage regularly, or get your e-mail address down to the HiPiLib
mailinglist.
HiPiLib
will then inform you regularly about new products, including new versions
of PIOLOGIE.
7.2 Reporting Bugs
You have encountered problems, while working with PIOLOGIE?
You can send a problem report. HiPiLib
will
try to eliminate the problem as soon as possible.
For conditions of full HiPiLib
support,
see product and license section.
Generally, problem reports concerning bugs are free and given promptly.
At answering problems concerning tasks and functionality - HiPiLib
will
do its best.
8 PIOLOGIE
Revision History
-
Version 1.3 was released in December 1999.
-
Version 1.2.1 was released in March 1998.
-
Version 1.2 was released in March 1998.
-
Version 1.1 was released in February 1998.
-
Version 1.0.2 was released in November 1997.
-
Version 1.0.1 was released in August 1997.
-
Version 1.0 was released in February 1997.
-
Version BETA built in November 1996, internal release.
-
Version ALPHA built in October 1996, internal release.
9 Natural Numbers: Natural
(natural.h)
Natural is a class that provides an arbitrary
precision natural number arithmetic. We can use this class Natural
like an unsigned built-in type, i.e. unsigned int, without length
restriction.
We support only one built-in type Digit
for Naturals, because of efficiency and portability.
The built-in type Digit is unsigned and contains
b
bits. The largest possible built-in number is g
= 2b-1.
9.1 Basic Operations
9.1.1 Constructors
| Algorithm: |
c := Natural(a) |
| Input: |
a ÎDigit. |
| Output: |
c ÎNatural
such that c = a [¯] |
| Algorithm: |
c := Natural(a) |
| Input: |
a ÎNatural. |
| Output: |
c ÎNatural
such that c = a [¯] |
| Algorithm: |
c := Natural(a, b) |
| Input: |
a Îchar*,
b Î Digit. |
| Output: |
c ÎNatural
such that c = a [¯] |
9.1.2 Assignments
| Algorithm: |
c := c = a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c = a [¯] |
| Algorithm: |
c := b = a |
| Input: |
a ÎDigit,
b ÎNatural. |
| Output: |
b ÎNatural,
c ÎDigit
such that b = a, c = a [¯] |
9.2 Arithmetical Operations
9.2.1 Addition (both arguments
of the same type)
| Algorithm: |
c := a+b |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = a+b [¯] |
| Algorithm: |
c := c += a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c : = c+a [¯] |
| Algorithm: |
c := ++a |
| Input: |
a ÎNatural. |
| Output: |
a,c ÎNatural
such that a : = a+1, c : = a [¯] |
| Algorithm: |
c := a++ |
| Input: |
a ÎNatural. |
| Output: |
a,c ÎNatural
such that c : = a, a : = a+1 [¯] |
9.2.2 Addition (mixed mode expression)
| Algorithm: |
c := a+b |
| Input: |
a ÎDigit,
b ÎNatural. |
| Output: |
c ÎNatural
such that c = a+b [¯] |
| Algorithm: |
c := a+b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c ÎNatural
such that c = a+b [¯] |
| Algorithm: |
c := c += a |
| Input: |
a ÎDigit,
c ÎNatural. |
| Output: |
c ÎNatural
such that c : = c+a [¯] |
9.2.3 Subtraction (both arguments
of the same type)
| Algorithm: |
c := a-b |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = a-b [¯] |
| Algorithm: |
c := c -= a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c : = c-a [¯] |
| Algorithm: |
c := -a |
| Input: |
a ÎNatural. |
| Output: |
a,c ÎNatural
such that a : = a-1, c : = a [¯] |
| Algorithm: |
c := a- |
| Input: |
a ÎNatural. |
| Output: |
a,c ÎNatural
such that c : = a, a : = a-1 [¯] |
9.2.4 Subtraction (mixed mode expression)
| Algorithm: |
c := a-b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c ÎNatural
such that c = a-b [¯] |
| Algorithm: |
c := c -= a |
| Input: |
a ÎDigit,
c ÎNatural. |
| Output: |
c ÎNatural
such that c : = c-a [¯] |
9.2.5 Multiplication (both arguments
of the same type)
| Algorithm: |
c := a*b |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = a·b [¯] |
| Algorithm: |
c := c *= a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c : = c·a [¯] |
9.2.6 Multiplication (mixed mode
expression)
| Algorithm: |
c := a*b |
| Input: |
a ÎDigit,
b ÎNatural. |
| Output: |
c ÎNatural
such that c = a·b [¯] |
| Algorithm: |
c := a*b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c ÎNatural
such that c = a·b [¯] |
| Algorithm: |
c := c *= a |
| Input: |
a ÎDigit,
c ÎNatural. |
| Output: |
c ÎNatural
such that c : = c·a [¯] |
9.2.7 Division (both arguments
of the same type)
| Algorithm: |
c := a/b |
| Input: |
a,b ÎNatural
where b ¹ 0. |
| Output: |
c ÎNatural
such that c = ëa/bû
[¯] |
| Algorithm: |
c := c /= a |
| Input: |
a,c ÎNatural
where a ¹ 0. |
| Output: |
c ÎNatural
such that c : = ëc/aû
[¯] |
| Algorithm: |
c := a%b |
| Input: |
a,b ÎNatural
where b ¹ 0. |
| Output: |
c ÎNatural
such that c = a-ëa/bû·b
[¯] |
| Algorithm: |
c := c %= a |
| Input: |
a,c ÎNatural
where a ¹ 0. |
| Output: |
c ÎNatural
such that c : = c-ëc/aû·a
[¯] |
9.2.8 Division (mixed mode expression)
| Algorithm: |
c := a/b |
| Input: |
a ÎNatural,
b ÎDigit
where b ¹ 0. |
| Output: |
c ÎNatural
such that c = ëa/bû
[¯] |
| Algorithm: |
c := c /= a |
| Input: |
c ÎNatural,
a ÎDigit
where a ¹ 0. |
| Output: |
c ÎNatural
such that c : = ëc/aû
[¯] |
| Algorithm: |
c := a%b |
| Input: |
a ÎNatural,
b ÎDigit
where b ¹ 0. |
| Output: |
c ÎDigit
such that c = a-ëa/bû·b
[¯] |
| Algorithm: |
c := a %= b |
| Input: |
a ÎNatural,
b ÎDigit
where b ¹ 0. |
| Output: |
c ÎDigit
such that c = a-ëa/bû·b,
a = c [¯] |
9.3 Bit Operations
9.3.1 Shifting
| Algorithm: |
c := a << b |
| Input: |
a ÎNatural,
b Îsize_t. |
| Output: |
c ÎNatural
such that c = a·2b [¯] |
| Algorithm: |
c := c <<= a |
| Input: |
a Îsize_t,
c Î Natural. |
| Output: |
c ÎNatural
such that c : = c·2a [¯] |
| Algorithm: |
c := a >> b |
| Input: |
a ÎNatural,
b Îsize_t. |
| Output: |
c ÎNatural
such that c = ë[a/( 2b)]û
[¯] |
| Algorithm: |
c := c >>= a |
| Input: |
a Îsize_t,
c Î Natural. |
| Output: |
c ÎNatural
such that c : = ë[c/( 2a)]û
[¯] |
9.3.2 Both arguments of the same
type
| Algorithm: |
c := a & b |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = aÙb [¯] |
| Algorithm: |
c := c &= a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c : = cÙa [¯] |
| Algorithm: |
c := a | b |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = aÚb [¯] |
| Algorithm: |
c := c |= a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c : = cÚa [¯] |
| Algorithm: |
c := a ^ b |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = ØaÙbÚaÙØb
[¯] |
| Algorithm: |
c := c ^= a |
| Input: |
a,c ÎNatural. |
| Output: |
c ÎNatural
such that c : = ØcÙaÚcÙØa
[¯] |
| Algorithm: |
c := ~a |
| Input: |
a ÎNatural. |
| Output: |
c ÎNatural
such that c = Øa [¯] |
9.3.3 Mixed mode expression
| Algorithm: |
c := a & b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c ÎDigit
such that c = aÙb [¯] |
| Algorithm: |
c := a &= b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
a ÎNatural,
c ÎDigit
such that a : = a Ùb, c = a
[¯] |
| Algorithm: |
c := a | b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c ÎNatural
such that c = a Úb [¯] |
| Algorithm: |
c := c |= a |
| Input: |
c ÎNatural,
a ÎDigit. |
| Output: |
c ÎNatural
such that c : = c Úa [¯] |
| Algorithm: |
c := c ^= a |
| Input: |
c ÎNatural,
a ÎDigit. |
| Output: |
c ÎNatural
such that c : = ØcÙaÚcÙØa
[¯] |
9.4 Comparisons
9.4.1 Both arguments of the same
type
| Algorithm: |
c := a == b |
| Input: |
a,b ÎNatural. |
| Output: |
c Îbool
such that if a = b then c = true else c = false
[¯] |
| Algorithm: |
c := a != b |
| Input: |
a,b ÎNatural. |
| Output: |
c Îbool
such that if a ¹ b then c = true
else c = false [¯] |
| Algorithm: |
c := a < b |
| Input: |
a,b ÎNatural. |
| Output: |
c Îbool
such that if a < b then c = true else c = false
[¯] |
| Algorithm: |
c := a <= b |
| Input: |
a,b ÎNatural. |
| Output: |
c Îbool
such that if a £ b then c = true
else c = false [¯] |
| Algorithm: |
c := a > b |
| Input: |
a,b ÎNatural. |
| Output: |
c Îbool
such that if a > b then c = true else c = false
[¯] |
| Algorithm: |
c := a >= b |
| Input: |
a,b ÎNatural. |
| Output: |
c Îbool
such that if a ³ b then c = true
else c = false [¯] |
9.4.2 Mixed mode expression
| Algorithm: |
c := a == b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c Îbool
such that if a = b then c = true else c = false
[¯] |
| Algorithm: |
c := a != b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c Îbool
such that if a ¹ b then c = true
else c = false [¯] |
| Algorithm: |
c := a < b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c Îbool
such that if a < b then c = true else c = false
[¯] |
| Algorithm: |
c := a <= b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c Îbool
such that if a £ b then c = true
else c = false [¯] |
| Algorithm: |
c := a > b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c Îbool
such that if a > b then c = true else c = false
[¯] |
| Algorithm: |
c := a >= b |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c Îbool
such that if a ³ b then c = true
else c = false [¯] |
9.5 Input/Output
9.5.1 Decimal
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Natural. |
| Output: |
o Îostream
[¯] |
| Note: |
Only decimal output is supported. |
| Algorithm: |
i := i >> a |
| Input: |
i Îistream. |
| Output: |
i Îistream,
a Î Natural
[¯] |
| Note: |
Only decimal input is supported. |
9.5.2 Internal Representation
| Algorithm: |
o := o << print(a) |
| Input: |
o Îostream,
a Î Natural. |
| Output: |
o Îostream
[¯] |
| Note: |
puts internal representation of
Naturala
on an output stream. |
| Algorithm: |
b := a.scan(i) |
| Input: |
a ÎNatural,
i Îistream. |
| Output: |
a ÎNatural,
i Îistream, b Îbool
[¯] |
| Note: |
gets Naturala
as an internal representation from input stream if b is true. |
9.6 Functions
9.6.1 Basic Functions
| Algorithm: |
c := a.odd() |
| Input: |
a ÎNatural. |
| Output: |
c Îbool
such that if 2|a then c = false else
c = true [¯] |
| Algorithm: |
c := a.even() |
| Input: |
a ÎNatural. |
| Output: |
c Îbool
such that if 2|a then c = true else
c = false [¯] |
| Algorithm: |
c := a.length() |
| Input: |
a ÎNatural. |
| Output: |
c Îsize_t
such that c = L(a) [¯] |
| Algorithm: |
c := a.highest() |
| Input: |
a ÎNatural. |
| Output: |
c ÎDigit
such that c = ë[a/( 2b(L(a)-1))]û
[¯] |
| Algorithm: |
c := a.lowest() |
| Input: |
a ÎNatural. |
| Output: |
c ÎDigit
such that c = aÙg [¯] |
| Algorithm: |
swap(a, b) |
| Input: |
a,b ÎNatural. |
| Output: |
a,b ÎNatural
such that t : = a, a : = b, b : = t |
|
where t ÎNatural
[¯] |
9.6.2 Absolute Value Functions
| Algorithm: |
c := sign(a) |
| Input: |
a ÎNatural. |
| Output: |
c Îbool
such that if a = 0 then c = false else c = true
[¯] |
| Algorithm: |
c := abs(a, b) |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = |a-b|
[¯] |
| Algorithm: |
d := abs(a, b, c) |
| Input: |
a,b ÎNatural. |
| Output: |
d Îint,
c Î Natural
such that c = |a-b|,
d·c = a-b [¯] |
9.6.3 Division Functions
| Algorithm: |
div(a, b, q, r) |
| Input: |
a,b,q,r ÎNatural
where b ¹ 0, q ¹
r. |
| Output: |
q,r ÎNatural
such that q = ëa/bû,
r = a-q·b [¯] |
| Algorithm: |
div(a, b, q, r) |
| Input: |
a ÎNatural,
b ÎDigit
where b ¹ 0. |
| Output: |
q ÎNatural,
r ÎDigit
such that q = ëa/bû,
r = a-q·b [¯] |
| Algorithm: |
c.split(n, a, b) |
| Input: |
a,b,c ÎNatural,
n Îsize_t where a ¹
b. |
| Output: |
a,b ÎNatural
such that a = ë[c/( 2bn)]û,
b = c-a·2bn [¯] |
9.6.4 Exponentiation Functions
| Algorithm: |
c := pow(a, b) |
| Input: |
a ÎNatural,
b ÎDigit. |
| Output: |
c ÎNatural
such that c = ab [¯] |
| Algorithm: |
c := pow(a, b) |
| Input: |
a, b ÎNatural. |
| Output: |
c ÎNatural
such that c = ab [¯] |
9.6.5 Root Functions
| Algorithm: |
sqrt(b, c, d) |
| Input: |
b ÎNatural. |
| Output: |
c,d ÎNatural
such that c = ëÖbû,
d = b - c2 [¯] |
| Algorithm: |
b := sqrt(a) |
| Input: |
a ÎNatural. |
| Output: |
b ÎNatural
such that b = ëÖaû
[¯] |
| Algorithm: |
b := root(a, n) |
| Input: |
a ÎNatural,
n ÎDigit. |
| Output: |
b ÎNatural
such that b = ënÖ{a}û
[¯] |
9.6.6 Logarithmical Functions
| Algorithm: |
b := log2(a) |
| Input: |
a ÎNatural. |
| Output: |
b ÎDigit
such that if a > 0 then b = ëlog2(a)û
else b = 0 [¯] |
9.6.7 Bit Manipulation Functions
| Algorithm: |
c.setbit(a) |
| Input: |
a ÎDigit,
c ÎNatural. |
| Output: |
c ÎNatural
such that c : = cÚ2a
[¯] |
| Algorithm: |
c.clearbit(a) |
| Input: |
a ÎDigit,
c ÎNatural. |
| Output: |
c ÎNatural
such that c : = cÙØ2a
[¯] |
| Algorithm: |
c := b.testbit(a) |
| Input: |
a ÎDigit,
b ÎNatural. |
| Output: |
c Îbool
such that if bÙ2a then c =
true
else c = false [¯] |
9.6.8 Random Numbers
| Algorithm: |
a.rand(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎNatural
such that a < 2n (random number) [¯] |
9.6.9 Conversions
| Algorithm: |
c := Ntoa(a, c, b) |
| Input: |
a ÎNatural,
b ÎDigit,
c Îchar* where 2 £
b £ 36, sizeof(c) > b[(L(a))/(
log2(b))]. |
| Output: |
c Îchar*
such that c = a [¯] |
| Algorithm: |
c := atoN(a, b) |
| Input: |
a Îchar*,
b Î Digit
where 2 £ b £
36. |
| Output: |
c ÎNatural
such that c = a [¯] |
| Algorithm: |
c := d.atoN(a, b) |
| Input: |
d ÎNatural,
a Îchar*, b ÎDigit
where 2 £ b £
36. |
| Output: |
d ÎNatural,
c Îchar* such that d = a
[¯] |
| Note: |
Returns a pointer to the first
occurrence of a non-digit character in a. |
9.6.10 Greatest Common Divisor
| Algorithm: |
c := gcd(a, b) |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = max{x ÎNatural\mid
x|a, x|b}
[¯] |
| Algorithm: |
c := lcm(a, b) |
| Input: |
a,b ÎNatural. |
| Output: |
c ÎNatural
such that c = min{x ÎNatural\mid
a|x, b|x}
[¯] |
10 Integers: Integer
(integer.h)
Integer is a class that provides an arbitrary
precision integer arithmetic. We can use this class Integer
like a signed built-in type, i.e. int, without length restriction.
We support only one built-in type SignDigit
for Integers, because of efficiency and portability.
The built-in type SignDigit is signed and
contains b bits. The largest possible built-in
number is 2b-1-1 and the smallest
is -2b-1.
10.1 Basic Operations
10.1.1 Constructors
| Algorithm: |
c := Integer(a) |
| Input: |
a ÎSignDigit. |
| Output: |
c ÎInteger
such that c = a [¯] |
| Algorithm: |
c := Integer(a) |
| Input: |
a ÎNatural. |
| Output: |
c ÎInteger
such that c = a [¯] |
| Algorithm: |
c := Integer(a) |
| Input: |
a ÎInteger. |
| Output: |
c ÎInteger
such that c = a [¯] |
| Algorithm: |
c := Integer(a, b) |
| Input: |
a Îchar*,
b Î Digit. |
| Output: |
c ÎInteger
such that c = a [¯] |
10.1.2 Assignments
| Algorithm: |
c := c = a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c = a [¯] |
| Algorithm: |
c := c = a |
| Input: |
a ÎNatural,
c ÎInteger. |
| Output: |
c ÎInteger
such that c = a [¯] |
| Algorithm: |
c := b = a |
| Input: |
a ÎSignDigit,
b ÎInteger. |
| Output: |
b ÎInteger,
c ÎSignDigit
such that b = a, c = a [¯] |
10.2 Arithmetical Operations
10.2.1 Addition (both arguments
of the same type
| Algorithm: |
c := a+b |
| Input: |
a,b ÎInteger. |
| Output: |
c ÎInteger
such that c = a+b [¯] |
| Algorithm: |
c := c += a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c+a [¯] |
| Algorithm: |
c := ++a |
| Input: |
a ÎInteger. |
| Output: |
a,c ÎInteger
such that a : = a+1, c : = a [¯] |
| Algorithm: |
c := a++ |
| Input: |
a ÎInteger. |
| Output: |
a,c ÎInteger
such that c : = a, a : = a+1 [¯] |
10.2.2 Addition (mixed mode expression
| Algorithm: |
c := a+b |
| Input: |
a ÎNatural,
b ÎInteger. |
| Output: |
c ÎInteger
such that c = a+b [¯] |
| Algorithm: |
c := a+b |
| Input: |
a ÎInteger,
b ÎNatural. |
| Output: |
c ÎInteger
such that c = a+b [¯] |
| Algorithm: |
c := a+b |
| Input: |
a ÎSignDigit,
b ÎInteger. |
| Output: |
c ÎInteger
such that c = a+b [¯] |
| Algorithm: |
c := a+b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c ÎInteger
such that c = a+b [¯] |
| Algorithm: |
c := c += a |
| Input: |
a ÎNatural,
c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c+a [¯] |
| Algorithm: |
c := c += a |
| Input: |
a ÎSignDigit,
c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c+a [¯] |
10.2.3 Subtraction (both arguments
of the same type)
| Algorithm: |
c := a-b |
| Input: |
a,b ÎInteger. |
| Output: |
c ÎInteger
such that c = a-b [¯] |
| Algorithm: |
c := c -= a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c-a [¯] |
| Algorithm: |
c := -a |
| Input: |
a ÎInteger. |
| Output: |
a,c ÎInteger
such that a : = a-1, c : = a [¯] |
| Algorithm: |
c := a- |
| Input: |
a ÎInteger. |
| Output: |
a,c ÎInteger
such that c : = a, a : = a-1 [¯] |
| Algorithm: |
c := -a |
| Input: |
a ÎInteger. |
| Output: |
c ÎInteger
such that c = -a [¯] |
10.2.4 Subtraction (mixed mode
expression)
| Algorithm: |
c := a-b |
| Input: |
a ÎNatural,
b ÎInteger. |
| Output: |
c ÎInteger
such that c = a-b [¯] |
| Algorithm: |
c := a-b |
| Input: |
a ÎInteger,
b ÎNatural. |
| Output: |
c ÎInteger
such that c = a-b [¯] |
| Algorithm: |
c := a-b |
| Input: |
a ÎSignDigit,
b ÎInteger. |
| Output: |
c ÎInteger
such that c = a-b [¯] |
| Algorithm: |
c := a-b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c ÎInteger
such that c = a-b [¯] |
| Algorithm: |
c := c -= a |
| Input: |
a ÎNatural,
c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c-a [¯] |
| Algorithm: |
c := c -= a |
| Input: |
a ÎSignDigit,
c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c-a [¯] |
10.2.5 Multiplication (both arguments
of the same type)
| Algorithm: |
c := a*b |
| Input: |
a,b ÎInteger. |
| Output: |
c ÎInteger
such that c = a·b [¯] |
| Algorithm: |
c := c *= a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c·a [¯] |
10.2.6 Multiplication (mixed mode
expression)
| Algorithm: |
c := a*b |
| Input: |
a ÎNatural,
b ÎInteger. |
| Output: |
c ÎInteger
such that c = a·b [¯] |
| Algorithm: |
c := a*b |
| Input: |
a ÎInteger,
b ÎNatural. |
| Output: |
c ÎInteger
such that c = a·b [¯] |
| Algorithm: |
c := a*b |
| Input: |
a ÎSignDigit,
b ÎInteger. |
| Output: |
c ÎInteger
such that c = a·b [¯] |
| Algorithm: |
c := a*b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c ÎInteger
such that c = a·b [¯] |
| Algorithm: |
c := c *= a |
| Input: |
a ÎSignDigit,
c ÎInteger. |
| Output: |
c ÎInteger
such that c : = c·a [¯] |
10.2.7 Division (both arguments
of the same type)
| Algorithm: |
c := a/b |
| Input: |
a,b ÎInteger
where b ¹ 0. |
| Output: |
c ÎInteger
such that c = sign(a·b)ë|a/b|û
[¯] |
| Algorithm: |
c := c /= a |
| Input: |
a,c ÎInteger
where a ¹ 0. |
| Output: |
c ÎInteger
such that c : = sign(a·c)ë|c/a|û
[¯] |
| Algorithm: |
c := a%b |
| Input: |
a,b ÎInteger
where b ¹ 0. |
| Output: |
c ÎInteger
such that c = a-sign(a·b)ë|a/b|û·b
[¯] |
| Algorithm: |
c := c %= a |
| Input: |
a,c ÎInteger
where a ¹ 0. |
| Output: |
c ÎInteger
such that c : = c-sign(a·c)ë|c/a|û·a
[¯] |
10.2.8 Division (mixed mode expression)
| Algorithm: |
c := a/b |
| Input: |
a ÎInteger,
b ÎSignDigit
where b ¹ 0. |
| Output: |
c ÎInteger
such that c = sign(a·b)ë|a/b|û
[¯] |
| Algorithm: |
c := a/b |
| Input: |
a ÎInteger,
b ÎNatural
where b ¹ 0. |
| Output: |
c ÎInteger
such that c = sign(a)ë[(|a|)/
b]û [¯] |
| Algorithm: |
c := a/b |
| Input: |
a ÎNatural,
b ÎInteger
where b ¹ 0. |
| Output: |
c ÎInteger
such that c = sign(b)ë[a/(
|b|)]û
[¯] |
| Algorithm: |
c := c /= a |
| Input: |
c ÎInteger,
a ÎNatural
where a ¹ 0. |
| Output: |
c ÎInteger
such that c : = sign(c)ë[(|c|)/
a]û [¯] |
| Algorithm: |
c := c /= a |
| Input: |
c ÎInteger,
a ÎSignDigit
where a ¹ 0. |
| Output: |
c ÎInteger
such that c : = sign(c·a)ë|c/a|û
[¯] |
| Algorithm: |
c := a%b |
| Input: |
a ÎInteger,
b ÎSignDigit
where b ¹ 0. |
| Output: |
c ÎSignDigit
such that c = a-sign(a·b)ë|a/b|û·b
[¯] |
| Algorithm: |
c := c %= a |
| Input: |
c ÎInteger,
a ÎNatural
where a ¹ 0. |
| Output: |
c ÎInteger
such that c : = c-sign(c)ë[(|c|)/
a]û·a [¯] |
| Algorithm: |
c := c %= a |
| Input: |
c ÎInteger,
a ÎSignDigit
where a ¹ 0. |
| Output: |
c ÎInteger
such that c : = c-sign(a·c)ë|c/a|û·a
[¯] |
10.3 Bit Operations
10.3.1 Shifting
| Algorithm: |
c := a << b |
| Input: |
a ÎInteger,
b Îsize_t. |
| Output: |
c ÎInteger
such that c = a·2b [¯] |
| Algorithm: |
c := c <<= a |
| Input: |
a Îsize_t,
c Î Integer. |
| Output: |
c ÎInteger
such that c : = c·2a [¯] |
| Algorithm: |
c := a >> b |
| Input: |
a ÎInteger,
b Îsize_t. |
| Output: |
c ÎInteger
such that c = sign(a)ë[(|a|)/(
2b)]û [¯] |
| Algorithm: |
c := c >>= a |
| Input: |
a Îsize_t,
c Î Integer. |
| Output: |
c ÎInteger
such that c : = sign(c)ë[(|c|)/(
2a)]û [¯] |
10.3.2 Both arguments of the same
type
| Algorithm: |
c := a & b |
| Input: |
a,b ÎInteger. |
| Output: |
c ÎInteger
such that c = aÙb [¯] |
| Algorithm: |
c := c &= a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c : = cÙa [¯] |
| Algorithm: |
c := a | b |
| Input: |
a,b ÎInteger. |
| Output: |
c ÎInteger
such that c = aÚb [¯] |
| Algorithm: |
c := c |= a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c : = cÚa [¯] |
| Algorithm: |
c := a ^ b |
| Input: |
a,b ÎInteger. |
| Output: |
c ÎInteger
such that c = ØaÙbÚaÙØb
[¯] |
| Algorithm: |
c := c ^= a |
| Input: |
a,c ÎInteger. |
| Output: |
c ÎInteger
such that c : = ØcÙaÚcÙØa
[¯] |
| Algorithm: |
c := ~a |
| Input: |
a ÎInteger. |
| Output: |
c ÎInteger
such that c = Øa [¯] |
10.3.3 Mixed mode expression
| Algorithm: |
c := a & b |
| Input: |
a ÎInteger,
b ÎDigit. |
| Output: |
c ÎDigit
such that c = aÙb [¯] |
| Algorithm: |
c := a &= b |
| Input: |
a ÎInteger,
b ÎDigit. |
| Output: |
a ÎInteger,
c ÎDigit
such that a : = a Ùb, c = a
[¯] |
| Algorithm: |
c := a | b |
| Input: |
a ÎInteger,
b ÎDigit. |
| Output: |
c ÎInteger
such that c = a Úb [¯] |
| Algorithm: |
c := c |= a |
| Input: |
c ÎInteger,
a ÎDigit. |
| Output: |
c ÎInteger
such that c : = c Úa [¯] |
10.4 Comparisons
10.4.1 Both arguments of the same
type
| Algorithm: |
c := a == b |
| Input: |
a,b ÎInteger. |
| Output: |
c Îbool
such that if a = b then c = true else c = false
[¯] |
| Algorithm: |
c := a != b |
| Input: |
a,b ÎInteger. |
| Output: |
c Îbool
such that if a ¹ b then c = true
else c = false [¯] |
| Algorithm: |
c := a < b |
| Input: |
a,b ÎInteger. |
| Output: |
c Îbool
such that if a < b then c = true else c = false
[¯] |
| Algorithm: |
c := a <= b |
| Input: |
a,b ÎInteger. |
| Output: |
c Îbool
such that if a £ b then c = true
else c = false [¯] |
| Algorithm: |
c := a > b |
| Input: |
a,b ÎInteger. |
| Output: |
c Îbool
such that if a > b then c = true else c = false
[¯] |
| Algorithm: |
c := a >= b |
| Input: |
a,b ÎInteger. |
| Output: |
c Îbool
such that if a ³ b then c = true
else c = false [¯] |
10.4.2 Mixed mode expression
| Algorithm: |
c := a == b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a = b then c = true else c = false
[¯] |
| Algorithm: |
c := a != b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a ¹ b then c = true
else c = false [¯] |
| Algorithm: |
c := a < b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a < b then c = true else c = false
[¯] |
| Algorithm: |
c := a <= b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a £ b then c = true
else c = false [¯] |
| Algorithm: |
c := a > b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a > b then c = true else c = false
[¯] |
| Algorithm: |
c := a >= b |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a ³ b then c = true
else c = false [¯] |
10.5 Input/Output
10.5.1 Decimal
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Integer. |
| Output: |
o Îostream
[¯] |
| Note: |
Only decimal output is supported. |
| Algorithm: |
i := i >> a |
| Input: |
i Îistream. |
| Output: |
i Îistream,
a Î Integer
[¯] |
| Note: |
Only decimal input is supported. |
10.5.2 Internal Representation
| Algorithm: |
o := o << print(a) |
| Input: |
o Îostream,
a Î Integer. |
| Output: |
o Îostream
[¯] |
| Note: |
puts internal representation of
Integer
a on an output stream. |
| Algorithm: |
b := a.scan(i) |
| Input: |
a ÎInteger,
i Îistream. |
| Output: |
a ÎInteger,
i Îistream, b Îbool
[¯] |
| Note: |
gets Integer
a as an internal representation from input stream if b is true. |
10.6 Functions
10.6.1 Basic Functions
| Algorithm: |
c := a.odd() |
| Input: |
a ÎInteger. |
| Output: |
c Îbool
such that if 2|a then c = false else
c = true [¯] |
| Algorithm: |
c := a.even() |
| Input: |
a ÎInteger. |
| Output: |
c Îbool
such that if 2|a then c = true else
c = false [¯] |
| Algorithm: |
c := a.length() |
| Input: |
a ÎInteger. |
| Output: |
c Îsize_t
such that c = L(|a|)
[¯] |
| Algorithm: |
c := a.highest() |
| Input: |
a ÎInteger. |
| Output: |
c ÎDigit
such that c = ë[(|a|)/(
2b(L(|a|)-1))]û
[¯] |
| Algorithm: |
c := a.lowest() |
| Input: |
a ÎInteger. |
| Output: |
c ÎDigit
such that c = |a|Ùg
[¯] |
| Algorithm: |
swap(a, b) |
| Input: |
a,b ÎInteger. |
| Output: |
a,b ÎInteger
such that t : = a, a : = b, b : = t |
|
where t ÎInteger
[¯] |
10.6.2 Absolute Value Functions
| Algorithm: |
c := sign(a) |
| Input: |
a ÎInteger. |
| Output: |
c Îint
such that |
|
if a = 0 then c = 0 |
|
else if a > 0 then c = 1 |
|
else c = -1 [¯] |
| Algorithm: |
c := abs(a) |
| Input: |
a ÎInteger. |
| Output: |
c ÎNatural
such that c = |a|
[¯] |
| Algorithm: |
c := units(a) |
| Input: |
a ÎInteger. |
| Output: |
a ÎInteger,
c Îint such that a : = |a|,
if a ³ 0 then c = 1 else c = -1 [¯] |
10.6.3 Division Functions
| Algorithm: |
div(a, b, c, d) |
| Input: |
a,b,c,d ÎInteger
where b ¹ 0, c ¹
d. |
| Output: |
c,d ÎInteger
such that c = sign(a·b)ë|a/b|û,
d = a-c·b [¯] |
| Algorithm: |
div(a, b, c, d) |
| Input: |
a ÎInteger,
b ÎSignDigit
where b ¹ 0. |
| Output: |
c ÎInteger,
d ÎSignDigit
such that c = sign(a·b)ë|a/b|û,
d = a-c·b [¯] |
| Algorithm: |
a.split(b, c, d) |
| Input: |
a,c,d ÎInteger,
b Îsize_t where c ¹
d. |
| Output: |
c,d ÎInteger
such that c = sign(a)ë[(|a|)/(
2bb)]û,
d = a-c·2bb [¯] |
10.6.4 Exponentiation Functions
| Algorithm: |
c := pow(a, b) |
| Input: |
a ÎInteger,
b ÎSignDigit. |
| Output: |
c ÎInteger
such that c = ab [¯] |
| Algorithm: |
c := pow(a, b) |
| Input: |
a, b ÎInteger. |
| Output: |
c ÎInteger
such that c = sign(a)bë|a|bû
[¯] |
10.6.5 Root Functions
| Algorithm: |
sqrt(a, b, c) |
| Input: |
a ÎInteger
where a ³ 0. |
| Output: |
b,c ÎInteger
such that b = ëÖaû,
c = a - b2 [¯] |
| Algorithm: |
b := sqrt(a) |
| Input: |
a ÎInteger
where a ³ 0. |
| Output: |
b ÎInteger
such that b = ëÖaû
[¯] |
| Algorithm: |
c := root(a, b) |
| Input: |
a ÎInteger,
b ÎSignDigit
where 2|b or a ³
0. |
| Output: |
c ÎInteger
such that c = sign(a)bë|a|1/bû
[¯] |
10.6.6 Logarithmical Functions
| Algorithm: |
b := log2(a) |
| Input: |
a ÎInteger. |
| Output: |
b ÎDigit
such that if |a|
> 0 then b = ëlog2|a|û+1
else b = 0 [¯] |
10.6.7 Bit Manipulation Functions
| Algorithm: |
c.setbit(a) |
| Input: |
a Îsize_t,
c Î Integer. |
| Output: |
c ÎInteger
such that c : = cÚ2a
[¯] |
| Algorithm: |
c.clearbit(a) |
| Input: |
a Îsize_t,
c Î Integer. |
| Output: |
c ÎInteger
such that c : = cÙØ2a
[¯] |
| Algorithm: |
c := b.testbit(a) |
| Input: |
a Îsize_t,
b Î Integer. |
| Output: |
c Îbool
such that if bÙ2a then c =
true
else c = false [¯] |
10.6.8 Random Numbers
| Algorithm: |
a.rand(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎInteger
such that |a| <
2n (random number) [¯] |
10.6.9 Conversions
| Algorithm: |
c := Itoa(a, c, b) |
| Input: |
a ÎInteger,
b ÎDigit,
c Îchar* where 2 £
b £ 36, sizeof(c) > b[(L(a))/(
log2(b))]. |
| Output: |
c Îchar*
such that c = a [¯] |
| Algorithm: |
c := atoI(a, b) |
| Input: |
a Îchar*,
b Î Digit
where 2 £ b £
36. |
| Output: |
c ÎInteger
such that c = a [¯] |
| Algorithm: |
c := d.atoI(a, b) |
| Input: |
d ÎInteger,
a Îchar*, b ÎDigit
where 2 £ b £
36. |
| Output: |
d ÎInteger,
c Îchar* such that d = a
[¯] |
| Note: |
Returns a pointer to the first
occurrence of a non-digit character in a. |
10.6.10 Greatest Common Divisor
| Algorithm: |
gcd(a, b, x, y, z) |
| Input: |
a,b ÎInteger. |
| Output: |
x,y,z ÎInteger
such that z = ax+by = gcd(a, b) [¯] |
11 Rational Numbers: Rational
(rational.h)
Rational is a class that provides an arbitrary
precision rational arithmetic.
A Rational consists of an Integer
as numerator and a Natural as denominator.
The numerator and denominator of a Rational
are always coprime.
We support only one built-in type SignDigit
for Rationals, because of efficiency and
portability. The built-in type SignDigit
is signed and contains b bits. The largest possible
built-in number is 2b-1-1 and the
smallest is -2b-1.
11.1 Basic Operations
11.1.1 Constructors
| Algorithm: |
c := Rational(a) |
| Input: |
a ÎSignDigit. |
| Output: |
c ÎRational
such that c = a/1 [¯] |
| Algorithm: |
c := Rational(a, b) |
| Input: |
a ÎInteger,
b ÎNatural
where b ¹ 0. |
| Output: |
c ÎRational
such that c = a/b [¯] |
| Algorithm: |
c := Rational(a) |
| Input: |
a ÎInteger. |
| Output: |
c ÎRational
such that c = a/1 [¯] |
| Algorithm: |
c := Rational(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎRational
such that c = a [¯] |
11.1.2 Selectors
| Algorithm: |
c := a.numerator() |
| Input: |
a ÎRational. |
| Output: |
c ÎInteger
such that c = a1 where [(a1)/( a2)] =
a [¯] |
| Algorithm: |
c := numerator(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎInteger
such that c = a1 where [(a1)/( a2)] =
a [¯] |
| Algorithm: |
c := a.denominator() |
| Input: |
a ÎRational. |
| Output: |
c ÎNatural
such that c = a2 where [(a1)/( a2)] =
a [¯] |
| Algorithm: |
c := denominator(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎNatural
such that c = a2 where [(a1)/( a2)] =
a [¯] |
11.1.3 Assignments
| Algorithm: |
c := c = a |
| Input: |
a,c ÎRational. |
| Output: |
c ÎRational
such that c = a [¯] |
| Algorithm: |
c := c = a |
| Input: |
a ÎInteger,
c ÎRational. |
| Output: |
c ÎRational
such that c = a/1 [¯] |
| Algorithm: |
c := b = a |
| Input: |
a ÎSignDigit,
b ÎRational. |
| Output: |
b ÎRational,
c ÎSignDigit
such that b = a/1, c = a [¯] |
11.2 Arithmetical Operations
11.2.1 Addition (both arguments
of the same type
| Algorithm: |
c := a+b |
| Input: |
a,b ÎRational. |
| Output: |
c ÎRational
such that c = a+b [¯] |
| Algorithm: |
c := c += a |
| Input: |
a,c ÎRational. |
| Output: |
c ÎRational
such that c : = c+a [¯] |
| Algorithm: |
c := ++a |
| Input: |
a ÎRational. |
| Output: |
a,c ÎRational
such that a : = a+1, c : = a [¯] |
| Algorithm: |
c := a++ |
| Input: |
a ÎRational. |
| Output: |
a,c ÎRational
such that c : = a, a : = a+1 [¯] |
11.2.2 Subtraction (both arguments
of the same type)
| Algorithm: |
c := a-b |
| Input: |
a,b ÎRational. |
| Output: |
c ÎRational
such that c = a-b [¯] |
| Algorithm: |
c := c -= a |
| Input: |
a,c ÎRational. |
| Output: |
c ÎRational
such that c : = c-a [¯] |
| Algorithm: |
c := -a |
| Input: |
a ÎRational. |
| Output: |
a,c ÎRational
such that a : = a-1, c : = a [¯] |
| Algorithm: |
c := a- |
| Input: |
a ÎRational. |
| Output: |
a,c ÎRational
such that c : = a, a : = a-1 [¯] |
| Algorithm: |
c := -a |
| Input: |
a ÎRational. |
| Output: |
c ÎRational
such that c = -a [¯] |
11.2.3 Multiplication (both arguments
of the same type)
| Algorithm: |
c := a*b |
| Input: |
a,b ÎRational. |
| Output: |
c ÎRational
such that c = a·b [¯] |
| Algorithm: |
c := c *= a |
| Input: |
a,c ÎRational. |
| Output: |
c ÎRational
such that c : = c·a [¯] |
11.2.4 Division (both arguments
of the same type)
| Algorithm: |
c := a/b |
| Input: |
a,b ÎRational
where b ¹ 0. |
| Output: |
c ÎRational
such that c = sign(a·b)ë|a/b|û
[¯] |
| Algorithm: |
c := c /= a |
| Input: |
a,c ÎRational
where a ¹ 0. |
| Output: |
c ÎRational
such that c : = sign(a·c)ë|c/a|û
[¯] |
11.3 Bit Operations
11.3.1 Shifting
| Algorithm: |
c := a << b |
| Input: |
a ÎRational,
b Îsize_t. |
| Output: |
c ÎRational
such that c = a·2b [¯] |
| Algorithm: |
c := c <<= a |
| Input: |
a Îsize_t,
c Î Rational. |
| Output: |
c ÎRational
such that c : = c·2a [¯] |
| Algorithm: |
c := a >> b |
| Input: |
a ÎRational,
b Îsize_t. |
| Output: |
c ÎRational
such that c = [a/( 2b)] [¯] |
| Algorithm: |
c := c >>= a |
| Input: |
a Îsize_t,
c Î Rational. |
| Output: |
c ÎRational
such that c : = [c/( 2a)] [¯] |
11.4 Comparisons
11.4.1 Both arguments of the same
type
| Algorithm: |
c := a == b |
| Input: |
a,b ÎRational. |
| Output: |
c Îbool
such that if a = b then c = true else c = false
[¯] |
| Algorithm: |
c := a != b |
| Input: |
a,b ÎRational. |
| Output: |
c Îbool
such that if a ¹ b then c = true
else c = false [¯] |
| Algorithm: |
c := a < b |
| Input: |
a,b ÎRational. |
| Output: |
c Îbool
such that if a < b then c = true else c = false
[¯] |
| Algorithm: |
c := a <= b |
| Input: |
a,b ÎRational. |
| Output: |
c Îbool
such that if a £ b then c = true
else c = false [¯] |
| Algorithm: |
c := a > b |
| Input: |
a,b ÎRational. |
| Output: |
c Îbool
such that if a > b then c = true else c = false
[¯] |
| Algorithm: |
c := a >= b |
| Input: |
a,b ÎRational. |
| Output: |
c Îbool
such that if a ³ b then c = true
else c = false [¯] |
11.4.2 Mixed mode expression
| Algorithm: |
c := a == b |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a = b then c = true else c = false
[¯] |
| Algorithm: |
c := a != b |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a ¹ b then c = true
else c = false [¯] |
| Algorithm: |
c := a < b |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a < b then c = true else c = false
[¯] |
| Algorithm: |
c := a <= b |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a £ b then c = true
else c = false [¯] |
| Algorithm: |
c := a > b |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a > b then c = true else c = false
[¯] |
| Algorithm: |
c := a >= b |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c Îbool
such that if a ³ b then c = true
else c = false [¯] |
11.5 Input/Output
11.5.1 Decimal
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Rational. |
| Output: |
o Îostream
[¯] |
| Note: |
Only decimal output is supported. |
| Algorithm: |
i := i >> a |
| Input: |
i Îistream. |
| Output: |
i Îistream,
a Î Rational
[¯] |
| Note: |
Only decimal input is supported. |
11.5.2 Internal Representation
| Algorithm: |
o := o << print(a) |
| Input: |
o Îostream,
a Î Rational. |
| Output: |
o Îostream
[¯] |
| Note: |
puts internal representation of
Rational
a on an output stream. |
| Algorithm: |
b := a.scan(i) |
| Input: |
a ÎRational,
i Îistream. |
| Output: |
a ÎRational,
i Îistream, b Îbool
[¯] |
| Note: |
gets Rational
a as an internal representation from input stream if b is true. |
11.6 Functions
11.6.1 Basic Functions
| Algorithm: |
swap(a, b) |
| Input: |
a,b ÎRational. |
| Output: |
a,b ÎRational
such that t : = a, a : = b, b : = t |
|
where t ÎRational
[¯] |
11.6.2 Absolute Value Functions
| Algorithm: |
c := abs(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎNatural
such that c = |a|
[¯] |
| Algorithm: |
c := sign(a) |
| Input: |
a ÎRational. |
| Output: |
c Îint
such that |
|
if a = 0 then c = 0 |
|
else if a > 0 then c = 1 |
|
else c = -1 [¯] |
11.6.3 Inversion Function
| Algorithm: |
b := inv(a) |
| Input: |
a ÎRational
where a ³ 0. |
| Output: |
b ÎRational
such that b = a-1 [¯] |
11.6.4 Exponentiation Functions
| Algorithm: |
c := pow(a, b) |
| Input: |
a ÎRational,
b ÎSignDigit. |
| Output: |
c ÎRational
such that c = ab [¯] |
| Algorithm: |
c := pow(a, b) |
| Input: |
a ÎRational,
b ÎInteger. |
| Output: |
c ÎRational
such that c = ab [¯] |
11.6.5 Integer Functions
| Algorithm: |
c := ceil(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎInteger
such that c = éaù
[¯] |
| Algorithm: |
c := floor(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎInteger
such that c = ëaû
[¯] |
| Algorithm: |
c := round(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎInteger
such that c = ëa+1/2û
[¯] |
| Algorithm: |
c := trunc(a) |
| Input: |
a ÎRational. |
| Output: |
c ÎInteger
such that c = sign(a)ë|a|û
[¯] |
11.6.6 Random Numbers
| Algorithm: |
a.rand(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎRational
such that |a1|
< 2n, a2 £ 2n
where [(a1)/( a2)] = a (random number) [¯] |
11.6.7 Conversions
| Algorithm: |
c := Rtoa(a, c, b) |
| Input: |
a ÎRational,
b ÎDigit,
c Îchar* where 2 £
b £ 36, sizeof(c) > b[(L(a))/(
log2(b))]. |
| Output: |
c Îchar*
such that c = a [¯] |
| Algorithm: |
c := atoR(a, b) |
| Input: |
a Îchar*,
b Î Digit
where 2 £ b £
36. |
| Output: |
c ÎRational
such that c = a [¯] |
| Algorithm: |
c := d.atoR(a, b) |
| Input: |
d ÎRational,
a Îchar*, b ÎDigit
where 2 £ b £
36. |
| Output: |
d ÎRational,
c Îchar* such that d = a
[¯] |
| Note: |
Returns a pointer to the first
occurrence of a non-digit character in a. |
12 Modular Arithmetic (modulo.h)
This package requires STL and the compiler must support templates.
12.1 Exponentiation
| Algorithm: |
d := pow(a, b, c) |
| Input: |
a,b,c Î
T where c > 0. |
| Output: |
d Î
T such that d º ab mod c
[¯] |
12.2 Modular Inverse
| Algorithm: |
c := inverse(a, b) |
| Input: |
a,b Î
T where b > 0. |
| Output: |
c Î
T such that c º a-1 mod b
[¯] |
12.3 Modular Square Root
| Algorithm: |
c := sqrt(a, b) |
| Input: |
a,b Î
T where b Î \mathbbP and ([ a
/ b ]) = 1. |
| Output: |
c Î
T such that c2 º a mod b
[¯] |
12.4 Chinese Remainder Theorem
| Algorithm: |
x := chinese(m1, m2, a1, a2) |
| Input: |
m1,m2,a1,a2 Î
T where 0 £ a1 < m1, 0 £
a2 < m2. |
| Output: |
x Î
T such that x º a1 mod m1 and x º
a2 mod m2 |
|
where 0 £
x < m1·m2 [¯] |
13 Number Theory (nmbrthry.h)
This package requires STL and the compiler must support templates.
13.1 Combinatorics
| Algorithm: |
b := factorial(a) |
| Input: |
a ÎDigit. |
| Output: |
b ÎNatural
such that b = a! [¯] |
| Algorithm: |
c := binomial(a, b) |
| Input: |
a,b ÎDigit. |
| Output: |
c ÎNatural
such that c = (a || b) [¯] |
13.2 Fibonacci Numbers
| Algorithm: |
c := fibonacci(n) |
| Input: |
n ÎDigit. |
| Output: |
c ÎNatural
such that c = Fn |
|
where F0 = 0, F1
= 1, Fk = Fk-1+Fk-2 for k ³
2 [¯] |
13.3 Primes
13.3.1 Constructor
| Algorithm: |
c := Primes() [¯] |
13.3.2 Functions
| Algorithm: |
c := n.firstPrime() |
| Input: |
n ÎPrimes. |
| Output: |
c ÎDigit
such that c = 2 [¯] |
| Algorithm: |
c := n.nextPrime(a) |
| Input: |
n ÎPrimes. |
| Output: |
a ÎDigit,
c Îbool such that if n.primNumber£
n.lastPrime() |
|
then c = true else c
= false [¯] |
| Algorithm: |
c := n.lastPrime() |
| Input: |
n ÎPrimes. |
| Output: |
c ÎDigit
such that c Î \mathbbP [¯] |
| Algorithm: |
c := n.numberOfPrimes(a) |
| Input: |
n ÎPrimes,
a ÎDigit. |
| Output: |
c ÎDigit
such that if a £ n.lastPrime()
then c = p(a) else c = 0 [¯] |
13.4 Primality Tests
| Algorithm: |
c := spsp(b, n) |
| Input: |
b,n Î
T where n º 1 mod 2. |
| Output: |
c Îbool
such that if b(n-1)/2k º 1 mod
n |
|
or $0
£
l < kb(n-1)/2l º -1
mod n then c = true else c = false |
|
where 2k\mid n-1 and
2k+1\nmid n-1 [¯] |
| Algorithm: |
c := MillerRabin(i, n) |
| Input: |
i Îunsigned
int, n Î Natural
where n º 1 mod 2. |
| Output: |
c Îbool
such that if "\mathbbP '
b £ pib(n-1)/2k º
1 mod n |
|
or $0
£
l < kb(n-1)/2l º -1
mod n then c = true else c = false |
|
where 2k\mid n-1 and
2k+1\nmid n-1 and pi is the ith prime [¯] |
| Algorithm: |
c := isprime(a) |
| Input: |
a ÎNatural. |
| Output: |
c Îbool
such that if a Î \mathbbP then c = true
else c = false [¯] |
13.5 Factorization
| Algorithm: |
factoring(a, c) |
| Input: |
a ÎNatural. |
| Output: |
c is a container over Naturals
with an output-iterator
|
|
if a ³
1 then a = Õc.begin() £
i < c.end()*i else c.begin() = c.end(), |
|
for all i Î[c.begin(),
c.end()[, j Î [i, c.end()[ : *i
£
*j [¯] |
13.6 Number-Theoretic Functions
| Algorithm: |
c := euler(a) |
| Input: |
a ÎNatural. |
| Output: |
c ÎNatural
such that c = j(a) : = aÕi
= 0t(1-[1/( pi)]) |
|
where a = Õi
= 0t pini
for t Î \mathbbN, ni Î
\mathbbN+, pi Î
\mathbbP, 0 £ i £
t [¯] |
13.7 Pell's Equation
| Algorithm: |
pell(a, b, c) |
| Input: |
a ÎDigit
where Öa
¹ëÖaû. |
| Output: |
b,c ÎNatural
such that b2 + a·c2 = 1 [¯] |
13.8 Jacobi Symbol
| Algorithm: |
c := jacobi(a, b) |
| Input: |
a,b Î
T where a,b > 0 and 2\nmid b. |
| Output: |
c Î
{-1,0,1} such that c = ([ a / b ])
[¯] |
14 Mathematical Constants (pi.h)
14.1 p
| Algorithm: |
a := Pi(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎPi
such that |a-p·10n|
< 1 [¯] |
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Pi. |
| Output: |
o Îostream
[¯] |
14.2 Öa
| Algorithm: |
a := Sqrt(a, n) |
| Input: |
a ÎDigit,
n Îsize_t. |
| Output: |
b ÎSqrt
such that |b-Ö(a)·10n|<
1 [¯] |
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Sqrt. |
| Output: |
o Îostream
[¯] |
14.3 z(3)
| Algorithm: |
a := Zeta3(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎZeta
such that |a-z(3)·10n|
< 1 [¯] |
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Zeta. |
| Output: |
o Îostream
[¯] |
14.4 exp(1)
| Algorithm: |
a := Exp1(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎExp1
such that |a-exp(1)·10n|
< 1 [¯] |
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Exp1. |
| Output: |
o Îostream
[¯] |
14.5 ln(a)
| Algorithm: |
b := Ln(a, n) |
| Input: |
a ÎDigit,
n Îsize_t. |
| Output: |
b ÎLn
such that |b-ln(a)·10n|
< 1 [¯] |
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î Ln. |
| Output: |
o Îostream
[¯] |
14.6 g
| Algorithm: |
a := EulerGamma(n) |
| Input: |
n Îsize_t. |
| Output: |
a ÎEulerGamma
such that |a-g·10n|
< 1 [¯] |
| Algorithm: |
o := o << a |
| Input: |
o Îostream,
a Î EulerGamma. |
| Output: |
o Îostream
[¯] |
15 Optimization
The following expressions are especially optimized
with a map to an internal function:
-
a = -a, where a Î Integer
or a Î Rational.
-
c += a*b, c -= a*b, where a,c ÎNatural
and b ÎDigit.
-
c += a*b, c -= a*b, where a,c ÎInteger
and b ÎSignDigit.
-
c += a*b, c -= a*b, where a ÎDigit
and b,c ÎNatural.
-
c += a*b, c -= a*b, where a ÎSignDigit
and b,c ÎInteger.
-
a = a+b, a = b+a, where a,b ÎNatural
or a,b ÎInteger.
-
b = a*a, b *= b, where a,b ÎNatural,
a,b ÎInteger
or a,b ÎRational.
-
c = a áopñb,
where a,b,c Î {Natural,
Integer},
áopñÎ
{+,-,*,/,%,&,|,^}.
-
c = a áopñb,
where a,b,c Î Rational,
áopñÎ
{+,-,*,/}.
-
c = a áopñb,
where a,c Î {Natural,
Integer,
Rational},
b Îsize_t, áopñÎ
{ << , >> }.
-
b = ~a, b = -a, where a,b Î Natural
or a,b Î Integer.
-
b = sqrt(a), where a,b Î Natural
or a,b Î Integer.
-
áctñc
= a áopñb,
where áctñÎ
{Natural,
Integer},
a,b,c Îáctñ,áopñÎ
{+,-,*,/,%,&,|,^}.
-
áctñc
= a áopñb,
where áctñÎRational,
a,b,c Îáctñ,áopñÎ
{+,-,*,/}.
-
áctñc
= a áopñb,
where áctñÎ
{Natural,
Integer,
Rational},
a,c Îáctñ,
b Î size_t,áopñÎ
{ << , >> }.
-
áctñb
= ~a, where áctñÎ
{Natural,
Integer},
a,b Îáctñ.
Footnotes:
1
At this moment only available in German language.
2
Needs the Number Theory package.