Java Reference
In-Depth Information
parameters to
drawFractal
include the center of the fractal and the overall
dimension. From this, we can compute, at line 5, the size of the large central
square. After handling the base case at lines 7 and 8, we compute the bound-
aries of the central rectangle. We can then draw the four miniature fractals at
lines 17 to 20. Finally, we draw the central square at line 23. Note that this
square must be drawn after the recursive calls. Otherwise, we obtain a differ-
ent picture (in Exercise 7.35, you are asked to describe the difference).
numerical applications
7.4
In this section we look at three problems drawn primarily from number theory.
Number theory used to be considered an interesting but useless branch of math-
ematics. However, in the last 30 years, an important application for number the-
ory has emerged: data security. We begin the discussion with a small amount of
mathematical background and then show recursive algorithms to solve three
problems. We can combine these routines in conjunction with a fourth algo-
rithm that is more complex (described in Chapter 9), to implement an algorithm
that can be used to encode and decode messages. To date, nobody has been able
to show that the encryption scheme described here is not secure.
Here are the four problems we examine.
Modular exponentiation:
Compute
X
N
(mod
P
).
1.
2.
Greatest common divisor:
Compute gcd(
A, B
).
3.
Multiplicative inverse:
Solve
AX
≡
1(mod
P
) for
X
.
4.
Primality testing:
Determine whether
N
is prime (deferred to Chapter 9).
The integers we expect to deal with are all large, requiring at least 100
digits each. Therefore we must have a way to represent large integers, along
with a complete set of algorithms for the basic operations of addition, subtrac-
tion, multiplication, division, and so on. Java provides the
BigInteger
class for
this purpose. Implementing it efficiently is no trivial matter, and in fact there
is extensive literature on the subject.
We use
long
numbers to simplify our code presentation. The algorithms
described here work with large objects but still execute in a reasonable
amount of time.
7.4.1
modular arithmetic
The problems in this section, as well as the implementation of the hash table
data structure (Chapter 20), require the use of the Java
%
operator. The
%
oper-
ator, denoted as
operator%
, computes the remainder of two integral types. For
example,
13%10
evaluates to 3, as does
3%10
, and
23%10
. When we compute the
Search WWH ::
Custom Search