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*.

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

WhileconditionstatementsWend

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

Do WhileconditionstatementsLoop

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*.

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*.

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

WhileconditionstatementsWhileEnd

*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 ]

Copyright © 2001 Brian Hetrick

Page last updated 30 December 2001.

Tutorial

Building Blocks I

Control Flow I

Loops

Control Flow II

Basic I/O

Algorithms

A First Program

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card