Numbers and Math

This section covers mathematical expressions and number types in Amzi! Prolog

  • Evaluating Mathematical Expressions
  • Mathematical Comparisons
  • Mathematical Operators
  • Bitwise Operators
  • Trigonometry Functions
  • Mathematical Functions
  • Built-in Mathematical Atoms
  • Numeric Type Testing
  • Mixed Mode Expressions
  • Mathematical Games

    • Evaluating Mathematical Expressions

    The various math symbols, such as + - * /, are defined as operators in Prolog. See section on operators for discussion of operators in Prolog. This means you can write expressions such as:

    As such, these are just Prolog structures, no different from any other structures represented using operator syntax.

    In other words, for most Prolog processing, the term 3 + 2 (internally +(3,2)) is treated no differently than say pet(duck,leona).

    To evaluate mathematical expressions, you need the built-in predicate is/2. The mathematical comparson operators also do mathematical evaluation.

    X is Y

    is/2 succeeds if X can be unified with the value of Y evaluated as an arithmetic expression.

    ==>Note that there is no 'assignment' in Prolog, and variables always unify, so you cannot say X is X + 1 because it is impossible for the two Xs to unify. You can say XX is X + 1, and proceed to use the new variable.

    Mathematical Comparisons

    Each of the following operators first performs mathematical evaluation of both sides, as described above, and then does a mathematical comparison of the results. These operators should be used for comparing numbers, even if they are not part of an expression.

    Unification, either implicit between goals and heads of clause, or explicit with =/2, may fail for different numeric types that represent the same number. For this reason unification should NOT be used to test for equality of two numbers.

    Examples

    X >= Y

    Evaluate each side and test for greater or equal.

    X =< Y

    Evaluate each side and test for less than or equal.

    X > Y

    Evaluate each side and test for greater than.

    X < Y

    Evaluate each side and test for less than.

    X =:= Y

    Evaluate each side and test for numerical equality.

    X =\= Y

    Evaluate each side and test for numerical inequality.

    X ~= Y

    Evaluate each side and test if the two sides are almost equal. Useful for comparing non-integer values.

    Mathematical Operators

    There are a number of mathematical operators that can be used in evaluable mathematical expressions.

    X + Y

    Sum of values of X and Y.

    X -  Y

    Value of X minus value of Y.

    -  X

    Evaluates to the negative of X evaluated.

    X * Y

    Value of X multiplied by value of Y.

    X /  Y

    Value of X divided by value of Y.

    X ** Y

    Evaluates to X raised to the Y power. When X is a fractional real (infinite precision) number, the precision of the result is limited by the Prolog flag, epsilon.

    X // Y

    Integer division of X by Y means the result is truncated to the absolute integer.

    X divs Y

    Integer division with a rounded rather than truncated answer, or more formally, such that the remainder is >= -Y/2 and < Y/2.

    X divu Y

    Integer division that is truncated. Works the same as // for positive integers, but for negative ones it ensures that the result times Y is less than X, or stated another way, the remainder is always positive.

    max(X,Y)

    The maximum of X and Y.

    min(X,Y)

    The minimum of X and Y.

    X mod Y

    The positive remainder after dividing the value of X by the value of Y. Corresponds with divu.

    X mods Y

    The remainder after rounded integer division (divs), or more formatlly, constrained so that the result is >= -Y/2 and < Y/2.

    X modu Y

    The remainder, constrained so that the result is positive, corresponding to divu.

    Bitwise Operators

    For the following bitwise operators the arguments must be integers.

    X /\  Y

    Bitwise "and" of value of X and value of Y.

    X \/  Y

    Bitwise "or" of value of X and value of Y.

    X << Y

    Evaluates to X bit-shifted left by Y places.

    X >> Y

    Evaluates to X bit-shifted right by Y places.

    \ X

    Evaluates to the bitwise complement of X (i.e., all those bits which were 1 become 0 and vice versa).

    X xor Y

    Evaluates to X exclusively or'd with Y.

    Trigonometry Functions

    The trigonomety functions all work with radians. You can use the built-in constants, degtorad and radtodeg to convert from radians to degrees and back.

    The trigonometry functions all work internally using double precision floating point numbers. If the 'decimals' Prolog flag is set to 'real', then the answer is converted to a real, but there will only be 15 digits of accuracy.

    sin(X)

    sin evaluates to the sine of X (in radians).

    cos(X)

    cos evaluates to the cosine of X (in radians)

    tan(X)

    tan evaluates to the tangent of X (in radians).

    asin(X)

    asin evaluates to the angle (in radians) whose arcsine is X.

    acos(X)

    acos evaluates to the angle (in radians) whose arccosine is X.

    atan(X)

    atan evaluates to the angle (in radians) whose arctangent is X.

    Mathematical Functions

    abs(X)

    abs evaluates to the absolute value of X.

    ceiling(X)

    ceiling evaluates to the smallest integer >= X.

    exp(X)

    exp evaluates to e raised to the power of X evaluated.

    float(X)

    float converts X to a double precision floating point number.

    floor(X)

    floor evaluates to the largest integer =< X.

    integer(X)

    integer converts X to an integer (truncating any fractional part).

    ln(X), log(X)

    ln and log both evaluate to the natural log (loge()) of X evaluated. Use log10(X) for log base 10.

    log10(X)

    log10 evaluates to the natural log (loge()) of X evaluated. Use log10(X) for log base 10.

    real(X)

    real converts X to a real number.

    round(X)

    round rounds X to the nearest integer and returns that value.

    sign(X)

    sign evaluates to 1 for positive numbers and -1 for negative numbers.

    sqrt(X)

    sqrt evaluates to the square root of X. When X is a real (infinite precision) number, the fractional precision is limited by the setting of the Prolog flag, epsilon.

    Built-in Atoms

    There are a number of built-in atoms, which have predetermined values that can be used in arithmetic expression.

    cpuclock
    A an integer with the number of milliseconds ticks expired. It is useful for timing functions, for example: 
    ?- T1 is cpuclock, dothing, T is (T1 - cpuclock)/1000, write(time:T).
    The predicate timer/1 provides a similar function.
    cputime
    A floating point number with the number of CPU seconds expired. It is useful for timing functions, for example: 
    ?- T1 is cputime, dothing, T is T1 - cputime, write(time:T).
    The predicate timer/1 provides a similar function.
    e
    The value "e" (2.718281828459045)
    pi
    The value "pi" (3.141592653589793)
    inf
    A value representing a floating point number larger than the largest possible representation, displayed as 1.#INF.
    ?- X is inf.
	X = 1.#INF
    degtorad
    The constant for converting degrees to radians, useful for trig functions. 2*pi/360.
    radtodeg
    The constant for converting radians to degrees, useful for trig functions. 360/2*pi.
    random
    A random floating point number >= 0.0 and < 1.0. For example, here's how to generate random rolls of 6-sided dice:
    ROLL is integer( random*6 + 1 )
    The seed (start) of the random sequence is always the same, but you can change it using seed_random/1. See below.

    seed_random(I)

    seed_random/1 is a predicate that seeds the random number generator with an integer argument. Random numbers, by default, always start from the same seed. This is often good for generating repeating test runs of an application. But non-test use of the program might require different random sequences each time. Here is one way to generate a unique seed at the start of a program:

    Number Types

    Internally, Amzi! uses five types of numbers (see overview):

    Only one type of float is used in a session, either single or double, depending on how the Prolog flag, floats, is set. Single precision floats can be stored in an internal Prolog cell, which is efficient, whereas double precision floats require their own storage.

    Both types of reals are used. The fixed reals are just a special case of a real that can fit into an internal Prolog cell, which is more efficient, rather than requiring its own storage.

    The following predicates that can be used for type testing of numbers.

    numeric_type(N,T)

    numeric_type/2 returns the type, T, of the number N. The type returned can be: integer, single_float, double_float, float, fixed_real, long_real, real. On backtracking, both the specific and more general types will be returned.

    numeric_type/2 fails if N is not a number, or if T is specified with the wrong type.

    Here is an example, showing the use of the Prolog flags, decimals and floats, and numeric_type.

    integer(N)

    integer/1 succeeds if N is of numeric type 'integer'. Note that integer/1 is a type test. To test if a decimal number is mathematically an integer, use is_integer/1.

    is_fraction(N)

    is_fraction/1 succeeds if N is mathematically a fraction.

    is_integer(N)

    is_integer/1 succeeds if N is mathematically an integer, so both 3 and 3.0 succeed as arguments.

    is_odd(N)

    is_odd/1 succeeds if N is mathematically an odd number.

    is_number(N)

    is_number/1 succeeds if N is a number.

    float(N)

    float/1 succeeds if N is of numeric type 'float', either single or double.

    single_float(N)

    single_float/1 succeeds if N is of numeric type 'single_float'.

    double_float(N)

    double_float/1 succeeds if N is of numeric type 'double_float'.

    real(N)

    real/1 succeeds if N is of numeric type 'real', either fixed or long.

    fixed_real(N)

    fixed_real/1 succeeds if N is of numeric type 'fixed_real'.

    long_real(N)

    long_real/1 succeeds if N is of numeric type 'long_real'.

    Mixed Mode Expressions

    Mixed mode expressions, involving integers and/or floats and/or reals, will promote the result to the more complex type. This means that the result of an expression will only be an integer if all the variables are integers, and any functions called can return an integer. Some functions, such as trigonometric ones, can only return floating point or real values.

    Mathematical expressions involving reals will always see if the answer can be stored as a fixed real instead of as a long real.

    Mathematical expressions involving floats are always calculated using double precision, but the result is stored as either single or double depending on the setting of the Prolog flag, 'floats'.

    Mixed mode involving floats and reals will promote to whichever one is specified as the default in the 'decimals' Prolog flag.

    Mathematical Games

    Thanks to our resident mathematician, Ray Reeves, there are a number of features in Amzi! Prolog designed for mathematical experimentation. Many of these are illustrated in his library of samples, ChezRay. Other comments follow:

    Modulo Arithmetic

    Using arithmetic on the domain of integers (Z) it is a straightforward matter to perform calculations that do not involve numbers exceeding 32 bits (including the sign bit). However, many expressions involve the quotient of two integers and even though the sought-for solution is within that range the sub-expressions may exceed it. That is where modulo arithmetic comes in.

    It may come as a suprise to hear that if all calculations are performed modulo some prime (domain Zm) and the true solution is less than that prime then the result will be the same.

    To this end, Amzi! Prolog has a 'modulo' flag which defaults to zero but can be set to some integer. If it is set to integer M not zero then the arithmetic operations +, -, * will be performed modulo M. You will notice that // was not included among those operators. This is because when M is prime the operations are being performed on an integer ring, and for every element in that ring there is a unique inverse. Multiplying a number by it's inverse corresponds to division in Z arithmetic.

    Built in to Amzi! Prolog is a set of primes which are as large as possible and of a particularly useful form for abstract fourier transforms, called fourier primes.

    fourierPrime(Index, Prime)

    At present, the Index runs from 1 to 11, the highest first. The inverse of an element E is found with the (bilateral) primitives:

    inverse(E, M, Inverse)
inverse(E, Inverse)

    In the second case the modulo flag value is used for M.

    Some typical applications of the method are nPr/2, nCr/2, mS1r/2 and mS2r/2 from my integer library, which count permutations, combinations and subsets. It is also used in the solution of simultaneous equations with integer coefficents, by means of determinants.

    If the solution itself is not within the 32-bit range the method can still be used with a set of primes, and from the set of solutions so obtained the Chinese Remainder Algorithm (cra) can be used to find the large unique solution. This works provided the product of the primes employed is greater than the solution, which in turn requires some insight into the probable result.

    To avoid that there is a cra which increments the prime set automatically until redundancy is detected. The primes are drawn from the set of fourier primes. When the result is large it cannot be denoted by a single integer, so it is presented as a list of gigadigits, which are integers less than 1 billion.

    Each gigadigit represents nine decimal digits, and if there are less than that a padding of prefixed zeroes is implied. This format is used because it conforms to a denotation of a 'real' integer, which is a new data type that Amzi! supports for large numbers. Thus the cra can be embedded in real data expressions, if required, or simply printed out in a real number format.

    Notes on Reals and Gigadigits

    Amzi! Prolog allows arithmetic of high precision. Real numbers are kept in a non-standard floating point format with a mantissa and exponent. The mantissa is an integer in an array of up to 2048 32-bit gigadigits. The exponent is a signed integer in twelve bits.

    For fun, run the following program which goes forever calculating factorials of increasingly large numbers. You'll need to [CTRL-Break] to end it. Note that the G exponents refer to 9 zeroes, not one, 1g1 is 1.0e9.

    main :-
  go(1,1).

go(N,T) :-
  write(N:T), nl,
  NN is N + 1,
  TT is T * NN,
  go(NN, TT).

    A real number is said to be normalized if there are no leading zeros and no trailing zeros in the mantissa, unless the real number is actually zero. The result of any real arithmetic operation is normalized.

    The base of the exponentiation is 1,000,000,000 (1 billion), so the numbers in the exponent are typically small. It's purpose is to efficiently pack large numbers with leading or trailing gigadigits that are zeroes.

    A gigadigit is a positive integer less than 1 billion. Think of the decimal digits in the denotation as the name of that gigadigit. There are 1 billion names.

    Gigadigits do not totally exploit 32-bit words but this has practical advantages because they facilitate the interface between decimal numbers and 32-bit words. Given an ordinary arithmetic number, each block of nine decimal digits in either direction from the decimal point denotes a gigadigit. Conversely, displaying a real number is just a concatenation of the displays of the individual digits.

    Generally, familiar integer operations will work on real integers, but 'for' (and maybe other things) have a limited range of 1 gigadigit.

    Integers and floats are still supported in addition to reals and are denoted the same way as before, but denotation of a number beyond the range of an integer will automatically produce a real. Integer or float denotions ending in 'G' will also produce a real.

    In addition, there is an exponential notation using the letter 'g' to denote reals. Thus 1g-1 denotes 0.000000001, and 1g2 succintly denotes 1 000000000 000000000.

    A real number may also be denoted by a prolog list of gigadigits (bounded integers) and optionally containing a decimal point ('.'), and optionally containing a leading negative sign ('-'). The advantage is that no leading (decimal) zeroes in the gigadigits are required or displayed.

    Real numbers are normally displayed in ordinary arithmetic style, with no punctuation or spaces. However, display/1 will display them as lists, so that long numbers are more easily read. Remember that each element in such a list denotes nine decimal digits, so if less than that are displayed then there are implicit leading zeros. eg: 

    display([1,1]*[1,1]). 
[1,2,1] % ie: 1000000002000000001

    As always, integer/1 succeeds only if the argument is of type integer. real/1 is a predicate that succeeds if the argument is of type real. To determine if a number (real, float or integer) is a mathematical integer use is_integer/1. is_fraction/1 is a predicate that succeeds if the argument is of type real (or float) and it's exponent is negative.

    Real bit operations are limited to xor, but the predicate is_odd/1 will check the last bit of an integer or real in column zero.

    Real number division can produce an infinite length, so the quotient length is limited to: length(num) + length(denom) + delta where delta is the current value of the set_prolog_flag delta (initially 2). ie. the precision of the quotient is limited to the precision of the given arguments plus delta.

    truncate/2 attempts to derive a real from a real with reduced length such that the new exponent is not less than that defined by the set_prolog_flag epsilon (initially -2). However, it will not reduce the number of gigadigits to be less than two. The main purpose of epsilon is to provide the user with a stopping criterion when generating convergent series.

    Mixed mode arithmetic involving a real and an integer or float works by internally promoting all operands to reals, if necessary. There are explicit integer_real/2 and float_real/2 bilateral primitives for the user. Note: converting from real to integer or float may not succeed.

    It is anticipated that real arrays may be useful beyond real number representation, and then a way of indexing into the array may be needed. The tool for this purpose is:

    nth(Index, Real, Gigit)

    For example:

    ?- nth(1, 234093420983203.24309823409823490823409g, X). 
    X = 234090000

    The internal format of a real array is:

    Descriptor, LSG, ... , MSG
0,          1,         Length

    where Descriptor is packed with Exponent, Sign and Length, LSG is the least significant mantissa gigadigit, MSG is the most significant mantissa gigadigit.

    Thus, in nth, the acceptable range of Index for gigadigits is the closed interval 1 to Length, and Index == 0 gets the Descriptor. nth/3 can also be applied to lists. Descriptor may be unpacked with: realDescr(Descriptor, Length, Exponent, Sign).

    Prime Numbers

    makeprimes(N)

    Generates offline array of primes up to N.

    Each new allocation will free any old one, so prime is a unique array that needs no handle to access.

    primes(LastIndex, HighPrime)

    HighPrime is the prime at the LastIndex of the prime array.

    prime(Index, Prime)

    Prime is the prime at the Index of the prime array.

    isPrime(P)

    Naive test for prime, using asserted prime array.

    primeFactors(N, F)

    Naive trial and error factoring using prime array.

    F is a list of the prime factors of N, in the form: [P**Exponent, ... ]. 

    ?- primes(20).
    ?- M = 2130706433, M1 is M - 1, primeFactors(M1,X).
    X = [2 ** 24,127 ]

    Rational Numbers

    These built-in predicates support rational number arithmetic, where a rational number is represented by a numerator and denominator using the '/' operator. The predicates always return the simplest form of the rational number.

    prodq/3 - can be used to multiply or divide rational numbers. The first two arguments are the multiplicands, the last the product. At least two of the three must be bound to either a rational or integer number.

    sumq/3 - can be used to add and subtract rational numbers.

    compareq/3 - compares rational numbers for testing. The first two arguments are the rational numbers, the third is an operator indicating the results of the comparison.

    Examples:

    ?- prodq(2/3,1/2,X).
X = 1/3 
yes
    
?- prodq(X,1/2,1/3).
X = 2/3 
yes
    
?- prodq(1/2,X,1/3).
X = 2/3 
yes
    
?- prodq(16/32,32/64,X).
X = 1/4 
yes
    
?- compareq(2/3,4/6,OP).
OP = = 
yes
    
?- compareq(2/3,1/2,OP).
OP = > 
yes
    
?- compareq(2/3,4/6,>).
no

    ?- sumq(2/3,5/6,X).
X = 3/2 
yes

    ?- sumq(X,5/6,3/2).
X = 2/3 
yes

    Continued Fractions

    A simple continued fraction of length n may be denoted by a Prolog list of integers in the following form:

    [cf, a0, a1, ... an]

    The atom cf is there to distinguish the cf list from an evaluable list of gigadigits.

    A continued fraction can be produced from a rational fraction q by q_cf/2 , which is a bilateral relationship.

    Irrational numbers may be represented by infinite continued fractions which repeat over the last p integers, where p is the length of the periodic part. Therefore they can be finitely represented. This is done here by denoting the periodic part as a sub-list:

    [cf, a0, a2, ... [p0, p1, ...]]

    The program rootn.pro denotes the irrational square roots of non-square integers up to 50, in this way with sqrtcf/2. This can be transformed to a rational with q_cf and the rational evaluated as decimal with is.

    Since the evaluation of a periodic continued fraction does not terminate we use the prolog flag epsilon to determine the desired precision. Be aware that the above procedure will be an approximation limited by epsilon and so the user should call truncate/2 (which also consults epsilon) on the result to extract the valid part.

    Copyright ©1987-2011 Amzi! inc. All Rights Reserved. Amzi! is a registered trademark and Logic Server is a trademark of Amzi! inc.