38  PART 7: ARITHMETIC WITH SCALED DIMENSIONS  TEX82 §99

99. Arithmetic with scaled dimensions. The principal computations performed by TEX are done entirely in terms of integers less than 2^{31} in magnitude; and divisions are done only when both dividend and divisor are nonnegative. Thus, the arithmetic specified in this program can be carried out in exactly the same way on a wide variety of computers, including some small ones. Why? Because the arithmetic calculations need to be spelled out precisely in order to guarantee that TEX will produce identical output on different machines. If some quantities were rounded differently in different implementations, we would find that line breaks and even page breaks might occur in different places. Hence the arithmetic of TEX has been designed with care, and systems that claim to be implementations of TEX82 should follow precisely the calculations as they appear in the present program.

(Actually there are three places where TEX uses div with a possibly negative numerator. These are harmless; see div in the index. Also if the user sets the or the to a negative value, some diagnostic information will involve negative-numerator division. The same remarks apply for mod as well as for div.)

100. Here is a routine that calculates half of an integer, using an unambiguous convention with respect to signed odd numbers. function half (x : integer ): integer ;

begin if odd (x) then half ← (x + 1) div 2

else half ← x div 2;

end;

101. Fixed-point arithmetic is done on scaled integers that are multiples of 2^{−16}. In other words, a binary point is assumed to be sixteen bit positions from the right end of a binary computer word.

define unity ≡ ´ 200000 { 2^{16}, represents 1.00000 }

define two ≡ ´ 400000 { 2^{17}, represents 2.00000 } ⟨ Types in the outer block 18 ⟩ +≡

scaled = integer ; { this type is used for scaled integers }

nonnegative integer = 0 . . ´ 17777777777 ; { 0 ≤ x < 2^{31} }

small number = 0 . . 63; { this type is self-explanatory }

102. The following function is used to create a scaled integer from a given decimal fraction (.d_{0}d_{1} … d_{k−1}), where 0 ≤ k ≤ 17. The digit d_{i} is given in dig [i], and the calculation produces a correctly rounded result. function round decimals (k : small number ): scaled ; { converts a decimal fraction }

var a: integer ; { the accumulator }

begin a ← 0;

while k > 0 do begin decr (k); a ← (a + dig [k] ∗ two) div 10; end;

round decimals ← (a + 1) div 2;

§103  TEX82  PART 7: ARITHMETIC WITH SCALED DIMENSIONS 39

end; 103. Conversely, here is a procedure analogous to print int . If the output of this procedure is subsequently read by TEX and converted by the round decimals routine above, it turns out that the original value will be reproduced exactly; the “simplest” such decimal number is output, but there is always at least one digit following the decimal point.

The invariant relation in the repeat loop is that a sequence of decimal digits yet to be printed will yield the original number if and only if they form a fraction f in the range s − δ ≤ 10 · 2^{16}f < s. We can stop if and only if f = 0 satisfies this condition; the loop will terminate before s can possibly become zero. procedure print scaled (s : scaled ); { prints scaled real, rounded to five digits }

var delta: scaled ; { amount of allowable inaccuracy }

begin if s < 0 then begin print char ( ); negate(s); { print the sign, if negative } end;

print int (s div unity ); { print the integer part }

print char ( ); s ← 10 ∗ (s mod unity ) + 5; delta ← 10;

repeat if delta > unity then s ← s + ´ 100000 − 50000; { round the last digit }

print char ( + (s div unity )); s ← 10 ∗ (s mod unity ); delta ← delta ∗ 10; until s ≤ delta; end;

104. Physical sizes that a TEX user specifies for portions of documents are represented internally as scaled points. Thus, if we define an ‘sp’ (scaled point) as a unit equal to 2^{−16} printer’s points, every dimension inside of TEX is an integer number of sp. There are exactly 4,736,286.72 sp per inch. Users are not allowed to specify dimensions larger than 2^{30} − 1 sp, which is a distance of about 18.892 feet (5.7583 meters); two such quantities can be added without overflow on a 32-bit computer.

The present implementation of TEX does not check for overflow when dimensions are added or subtracted. This could be done by inserting a few dozen tests of the form ‘if x ≥ ´ 10000000000 then report overflow ’, but the chance of overflow is so remote that such tests do not seem worthwhile.

TEX needs to do only a few arithmetic operations on scaled quantities, other than addition and subtraction, and the following subroutines do most of the work. A single computation might use several subroutine calls, and it is desirable to avoid producing multiple error messages in case of arithmetic overflow; so the routines set the global variable arith error to true instead of reporting errors directly to the user. Another global variable, remainder , holds the remainder after a division. ⟨ Global variables 13 ⟩ +≡ arith error : boolean; { has arithmetic overflow occurred recently? } remainder : scaled ; { amount subtracted to get an exact division }

105. The first arithmetical subroutine we need computes nx + y, where x and y are scaled and n is an integer. We will also use it to multiply integers.

define nx plus y (#) ≡ mult and add (#, ´ 7777777777 )

define mult integers (#) ≡ mult and add (#, 0, ´ 17777777777 ) function mult and add (n : integer ; x, y, max answer : scaled ): scaled ;

begin if n < 0 then begin negate(x); negate(n); end;

if n = 0 then mult and add ← y

else if ((x ≤ (max answer − y) div n) ∧ (−x ≤ (max answer + y) div n)) then mult and add ← n ∗ x + y

else begin arith error ← true; mult and add ← 0;

end; end; 106. We also need to divide scaled dimensions by integers. function x over n(x : scaled ; n : integer ): scaled ;

var negative: boolean; { should remainder be negated? } begin negative ← false; if n = 0 then

begin arith error ← true; x over n ← 0; remainder ← x;

end else begin if n < 0 then

begin negate(x); negate(n); negative ← true; end;

if x ≥ 0 then begin x over n ← x div n; remainder ← x mod n; end

else begin x over n ← −((−x) div n); remainder ← −((−x) mod n);

end; end;

if negative then negate(remainder ); end;

107. Then comes the multiplication of a scaled number by a fraction n/d, where n and d are nonnegative integers ≤ 2^{16} and d is positive. It would be too dangerous to multiply by n and then divide by d, in separate operations, since overflow might well occur; and it would be too inaccurate to divide by d and then multiply by n. Hence this subroutine simulates 1.5-precision arithmetic. function xn over d (x : scaled ; n, d : integer ): scaled ;

var positive: boolean; { was x ≥ 0? }

t, u, v: nonnegative integer ; { intermediate quantities } begin if x ≥ 0 then positive ← true else begin negate(x); positive ← false;

end; t ← (x mod ´ 100000 ) ∗ n; u ← (x div ´ 100000 ) ∗ n + (t div ´ 100000 ); v ← (u mod d) ∗ ´ 100000 + (t mod ´ 100000 ); if u div d ≥ ´ 100000 then arith error ← true else u ← ´ 100000 ∗ (u div d) + (v div d);

if positive then

begin xn over d ← u; remainder ← v mod d;

end else begin xn over d ← −u; remainder ← −(v mod d);

end; end; 108. The next subroutine is used to compute the “badness” of glue, when a total t is supposed to be made from amounts that sum to s. According to The TEXbook, the badness of this situation is 100(t/s)^{3}; however, badness is simply a heuristic, so we need not squeeze out the last drop of accuracy when computing it. All we really want is an approximation that has similar properties.

The actual method used to compute the badness is easier to read from the program than to describe in words. It produces an integer value that is a reasonably close approximation to 100(t/s)^{3}, and all implementations of TEX should use precisely this method. Any badness of 2^{13} or more is treated as infinitely bad, and represented by 10000.

It is not difficult to prove that

badness (t + 1, s) ≥ badness (t, s) ≥ badness (t, s + 1).

The badness function defined here is capable of computing at most 1095 distinct values, but that is plenty.

define inf bad = 10000 { infinitely bad value } function badness (t, s : scaled ): halfword ; { compute badness, given t ≥ 0 }

var r: integer ; { approximation to αt/s, where α^{3} ≈ 100 · 2^{18} }

begin if t = 0 then badness ← 0

else if s ≤ 0 then badness ← inf bad

else begin if t ≤ 7230584 then r ← (t ∗ 297) div s { 297^{3} = 99.94 × 2^{18} }

else if s ≥ 1663497 then r ← t div (s div 297)

else r ← t; if r > 1290 then badness ← inf bad { 1290^{3} < 2^{31} < 1291^{3} } else badness ← (r ∗ r ∗ r + ´ 400000 ) div ´ 1000000 ; end; { that was r^{3}/2^{18}, rounded to the nearest integer }

end;

109. When TEX “packages” a list into a box, it needs to calculate the proportionality ratio by which the glue inside the box should stretch or shrink. This calculation does not affect TEX’s decision making, so the precise details of rounding, etc., in the glue calculation are not of critical importance for the consistency of results on different computers.

We shall use the type glue ratio for such proportionality ratios. A glue ratio should take the same amount of memory as an integer (usually 32 bits) if it is to blend smoothly with TEX’s other data structures. Thus glue ratio should be equivalent to short real in some implementations of Pascal. Alternatively, it is possible to deal with glue ratios using nothing but fixed-point arithmetic; see TUGboat 3,1 (March 1982), 10–27. (But the routines cited there must be modified to allow negative glue ratios.)

define set glue ratio zero(#) ≡ # ← 0.0 { store the representation of zero ratio }

define set glue ratio one(#) ≡ # ← 1.0 { store the representation of unit ratio }

define float (#) ≡ # { convert from glue ratio to type real }

define unfloat (#) ≡ # { convert from real to type glue ratio }

define float constant (#) ≡ #.0 { convert integer constant to real } ⟨ Types in the outer block 18 ⟩ +≡

glue ratio = real ; { one-word representation of a glue expansion factor }