Calculator Programming Tutorial

Programming Building Blocks I

Control Flow I

Loops

Introduction

Consider the problem of determining the smallest non-unitary divisor of a number, that is, the smallest number greater than 1 what divides the number. A simple (and inefficient) way to find this divisor is to check all the numbers 2, 3, ..., up to the number. We know that any positive integer divides itself, so we know we will always find a divisor. The following flow chart illustrates this algorithm.

The candidate divisor, d, is started at 2 (“d := 2”). If d (2) does not divide n, d is replaced by d+1 (3). If the new d (3) does not divide n, d is replaced by d+1 (4). If this new d (4) does not divide n, d is replaced by d+1 (5). If this d (5) does not divide n, d is replaced by d+1 (6). This process continues until a d is found which does divide n. Then, that value of d is returned as the divisor.

This type of construct, the loop, is the last of the three types of basic control flow needed to produce arbitrary programs. In general, the overall structure of this type of loop (the “pre-tested” loop) is:

The condition determines whether the loop body is to be executed. If the condition is true, the loop body executes once. The condition is then reexamined. The loop body continues to execute as long as the condition is true. When the condition becomes false, the loop terminates — processing continues with whatever comes after the loop.

For the loop to terminate, the condition must at some time become false. Generally, this means the body of the loop must perform some computation that affects the condition in some way. In our divisor search, for example, we were changing one of the two variables engaged in the relationship (d divides n). Further, we knew from our analysis that the condition would eventually be satisfied. If this does not occur, the condition never changes state, and we have what is called an infinite loop. (Strictly speaking, of course, there is no such thing as an infinite loop. Someone, somewhere, will eventually want to know what the computer is doing, and stop it if it appears “stuck.” Or the power will fail. Or the continent will be subducted into the mantle. Or the sun will go nova. Or all matter in the universe will decay into iron and the semiconductors will stop semiconducting. But we still call it an “infinite” loop. Such is life.)

A loop, therefore, is a mechanism for checking on the progress of a computation; or, to put it another way, a mechanism for repeating a computation as many times as needed.

While the body of the loop and the condition controlling the loop may have any relationship at all — even none, which generally yields an infinite loop — the clearest and safest way of writing a loop is to ensure that a loop invariant exists. A loop invariant is a statement that is true at each entrance to the loop condition — both the first one and all subsequent ones. In the case of our divisor search, the loop invariant is “the number n does not have a divisor (other than 1) with value less than d.” This is a provable property of the loop.

Generally, a loop invariant should have two properties, both of which are important. The first property is that the loop invariant should be capable of proving the loop will terminate. In our case, we can prove that n does have a divisor — if nothing else, n itself — and that d will eventually reach it. The second property is that the loop invariant should be capable of proving the loop yields the results desired. In our case, the loop invariant — that n has no divisors (other than 1) less than d — straightforwardly gives us that the final d is the smallest divisor of n.

Loops in Visual Basic for Applications

There are two syntax forms for pre-tested loops in Visual Basic for Applications. The first, “old style,” is common but officially deprecated:

While condition
    statements
Wend

The second, “new style,” is less common but officially preferred:

Do While condition
    statements
Loop

The semantics of the two forms are identical. Condition is an expression that determines whether the statement sequence statements is to be executed. The first time condition evaluates to be false (or zero), execution passes to the statement following the loop construct. Until then, the statement sequence statements is executed.

Our sample divisor search algorithm is expressed in Visual Basic as:

Dim lN As Long
Dim lD As Long
...
lD = 2
Do While (lN \ lD) * lD <> lN
    lD = lD + 1
Loop

When this loop terminates, lD is the smallest non-unitary divisor of lN.

The divisibility test may require some investigation. The backslash (\) operator in Visual Basic performs an integer division — the integer portion of the quotient is retained, and any fractional part is discarded. The test forms the integer portion of the quotient n/d, then multiplies the quotient by d, and finally tests this product against n using the inequality comparision <>. If the two expressions are equal, then the integer portion of the quotient n/d is the quotient n/d itself. This in turn implies there is no remainder to the division. This in turn implies divisibility of n by d.

Loops in JavaScript

The syntax for a pre-tested loop in JavaScript is:

while (condition)
    statement

Condition is an expression that determines whether the statement statement is to be executed. The parentheses around condition are a part of the statement syntax, and cannot be omitted. The first time condition becomes false (or zero), execution passes to the statement following the loop construct. Until then, statement is executed.

As with JavaScript�s if statement, the single statement statement may in fact be a block. Frequently, JavaScript loops are written as:

while (condition)
{
    statements;
}

Our sample divisor search algorithm is expressed in JavaScript as:

var d = 2;
while (Math.floor (n / d) * d != n)
{
    d ++;
}

When this loop terminates, d is the smallest non-unitary divisor of n.

The divisibility test may require some investigation. The division (/) operator in JavaScript forms the quotient of its two arguments to the limit of numeric precision. This includes the fractional part of the quotient. There is no “integer division” operator in JavaScript. However, the Math.foor() function then “corrects” this quotient by finding the greatest integer not larger than its argument. In this case, Math.floor() discards any fractional part of the quotient. The test forms the integer portion of the quotient n/d, then multiplies the quotient by d, and finally tests this product against n using the inequality comparision !=. If the two expressions are equal, then the integer portion of the quotient n/d is the quotient n/d itself. This in turn implies there is no remainder to the division. This in turn implies divisibility of n by d.

Loops in the calculator

The syntax for a pre-tested loop in the calculator is:

While condition
statements
WhileEnd

Condition is an expression that determines whether the statement sequence statements is to be executed. The first time condition becomes false (or zero), execution passes to the statement following the loop construct. Until then, the statement sequence statements is executed.

Our sample divisor search algorithm is expressed in the calculator as:

2→D
While DInt(N/D)≠N
D+1→D
WhileEnd

When this loop terminates, D is the smallest non-unitary divisor of N.

The divisibility test may require some investigation. The division (/) operator in the calculator forms the quotient of its two arguments to the limit of numeric precision. This includes the fractional part of the quotient. There is no “integer division” operator in the calculator. However, the Int() function then “corrects” this quotient by discarding any fractional part of the quotient. The test forms the integer portion of the quotient n/d, then multiplies the quotient by d, and finally tests this product against n using the inequality comparision ≠. If the two expressions are equal, then the integer portion of the quotient n/d is the quotient n/d itself. This in turn implies there is no remainder to the division. This in turn implies divisibility of n by d.

[ Previous page | Top of page | Next page ]