Examples
User documentation
Here is a collection of basic operations available for integer values;
see also the more advanced functions in NumTheory
.
CoCoALib functions which expect integer values will accept either
machine integer values or BigInt
values -- they may be mixed. The
return type is usually BigInt
; the few cases where the return type
is long
are clearly indicated. Remember that basic arithmetic
operations between two machine integers are handled directly by C++
(with its rules and restrictions e.g. overflow).
If you want to write new functions which accept machine integers as
arguments, take a look at the class MachineInt
which is designed
for this purpose (handling both signed and unsigned machine integers
safely).
Queries
IsEven(n)
-- true iffn
is evenIsOdd(n)
-- true iffn
is oddIsPowerOf2(n)
-- true iffn
is a power of 2IsDivisible(n,d)
-- true iffn
is divisible byd
(throwsERR::DivByZero
ifd
is zero)IsSquare(n)
-- true iffn
is a perfect squareIsPower(n)
-- true iffn
is a perfect k-th power for some k > 1IsExactFloorRoot(X,n,r)
-- true iffn
is a perfectr
-th power, assignsFloorRoot(N,r)
toX
; error ifn < 0
or ifb < 1
Only for BigInt
IsZero(N)
-- true iffN
is zeroIsOne(N)
-- true iffN
is 1IsMinusOne(N)
-- true iffN
is -1
Operations
Infix operators
- normal arithmetic (potentially inefficient because of temporaries)
=
assignment+
the sum-
the difference*
the product/
integer quotient (truncated "towards zero")%
remainder (same sign as quotient if non-zero); satisfies a = b*(a/b)+(a%b); see alsoLeastNNegRemainder
andSymmRemainder
(below)
NOTE: you cannot use ^
for exponentiation; you must use the function power
instead. We decided this
because it is too easy to write misleading code: for instance,
a*b^2
is interpreted by the compiler as (a*b)^2
. There is no
way to make the C++ compiler use the expected interpretation.
- arithmetic and assignment
- arithmetic ordering
==
,!=
<
,<=
,>
,>=
-- comparison (using the normal arithmetic ordering) -- see also thecmp
function below.
- increment/decrement
++
,--
(prefix, e.g.++a
) use these if you can++
,--
(postfix, e.g.a++
) avoid these if you can, as they create temporaries
cmp
(three way comparison)
cmp(a, b)
-- returns anint
which is< 0
,== 0
, or> 0
ifa < b
,a == b
, ora > b
respectivelyCmpAbs(a,b)
-- same ascmp(abs(a),abs(b))
but might be faster.
Sundry standard functions
IMPORTANT NOTES
The arguments of the functions below may be either a machine integer or a BigInt
.
abs(n)
-- the absolute value ofn
sign(n)
-- returnsint
with value -1 ifn<0
, 0 ifn==0
, and +1 ifn>0
LeastNNegRemainder(x,m)
-- least non-negative remainder; throwsERR::DivByZero
ifm==0
; result islong
ifm
is a machine integerSymmRemainder(x,m)
-- symmetric remainder; throwsERR::DivByZero
ifm==0
; result islong
ifm
is a machine integerlog(n)
-- natural logarithm ofn
(as adouble
); error if `` n <= 0``LogAbs(n)
-- equiv tolog(abs(n))
RoundDiv(n,d)
-- rounded division ofn
byd
, (currently halves round away from 0)MultiplicityOf2(n)
-- return along
being the multiplicity of 2 dividingn
; error ifn==0
.FloorSqrt(n)
-- the integer part (floor) of the square root ofn
FloorLog2(n)
-- same asFloorLogBase(n,2)
FloorLog10(n)
-- same asFloorLogBase(n,10)
FloorLogBase(n,b)
-- (returnslong
) the integer part (floor) oflog(abs(n))/log(b)
; error ifn=0
orb<2
SmallPower(a, b)
-- (returnslong
) returnsa
to the powerb
(error ifb<0
; no check for overflow)
These functions always return BigInt
power(a, b)
-- returnsa
to the powerb
(error ifb<0
);power(0,0)
gives 1factorial(n)
-- factorial for non-negativen
primorial(n)
-- primorial for non-negativen
LogFactorial(n)
-- approx natural log offactorial(n)
(abs.err. < 5*10^(-8))RangeFactorial(lo,hi)
--lo*(lo+1)*(lo+2)*...*hi
NB both limits are included!binomial(n, r)
-- binomial coefficientfibonacci(n)
--n
-th Fibonacci numberFloorRoot(N,r)
-- floor of ther
-th root ofN
(error ifN < 0
or ifr<2
); see alsoIsExactFloorRoot
Conversion functions
Only for BigInt
mantissa(N)
--N
represented as a floating-point number. IfN
is zero, produces 0.0. IfN>0
, produces a value between 0.5 and 0.999...; otherwise (whenN<0
) a value between -0.5 and -0.999... The bits of the floating point result are the topmost bits of the binary representation ofN
.exponent(N)
-- result is along
whose value is the least integer e such that 2^e > abs(n). IfN
is zero, result is zero.
Miscellany
Only for BigInt
SizeInBase(N, b)
-- (returnslong
) the number of digitsN
has when written in baseb
. Very fast! WARNING the result may sometimes to be too large by 1; use1+FloorLogBase(N)
to get the exact result.
Procedures for arithmetic
These procedures are ugly but may give a slight gain in speed. Use them only if you really must; it is probably better to use GMP directly if speed is so very important.
We expect these procedures (except quorem
) to become obsolete
when CoCoALib upgrades to the C++11 standard.
Assignment is always to leftmost argument(s) a
, a BigInt
.
Second and/or third argument of type BigInt
.
add(a, b, c)
-- a = b+csub(a, b, c)
-- a = b-cmul(a, b, c)
-- a = b*cdiv(a, b, c)
-- a = b/c (truncated integer quotient)mod(a, b, c)
-- a = b%c (remainder s.t. b = quot*c + rem)quorem(a, b, c, d)
-- same as a = c/d, b = c%ddivexact(a, b, c)
-- a = b/c (fast, but division must be exact)power(a, b, c)
-- a = b^c, where 0^0 gives 1neg(a, b)
-- a = -babs(a, b)
-- a = abs(b)
Error Conditions and Exceptions
Error conditions are signalled by exceptions. Examples of error conditions
are impossible arithmetic operations such as division by zero, overly large
arguments (e.g. second argument to binomial must fit into a machine
long
), and exhaustion of resources.
Currently the exception structure is very simplistic:
- exceptions indicating exhaustion of resources are those from the system, this library does not catch them;
- all other errors produce a
CoCoA::ErrorInfo
exception; for instance
ERR::ArgTooBig |
value supplied is too large for the answer to be computed |
ERR::BadArg |
unsuitable arg(s) supplied (or input number too large) |
ERR::BadNumBase |
the base must be between 2 and 36 |
ERR::BadPwrZero |
attempt to raise 0 to negative power |
ERR::DivByZero |
division by zero |
ERR::ExpTooBig |
exponent is too large |
ERR::IntDivByNeg |
inexact integer division by a negative divisor |
ERR::NegExp |
negative exponent |
ERR::ZeroModulus |
the modulus specified is zero |
Maintainer Documentation
The implementation of cmp
is more convoluted than I'd like; it must
avoid internal overflow.
The implementation of RoundDiv
was more difficult than I had expected.
Part of the problem was making sure that needless overflow would never
occur: this was especially relevant in the auxiliary functions
uround_half_up
and uround_half_down
. It would be nice if a
neater implementation could be achieved -- it seems strange that the
C/C++ standard libraries do not already offer such a function. The
standard C functions lround
almost achieves what is needed here, but
there are two significant shortcomings: rounding is always away from zero
(rather than towards +infinity), and there could be loss of accuracy if
the quotient exceeds 1/epsilon. There is also a standard function ldiv
which computes quotient and remainder, but it seems to be faster to compute
the two values explicitly.
NOTE: if you change rounding of halves, you must change TWO fns (RoundDiv
for machine ints and RoundDiv
for big ints).
Bugs, shortcomings and other ideas
The power functions could allow high powers of -1,0,1 (without complaining about the exponent being too big). But is it worth it?
Only partial access to all the various division functions offered by the C interface to GMP. Many other GMP functions are not directly accessible.
IsExactFloorRoot
has rather a lot of signatures.
Main changes
2019
- April
- renamed
iroot
toFloorRoot
(and only for non-negatives!) - renamed
IsExactIroot
toIsExactFloorRoot
(and only for non-negatives!) 2014
- renamed
- March
- clarified that 0^0 gives 1 2012
- May (v0.9951):
- moved common operations on
BigInt
andMachineInt
together intoIntOperations
-
- moved common operations on