Chapter One. Elements of Programming

Our goal in this chapter is to convince you that writing a program is easier than writing a piece of text, such as a paragraph or essay. Writing prose is difficult: we spend many years in school to learn how to do it. By contrast, just a few building blocks suffice to enable us to write programs that can help solve all sorts of fascinating, but otherwise unapproachable, problems. In this chapter, we take you through these building blocks, get you started on programming in Java, and study a variety of interesting programs. You will be able to express yourself (by writing programs) within just a few weeks. Like the ability to write prose, the ability to program is a lifetime skill that you can continually refine well into the future.

In this book, you will learn the Java programming language. This task will be much easier for you than, for example, learning a foreign language. Indeed, programming languages are characterized by only a few dozen vocabulary words and rules of grammar. Much of the material that we cover in this book could be expressed in the Python or C++ languages, or any of several other modern programming languages. We describe everything specifically in Java so that you can get started creating and running programs right away. On the one hand, we will focus on learning to program, as opposed to learning details about Java. On the other hand, part of the challenge of programming is knowing which details are relevant in a given situation. Java is widely used, so learning to program in this language will enable you to write programs on many computers (your own, for example). Also, learning to program in Java will make it easy for you to learn other languages, including lower-level languages such as C and specialized languages such as Matlab.

http://introcs.cs.princeton.edu/java

We refer to this site as the booksite. It contains an extensive amount of supplementary information about the material in this book for your reference and use while programming.

• Create a program by typing it into a file named, say, MyProgram.java.

• Compile it by typing javac MyProgram.java in a terminal window.

• Execute (or run) it by typing java MyProgram in the terminal window.

In the first step, you start with a blank screen and end with a sequence of typed characters on the screen, just as when you compose an email message or an essay. Programmers use the term code to refer to program text and the term coding to refer to the act of creating and editing the code. In the second step, you use a system application that compiles your program (translates it into a form more suitable for the computer) and puts the result in a file named MyProgram.class. In the third step, you transfer control of the computer from the system to your program (which returns control back to the system when finished). Many systems have several different ways to create, compile, and execute programs. We choose the sequence given here because it is the simplest to describe and use for small programs.

public class HelloWorld
{
   public static void main(String[] args)
   {
      // Prints "Hello, World" in the terminal window.
      System.out.println("Hello, World");
   }
}

% javac HelloWorld.java
% java HelloWorld
Hello, World

PROGRAM 1.1.1 is an example of a complete Java program. Its name is HelloWorld, which means that its code resides in a file named HelloWorld.java (by convention in Java). The program’s sole action is to print a message to the terminal window. For continuity, we will use some standard Java terms to describe the program, but we will not define them until later in the book: PROGRAM 1.1.1 consists of a single class named HelloWorld that has a single method named main(). (When referring to a method in the text, we use () after the name to distinguish it from other kinds of names.) Until SECTION 2.1, all of our classes will have this same structure. For the time being, you can think of “class” as meaning “program.”

The first line of a method specifies its name and other information; the rest is a sequence of statements enclosed in curly braces, with each statement typically followed by a semicolon. For the time being, you can think of “programming” as meaning “specifying a class name and a sequence of statements for its main() method,” with the heart of the program consisting of the sequence of statements in the main() method (its body). PROGRAM 1.1.1 contains two such statements:

• The first statement is a comment, which serves to document the program. In Java a single-line comment begins with two '/' characters and extends to the end of the line. In this book, we display comments in gray. Java ignores comments—they are present only for human readers of the program.

• The second statement is a print statement. It calls the method named System.out.println() to print a text message—the one specified between the matching double quotes—to the terminal window.

In the next two sections, you will learn about many different kinds of statements that you can use to make programs. For the moment, we will use only comments and print statements, like the ones in HelloWorld.

When you type java followed by a class name in your terminal window, the system calls the main() method that you defined in that class, and executes its statements in order, one by one. Thus, typing java HelloWorld causes the system to call the main() method in PROGRAM 1.1.1 and execute its two statements. The first statement is a comment, which Java ignores. The second statement prints the specified message to the terminal window.

Since the 1970s, it has been a tradition that a beginning programmer’s first program should print Hello, World. So, you should type the code in PROGRAM 1.1.1 into a file, compile it, and execute it. By doing so, you will be following in the footsteps of countless others who have learned how to program. Also, you will be checking that you have a usable editor and terminal application. At first, accomplishing the task of printing something out in a terminal window might not seem very interesting; upon reflection, however, you will see that one of the most basic functions that we need from a program is its ability to tell us what it is doing.

For the time being, all our program code will be just like PROGRAM 1.1.1, except with a different sequence of statements in main(). Thus, you do not need to start with a blank page to write a program. Instead, you can

• Copy HelloWorld.java into a new file having a new program name of your choice, followed by .java.

• Replace HelloWorld on the first line with the new program name.

• Replace the comment and print statements with a different sequence of statements.

Your program is characterized by its sequence of statements and its name. Each Java program must reside in a file whose name matches the one after the word class on the first line, and it also must have a .java extension.

You can fix or avoid most errors by carefully examining the program as you create it, the same way you fix spelling and grammatical errors when you compose an email message. Some errors, known as compile-time errors, are identified when you compile the program, because they prevent the compiler from doing the translation. Other errors, known as run-time errors, do not show up until you execute the program.

In general, errors in programs, also commonly known as bugs, are the bane of a programmer’s existence: the error messages can be confusing or misleading, and the source of the error can be very hard to find. One of the first skills that you will learn is to identify errors; you will also learn to be sufficiently careful when coding, to avoid making many of them in the first place. You can find several examples of errors in the Q&A at the end of this section.

public class UseArgument
{
   public static void main(String[] args)
   {
      System.out.print("Hi, ");
      System.out.print(args[0]);
      System.out.println(". How are you?");
   }
}

% javac UseArgument.java
% java UseArgument Alice
Hi, Alice. How are you?
% java UseArgument Bob
Hi, Bob. How are you?

In addition to the System.out.println() method, UseArgument calls the System.out.print() method. This method is just like System.out.println(), but prints just the specified string (and not a newline character).

Again, accomplishing the task of getting a program to print back out what we type in to it may not seem interesting at first, but upon reflection you will realize that another basic function of a program is its ability to respond to basic information from the user to control what the program does. The simple model that UseArgument represents will suffice to allow us to consider Java’s basic programming mechanism and to address all sorts of interesting computational problems.

Stepping back, we can see that UseArgument does neither more nor less than implement a function that maps a string of characters (the command-line argument) into another string of characters (the message printed back to the terminal window). When using it, we might think of our Java program as a black box that converts our input string to some output string.

This model is attractive because it is not only simple but also sufficiently general to allow completion, in principle, of any computational task. For example, the Java compiler itself is nothing more than a program that takes one string of characters as input (a .java file) and produces another string of characters as output (the corresponding .class file). Later, you will be able to write programs that accomplish a variety of interesting tasks (though we stop short of programs as complicated as a compiler). For the moment, we will live with various limitations on the size and type of the input and output to our programs; in SECTION 1.5, you will see how to incorporate more sophisticated mechanisms for program input and output. In particular, you will see that we can work with arbitrarily long input and output strings and other types of data such as sound and pictures.

A. The programs that we are writing are very similar to their counterparts in several other languages, so our choice of language is not crucial. We use Java because it is widely available, embraces a full set of modern abstractions, and has a variety of automatic checks for mistakes in programs, so it is suitable for learning to program. There is no perfect language, and you certainly will be programming in other languages in the future.

Q. Do I really have to type in the programs in the book to try them out? I believe that you ran them and that they produce the indicated output.

A. Everyone should type in and run HelloWorld. Your understanding will be greatly magnified if you also run UseArgument, try it on various inputs, and modify it to test different ideas of your own. To save some typing, you can find all of the code in this book (and much more) on the booksite. This site also has information about installing and running Java on your computer, answers to selected exercises, web links, and other extra information that you may find useful while programming.

Q. What is the meaning of the words public, static, and void?

A. These keywords specify certain properties of main() that you will learn about later in the book. For the moment, we just include these keywords in the code (because they are required) but do not refer to them in the text.

Q. What is the meaning of the //, /*, and */ character sequences in the code?

A. They denote comments, which are ignored by the compiler. A comment is either text in between /* and */ or at the end of a line after //. Comments are indispensable because they help other programmers to understand your code and even can help you to understand your own code in retrospect. The constraints of the book format demand that we use comments sparingly in our programs; instead we describe each program thoroughly in the accompanying text and figures. The programs on the booksite are commented to a more realistic degree.

Q. What are Java’s rules regarding tabs, spaces, and newline characters?

A. Such characters are known as whitespace characters. Java compilers consider all whitespace in program text to be equivalent. For example, we could write HelloWorld as follows:

Click here to view code image

public class HelloWorld { public static void main ( String
[] args) { System.out.println("Hello, World")         ; } }

But we do normally adhere to spacing and indenting conventions when we write Java programs, just as we indent paragraphs and lines consistently when we write prose or poetry.

Q. What are the rules regarding quotation marks?

A. Material inside double quotation marks is an exception to the rule defined in the previous question: typically, characters within quotes are taken literally so that you can precisely specify what gets printed. If you put any number of successive spaces within the quotes, you get that number of spaces in the output. If you accidentally omit a quotation mark, the compiler may get very confused, because it needs that mark to distinguish between characters in the string and other parts of the program.

Q. What happens when you omit a curly brace or misspell one of the words, such as public or static or void or main?

A. It depends upon precisely what you do. Such errors are called syntax errors and are usually caught by the compiler. For example, if you make a program Bad that is exactly the same as HelloWorld except that you omit the line containing the first left curly brace (and change the program name from HelloWorld to Bad), you get the following helpful message:

Click here to view code image

% javac Bad.java
Bad.java:1: error: '{' expected
public class Bad
                ^
1 error

From this message, you might correctly surmise that you need to insert a left curly brace. But the compiler may not be able to tell you exactly which mistake you made, so the error message may be hard to understand. For example, if you omit the second left curly brace instead of the first one, you get the following message:

Click here to view code image

% javac Bad.java
Bad.java:3: error: ';' expected
   public static void main(String[] args)
                                         ^
Bad.java:7: error: class, interface, or enum expected
}
^
2 errors

One way to get used to such messages is to intentionally introduce mistakes into a simple program and then see what happens. Whatever the error message says, you should treat the compiler as a friend, because it is just trying to tell you that something is wrong with your program.

Q. Which Java methods are available for me to use?

A. There are thousands of them. We introduce them to you in a deliberate fashion (starting in the next section) to avoid overwhelming you with choices.

Q. When I ran UseArgument, I got a strange error message. What’s the problem?

A. Most likely, you forgot to include a command-line argument:

Click here to view code image

% java UseArgument
Hi, Exception in thread "main"
java.lang.ArrayIndexOutOfBoundsException: 0
        at UseArgument.main(UseArgument.java:6)

Java is complaining that you ran the program but did not type a command-line argument as promised. You will learn more details about array indices in SECTION 1.4. Remember this error message—you are likely to see it again. Even experienced programmers forget to type command-line arguments on occasion.

1.1.2 Describe what happens if you omit the following in HelloWorld.java:

a. public

b. static

c. void

d. args

1.1.3 Describe what happens if you misspell (by, say, omitting the second letter) the following in HelloWorld.java:

a. public

b. static

c. void

d. args

1.1.4 Describe what happens if you put the double quotes in the print statement of HelloWorld.java on different lines, as in this code fragment:

System.out.println("Hello,
                    World");

1.1.5 Describe what happens if you try to execute UseArgument with each of the following command lines:

a. java UseArgument java

b. java UseArgument @!&^%

c. java UseArgument 1234

d. java UseArgument.java Bob

e. java UseArgument Alice Bob

1.1.6 Modify UseArgument.java to make a program UseThree.java that takes three names as command-line arguments and prints a proper sentence with the names in the reverse of the order given, so that, for example, java UseThree Alice Bob Carol prints Hi Carol, Bob, and Alice.

There are eight primitive types of data in Java, mostly for different kinds of numbers. Of the eight primitive types, we most often use these: int for integers; double for real numbers; and boolean for true–false values. Other data types are available in Java libraries: for example, the programs in SECTION 1.1 use the type String for strings of characters. Java treats the String type differently from other types because its usage for input and output is essential. Accordingly, it shares some characteristics of the primitive types; for example, some of its operations are built into the Java language. For clarity, we refer to primitive types and String collectively as built-in types. For the time being, we concentrate on programs that are based on computing with built-in types. Later, you will learn about Java library data types and building your own data types. Indeed, programming in Java often centers on building data types, as you shall see in CHAPTER 3.

After defining basic terms, we consider several sample programs and code fragments that illustrate the use of different types of data. These code fragments do not do much real computing, but you will soon see similar code in longer programs. Understanding data types (values and operations on them) is an essential step in beginning to program. It sets the stage for us to begin working with more intricate programs in the next section. Every program that you write will use code like the tiny fragments shown in this section.

int a, b, c;
a = 1234;
b = 99;
c = a + b;

The first line is a declaration statement that declares the names of three variables using the identifiers a, b, and c and their type to be int. The next three lines are assignment statements that change the values of the variables, using the literals 1234 and 99, and the expression a + b, with the end result that c has the value 1333.

int a = 1234;
int b = 99;

Most often, we declare and initialize a variable in this manner at the point of its first use in our program.

int t = a;
a = b;
b = t;

To do so, use a time-honored method of examining program behavior: study a table of the variable values after each statement (such a table is known as a trace).

Next, we consider these details for the basic built-in types that you will use most often (strings, integers, floating-point numbers, and true–false values), along with sample code illustrating their use. To understand how to use a data type, you need to know not just its defined set of values, but also which operations you can perform, the language mechanism for invoking the operations, and the conventions for specifying literals.

The String type represents sequences of characters. You can specify a String literal by enclosing a sequence of characters within double quotes, such as "Hello, World". The String data type is not a primitive type, but Java sometimes treats it like one. For example, the concatenation operator (+) takes two String operands and produces a third String that is formed by appending the characters of the second operand to the characters of the first operand.

The concatenation operation (along with the ability to declare String variables and to use them in expressions and assignment statements) is sufficiently powerful to allow us to attack some nontrivial computing tasks. As an example, Ruler (PROGRAM 1.2.1) computes a table of values of the ruler function that describes the relative lengths of the marks on a ruler. One noteworthy feature of this computation is that it illustrates how easy it is to craft a short program that produces a huge amount of output. If you extend this program in the obvious way to print five lines, six lines, seven lines, and so forth, you will see that each time you add two statements to this program, you double the size of the output. Specifically, if the program prints n lines, the nth line contains 2ⁿ–1 numbers. For example, if you were to add statements in this way so that the program prints 30 lines, it would print more than 1 billion numbers.

---

Program 1.2.1 String concatenation

Click here to view code image

public class Ruler
{
   public static void main(String[] args)
   {
      String ruler1 = "1";
      String ruler2 = ruler1 + " 2 " + ruler1;
      String ruler3 = ruler2 + " 3 " + ruler2;
      String ruler4 = ruler3 + " 4 " + ruler3;
      System.out.println(ruler1);
      System.out.println(ruler2);
      System.out.println(ruler3);
      System.out.println(ruler4);
   }
}

This program prints the relative lengths of the subdivisions on a ruler. The nth line of output is the relative lengths of the marks on a ruler subdivided in intervals of 1/2ⁿ of an inch. For example, the fourth line of output gives the relative lengths of the marks that indicate intervals of one-sixteenth of an inch on a ruler.

---

% javac Ruler.java
% java Ruler
1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

---

---

Our most frequent use (by far) of the concatenation operation is to put together results of computation for output with System.out.println(). For example, we could simplify UseArgument (PROGRAM 1.1.2) by replacing its three statements in main() with this single statement:

Click here to view code image

System.out.println("Hi, " + args[0] + ". How are you?");

We have considered the String type first precisely because we need it for output (and command-line arguments) in programs that process not only strings but other types of data as well. Next we consider two convenient mechanisms in Java for converting numbers to strings and strings to numbers.

Click here to view code image

String a = "1234";            String a = "1234";
String b = "99";              int b = 99;
String c = a + b;             String c = a + b;

are both the same: they assign to c the value "123499". We use this automatic conversion liberally to form String values for use with System.out.print() and System.out.println(). For example, we can write statements like this one:

Click here to view code image

System.out.println(a + " + " + b + " = " + c);

If a, b, and c are int variables with the values 1234, 99, and 1333, respectively, then this statement prints the string 1234 + 99 = 1333.

With these mechanisms, our view of each Java program as a black box that takes string arguments and produces string results is still valid, but we can now interpret those strings as numbers and use them as the basis for meaningful computations.

Standard arithmetic operators for addition/subtraction (+ and -), multiplication (*), division (/), and remainder (%) for the int data type are built into Java. These operators take two int operands and produce an int result, with one significant exception—division or remainder by zero is not allowed. These operations are defined as in grade school (keeping in mind that all results must be integers): given two int values a and b, the value of a / b is the number of times b goes into a with the fractional part discarded, and the value of a % b is the remainder that you get when you divide a by b. For example, the value of 17 / 3 is 5, and the value of 17 % 3 is 2. The int results that we get from arithmetic operations are just what we expect, except that if the result is too large to fit into int’s 32-bit representation, then it will be truncated in a well-defined manner. This situation is known as overflow. In general, we have to take care that such a result is not misinterpreted by our code. For the moment, we will be computing with small numbers, so you do not have to worry about these boundary conditions.

public class IntOps
{
   public static void main(String[] args)
   {
      int a = Integer.parseInt(args[0]);
      int b = Integer.parseInt(args[1]);
      int p = a * b;
      int q = a / b;
      int r = a % b;
      System.out.println(a + " * " + b + " = " + p);
      System.out.println(a + " / " + b + " = " + q);
      System.out.println(a + " % " + b + " = " + r);
      System.out.println(a + " = " + q + " * " + b + " + " + r);
   }
}

% javac IntOps.java
% java IntOps 1234 99
1234 * 99 = 122166
1234 / 99 = 12
1234 % 99 = 46
1234 = 12 * 99 + 46

PROGRAM 1.2.2 illustrates three basic operations (multiplication, division, and remainder) for manipulating integers,. It also demonstrates the use of Integer.parseInt() to convert String values on the command line to int values, as well as the use of automatic type conversion to convert int values to String values for output.

Three other built-in types are different representations of integers in Java. The long, short, and byte types are the same as int except that they use 64, 16, and 8 bits respectively, so the range of allowed values is accordingly different. Programmers use long when working with huge integers, and the other types to save space. You can find a table with the maximum and minimum values for each type on the booksite, or you can figure them out for yourself from the numbers of bits.

You can specify a double literal with a sequence of digits with a decimal point. For example, the literal 3.14159 represents a six-digit approximation to π. Alternatively, you specify a double literal with a notation like scientific notation: the literal 6.022e23 represents the number 6.022 × 10²³. As with integers, you can use these conventions to type floating-point literals in your programs or to provide floating-point numbers as string arguments on the command line.

The arithmetic operators +, -, *, and / are defined for double. Beyond these built-in operators, the Java Math library defines the square root function, trigonometric functions, logarithm/exponential functions, and other common functions for floating-point numbers. To use one of these functions in an expression, you type the name of the function followed by its argument in parentheses. For example, the code Math.sqrt(2.0) evaluates to a double value that is approximately the square root of 2. We discuss the mechanism behind this arrangement in more detail in SECTION 2.1 and more details about the Math library at the end of this section.

public class Quadratic
{
   public static void main(String[] args)
   {
      double b = Double.parseDouble(args[0]);
      double c = Double.parseDouble(args[1]);
      double discriminant = b*b - 4.0*c;
      double d = Math.sqrt(discriminant);
      System.out.println((-b + d) / 2.0);
      System.out.println((-b - d) / 2.0);
   }
}

% javac Quadratic.java
% java Quadratic -3.0 2.0
2.0
1.0

% java Quadratic -1.0 -1.0
1.618033988749895
-0.6180339887498949
% java Quadratic 1.0 1.0
NaN
NaN

When working with floating-point numbers, one of the first things that you will encounter is the issue of precision. For example, printing 5.0/2.0 results in 2.5 as expected, but printing 5.0/3.0 results in 1.6666666666666667. In SECTION 1.5, you will learn Java’s mechanism for controlling the number of significant digits that you see in output. Until then, we will work with the Java default output format.

The result of a calculation can be one of the special values Infinity (if the number is too large to be represented) or NaN (if the result of the calculation is undefined). Though there are myriad details to consider when calculations involve these values, you can use double in a natural way and begin to write Java programs instead of using a calculator for all kinds of calculations. For example, PROGRAM 1.2.3 shows the use of double values in computing the roots of a quadratic equation using the quadratic formula. Several of the exercises at the end of this section further illustrate this point.

As with long, short, and byte for integers, there is another representation for real numbers called float. Programmers sometimes use float to save space when precision is a secondary consideration. The double type is useful for about 15 significant digits; the float type is good for only about 7 digits. We do not use float in this book.

The most important operations defined for booleans are and (&&), or (||), and not (!), which have familiar definitions:

• a && b is true if both operands are true, and false if either is false.

• a || b is false if both operands are false, and true if either is true.

• !a is true if a is false, and false if a is true.

Despite the intuitive nature of these definitions, it is worthwhile to fully specify each possibility for each operation in tables known as truth tables. The not function has only one operand: its value for each of the two possible values of the operand is specified in the second column. The and and or functions each have two operands: there are four different possibilities for operand values, and the values of the functions for each possibility are specified in the right two columns.

We can use these operators with parentheses to develop arbitrarily complex expressions, each of which specifies a well-defined boolean function. Often the same function appears in different guises. For example, the expressions (a && b) and !(!a || !b) are equivalent.

The study of manipulating expressions of this kind is known as Boolean logic. This field of mathematics is fundamental to computing: it plays an essential role in the design and operation of computer hardware itself, and it is also a starting point for the theoretical foundations of computation. In the present context, we are interested in boolean expressions because we use them to control the behavior of our programs. Typically, a particular condition of interest is specified as a boolean expression, and a piece of program code is written to execute one set of statements if that expression is true and a different set of statements if the expression is false. The mechanics of doing so are the topic of SECTION 1.3.

public class LeapYear
{
   public static void main(String[] args)
   {
      int year = Integer.parseInt(args[0]);
      boolean isLeapYear;
      isLeapYear = (year % 4 == 0);
      isLeapYear = isLeapYear && (year % 100 != 0);
      isLeapYear = isLeapYear || (year % 400 == 0);
      System.out.println(isLeapYear);
   }
}

% javac LeapYear.java
% java LeapYear 2004
true
% java LeapYear 1900
false
% java LeapYear 2000
true

Even without going into the details of number representation, it is clear that the operations for the various types are quite different. For example, it is one thing to compare two ints to check that (2 <= 2) is true, but quite another to compare two doubles to check whether (2.0 <= 0.002e3) is true. Still, these operations are well defined and useful to write code that tests for conditions such as (b*b - 4.0*a*c) >= 0.0, which is frequently needed, as you will see.

The comparison operations have lower precedence than arithmetic operators and higher precedence than boolean operators, so you do not need the parentheses in an expression such as (b*b - 4.0*a*c) >= 0.0, and you could write an expression such as month >= 1 && month <= 12 without parentheses to test whether the value of the int variable month is between 1 and 12. (It is better style to use the parentheses, however.)

Comparison operations, together with boolean logic, provide the basis for decision making in Java programs. PROGRAM 1.2.4 is an example of their use, and you can find other examples in the exercises at the end of this section. More importantly, in SECTION 1.3 we will see the role that boolean expressions play in more sophisticated programs.

For convenience, we will consistently summarize the library methods that you need to know how to use in tables like this one:

Such a table is known as an application programming interface (API). Each method is described by a line in the API that specifies the information you need to know to use the method. The code in the tables is not the code that you type to use the method; it is known as the method’s signature. The signature specifies the type of the arguments, the method name, and the type of the result that the method computes (the return value).

In your code, you can call a method by typing its name followed by arguments, enclosed in parentheses and separated by commas. When Java executes your program, we say that it calls (or evaluates) the method with the given arguments and that the method returns a value. A method call is an expression, so you can use a method call in the same way that you use variables and literals to build up more complicated expressions. For example, you can write expressions like Math.sin(x) * Math.cos(y) and so on. An argument is also an expression, so you can write code like Math.sqrt(b*b - 4.0*a*c) and Java knows what you mean—it evaluates the argument expression and passes the resulting value to the method.

The API tables on the facing page show some of the commonly used methods in Java’s Math library, along with the Java methods we have seen for printing text to the terminal window and for converting strings to primitive types. The following table shows several examples of calls that use these library methods:

With three exceptions, the methods on the previous page are pure—given the same arguments, they always return the same value, without producing any observable side effect. The method Math.random() is impure because it returns potentially a different value each time it is called; the methods System.out.print() and System.out.println() are impure because they produce side effects—printing strings to the terminal. In APIs, we use a verb phrase to describe the behavior of a method that produces side effects; otherwise, we use a noun phrase to describe the return value. The keyword void designates a method that does not return a value (and whose main purpose is to produce side effects).

The Math library also defines the constant values Math.PI (for π) and Math.E (for e), which you can use in your programs. For example, the value of Math.sin(Math.PI/2) is 1.0 and the value of Math.log(Math.E) is 1.0 (because Math.sin() takes its argument in radians and Math.log() implements the natural logarithm function).

These APIs are typical of the online documentation that is the standard in modern programming. The extensive online documentation of the Java APIs is routinely used by professional programmers, and it is available to you (if you are interested) directly from the Java website or through our booksite. You do not need to go to the online documentation to understand the code in this book or to write similar code, because we present and explain in the text all of the library methods that we use in APIs like these and summarize them in the endpapers. More important, in CHAPTERS 2 AND 3 you will learn in this book how to develop your own APIs and to implement methods for your own use.

Casting has higher precedence than arithmetic operations—any cast is applied to the value that immediately follows it. For example, if we write int value = (int) 11 * 0.25, the cast is no help: the literal 11 is already an integer, so the cast (int) has no effect. In this example, the compiler produces a possible loss of precision error message because there would be a loss of precision in converting the resulting value (2.75) to an int for assignment to value. The error is helpful because the intended computation for this code is likely (int) (11 * 0.25), which has the value 2, not 2.75.

public class RandomInt
{
   public static void main(String[] args)
   {
      int n = Integer.parseInt(args[0]);
      double r = Math.random();   // uniform between 0.0 and 1.0
      int value = (int) (r * n);  // uniform between 0 and n-1
      System.out.println(value);
   }
}

% javac RandomInt.java
% java RandomInt 1000
548
% java RandomInt 1000
141
% java RandomInt 1000000
135032

a possible loss of precision error message because there would be a loss of precision in converting the resulting value (2.75) to an int for assignment to value. The error is helpful because the intended computation for this code is likely (int) (11 * 0.25), which has the value 2, not 2.75.

Beginning programmers tend to find type conversion to be an annoyance, but experienced programmers know that paying careful attention to data types is a key to success in programming. It may also be a key to avoiding failure: in a famous incident in 1996, a French rocket exploded in midair because of a type-conversion problem. While a bug in your program may not cause an explosion, it is well worth your while to take the time to understand what type conversion is all about. After you have written just a few programs, you will see that an understanding of data types will help you not only compose compact code but also make your intentions explicit and avoid subtle bugs in your programs.

When programming in Java, we have to be aware that every operation is defined only in the context of its data type (so we may need type conversions) and that all types can have only a finite number of values (so we may need to live with imprecise results).

The boolean type and its operations—&&, ||, and !—are the basis for logical decision making in Java programs, when used in conjunction with the mixed-type comparison operators ==, !=, <, >, <=, and >=. Specifically, we use boolean expressions to control Java’s conditional (if) and loop (for and while) constructs, which we will study in detail in the next section.

The numeric types and Java’s libraries give us the ability to use Java as an extensive mathematical calculator. We write arithmetic expressions using the built-in operators +, -, *, /, and % along with Java methods from the Math library.

Although the programs in this section are quite rudimentary by the standards of what we will be able to do after the next section, this class of programs is quite useful in its own right. You will use primitive types and basic mathematical functions extensively in Java programming, so the effort that you spend now in understanding them will certainly be worthwhile.

A. Strings are sequences of characters that are encoded with Unicode, a modern standard for encoding text. Unicode supports more than 100,000 different characters, including more than 100 different languages plus mathematical and musical symbols.

Q. Can you use < and > to compare String values?

A. No. Those operators are defined only for primitive-type values.

Q. How about == and !=?

A. Yes, but the result may not be what you expect, because of the meanings these operators have for nonprimitive types. For example, there is a distinction between a String and its value. The expression "abc" == "ab" + x is false when x is a String with value "c" because the two operands are stored in different places in memory (even though they have the same value). This distinction is essential, as you will learn when we discuss it in more detail in SECTION 3.1.

Q. How can I compare two strings like words in a book index or dictionary?

A. We defer discussion of the String data type and associated methods until SECTION 3.1, where we introduce object-oriented programming. Until then, the string concatenation operation suffices.

Q. How can I specify a string literal that is too long to fit on a single line?

A. You can’t. Instead, divide the string literal into independent string literals and concatenate them together, as in the following example:

Click here to view code image

String dna = "ATGCGCCCACAGCTGCGTCTAAACCGGACTCTG" +
             "AAGTCCGGAAATTACACCTGTTAG";

A. The simplest representation is for small positive integers, where the binary number system is used to represent each integer with a fixed amount of computer memory.

Q. What’s the binary number system?

A. In the binary number system, we represent an integer as a sequence of bits. A bit is a single binary (base 2) digit—either 0 or 1—and is the basis for representing information in computers. In this case the bits are coefficients of powers of 2. Specifically, the sequence of bits b_nb_n–1...b₂b₁b₀ represents the integer

b_n2ⁿ + b_n–12^n–1 + ... + b₂2² + b₁2¹ + b₀2⁰

For example, 1100011 represents the integer

99 = 1·64 + 1·32 + 0·16 + 0·8 + 0·4 + 1·2 +1·1

The more familiar decimal number system is the same except that the digits are between 0 and 9 and we use powers of 10. Converting a number to binary is an interesting computational problem that we will consider in the next section. Java uses 32 bits to represent int values. For example, the decimal integer 99 might be represented with the 32 bits 00000000000000000000000001100011.

Q. How about negative numbers?

A. Negative numbers are handled with a convention known as two’s complement, which we need not consider in detail. This is why the range of int values in Java is –2147483648 (–2³¹) to 2147483647 (2³¹ – 1). One surprising consequence of this representation is that int values can become negative when they get large and overflow (exceed 2147483647). If you have not experienced this phenomenon, see EXERCISE 1.2.10. A safe strategy is to use the int type when you know the integer values will be fewer than ten digits and the long type when you think the integer values might get to be ten digits or more.

Q. It seems wrong that Java should just let ints overflow and give bad values. Shouldn’t Java automatically check for overflow?

A. Yes, this issue is a contentious one among programmers. The short answer for now is that the lack of such checking is one reason such types are called primitive data types. A little knowledge can go a long way in avoiding such problems. Again, it is fine to use the int type for small numbers, but when values run into the billions, you cannot.

Q. What is the value of Math.abs(-2147483648)?

A. -2147483648. This strange (but true) result is a typical example of the effects of integer overflow and two’s complement representation.

Q. What do the expressions 1 / 0 and 1 % 0 evaluate to in Java?

A. Each generates a run-time exception, for division by zero.

Q. What is the result of division and remainder for negative integers?

A. The quotient a / b rounds toward 0; the remainder a % b is defined such that (a / b) * b + a % b is always equal to a. For example, -14 / 3 and 14 / -3 are both -4, but -14 % 3 is -2 and 14 % -3 is 2. Some other languages (including Python) have different conventions when dividing by negative integers.

Q. Why is the value of 10 ^ 6 not 1000000 but 12?

A. The ^ operator is not an exponentiation operator, which you must have been thinking. Instead, it is the bitwise exclusive or operator, which is seldom what you want. Instead, you can use the literal 1e6. You could also use Math.pow(10, 6) but doing so is wasteful if you are raising 10 to a known power.

A. The decimal point can “float” across the digits that make up the real number. In contrast, with integers the (implicit) decimal point is fixed after the least significant digit.

Q. How does Java store floating-point numbers internally?

A. Java follows the IEEE 754 standard, which supported in hardware by most modern computer systems. The standard specifies that a floating-point number is stored using three fields: sign, mantissa, and exponent. If you are interested, see the booksite for more details. The IEEE 754 standard also specifies how special floating-point values—positive zero, negative zero, positive infinity, negative infinity, and NaN (not a number)—should be handled. In particular, floating-point arithmetic never leads to a run-time exception. For example, the expression -0.0/3.0 evaluates to -0.0, the expression 1.0/0.0 evaluates to positive infinity, and Math.sqrt(-2.0) evaluates to NaN.

Q. Fifteen digits for floating-point numbers certainly seems enough to me. Do I really need to worry much about precision?

A. Yes, because you are used to mathematics based on real numbers with infinite precision, whereas the computer always deals with finite approximations. For example, the expression (0.1 + 0.1 == 0.2) evaluates to true but the expression (0.1 + 0.1 + 0.1 == 0.3) evaluates to false! Pitfalls like this are not at all unusual in scientific computing. Novice programmers should avoid comparing two floating-point numbers for equality.

Q. How can I initialize a double variable to NaN or infinity?

A. Java has built-in constants available for this purpose: Double.NaN, Double.POSITIVE_INFINITY, and Double.NEGATIVE_INFINITY.

Q. Are there functions in Java’s Math library for other trigonometric functions, such as cosecant, secant, and cotangent?

A. No, but you could use Math.sin(), Math.cos(), and Math.tan() to compute them. Choosing which functions to include in an API is a tradeoff between the convenience of having every function that you need and the annoyance of having to find one of the few that you need in a long list. No choice will satisfy all users, and the Java designers have many users to satisfy. Note that there are plenty of redundancies even in the APIs that we have listed. For example, you could use Math.sin(x)/Math.cos(x) instead of Math.tan(x).

Q. It is annoying to see all those digits when printing a double. Can we arrange System.out.println() to print just two or three digits after the decimal point?

A. That sort of task involves a closer look at the method used to convert from double to String. The Java library function System.out.printf() is one way to do the job, and it is similar to the basic printing method in the C programming language and many modern languages, as discussed in SECTION 1.5. Until then, we will live with the extra digits (which is not all bad, since doing so helps us to get used to the different primitive types of numbers).

A. The compiler complains when you refer to that variable in an expression. For example, IntOpsBad is the same as PROGRAM 1.2.2 except that the variable p is not declared (to be of type int).

Click here to view code image

% javac IntOpsBad.java
IntOpsBad.java:7: error: cannot find symbol
      p = a * b;
      ^
  symbol:   variable p
  location: class IntOpsBad
IntOpsBad.java:10: error: cannot find symbol
      System.out.println(a + " * " + b + " = " + p);
                                                 ^
  symbol:   variable p
  location: class IntOpsBad
2 errors

The compiler says that there are two errors, but there is really just one: the declaration of p is missing. If you forget to declare a variable that you use often, you will get quite a few error messages. A good strategy is to correct the first error and check that correction before addressing later ones.

Q. What happens if I forget to initialize a variable?

A. The compiler checks for this condition and will give you a variable might not have been initialized error message if you try to use the variable in an expression before you have initialized it.

Q. Is there a difference between the = and == operators?

A. Yes, they are quite different! The first is an assignment operator that changes the value of a variable, and the second is a comparison operator that produces a boolean result. Your ability to understand this answer is a sure test of whether you understood the material in this section. Think about how you might explain the difference to a friend.

Q. Can you compare a double to an int?

A. Not without doing a type conversion, but remember that Java usually does the requisite type conversion automatically. For example, if x is an int with the value 3, then the expression (x < 3.1) is true—Java converts x to double (because 3.1 is a double literal) before performing the comparison.

Q. Will the statement a = b = c = 17; assign the value 17 to the three integer variables a, b, and c?

A. Yes. It works because an assignment statement in Java is also an expression (that evaluates to its right-hand side) and the assignment operator is right associative. As a matter of style, we do not use such chained assignments in this book.

Q. Will the expression (a < b < c) test whether the values of three integer variables a, b, and c are in strictly ascending order?

A. No, it will not compile because the expression a < b produces a boolean value, which would then be compared to an int value. Java does not support chained comparisons. Instead, you need to write (a < b && b < c).

Q. Why do we write (a && b) and not (a & b)?

A. Java also has an & operator that you may encounter if you pursue advanced programming courses.

Q. What is the value of Math.round(6.022e23)?

A. You should get in the habit of typing in a tiny Java program to answer such questions yourself (and trying to understand why your program produces the result that it does).

Q. I’ve heard Java referred to as a statically typed language. What does this mean?

A. Static typing means that the type of every variable and expression is known at compile time. Java also verifies and enforces type constraints at compile time; for example, your program will not compile if you attempt to store a value of type double in a variable of type int or call Math.sqrt() with a String argument.

int t = a; b = t; a = b;

1.2.2 Write a program that uses Math.sin() and Math.cos() to check that the value of cos² θ + sin² θ is approximately 1 for any θ entered as a command-line argument. Just print the value. Why are the values not always exactly 1?

1.2.3 Suppose that a and b are boolean variables. Show that the expression

Click here to view code image

(!(a && b) && (a || b)) || ((a && b) || !(a || b))

evaluates to true.

1.2.4 Suppose that a and b are int variables. Simplify the following expression: (!(a < b) && !(a > b)).

1.2.5 The exclusive or operator ^ for boolean operands is defined to be true if they are different, false if they are the same. Give a truth table for this function.

1.2.6 Why does 10/3 give 3 and not 3.333333333?

Solution. Since both 10 and 3 are integer literals, Java sees no need for type conversion and uses integer division. You should write 10.0/3.0 if you mean the numbers to be double literals. If you write 10/3.0 or 10.0/3, Java does implicit conversion to get the same result.

1.2.7 What does each of the following print?

a. System.out.println(2 + "bc");

b. System.out.println(2 + 3 + "bc");

c. System.out.println((2+3) + "bc");

d. System.out.println("bc" + (2+3));

e. System.out.println("bc" + 2 + 3);

Explain each outcome.

1.2.8 Explain how to use PROGRAM 1.2.3 to find the square root of a number.

1.2.9 What does each of the following print?

a. System.out.println('b');

b. System.out.println('b' + 'c');

c. System.out.println((char) ('a' + 4));

Explain each outcome.

1.2.10 Suppose that a variable a is declared as int a = 2147483647 (or equivalently, Integer.MAX_VALUE). What does each of the following print?

a. System.out.println(a);

b. System.out.println(a+1);

c. System.out.println(2-a);

d. System.out.println(-2-a);

e. System.out.println(2*a);

f. System.out.println(4*a);

Explain each outcome.

1.2.11 Suppose that a variable a is declared as double a = 3.14159. What does each of the following print?

a. System.out.println(a);

b. System.out.println(a+1);

c. System.out.println(8/(int) a);

d. System.out.println(8/a);

e. System.out.println((int) (8/a));

Explain each outcome.

1.2.12 Describe what happens if you write sqrt instead of Math.sqrt in PROGRAM 1.2.3.

1.2.13 Evaluate the expression (Math.sqrt(2) * Math.sqrt(2) == 2).

1.2.14 Write a program that takes two positive integers as command-line arguments and prints true if either evenly divides the other.

1.2.15 Write a program that takes three positive integers as command-line arguments and prints false if any one of them is greater than or equal to the sum of the other two and true otherwise. (Note: This computation tests whether the three numbers could be the lengths of the sides of some triangle.)

1.2.16 A physics student gets unexpected results when using the code

Click here to view code image

 double force = G * mass1 * mass2 / r * r;

to compute values according to the formula F = Gm₁m₂ / r². Explain the problem and correct the code.

1.2.17 Give the value of the variable a after the execution of each of the following sequences of statements:

Click here to view code image

int a = 1;    boolean a = true;    int a = 2;
a = a + a;    a = !a;              a = a * a;
a = a + a;    a = !a;              a = a * a;
a = a + a;    a = !a;              a = a * a;

1.2.18 Write a program that takes two integer command-line arguments x and y and prints the Euclidean distance from the point (x, y) to the origin (0, 0).

1.2.19 Write a program that takes two integer command-line arguments a and b and prints a random integer between a and b, inclusive.

1.2.20 Write a program that prints the sum of two random integers between 1 and 6 (such as you might get when rolling dice).

1.2.21 Write a program that takes a double command-line argument t and prints the value of sin(2t) + sin(3t).

1.2.22 Write a program that takes three double command-line arguments x₀, v₀, and t and prints the value of x₀ + v₀t – g t² / 2, where g is the constant 9.80665. (Note: This value is the displacement in meters after t seconds when an object is thrown straight up from initial position x₀ at velocity v₀ meters per second.)

1.2.23 Write a program that takes two integer command-line arguments m and d and prints true if day d of month m is between 3/20 and 6/20, false otherwise.

1.2.25 Wind chill. Given the temperature T (in degrees Fahrenheit) and the wind speed v (in miles per hour), the National Weather Service defines the effective temperature (the wind chill) as follows:

w = 35.74 + 0.6215 T + (0.4275 T – 35.75) v^0.16

Write a program that takes two double command-line arguments temperature and velocity and prints the wind chill. Use Math.pow(a, b) to compute a^b. Note: The formula is not valid if T is larger than 50 in absolute value or if v is larger than 120 or less than 3 (you may assume that the values you get are in that range).

1.2.26 Polar coordinates. Write a program that converts from Cartesian to polar coordinates. Your program should accept two double command-line arguments x and y and print the polar coordinates r and θ. Use the method Math.atan2(y, x) to compute the arctangent value of y/x that is in the range from -π to π.

1.2.27 Gaussian random numbers. Write a program RandomGaussian that prints a random number r drawn from the Gaussian distribution. One way to do so is to use the Box–Muller formula

r = sin(2 π v) (–2 ln u)^1/2

where u and v are real numbers between 0 and 1 generated by the Math.random() method.

1.2.28 Order check. Write a program that takes three double command-line arguments x, y, and z and prints true if the values are strictly ascending or descending (x < y < z or x > y > z), and false otherwise.

1.2.29 Day of the week. Write a program that takes a date as input and prints the day of the week that date falls on. Your program should accept three int command-line arguments: m (month), d (day), and y (year). For m, use 1 for January, 2 for February, and so forth. For output, print 0 for Sunday, 1 for Monday, 2 for Tuesday, and so forth. Use the following formulas, for the Gregorian calendar:

y₀ = y – (14 – m) / 12
x = y₀ + y₀ / 4 – y₀ / 100 + y₀ / 400
m₀ = m + 12 × ((14 – m) / 12) – 2
d₀ = (d + x + (31 × m₀) / 12) % 7

Example: On which day of the week did February 14, 2000 fall?

y₀ = 2000 – 1 = 1999
x = 1999 + 1999 / 4 – 1999 / 100 + 1999 / 400 = 2483
m₀ = 2 + 12 × 1 – 2 = 12
d₀ = (14 + 2483 + (31 × 12) / 12) % 7 = 2500 % 7 = 1

Answer: Monday.

1.2.30 Uniform random numbers. Write a program that prints five uniform random numbers between 0 and 1, their average value, and their minimum and maximum values. Use Math.random(), Math.min(), and Math.max().

1.2.31 Mercator projection. The Mercator projection is a conformal (angle-preserving) projection that maps latitude φ and longitude λ to rectangular coordinates (x, y). It is widely used—for example, in nautical charts and in the maps that you print from the web. The projection is defined by the equations x = λ – λ₀ and y = 1/2 ln ((1 + sin φ) / (1 – sin φ)), where λ₀ is the longitude of the point in the center of the map. Write a program that takes λ₀ and the latitude and longitude of a point from the command line and prints its projection.

1.2.32 Color conversion. Several different formats are used to represent color. For example, the primary format for LCD displays, digital cameras, and web pages, known as the RGB format, specifies the level of red (R), green (G), and blue (B) on an integer scale from 0 to 255. The primary format for publishing books and magazines, known as the CMYK format, specifies the level of cyan (C), magenta (M), yellow (Y), and black (K) on a real scale from 0.0 to 1.0. Write a program RGBtoCMYK that converts RGB to CMYK. Take three integers—r, g, and b—from the command line and print the equivalent CMYK values. If the RGB values are all 0, then the CMY values are all 0 and the K value is 1; otherwise, use these formulas:

w = max (r / 255, g / 255, b / 255)
c = (w – (r / 255)) / w
m = (w – (g / 255)) / w
y = (w – (b / 255)) / w
k = 1 – w

1.2.33 Great circle. Write a program GreatCircle that takes four double command-line arguments—x1, y1, x2, and y2—(the latitude and longitude, in degrees, of two points on the earth) and prints the great-circle distance between them. The great-circle distance (in nautical miles) is given by the following equation:

d = 60 arccos(sin(x₁) sin(x₂) + cos(x₁) cos(x₂) cos(y₁ – y₂))

Note that this equation uses degrees, whereas Java’s trigonometric functions use radians. Use Math.toRadians() and Math.toDegrees() to convert between the two. Use your program to compute the great-circle distance between Paris (48.87° N and –2.33° W) and San Francisco (37.8° N and 122.4° W).

1.2.34 Three-sort. Write a program that takes three integer command-line arguments and prints them in ascending order. Use Math.min() and Math.max().

1.2.35 Dragon curves. Write a program to print the instructions for drawing the dragon curves of order 0 through 5. The instructions are strings of F, L, and R characters, where F means “draw line while moving 1 unit forward,” L means “turn left,” and R means “turn right.” A dragon curve of order n is formed when you fold a strip of paper in half n times, then unfold to right angles. The key to solving this problem is to note that a curve of order n is a curve of order n–1 followed by an L followed by a curve of order n–1 traversed in reverse order, and then to figure out a similar description for the reverse curve.

Specifically, we consider Java statements that implement conditionals, where some other statements may or may not be executed depending on certain conditions, and loops, where some other statements may be executed multiple times, again depending on certain conditions. As you will see in this section, conditionals and loops truly harness the power of the computer and will equip you to write programs to accomplish a broad variety of tasks that you could not contemplate attempting without a computer.

Click here to view code image

if (<boolean expression>) { <statements> }

This description introduces a formal notation known as a template that we will use to specify the format of Java constructs. We put within angle brackets (< >) a construct that we have already defined, to indicate that we can use any instance of that construct where specified. In this case, <boolean expression> represents an expression that evaluates to a boolean value, such as one involving a comparison operation, and <statements> represents a statement block (a sequence of Java statements). This latter construct is familiar to you: the body of main() is such a sequence. If the sequence is a single statement, the curly braces are optional. It is possible to make formal definitions of <boolean expression> and <statements>, but we refrain from going into that level of detail. The meaning of an if statement is self-explanatory: the statement(s) in the sequence are to be executed if and only if the expression is true.

As a simple example, suppose that you want to compute the absolute value of an int value x. This statement does the job:

if (x < 0) x = -x;

(More precisely, it replaces x with the absolute value of x.) As a second simple example, consider the following statement:

if (x > y)
{
   int t = x;
   x = y;
   y = t;
}

This code puts the smaller of the two int values in x and the larger of the two values in y, by exchanging the values in the two variables if necessary.

You can also add an else clause to an if statement, to express the concept of executing either one statement (or sequence of statements) or another, depending on whether the boolean expression is true or false, as in the following template:

Click here to view code image

if (<boolean expression>) <statements T>
else                      <statements F>

As a simple example of the need for an else clause, consider the following code, which assigns the maximum of two int values to the variable max:

if (x > y) max = x;
else       max = y;

One way to understand control flow is to visualize it with a diagram called a flowchart. Paths through the flowchart correspond to flow-of-control paths in the program. In the early days of computing, when programmers used low-level languages and difficult-to-understand flows of control, flowcharts were an essential part of programming. With modern languages, we use flowcharts just to understand basic building blocks like the if statement.

The accompanying table contains some examples of the use of if and if-else statements. These examples are typical of simple calculations you might need in programs that you write. Conditional statements are an essential part of programming. Since the semantics (meaning) of statements like these is similar to their meanings as natural-language phrases, you will quickly grow used to them.

PROGRAM 1.3.1 is another example of the use of the if-else statement, in this case for the task of simulating a fair coin flip. The body of the program is a single statement, like the ones in the table, but it is worth special attention because it introduces an interesting philosophical issue that is worth contemplating: can a computer program produce random values? Certainly not, but a program can produce numbers that have many of the properties of random numbers.

if (x > y)
{
   int t = x;
   x = y;
   y = t;
}

if (x > y) max = x;
else       max = y;

if (den == 0) System.out.println("Division by zero");
else          System.out.println("Quotient = " + num/den);

double discriminant = b*b - 4.0*c;
if (discriminant < 0.0)
{
   System.out.println("No real roots");
}
else
{
   System.out.println((-b + Math.sqrt(discriminant))/2.0);
   System.out.println((-b - Math.sqrt(discriminant))/2.0);
}

public class Flip
{
   public static void main(String[] args)
   {  // Simulate a fair coin flip.
      if (Math.random() < 0.5) System.out.println("Heads");
      else                     System.out.println("Tails");
   }
}

% java Flip
Heads
% java Flip
Tails
% java Flip
Tails

Click here to view code image

while (<boolean expression>) { <statements> }

The while statement has the same form as the if statement (the only difference being the use of the keyword while instead of if), but the meaning is quite different. It is an instruction to the computer to behave as follows: if the boolean expression is false, do nothing; if the boolean expression is true, execute the sequence of statements (just as with an if statement) but then check the expression again, execute the sequence of statements again if the expression is true, and continue as long as the expression is true. We refer to the statement block in a loop as the body of the loop. As with the if statement, the curly braces are optional if a while loop body has just one statement. The while statement is equivalent to a sequence of identical if statements:

Click here to view code image

if (<boolean expression>) { <statements> }
if (<boolean expression>) { <statements> }
if (<boolean expression>) { <statements> }
...

At some point, the code in one of the statements must change something (such as the value of some variable in the boolean expression) to make the boolean expression false, and then the sequence is broken.

A common programming paradigm involves maintaining an integer value that keeps track of the number of times a loop iterates. We start at some initial value, and then increment the value by 1 each time through the loop, testing whether it exceeds a predetermined maximum before deciding to continue. TenHellos (PROGRAM 1.3.2) is a simple example of this paradigm that uses a while statement. The key to the computation is the statement

i = i + 1;

As a mathematical equation, this statement is nonsense, but as a Java assignment statement it makes perfect sense: it says to compute the value i + 1 and then assign the result to the variable i. If the value of i was 4 before the statement, it becomes 5 afterward; if it was 5, it becomes 6; and so forth. With the initial condition in TenHellos that the value of i starts at 4, the statement block is executed seven times until the sequence is broken, when the value of i becomes 11.

Using the while loop is barely worthwhile for this simple task, but you will soon be addressing tasks where you will need to specify that statements be repeated far too many times to contemplate doing it without loops. There is a profound difference between programs with while statements and programs without them, because while statements allow us to specify a potentially unlimited number of statements to be executed in a program. In particular, the while statement allows us to specify lengthy computations in short programs. This ability opens the door to writing programs for tasks that we could not contemplate addressing without a computer. But there is also a price to pay: as your programs become more sophisticated, they become more difficult to understand.

public class TenHellos
{
   public static void main(String[] args)
   {  // Print 10 Hellos.
      System.out.println("1st Hello");
      System.out.println("2nd Hello");
      System.out.println("3rd Hello");
      int i = 4;
      while (i <= 10)
      {  // Print the ith Hello.
         System.out.println(i + "th Hello");
         i = i + 1;
      }
   }
}

% java TenHellos
1st Hello
2nd Hello
3rd Hello
4th Hello
5th Hello
6th Hello
7th Hello
8th Hello
9th Hello
10th Hello

PowersOfTwo (PROGRAM 1.3.3) uses a while loop to print out a table of the powers of 2. Beyond the loop control counter i, it maintains a variable power that holds the powers of 2 as it computes them. The loop body contains three statements: one to print the current power of 2, one to compute the next (multiply the current one by 2), and one to increment the loop control counter.

There are many situations in computer science where it is useful to be familiar with powers of 2. You should know at least the first 10 values in this table and you should note that 2¹⁰ is about 1 thousand, 2²⁰ is about 1 million, and 2³⁰ is about 1 billion.

PowersOfTwo is the prototype for many useful computations. By varying the computations that change the accumulated value and the way that the loop control variable is incremented, we can print out tables of a variety of functions (see EXERCISE 1.3.12).

It is worthwhile to carefully examine the behavior of programs that use loops by studying a trace of the program. For example, a trace of the operation of PowersOfTwo should show the value of each variable before each iteration of the loop and the value of the boolean expression that controls the loop. Tracing the operation of a loop can be very tedious, but it is often worthwhile to run a trace because it clearly exposes what a program is doing.

PowersOfTwo is nearly a self-tracing program, because it prints the values of its variables each time through the loop. Clearly, you can make any program produce a trace of itself by adding appropriate System.out.println() statements. Modern programming environments provide sophisticated tools for tracing, but this tried-and-true method is simple and effective. You certainly should add print statements to the first few loops that you write, to be sure that they are doing precisely what you expect.

public class PowersOfTwo
{
   public static void main(String[] args)
   {  // Print the first n powers of 2.
      int n = Integer.parseInt(args[0]);
      int power = 1;
      int i = 0;
      while (i <= n)
      {  // Print ith power of 2.
         System.out.println(i + " " + power);
         power = 2 * power;
         i = i + 1;
      }
   }
}

  n   | loop termination value
  i   | loop control counter
power | current power of 2

% java PowersOfTwo 5
0 1
1 2
2 4
3 8
4 16
5 32

% java PowersOfTwo 29
0 1
1 2
2 4
...
27 134217728
28 268435456
29 536870912

There is a hidden trap in PowersOfTwo, because the largest integer in Java’s int data type is 2³¹ – 1 and the program does not test for that possibility. If you invoke it with java PowersOfTwo 31, you may be surprised by the last line of output printed:

...
1073741824
-2147483648

The variable power becomes too large and takes on a negative value because of the way Java represents integers. The maximum value of an int is available for us to use as Integer.MAX_VALUE. A better version of PROGRAM 1.3.3 would use this value to test for overflow and print an error message if the user types too large a value, though getting such a program to work properly for all inputs is trickier than you might think. (For a similar challenge, see EXERCISE 1.3.16.)

As a more complicated example, suppose that we want to compute the largest power of 2 that is less than or equal to a given positive integer n. If n is 13, we want the result 8; if n is 1000, we want the result 512; if n is 64, we want the result 64; and so forth. This computation is simple to perform with a while loop:

int power = 1;
while (power <= n/2)
   power = 2*power;

It takes some thought to convince yourself that this simple piece of code produces the desired result. You can do so by making these observations:

• power is always a power of 2.

• power is never greater than n.

• power increases each time through the loop, so the loop must terminate.

• After the loop terminates, 2*power is greater than n.

Reasoning of this sort is often important in understanding how while loops work. Even though many of the loops you will write will be much simpler than this one, you should be sure to convince yourself that each loop you write will behave as you expect.

The logic behind such arguments is the same whether the loop iterates just a few times, as in TenHellos, or dozens of times, as in PowersOfTwo, or millions of times, as in several examples that we will soon consider. That leap from a few tiny cases to a huge computation is profound. When writing loops, understanding how the values of the variables change each time through the loop (and checking that understanding by adding statements to trace their values and running for a small number of iterations) is essential. Having done so, you can confidently remove those training wheels and truly unleash the power of the computer.

Click here to view code image

for (<initialize>; <boolean expression>; <increment>)
{
   <statements>
}

This code is, with only a few exceptions, equivalent to

<initialize>;
while (<boolean expression>)
{
   <statements>
   <increment>;
}

Your Java compiler might even produce identical results for the two loops. In truth, <initialize> and <increment> can be more complicated statements, but we nearly always use for loops to support this typical initialize-and-increment programming idiom. For example, the following two lines of code are equivalent to the corresponding lines of code in TenHellos (PROGRAM 1.3.2):

Click here to view code image

for (int i = 4; i <= 10; i = i + 1)
   System.out.println(i + "th Hello");

Typically, we work with a slightly more compact version of this code, using the shorthand notation discussed next.

Click here to view code image

i = i+1;   i++;   ++i;   i += 1;

You can also say i-- or --i or i -= 1 or i = i-1 to decrement that value of i by 1. Most programmers use i++ or i-- in for loops, though any of the others would do. The ++ and -- constructs are normally used for integers, but the compound assignment constructs are useful operations for any arithmetic operator in any primitive numeric type. For example, you can say power *= 2 or power += power instead of power = 2*power. All of these idioms are provided for notational convenience, nothing more. These shortcuts came into widespread use with the C programming language in the 1970s and have become standard. They have survived the test of time because they lead to compact, elegant, and easily understood programs. When you learn to write (and to read) programs that use them, you will be able to transfer that skill to programming in numerous modern languages, not just Java.

Choosing among different formulations of the same computation is a matter of each programmer’s taste, as when a writer picks from among synonyms or chooses between using active and passive voice when composing a sentence. You will not find good hard-and-fast rules on how to write a program any more than you will find such rules on how to compose a paragraph. Your goal should be to find a style that suits you, gets the computation done, and can be appreciated by others.

The accompanying table includes several code fragments with typical examples of loops used in Java code. Some of these relate to code that you have already seen; others are new code for straightforward computations. To cement your understanding of loops in Java, write some loops for similar computations of your own invention, or do some of the early exercises at the end of this section. There is no substitute for the experience gained by running code that you create yourself, and it is imperative that you develop an understanding of how to write Java code that uses loops.

int power = 1;
while (power <= n/2)
   power = 2*power;
System.out.println(power);

int sum = 0;
for (int i = 1; i <= n; i++)
   sum += i;
System.out.println(sum);

int product = 1;
for (int i = 1; i <= n; i++)
   product *= i;
System.out.println(product);

for (int i = 0; i <= n; i++)
   System.out.println(i + " " + 2*Math.PI*i/n);

String ruler = "1";
for (int i = 2; i <= n; i++)
   ruler = ruler + " " + i + " " + ruler;
System.out.println(ruler);

To emphasize the nesting, we use indentation in the program code. We refer to the i loop as the outer loop and the j loop as the inner loop. The inner loop iterates all the way through for each iteration of the outer loop. As usual, the best way to understand a new programming construct like this is to study a trace.

DivisorPattern has a complicated control flow, as you can see from its flowchart. A diagram like this illustrates the importance of using a limited number of simple control flow structures in programming. With nesting, you can compose loops and conditionals to build programs that are easy to understand even though they may have a complicated control flow. A great many useful computations can be accomplished with just one or two levels of nesting. For example, many programs in this book have the same general structure as DivisorPattern.

public class DivisorPattern
{
   public static void main(String[] args)
   {  // Print a square that visualizes divisors.
      int n = Integer.parseInt(args[0]);
      for (int i = 1; i <= n; i++)
      {  // Print the ith line.
         for (int j = 1; j <= n; j++)
         {  // Print the jth element in the ith line.
            if ((i % j == 0) || (j % i == 0))
               System.out.print("* ");
            else
               System.out.print("  ");
         }
         System.out.println(i);
      }
   }
}

n | number of rows and columns
i | row index
j | column index

% java DivisorPattern 3
* * *  1
* *    2
*   *  3
% java DivisorPattern 12
* * * * * * * * * * * * 1
* *   *   *   *   *   * 2
*   *     *     *     * 3
* *   *       *       * 4
*       *         *     5
* * *     *           * 6
*           *           7
* *   *       *         8
*   *           *       9
* *     *         *     10
*                   *   11
* * * *   *           * 12

As a second example of nesting, consider the following program fragment, which a tax preparation program might use to compute income tax rates:

Click here to view code image

if      (income <      0) rate = 0.00;
else if (income <   8925) rate = 0.10;
else if (income <  36250) rate = 0.15;
else if (income <  87850) rate = 0.23;
else if (income < 183250) rate = 0.28;
else if (income < 398350) rate = 0.33;
else if (income < 400000) rate = 0.35;
else                      rate = 0.396;

In this case, a number of if statements are nested to test from among a number of mutually exclusive possibilities. This construct is a special one that we use often. Otherwise, it is best to use curly braces to resolve ambiguities when nesting if statements. This issue and more examples are addressed in the Q&A and exercises.

The examples that we consider here involve computing with numbers. Several of our examples are tied to problems faced by mathematicians and scientists throughout the past several centuries. While computers have existed for only 70 years or so, many of the computational methods that we use are based on a rich mathematical tradition tracing back to antiquity.

public class HarmonicNumber
{
   public static void main(String[] args)
   {  // Compute the nth harmonic number.
      int n = Integer.parseInt(args[0]);
      double sum = 0.0;
      for (int i = 1; i <= n; i++)
      {  // Add the ith term to the sum.
         sum += 1.0/i;
      }
      System.out.println(sum);
   }
}

 n  | number of terms in sum
 i  | loop index
sum | cumulated sum

% java HarmonicNumber 2
1.5
% java HarmonicNumber 10
2.9289682539682538

% java HarmonicNumber 10000
7.485470860550343
% java HarmonicNumber 1000000
14.392726722864989

public class Sqrt
{
   public static void main(String[] args)
   {
      double c = Double.parseDouble(args[0]);
      double EPSILON = 1e-15;
      double t = c;
      while (Math.abs(t - c/t) > EPSILON * t)
      {  // Replace t by the average of t and c/t.
         t = (c/t + t) / 2.0;
      }
      System.out.println(t);
   }
}

   c    | argument
EPSILON | error tolerance
   t    | estimate of square root of c

% java Sqrt 2.0
1.414213562373095
% java Sqrt 2544545
1595.1630010754388

Computing the square root of a positive number c is equivalent to finding the positive root of the function f (x) = x² – c. For this special case, Newton’s method amounts to the process implemented in Sqrt (see EXERCISE 1.3.19). Start with the estimate t = c. If t is equal to c / t, then t is equal to the square root of c, so the computation is complete. If not, refine the estimate by replacing t with the average of t and c / t. With Newton’s method, we get the value of the square root of 2 accurate to 15 decimal places in just 5 iterations of the loop.

Newton’s method is important in scientific computing because the same iterative approach is effective for finding the roots of a broad class of functions, including many for which analytic solutions are not known (and for which the Java Math library is no help). Nowadays, we take for granted that we can find whatever values we need of mathematical functions; before computers, scientists and engineers had to use tables or compute values by hand. Computational techniques that were developed to enable calculations by hand needed to be very efficient, so it is not surprising that many of those same techniques are effective when we use computers. Newton’s method is a classic example of this phenomenon. Another useful approach for evaluating mathematical functions is to use Taylor series expansions (see EXERCISE 1.3.37 and EXERCISE 1.3.38).

public class Binary
{
   public static void main(String[] args)
   {  // Print binary representation of n.
      int n = Integer.parseInt(args[0]);
      int power = 1;
      while (power <= n/2)
         power *= 2;
      // Now power is the largest power of 2 <= n.

      while (power > 0)
      {  // Cast out powers of 2 in decreasing order.
         if (n < power) { System.out.print(0);             }
         else           { System.out.print(1); n -= power; }
         power /= 2;
      }
      System.out.println();
   }
}

  n   | integer to convert
power | current power of 2

% java Binary 19
10011
% java Binary 100000000
101111101011110000100000000

In Binary, the variable power corresponds to the current weight being tested, and the variable n accounts for the excess (unknown) part of the object’s weight (to simulate leaving a weight on the balance, we just subtract that weight from n). The value of power decreases through the powers of 2. When it is larger than n, Binary prints 0; otherwise, it prints 1 and subtracts power from n. As usual, a trace (of the values of n, power, n < power, and the output bit for each loop iteration) can be very useful in helping you to understand the program. Read from top to bottom in the rightmost column of the trace, the output is 10011, the binary representation of 19.

Converting data from one representation to another is a frequent theme in writing computer programs. Thinking about conversion emphasizes the distinction between an abstraction (an integer like the number of hours in a day) and a representation of that abstraction (24 or 11000). The irony here is that the computer’s representation of an integer is actually based on its binary representation.

Gambler (PROGRAM 1.3.8) is a simulation that can help answer these questions. It does a sequence of trials, using Math.random() to simulate the sequence of bets, continuing until either the gambler is broke or the goal is reached, and keeping track of the number of times the gambler reaches the goal and the number of bets. After running the experiment for the specified number of trials, it averages and prints the results. You might wish to run this program for various values of the command-line arguments, not necessarily just to plan your next trip to the casino, but to help you think about the following questions: Is the simulation an accurate reflection of what would happen in real life? How many trials are needed to get an accurate answer? What are the computational limits on performing such a simulation? Simulations are widely used in applications in economics, science, and engineering, and questions of this sort are important in any simulation.

In the case of Gambler, we are verifying classical results from probability theory, which say the probability of success is the ratio of the stake to the goal and that the expected number of bets is the product of the stake and the desired gain (the difference between the goal and the stake). For example, if you go to Monte Carlo to try to turn $500 into $2,500, you have a reasonable (20%) chance of success, but you should expect to make a million $1 bets! If you try to turn $1 into $1,000, you have a 0.1% chance and can expect to be done (ruined, most likely) in about 999 bets.

Simulation and analysis go hand-in-hand, each validating the other. In practice, the value of simulation is that it can suggest answers to questions that might be too difficult to resolve with analysis. For example, suppose that our gambler, recognizing that there will never be enough time to make a million bets, decides ahead of time to set an upper limit on the number of bets. How much money can the gambler expect to take home in that case? You can address this question with an easy change to PROGRAM 1.3.8 (see EXERCISE 1.3.26), but addressing it with mathematical analysis is not so easy.

public class Gambler
{
   public static void main(String[] args)
   {  // Run trials experiments that start with
      // $stake and terminate on $0 or $goal.
      int stake  = Integer.parseInt(args[0]);
      int goal   = Integer.parseInt(args[1]);
      int trials = Integer.parseInt(args[2]);
      int bets = 0;
      int wins = 0;
      for (int t = 0; t < trials; t++)
      {  // Run one experiment.
         int cash = stake;
         while (cash > 0 && cash < goal)
         {  // Simulate one bet.
             bets++;
             if (Math.random() < 0.5) cash++;
             else                     cash--;
         }  // Cash is either 0 (ruin) or $goal (win).
         if (cash == goal) wins++;
      }
      System.out.println(100*wins/trials + "% wins");
      System.out.println("Avg # bets: " + bets/trials);
   }
}

 stake | initial stake
 goal  | walkaway goal
trials | number of trials
 bets  | bet count
 wins  | win count
 cash  | cash on hand

% java Gambler 10 20 1000
50% wins
Avg # bets: 100
% java Gambler 10 20 1000
51% wins
Avg # bets: 98

% java Gambler 50 250 100
19% wins
Avg # bets: 11050
% java Gambler 500 2500 100
21% wins
Avg # bets: 998071

Although Factors is compact, it certainly will take some thought to convince yourself that it produces the desired result for any given integer. As usual, following a trace that shows the values of the variables at the beginning of each iteration of the outer for loop is a good way to understand the computation. For the case where the initial value of n is 3757208, the inner while loop iterates three times when factor is 2, to remove the three factors of 2; then zero times when factor is 3, 4, 5, and 6, since none of those numbers divides 469651; and so forth. Tracing the program for a few example inputs reveals its basic operation. To convince ourselves that the program will behave as expected for all inputs, we reason about what we expect each of the loops to do. The while loop prints and removes from n all factors of factor, but the key to understanding the program is to see that the following fact holds at the beginning of each iteration of the for loop: n has no factors between 2 and factor-1. Thus, if factor is not prime, it will not divide n; if factor is prime, the while loop will do its job. Once we know that n has no divisors less than or equal to factor, we also know that it has no factors greater than n/factor, so we need look no further when factor is greater than n/factor.

In a more naïve implementation, we might simply have used the condition (factor < n) to terminate the for loop. Even given the blinding speed of modern computers, such a decision would have a dramatic effect on the size of the numbers that we could factor. EXERCISE 1.3.28 encourages you to experiment with the program to learn the effectiveness of this simple change. On a computer that can do billions of operations per second, we could factor numbers on the order of 10⁹ in a few seconds; with the (factor <= n/factor) test, we can factor numbers on the order of 10¹⁸ in a comparable amount of time. Loops give us the ability to solve difficult problems, but they also give us the ability to construct simple programs that run slowly, so we must always be cognizant of performance.

public class Factors
{
   public static void main(String[] args)
   {  // Print the prime factorization of n.
      long n = Long.parseLong(args[0]);
      for (long factor = 2; factor <= n/factor; factor++)
      {  // Test potential factor.
         while (n % factor == 0)
         {  // Cast out and print factor.
            n /= factor;
            System.out.print(factor + " ");
         }  // Any factor of n must be greater than factor.
      }
      if (n > 1) System.out.print(n);
      System.out.println();
   }
}

   n   | unfactored part
factor | potential factor

% java Factors 3757208
2 2 2 7 13 13 397

% java Factors 287994837222311
17 1739347 9739789

In modern applications in cryptography, there are important situations where we wish to factor truly huge numbers (with, say, hundreds or thousands of digits). Such a computation is prohibitively difficult even with the use of a computer.

Click here to view code image

int factor;
for (factor = 2; factor <= n/factor; factor++)
   if (n % factor == 0) break;
if (factor > n/factor)
   System.out.println(n + " is prime");

There are two different ways to leave this loop: either the break statement is executed (because factor divides n, so n is not prime) or the loop-continuation condition is not satisfied (because no factor with factor <= n/factor was found that divides n, which implies that n is prime). Note that we have to declare factor outside the for loop instead of in the initialization statement so that its scope extends beyond the loop.

Click here to view code image

switch (day)
{
   case 0: System.out.println("Sun"); break;
   case 1: System.out.println("Mon"); break;
   case 2: System.out.println("Tue"); break;
   case 3: System.out.println("Wed"); break;
   case 4: System.out.println("Thu"); break;
   case 5: System.out.println("Fri"); break;
   case 6: System.out.println("Sat"); break;
}

When you have a program that seems to have a long and regular sequence of if statements, you might consider consulting the booksite and using a switch statement, or using an alternate approach described in SECTION 1.4.

Click here to view code image

do { <statements> } while (<boolean expression>);

The meaning of this statement is the same as

Click here to view code image

while (<boolean expression>) { <statements> }

except that the first test of the boolean condition is omitted. If the boolean condition initially holds, there is no difference. For an example in which do-while is useful, consider the problem of generating points that are randomly distributed in the unit disk. We can use Math.random() to generate x- and y-coordinates independently to get points that are randomly distributed in the 2-by-2 square centered on the origin. Most points fall within the unit disk, so we just reject those that do not. We always want to generate at least one point, so a do-while loop is ideal for this computation. The following code sets x and y such that the point (x, y) is randomly distributed in the unit disk:

Click here to view code image

do
{  // Scale x and y to be random in (-1, 1).
   x = 2.0*Math.random() - 1.0;
   y = 2.0*Math.random() - 1.0;
} while (x*x + y*y > 1.0);

Since the area of the disk is π and the area of the square is 4, the expected number of times the loop is iterated is 4/π (about 1.27).

First, suppose that such a loop calls System.out.println(). For example, if the loop-continuation condition in TenHellos were (i > 3) instead of (i <= 10), it would always be true. What happens? Nowadays, we use print as an abstraction to mean display in a terminal window and the result of attempting to display an unlimited number of lines in a terminal window is dependent on operating-system conventions. If your system is set up to have print mean print characters on a piece of paper, you might run out of paper or have to unplug the printer. In a terminal window, you need a stop printing operation. Before running programs with loops on your own, you make sure that you know what to do to “pull the plug” on an infinite loop of System.out.println() calls and then test out the strategy by making the change to TenHellos indicated above and trying to stop it. On most systems, <Ctrl-C> means stop the current program, and should do the job.

public class BadHellos
...
int i = 4;
while (i > 3)
{
   System.out.println
      (i + "th Hello");
   i = i + 1;
}
...

% java BadHellos
1st Hello
2nd Hello
3rd Hello
5th Hello
6th Hello
7th Hello
...

An infinite loop

Second, nothing might happen. If your program has an infinite loop that does not produce any output, it will spin through the loop and you will see no results at all. When you find yourself in such a situation, you can inspect the loops to make sure that the loop exit condition always happens, but the problem may not be easy to identify. One way to locate such a bug is to insert calls to System.out.println() to produce a trace. If these calls fall within an infinite loop, this strategy reduces the problem to the case discussed in the previous paragraph, but the output might give you a clue about what to do.

You might not know (or it might not matter) whether a loop is infinite or just very long. Even BadHellos eventually would terminate after printing more than 1 billion lines because of integer overflow. If you invoke PROGRAM 1.3.8 with arguments such as java Gambler 100000 200000 100, you may not want to wait for the answer. You will learn to be aware of and to estimate the running time of your programs.

Why not have Java detect infinite loops and warn us about them? You might be surprised to know that it is not possible to do so, in general. This counterintuitive fact is one of the fundamental results of theoretical computer science.

To learn how to use conditionals and loops, you must practice writing and debugging programs with if, while, and for statements. The exercises at the end of this section provide many opportunities for you to begin this process. For each exercise, you will write a Java program, then run and test it. All programmers know that it is unusual to have a program work as planned the first time it is run, so you will want to have an understanding of your program and an expectation of what it should do, step by step. At first, use explicit traces to check your understanding and expectation. As you gain experience, you will find yourself thinking in terms of what a trace might produce as you compose your loops. Ask yourself the following kinds of questions: What will be the values of the variables after the loop iterates the first time? The second time? The final time? Is there any way this program could get stuck in an infinite loop?

Loops and conditionals are a giant step in our ability to compute: if, while, and for statements take us from simple straight-line programs to arbitrarily complicated flow of control. In the next several chapters, we will take more giant steps that will allow us to process large amounts of input data and allow us to define and process types of data other than simple numeric types. The if, while, and for statements of this section will play an essential role in the programs that we consider as we take these steps.

A. We repeat this question here to remind you to be sure not to use = when you mean == in a boolean expression. The expression (x = y) assigns the value of y to x, whereas the expression (x == y) tests whether the two variables currently have the same values. In some programming languages, this difference can wreak havoc in a program and be difficult to detect, but Java’s type safety usually will come to the rescue. For example, if we make the mistake of typing (cash = goal) instead of (cash == goal) in PROGRAM 1.3.8, the compiler finds the bug for us:

Click here to view code image

javac Gambler.java
Gambler.java:18: incompatible types
found : int
required: boolean
if (cash = goal) wins++;
    ^
1 error

Be careful about writing if (x = y) when x and y are boolean variables, since this will be treated as an assignment statement, which assigns the value of y to x and evaluates to the truth value of y. For example, you should write if (!isPrime) instead of if (isPrime = false).

Q. So I need to pay attention to using == instead of = when writing loops and conditionals. Is there something else in particular that I should watch out for?

A. Another common mistake is to forget the braces in a loop or conditional with a multi-statement body. For example, consider this version of the code in Gambler:

Click here to view code image

for (int t = 0; t < trials; t++)
   for (cash = stake; cash > 0 && cash < goal; bets++)
      if (Math.random() < 0.5) cash++;
      else                     cash--;
   if (cash == goal) wins++;

The code appears correct, but it is dysfunctional because the second if is outside both for loops and gets executed just once. Many programmers always use braces to delimit the body of a loop or conditional precisely to avoid such insidious bugs.

Q. Anything else?

A. The third classic pitfall is ambiguity in nested if statements:

Click here to view code image

if <expr1> if <expr2> <stmntA> else <stmntB>

In Java, this is equivalent to

Click here to view code image

if <expr1> { if <expr2> <stmntA> else <stmntB> }

even if you might have been thinking

Click here to view code image

if <expr1> { if <expr2> <stmntA> } else <stmntB>

Again, using explicit braces to delimit the body is a good way to avoid this pitfall.

Q. Are there cases where I must use a for loop but not a while, or vice versa?

A. No. Generally, you should use a for loop when you have an initialization, an increment, and a loop continuation test (if you do not need the loop control variable outside the loop). But the equivalent while loop still might be fine.

Q. What are the rules on where we declare the loop-control variables?

A. Opinions differ. In older programming languages, it was required that all variables be declared at the beginning of a block, so many programmers are in this habit and a lot of code follows this convention. But it makes a great deal of sense to declare variables where they are first used, particularly in for loops, when it is normally the case that the variable is not needed outside the loop. However, it is not uncommon to need to test (and therefore declare) the loop-control variable outside the loop, as in the primality-testing code we considered as an example of the break statement.

Q. What is the difference between ++i and i++?

A. As statements, there is no difference. In expressions, both increment i, but ++i has the value after the increment and i++ the value before the increment. In this book, we avoid statements like x = ++i that have the side effect of changing variable values. So, it is safe to not worry much about this distinction and just use i++ in for loops and as a statement. When we do use ++i in this book, we will call attention to it and say why we are using it.

Q. In a for loop, <initialize> and <increment> can be statements more complicated than declaring, initializing, and updating a loop-control variable. How can I take advantage of this ability?

A. The <initialize> and <increment> can be sequences of statements, separated by commas. This notation allows for code that initializes and modifies other variables besides the loop-control variable. In some cases, this ability leads to compact code. For example, the following two lines of code could replace the last eight lines in the body of the main() method in PowersOfTwo (PROGRAM 1.3.3):

Click here to view code image

for (int i = 0, power = 1; i <= n; i++, power *= 2)
   System.out.println(i + " " + power);

Such code is rarely necessary and better avoided, particularly by beginners.

Q Can I use a double variable as a loop-control variable in a for loop?

A It is legal, but generally bad practice to do so. Consider the following loop:

Click here to view code image

for (double x = 0.0; x <= 1.0; x += 0.1)
   System.out.println(x + " " + Math.sin(x));

How many times does it iterate? The number of iterations depends on an equality test between double values, which may not always give the result that you expect because of floating-point precision.

Q. Anything else tricky about loops?

A. Not all parts of a for loop need to be filled in with code. The initialization statement, the boolean expression, the increment statement, and the loop body can each be omitted. It is generally better style to use a while statement than null statements in a for loop. In the code in this book, we avoid such empty statements.

1.3.2 Write a more general and more robust version of Quadratic (PROGRAM 1.2.3) that prints the roots of the polynomial ax² + bx + c, prints an appropriate message if the discriminant is negative, and behaves appropriately (avoiding division by zero) if a is zero.

1.3.3 What (if anything) is wrong with each of the following statements?

a. if (a > b) then c = 0;

b. if a > b { c = 0; }

c. if (a > b) c = 0;

d. if (a > b) c = 0 else b = 0;

1.3.4 Write a code fragment that prints true if the double variables x and y are both strictly between 0 and 1, and false otherwise.

1.3.5 Write a program RollLoadedDie that prints the result of rolling a loaded die such that the probability of getting a 1, 2, 3, 4, or 5 is 1/8 and the probability of getting a 6 is 3/8.

1.3.6 Improve your solution to EXERCISE 1.2.25 by adding code to check that the values of the command-line arguments fall within the ranges of validity of the formula, and by also adding code to print out an error message if that is not the case.

1.3.7 Suppose that i and j are both of type int. What is the value of j after each of the following statements is executed?

a. for (i = 0, j = 0; i < 10; i++) j += i;

b. for (i = 0, j = 1; i < 10; i++) j += j;

c. for (j = 0; j < 10; j++) j += j;

d. for (i = 0, j = 0; i < 10; i++) j += j++;

1.3.8 Rewrite TenHellos to make a program Hellos that takes the number of lines to print as a command-line argument. You may assume that the argument is less than 1000. Hint: Use i % 10 and i % 100 to determine when to use st, nd, rd, or th for printing the ith Hello.

1.3.9 Write a program that, using one for loop and one if statement, prints the integers from 1,000 to 2,000 with five integers per line. Hint: Use the % operation.

1.3.10 Write a program that takes an integer command-line argument n, uses Math.random() to print n uniform random values between 0 and 1, and then prints their average value (see EXERCISE 1.2.30).

1.3.11 Describe what happens when you try to print a ruler function (see the table on page 57) with a value of n that is too large, such as 100.

1.3.12 Write a program FunctionGrowth that prints a table of the values log n, n, n log_e n, n², n³, and 2ⁿ for n = 16, 32, 64, ..., 2,048. Use tabs ( characters) to align columns.

1.3.13 What are the values of m and n after executing the following code?

int n = 123456789;
int m = 0;
while (n != 0)
{
   m = (10 * m) + (n % 10);
   n = n / 10;
}

1.3.14 What does the following code fragment print?

int f = 0, g = 1;
for (int i = 0; i <= 15; i++)
{
   System.out.println(f);
   f = f + g;
   g = f - g;
}

Solution. Even an expert programmer will tell you that the only way to understand a program like this is to trace it. When you do, you will find that it prints the values 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 134, 233, 377, and 610. These numbers are the first sixteen of the famous Fibonacci sequence, which are defined by the following formulas: F₀ = 0, F₁ = 1, and F_n = F_n-1 + F_n-2 for n > 1.

1.3.15 How many lines of output does the following code fragment produce?

Click here to view code image

for (int i = 0; i < 999; i++);
{  System.out.println("Hello");  }

Solution. One. Note the spurious semicolon at the end of the first line.

1.3.16 Write a program that takes an integer command-line argument n and prints all the positive powers of 2 less than or equal to n. Make sure that your program works properly for all values of n.

1.3.17 Expand your solution to EXERCISE 1.2.24 to print a table giving the total amount of money you would have after t years for t = 0 to 25..

1.3.18 Unlike the harmonic numbers, the sum 1/1² + 1/2² + ... + 1/n² does converge to a constant as n grows to infinity. (Indeed, the constant is π²/6, so this formula can be used to estimate the value of π.) Which of the following for loops computes this sum? Assume that n is an int variable initialized to 1000000 and sum is a double variable initialized to 0.0.

a. for (int i = 1; i <= n; i++) sum += 1 / (i*i);

b. for (int i = 1; i <= n; i++) sum += 1.0 / i*i;

c. for (int i = 1; i <= n; i++) sum += 1.0 / (i*i);

d. for (int i = 1; i <= n; i++) sum += 1 / (1.0*i*i);

1.3.19 Show that PROGRAM 1.3.6 implements Newton’s method for finding the square root of c. Hint: Use the fact that the slope of the tangent to a (differentiable) function f (x) at x = t is f′(t) to find the equation of the tangent line, and then use that equation to find the point where the tangent line intersects the x-axis to show that you can use Newton’s method to find a root of any function as follows: at each iteration, replace the estimate t by t – f (t) / f ′(t).

1.3.20 Using Newton’s method, develop a program that takes two integer command-line arguments n and k and prints the kth root of n (Hint: See EXERCISE 1.3.19).

1.3.21 Modify Binary to get a program Kary that takes two integer command-line arguments i and k and converts i to base k. Assume that i is an integer in Java’s long data type and that k is an integer between 2 and 16. For bases greater than 10, use the letters A through F to represent the 11th through 16th digits, respectively.

1.3.22 Write a code fragment that puts the binary representation of a positive integer n into a String variable s.

Solution. Java has a built-in method Integer.toBinaryString(n) for this job, but the point of the exercise is to see how such a method might be implemented. Working from PROGRAM 1.3.7, we get the solution

Click here to view code image

String s = "";
int power = 1;
while (power <= n/2) power *= 2;
while (power > 0)
{
   if (n < power) { s += 0;             }
   else           { s += 1; n -= power; }
   power /= 2;
}

A simpler option is to work from right to left:

Click here to view code image

String s = "";
for (int i = n; i > 0; i /= 2)
   s = (i % 2) + s;

Both of these methods are worthy of careful study.

1.3.23 Write a version of Gambler that uses two nested while loops or two nested for loops instead of a while loop inside a for loop.

1.3.24 Write a program GamblerPlot that traces a gambler’s ruin simulation by printing a line after each bet in which one asterisk corresponds to each dollar held by the gambler.

1.3.25 Modify Gambler to take an extra command-line argument that specifies the (fixed) probability that the gambler wins each bet. Use your program to try to learn how this probability affects the chance of winning and the expected number of bets. Try a value of p close to 0.5 (say, 0.48).

1.3.26 Modify Gambler to take an extra command-line argument that specifies the number of bets the gambler is willing to make, so that there are three possible ways for the game to end: the gambler wins, loses, or runs out of time. Add to the output to give the expected amount of money the gambler will have when the game ends. Extra credit: Use your program to plan your next trip to Monte Carlo.

1.3.27 Modify Factors to print just one copy each of the prime divisors.

1.3.28 Run quick experiments to determine the impact of using the termination condition (factor <= n/factor) instead of (factor < n) in Factors in PROGRAM 1.3.9. For each method, find the largest n such that when you type in an n-digit number, the program is sure to finish within 10 seconds.

1.3.29 Write a program Checkerboard that takes an integer command-line argument n and uses a loop nested within a loop to print out a two-dimensional n-by-n checkerboard pattern with alternating spaces and asterisks.

1.3.30 Write a program GreatestCommonDivisor that finds the greatest common divisor (gcd) of two integers using Euclid’s algorithm, which is an iterative computation based on the following observation: if x is greater than y, then if y divides x, the gcd of x and y is y; otherwise, the gcd of x and y is the same as the gcd of x % y and y.

1.3.31 Write a program RelativelyPrime that takes an integer command-line argument n and prints an n-by-n table such that there is an * in row i and column j if the gcd of i and j is 1 (i and j are relatively prime) and a space in that position otherwise.

1.3.32 Write a program PowersOfK that takes an integer command-line argument k and prints all the positive powers of k in the Java long data type. Note: The constant Long.MAX_VALUE is the value of the largest integer in long.

1.3.33 Write a program that prints the coordinates of a random point (a, b, c) on the surface of a sphere. To generate such a point, use Marsaglia’s method: Start by picking a random point (x, y) in the unit disk using the method described at the end of this section. Then, set a to 2⁢x1−x2−y2, b to 21−x2−y2, and c to 1– 2 (x² + y²).

1.3.35 Checksum. The International Standard Book Number (ISBN) is a 10-digit code that uniquely specifies a book. The rightmost digit is a checksum digit that can be uniquely determined from the other 9 digits, from the condition that d₁ + 2d₂ +3d₃ + ... + 10d₁₀ must be a multiple of 11 (here d_i denotes the ith digit from the right). The checksum digit d₁ can be any value from 0 to 10. The ISBN convention is to use the character 'X' to denote 10. As an example, the checksum digit corresponding to 020131452 is 5 since 5 is the only value of x between 0 and 10 for which

10·0 + 9·2 + 8·0 + 7·1 + 6·3 + 5·1 +4·4 +3·5 + 2·2 + 1·x

is a multiple of 11. Write a program that takes a 9-digit integer as a command-line argument, computes the checksum, and prints the ISBN number.

1.3.36 Counting primes. Write a program PrimeCounter that takes an integer command-line argument n and finds the number of primes less than or equal to n. Use it to print out the number of primes less than or equal to 10 million. Note: If you are not careful, your program may not finish in a reasonable amount of time!

1.3.37 2D random walk. A two-dimensional random walk simulates the behavior of a particle moving in a grid of points. At each step, the random walker moves north, south, east, or west with probability equal to 1/4, independent of previous moves. Write a program RandomWalker that takes an integer command-line argument n and estimates how long it will take a random walker to hit the boundary of a 2n-by-2n square centered at the starting point.

1.3.38 Exponential function. Assume that x is a positive variable of type double. Write a code fragment that uses the Taylor series expansion to set the value of sum to e^x = 1 + x + x²/2! + x³/3! + . . . .

Solution. The purpose of this exercise is to get you to think about how a library function like Math.exp() might be implemented in terms of elementary operators. Try solving it, then compare your solution with the one developed here.

We start by considering the problem of computing one term. Suppose that x and term are variables of type double and n is a variable of type int. The following code fragment sets term to xⁿ / n ! using the direct method of having one loop for the numerator and another loop for the denominator, then dividing the results:

Click here to view code image

double num = 1.0, den = 1.0;
for (int i = 1; i <= n; i++) num *= x;
for (int i = 1; i <= n; i++) den *= i;
double term = num/den;

A better approach is to use just a single for loop:

Click here to view code image

double term = 1.0;
for (i = 1; i <= n; i++) term *= x/i;

Besides being more compact and elegant, the latter solution is preferable because it avoids inaccuracies caused by computing with huge numbers. For example, the two-loop approach breaks down for values like x = 10 and n = 100 because 100! is too large to represent as a double.

To compute e^x, we nest this for loop within another for loop:

Click here to view code image

double term = 1.0;
double sum = 0.0;
for (int n = 1; sum != sum + term; n++)
{
   sum += term;
   term = 1.0;
   for (int i = 1; i <= n; i++) term *= x/i;
}

The number of times the loop iterates depends on the relative values of the next term and the accumulated sum. Once the value of the sum stops changing, we leave the loop. (This strategy is more efficient than using the loop-continuation condition (term > 0) because it avoids a significant number of iterations that do not change the value of the sum.) This code is effective, but it is inefficient because the inner for loop recomputes all the values it computed on the previous iteration of the outer for loop. Instead, we can make use of the term that was added in on the previous loop iteration and solve the problem with a single for loop:

Click here to view code image

double term = 1.0;
double sum = 0.0;
for (int n = 1; sum != sum + term; n++)
{
   sum += term;
   term *= x/n;
}

1.3.39 Trigonometric functions. Write two programs, Sin and Cos, that compute the sine and cosine functions using their Taylor series expansions sin x = x – x³/3! + x⁵/5! – ... and cos x = 1 – x²/2! + x⁴/4! – ... .

1.3.40 Experimental analysis. Run experiments to determine the relative costs of Math.exp() and the methods from EXERCISE 1.3.38 for computing e^x: the direct method with nested for loops, the improvement with a single for loop, and the latter with the loop-continuation condition (term > 0). Use trial-and-error with a command-line argument to determine how many times your computer can perform each computation in 10 seconds.

1.3.41 Pepys problem. In 1693 Samuel Pepys asked Isaac Newton which is more likely: getting 1 at least once when rolling a fair die six times or getting 1 at least twice when rolling it 12 times. Write a program that could have provided Newton with a quick answer.

1.3.42 Game simulation. In the game show Let’s Make a Deal, a contestant is presented with three doors. Behind one of them is a valuable prize. After the contestant chooses a door, the host opens one of the other two doors (never revealing the prize, of course). The contestant is then given the opportunity to switch to the other unopened door. Should the contestant do so? Intuitively, it might seem that the contestant’s initial choice door and the other unopened door are equally likely to contain the prize, so there would be no incentive to switch. Write a program MonteHall to test this intuition by simulation. Your program should take a command-line argument n, play the game n times using each of the two strategies (switch or do not switch), and print the chance of success for each of the two strategies.

1.3.43 Median-of-5. Write a program that takes five distinct integers as command-line arguments and prints the median value (the value such that two of the other integers are smaller and two are larger). Extra credit: Solve the problem with a program that compares values fewer than 7 times for any given input.

1.3.44 Sorting three numbers. Suppose that the variables a, b, c, and t are all of the type int. Explain why the following code puts a, b, and c in ascending order:

Click here to view code image

if (a > b) { t = a; a = b; b = t; }
if (a > c) { t = a; a = c; c = t; }
if (b > c) { t = b; b = c; c = t; }

1.3.45 Chaos. Write a program to study the following simple model for population growth, which might be applied to study fish in a pond, bacteria in a test tube, or any of a host of similar situations. We suppose that the population ranges from 0 (extinct) to 1 (maximum population that can be sustained). If the population at time t is x, then we suppose the population at time t + 1 to be r x (1–x), where the argument r, known as the fecundity parameter, controls the rate of growth. Start with a small population—say, x = 0.01—and study the result of iterating the model, for various values of r. For which values of r does the population stabilize at x = 1 – 1/r? Can you say anything about the population when r is 3.5? 3.8? 5?

1.3.46 Euler’s sum-of-powers conjecture. In 1769 Leonhard Euler formulated a generalized version of Fermat’s Last Theorem, conjecturing that at least n nth powers are needed to obtain a sum that is itself an nth power, for n > 2. Write a program to disprove Euler’s conjecture (which stood until 1967), using a quintuply nested loop to find four positive integers whose 5th power sums to the 5th power of another positive integer. That is, find a, b, c, d, and e such that a⁵ + b⁵ + c⁵ + d⁵ = e⁵. Use the long data type.