Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

13. Reprise:  Syntax and Data Types

Last revision:  September 12 1996

In this lesson we take a break from our long march of new functions and
consider some basic programming language topics: operator associativity and
machine precision.

Operator Associativity

We learned at the beginning of the course that Mathematica interprets some
operations as having precedence over others, such as multiplication over
addition.  In this way Mathematica can begin to parse an expression, which
is to say to decide which parts of it to execute first.  A moment's thought
about how to order the operations in an expression, however, leads one to
the conclusion that knowing precedence is not enough.  What if, for
example, there are several of the same operation in a row, as in "2 + 3 +
2" or "2 ^ 3 ^ 2"?  In the first case, we know that addition is
associative, so that it does not matter whether Mathematica chooses to
evaluate "(2+3)+2" or "2+(3+2)".  However, for exponentiation, it surely
makes a difference:  "(2^3)^2" evaluates to 8^2=64, while "2^(3^2)"
evaluates to 2^9=512. Every operator in Mathematica, or any other language,
must have its associativity specified, i.e., how a sequence of values,
consecutively joined by such an operator, should be parenthesized.
Operators are typically either left-associative or right-associative;
left-associative operators group (or parenthesize) from the left (so that
"2+2+2+2" becomes "((2+2)+2)+2"), while right-associative operators group
from the right (so that "2^3^2" becomes "2^(3^2)").

Left-associative operators which we have considered are subtraction ("-"),
division ("/"), the function-call operator ("[.]"), and the part-extraction
operator ("[[.]]").  Right-associative operators we have considered include
exponentiation ("^"), the boolean not operator ("!"), and the assignment
operator ("=").  For many other operators in Mathematica, the associativity
is irrelevant because the operations are mathematically associative: one
can parenthesize values connected by such operators in any way and end up
with the same answer, such as addition ("+"), multiplication ("*"), the
boolean and operator ("&&"), and the boolean or operator ("||").

At first glance, one might wonder why all operators are not
left-associative.  For an example of why an operator should be
right-associative, we consider the most important right-associative
operator, namely, the assignment operator "=".  The assignment operator is
right-associative so that one can assign one value to several variables, as
in the statement "a = b = 3".  It works as follows:  since "=" is
right-associative, the expression is grouped as "a=(b=3)", the
subexpression "b=3" is evaluated (which sets "b" to "3" and returns the
value 3), and then the expression "a=3" is evaluated, setting "a" to the
value "3".  If it were left-associative, the evaluation would be otherwise:
the grouping would be "(a=b)=3", so "a=b" would be evaluated (and "a"
would be assigned the value "b"), and then, since "b" was the return value
of "(a=b)", the expression "b=3" would be evaluated.  At the end, then, "b"
would have the value "3" and "a" would have the old value of "b", which is
not a behavior we would like.

Machine-Precision Numbers

Recall that Mathematica separates numbers into two categories: exact
(Integers, Rationals, and any other data type using which it is possible to
represent a number exactly) on one hand, and numerical approximations on
the other, in which the precision is limited and implicitly specified (such
as a Real number which, for all Mathematica knows, is only an approximation
up to the number of digits you specified:  1.0 approximates some number
which is less than 0.5 away from 1.0).  Numbers can also be separated
according to whether or not they are machine-precision.  On most computers,
there are special internal data types called machine-precision integers and
machine-precision approximations, and we cover these data types because in
most programming languages, the numbers that a programmer works with must
be machine-precision.  There is a significant advantage to using
machine-precision numbers: computers can manipulate and compute with these
numbers much more quickly than with those which are not machine-precision.
Mathematica does a yeoman's job of masking this distinction, making us
believe that all numbers, regardless of size, are easily to manipulate, but
this is not really true!

Machine-Precision Integers

Each computer, be it an IBM-compatible personal computer, a Hewlett-Packard
workstation, or a Cray supercomputer, has a certain size of integers that
it can store and manipulate easily.  Since computers represent integers
using bits, which are binary digits taking only the values zero and one, we
consider the size of an integer to be the number of bits required to
represent it in base 2.

What is "base 2"?  Our number system is base 10, by which we mean that when
we write down a number, the place values (from right to left) are 1s, 10s,
100s, 1000s, and so on. Thus the number 345 means (thinking right-to-left)
5+4*10+3*100 or (thinking left-to-right) 3*100+4*10+5.  In base 2, the
place values are similarly powers, but are, instead of powers of 10, powers
of 2:  1s, 2s, 4s, 8s, 16s, and so on.  Thus the number 1001 in base 2
means (thinking right-to-left) 1+0*2+0*4+1*8 or (thinking left-to-right)
1*8+0*4+0*2+1.  Notice that in base 10 we have the digits 0 through 9; in
base 2, the only digits allowed are 0 and 1.  From mathematics class we
know that any integer can be written in base 10 or base 2, and, in fact,
Mathematica has a command that turns a normal number (written in base 10)
into its base 2 form:  "IntegerDigits[ ... ,2]".  For instance,
"IntegerDigits[10,2]" gives the base 2 representation of the number of
fingers on our hands.

IntegerDigits[10,2]

Note that four bits were necessary, since 10=1*2^3+0*2^2+1*2+0.  How large
a number could a computer represent if it allowed 4 bits?  Well, the
maximum number would be derived by choosing every digit to be the largest
possible, which in this case is to make every digit a 1.  We find then that
the largest 4-bit base 2 number is 1*2^3+1*2^2+1*2+1 (taking all of the
bits to be 1), which is 15.  There is a formula to compute the largest
integer expressible by using "n" bits:  "(2^n)-1".  If a computer allows
"n"-bit integers, and we use all of the bits for the base 2 representation
of an integer, then we could represent the integers from 0 to "(2^n)-1".

However, most computer users have a use for negative numbers also.  In
order to signal whether or not an integer is positive or negative, we can
devote to an indication of the sign:  if the designated bit is zero, the
integer is positive, while if the designated bit is one, then the integer
is negative.  Hence, if we had 4 bits and used one for the sign bit, then
the largest positive integer would be 2^3-1, or 7.  What would the largest
negative number be?  We could form the largest positive number and then use
the sign bit to indicate that it is negative, yielding  "-(2^(n-1)-1)",
where "n" is the number of total bits, counting the sign bit.  Putting
these two facts together, if a computer represents integers with "n" bits,
counting the sign bit, then the range of integers expressible is
-(2^(n-1)-1) to (2^(n-1))-1.

(The attentive reader will notice that we have 2^n possible values with "n"
bits, and if we have 2^(n-1)-1 positive numbers, 2^(n-1)-1 negative
numbers, and a value representing zero, we still have one pattern of bits
left over, namely all zeros with the sign bit turned on.  Different
computer processors evaluate this number differently, and for our purposes
we ignore this discrepancy.)

Machine-Precision Approximations

The range of integers that a computer can easily store exactly is quite
limited, as the preceding section should have convinced you.  However,
computers are widely used to handle much larger numbers--albeit with an
accuracy trade-off. Recall from high school how numbers are represented in
scientific notation:  "x.xxxxx * 10^y". Instead of restricting the range of
values of an integer, computers can restrict the number of digits of
precision of a numeric approximation such as "x.xxxx * 10^y", as well as a
power of ten with which to multiply the number.  Computers usually allow a
fixed number of digits (actually, a fixed number of bits) for the mantissa
(the part with x's) and a fixed number of digits (actually, a fixed number
of bits) for the exponent (the y). The number 2.5, for instance, has
mantissa 2.5 and exponent 0; the number 0.00001234 has mantissa 1.234 and
exponent -5.  Similarly, the number 123400000 has mantissa 1.234 and
exponent 6.  As you might imagine, if the number in question has more
significant digits than a mantissa will allow, then the computer can only
store an approximation.  For instance, suppose the mantissa is allowed to
be no greater than 5 decimal digits.  Then the computer in question could
not distinguish between 1234567890000 and 1234567899999, since each would
be stored as 1.2345 * 10^12.

We can ask Mathematica the largest positive and smallest positive numbers
that the computers we are using can handle:

$MinMachineNumber

gives the smallest positive number, while

$MaxMachineNumber

gives the largest positive number.

To ask how many decimal digits the machine keeps in a machine-precision
approximation, we ask Mathematica to evaluate the following:

$MachinePrecision