EWD249 - 47

-i.e. as separately as 2b and 2c-, but we feel that it is a little premature for this drastic decision.) We are going to express

1. that, ord being a non-decreasing function of j and j only increasing in value, adjustment of ord implies a conditional increase;

2. that, whether p[n] is a factor of j is given by the question whether the remainder equal zero.

This leads to

level 2b4(4):
2b3(4)a   =   2b4(4)a
2b3(4)b   =
begin while "ord too small" do "increase ord by one" end;
2b3(4)c   =
begin integer r;
      "make r equal to remainder of j over p[n]";
      jprime:= (r ≠ 0)
end

expressed in terms of
2b4(4)a     still meaning "set ord initial"
2b4(4)b     "ord too small"
2b4(4)c     "increase ord by one"
2b4(4)d     "make r equal to remainder of j over p[n]"

If we have a built-in division, the implementation of "make r equal to the remainder of j over p[n]" can be assumed to be an easy matter. The case that the refinement of 2b4(4)d can be treated independently is now left to the interested reader. To give the algorithm an unexpected turn we shall assume the absence of a convenient remainder computation. In that case the algorithm

            "r:= j; while r > 0 do r:= r - p[n]"

would lead to the (non-positive) remainder but it would be most unattractive from the point of view of computation time. Again this asks for the introduction of some additional tabulated material (similar to the way in which "ord" has been introduced).

We want to know whether a given value of j is a multiple of p[n] for n < ord. In order to assist us in this analysis we introduce a second array in the elements