Java Reference
In-Depth Information
2.4.1 Loop statement:
while
The syntax of a
while
loop statement is as follows:
while (boolean_expression)
{block_instruction;}
This means that while the
boolean expression
is evaluated to
true
,the
sequence of instructions contained in the
block instruction
is executed.
Consider calculating the
greatest common divisor
(gcd for short) of two integers
a
and
b
. That is, the largest common divisor
c
such that both
a
and
b
can be
divided by
c
. For example, the GCD of
a
=30and
b
= 105 is 15 since
a
=2
×
3
×
5and
b
=5
7. Euclid came up with a simple algorithm published for solving
this task. The algorithm was reported in his topics
Elements
around
3
300 BC.
Computing the GCD is an essential number operation that requires quite a
large amount of computation for large numbers. The GCD problem is related
to many hot topics of cryptographic systems nowadays. Euclid's algorithm is
quite simple: If
a
=
b
then clearly the GCD of
a
and
b
is
c
=
a
=
b
. Otherwise,
consider the largest integer, say
a
without loss of generality, and observe the
important property that
×
3
×
GCD(
a, b
)=GCD(
a
−
b, b
)
.
Therefore, applying this equality reduces the total sum
a
+
b
, and at some
point, after
k
iterations, we will necessarily have
a
k
=
b
k
. Let us prove a
stronger result: GCD(
a, b
)=GCD(
b, a
mod
b
).
Proof
To see this, let us write
a
=
qb
+
r
where
q
is the quotient of the Euclidean
division and
r
its reminder. Any common divisor
c
of
a
and
b
is also a common
divisor of
r
: Indeed, suppose we have
a
=
ca
and
b
=
cb
, then
r
=
a
−
qb
=
(
a
−
qb
)
c
. Since all these numbers are integers, this implies that
r
is divisible
by
c
. It follows that the greatest common divisor
g
or
a
and
b
is also the greatest
common divisor of
b
and
r
.
Let us implement this routine using the
while
loop statement. The terminating
state is when
a
=
b
. Therefore, while
a
=
b
(written in Java as
a!=b
), we retrieve
that smaller number to the larger number using a
if
conditional structure. This
gives the following source code:
3
It is alleged that the algorithm was likely already known in 500 BC.
Search WWH ::
Custom Search