Numeric Notes

Because the Java primitive types are stored in fixed-size spaces, as a Python float is, they have restrictions. In particular int is not of unlimited size. Java has a number of sizes. The most common integer types are int and the larger long.

char

A char is a single character, with literals in single quotes, like 'x'. In Java this is distinct from a String, even a String with one character, like “x”. Technically char is a small numeric type: It just prints as a character, but can be used in arithmetic expressions. (More later.) Coming from Python, errors confusing a char and a one-character String are common!

Because the Java primitive types are stored in fixed-size spaces, like a Python float is, they have restrictions. Limits are accessible in Java with wrapper class static values: Integer.MAX_VALUE, Integer.MIN_VALUE, Double.MAX_VALUE, .... Here is some of the data collected:

long

64 bits; range -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

int

32 bits; range -2,147,483,648 to 2,147,483,647

double

64 bits; maximum magnitude: 1.7976931348623157(10³⁰⁸); about 15 digits of accuracy

float

32 bits; maximum magnitude: 3.402823(10³⁸); about 7 digits of accuracy

Operators - not in Java4Python

Java does arithmetic in the temperature conversion program. More detailed discussion of operators is in order:

Just as some Java data types correspond closely Python, while others have less in common, the same is true of operators.

+ - *

Addition, subtraction, multiplication and negation correspond closely, except if the result does not fit in the range of the result type: then an overflow error occurs, silently in Java! This could be a huge and hard to debug problem in Java!

/

Java does not use // for any division. (Rather // starts a comment.) Instead / does double duty, based on the type of the operands. If at least one operand is a double, it behaves like Python /. If both are ints, it behaves like Python // - only when both operands have the same sign, but not when the real number result would be negative: Python returns the floor of the real division (greatest integer <= real result) while Java truncates toward 0.

In the Fahrenheit conversion program, note that the expression (fahr - 32) * 5.0/9.0 evaluates correctly, and would have the same result if written (fahr - 32) * 5/9. Evaluating from left to right starting with double variable fahr means every intermediate operation produces a double result. However, the expression (fahr - 32) * (5/9) would not be the same! The parentheses around 5/9 means this integer quotient is calculated separately. The int operands means it would be the same as Python 5//9, so it equals 0! In Java 5/9 is not anything like 5/9 in math!

+ with a string

See the use of the + operator to print the result in the temperature conversion program. In Java + concatenates strings like in Python, but the use is more general than in Python: Python requires both operands to be strings. Java requires only one of the operands to be a string, and the second will be implicitly converted to a string. For example if x is an int, the expression "Value: " + x is illegal in Python, but fine in Java. In Python we would have to make the type conversion explicit: "Value: " + str(x).

The + operator is important in printing, since System.out.println is allowed only one parameter, not a list of parameters like in Python. Hence the one parameter is often an expression. One way to make a larger expression is with +. Later we will also see that Java has a format method something like in Python.

%

The remainder operation % is the same in both languages if the sign of both operands is the same, but not with different signs. With integers d and n, d*(n//d) + n%d always equals n in Python, and d*(n/d) + n%d always equals n in Java, but since integer division works differently with different signs, so does %.

&& || !

Boolean operator and, or and not in Python correspond exactly to Java &&, || and ! if operands have Boolean values.

+= ++ --

Java also allows the modification operators like +=. Incrementing and decrementing by 1 have special operators ++ and --, as illustrated in the List section.

==

With primitive numeric data, == checks for mathematical equality, like in Python. However, when two objects are compared in Java using the == operator they are tested to see if they are exactly the same object, that is do the two objects occupy the same exact space in the computers memory (Python is operator). You will see later that you need to use an equals method with objects like Strings.

Play with these in jshell! Get used to the similarities and differences. Here are a few specific ideas:

• Set two int values x and y. Choose them so x+y will not have the right mathematical value.

• Set long variables s and t to the same values. See that s+t has the right numerical value.

• Compare 3/2 and 3.0/2 in Java.

• Have a Python program or console going too. Compare -5 % 2 in Python and Java.

• Also compare Python 2*(-5//2) + -5 % 2 and Java 2*(-5/2) + -5 % 2

• Check that the boolean operator behavior match Python. For instance variations on

  (3 > 5) || (1 < 9 )
  (3 > 5) && (1 < 9 )
  

Declaring Variables Notes

In the temperature conversion example above, lines 5—7 contain variable declarations. If we use double rather than Double in lines 5 and 6, then fahr and cel are going to refer directly to spaces that store the primitive double data. Here I follow the usual form, and use the smaller and more efficient primitive type double, not the object type Double. We will use object wrapper classes only in the few places where they are required.

The declarations means that if we were to try an assignment like fahr = "xyz" the compiler would generate an error because "xyz" is a string and fahr is supposed to be a double.

The variable in will reference a Scanner object, discussed more below.

For Python programmers the following error is likely to be even more common. Suppose we forgot the declaration for cel and instead left line 6 blank. What would happen when we type javac TempConv.java on the command line?

TempConv.java:13: cannot find symbol

symbol : variable cel

location: class TempConv

cel = (fahr - 32) * 5.0/9.0;

^

TempConv.java:14: cannot find symbol

symbol : variable cel

location: class TempConv

System.out.println("The temperature in C is: " + cel);

^

2 errors

When you see the first kind of error, where the symbol is on the left side of the equals sign it usually means that you have not declared the variable. If you have ever tried to use a Python variable that you have not initialized the second error message will be familiar to you. The difference here is that we see the message before we ever try to test our program. More common error messages are discussed in the later section Common mistakes.

Data Review Questions

1. Most of Java arithmetic is just like normal math. The exceptions are most important: What are they?

2. What are the consequences of numerical value types each being stored in a fixed amount of memory space?

3. What is the order of operations if several of the same level, are chained together like x + y + z? This can matter in Java (including in a question below).

4. Which of these individual two-line fragments could fit into a legal Java program? Explain:

   w = 3;
   w = 4;
   
   x = 3;
   x = x+1;
   
   y = 3;
   y = "hello";
   
   z = 3.5
   z = 3;
   
   q = 3;
   q + 1 = q;
   

5. For the legal pairs above, what could the type of the variable have been declared? You can check them in jshell, giving the declaration first.

Input / Output / Scanner Notes

In the creation of the Scanner object: Java is verbose when calling a constructor for an object type like Scanner. The constructor must be preceded by the keyword new, as in in = new Scanner(System.in); Like forgetting semicolons, omitting the new is a really common error for Python programmers. Try removing the new and run, and see what the error says -- so you are prepared!

I object to the book's use of the wrapper types like Double when discussing the Scanner class. The wrapper classes are even listed as return types in the book, like for nextDouble(): In fact all the basic numeric ones return primitive types like double.

Again, because primitives have less overhead, and Java generally wraps/unwraps implicitly as needed, use the primitive type where you can (most everywhere).

Note that the Scanner input methods significantly differ from Python input with types. Python conveniently includes the prompt parameter for the input function. In Java you need to have a separate preceding statement to print the prompt (or as we will see later, write our own utility methods that do both).

The table of Scanner methods ends with nextLine(). This is like Python input() (no prompt) IF you are at the start of input or last used nextLine() for the previous line. The difference is that in Python, you always read a whole line at a time, and pass the newline to be ready for the start of the next line, but the other Java Scanner input methods, like nextInt(), read to the end of a token ONLY,(even through several lines if there is only whitespace in between), but not necessarily to the end of a line, and always leaving any following newline unread. Calling nextLine() reads through the next '\n', which could just be the rest of a line after a token read with something like nextInt().

For example if the next part of the input for Scanner in is

42

the answer to the universe and everything

and you have the code

int n = in.nextInt();  // ok, n is 42
String s =  in.nextLine();  oops, s is ""

You would need a middle line in.nextLine(); for s to be the long string. Easy to cause problems!

Java has both println and print methods. The latter does not automatically add a newline.

This can be simulated in Python:

print(s, end='')

is like System.out.print(s).

The methods hasNextInt, hasNextDouble can check to see if the next token after possible whitespace has the proper form to be seen as an int or double.

A Scanner can also be used to read from a file or just a string. Both are finite - with an end. In that context the all the hasNext... methods will make sense, including plain hasNext, meaning there is some kind of token still to come. This makes little sense in reading from the keyboard, where you could enter more data forever. If you use hasNext with the keyboard, your program would just stop and wait for more lines if you entered nothing but whitespace. Also important for reading for a file or String: hasNextLine.

Please skip the final GUI example using the Swing class.

Division Exercise

Write a program Div.java with class Div

• Prompts the user to enter an integer

• Read it with a Scanner

• Prompts the user to enter another integer, and then read it

• Label and print the values of the integer quotient, remainder, and real quotient. For instance if the user enters 7 and then 2 you might print

  7 divided by 2 is 3 with a remainder of 1.

  The real quotient is 3.5.

Numeric Type Conversions

This section is not in Java4Python.

We had fewer numeric types in Python, so there were fewer conversion issues. We already saw in Python that 2.3 + 5 (float + int) made sense: the less general type int is converted implicitly to the more general type float. The same is true in Java.

In Python constructors could do explicit conversion, including where information is lost:

x = 2.8      # float
y = int(x)   # int 2
x = -5.7     # float
y = int(x)   # int -5

Converting a float to an int truncates toward 0 - losing the fractional part.

The exact same idea appears in Java with very different notation, called casting. A cast involves the new type name in parentheses before the value to be converted:

double x = 2.8;
int y = (int) x;
x = -5.7;
y = (int) x;

The resulting int values are truncations like in Python. An explicit cast is generally only needed when the new type holds less information. The other direction can be implicit:

double z = 2;

The Java char type can be trickier. It is a numeric type smaller than an int. Binary arithmetic operations with numeric types smaller than int get automatically converted to int operations. The character 'A' has numeric value (its ASCII code) 65. The following letters of the alphabet have successive numeric values.

char ch = 'A';
int v = ch; // 65
ch++;  // now ch is 'B'
v = ch; // 66
ch = (char)(c+1);  // 'C'  Note cast!!
int diff = ch - 'A' //2: 'C' 2 after 'A'
boolean isPast = ch > 'A'; // true

If the cast had been left out in the third to last line:

ch = ch + 1;

there would be an error, since ch + 1 is a char plus an int, where the char is implicitly converted to an int for the arithmetic, but then the larger type int cannot be assigned back to the smaller type char without an explicit cast.

The error in IntelliJ IDEA 2018 if the cast is omitted is:

java: incompatible types: possible lossy conversion from int to char

What if you want to round rather than truncate a double. There is a method Math.round, but it produces a long, This can be combined with casting to int:

double x = 2.8;
int r = (int)Math.round(x);  // r is 3, not 2: rounded not truncated.

We have been discussing casts with primitives. The same word, cast, and notation are used with objects with a totally different interpretation. It will only make sense after you study inheritance in your next class. We skip it here!

While Python has simple conversion syntax to change a string to a number, Java is more verbose:

int i = Integer.parseInt("-22");  // i is -22
double d = Double.parseDouble("-3.5");  // d is 3.5

The shortest notation to convert a number v, or anything else, to a String is "" + v using the conversion ability of + with a String.

Conversion and Op Questions

1. What is printed?

   int x = 7, y = 2;
   double d = 5.678;
   char ch = 'H';
   ch--;
   System.out.println(x/y);
   System.out.println((int)d);
   System.out.println(ch);
   System.out.println('J' - ch);
   System.out.println('B' > ch);
   

2. This is not obvious for many. What is printed? Explain.

   int x = 2, y = 3;
   System.out.println('Sum is ' + x + y);
   

   How would you fix it without further setting the value of a variable?

3. Which of these casts is necessary, and which could be left out (and be legal and mean the same thing)? Before testing, think what the values of the variables will be:

   int x= (int)5.8;
   double y = (double)6;
   char c = (char)('a' + 1);
   int z = (int)'a' + 1;
   

String Notes

Unfortunately Java Strings do not allow indexing with square brackets. You need to use named methods instead. Here are some pretty direct conversions/comparisons.

Examples below use string/String variables called w and u:

No negative indices in Java: Python allows negative indices, like w[-2] for the value of the second to last character. In Java you must have nonnegative indices, so the corresponding thing in Java would be w.charAt(w.length - 2).

In Java the split method must have a parameter, and it is a regular expressions, or regex for short: another specialized language with variants embedded in many programming languages. To match the behavior of a Python string parameter, treated verbatim, you need to escape any of the following characters you use: []{}()+*^$?

The regex escape character is \, but unfortunately that is also the string escape character, so to get it to the regex, it, too, needs to be escaped. So if you wanted to split on +, you would need st.split("\\+").

Note the error: The first example for split in the book's String table is illegal. Here is a correction. It is tricky: Python w.split() (no Python parameter) ignores white space on either end of string w, and splits out tokens with any number of whitespace characters in between. Java will generate empty strings in the list if there is whitespace at the beginning, and you need a regex to handle multiple whitespace characters together, so to match Python you need the mouthful w.trim().split("\\s+").

We did not discuss the last four string methods in the table in FOPP. Here is more on the methods for Java: the Python acts the same way:

String replace(String target, String replacement)

Returns a String formed from this String by replacing all occurrences of the substring target by replacement.

Example:

If String s is "This is it!", then

s.replace(" ", "/") returns "This/is/it!"

s.replace("is", "at") returns "That at it!"

"oooooh".replace("oo", "ah") returns "ahahoh"

int indexOf(String target)

Returns the index of the beginning of the first occurrence of the String target in this String object. Returns -1 if target is not found.

Example: Suppose String state is "Mississippi", so showing the indices we have:

01234567890
Mississippi

Then

state.indexOf("is") returns 1

state.indexOf("sip" returns 6

state.indexOf("ii") returns -1

This variation of indexOf has a second parameter:

int indexOf(String target, int start)

Returns the index of the beginning of the first occurrence of the String target in this String object, starting at index start or after. Returns -1 if target is not found.

Example, using Mississippi again:

state.indexOf("is", 0) returns 1 (same as state.indexOf("is"))

state.indexOf("is", 2 returns 4

state.indexOf("is", 5 returns -1

state.indexOf("is", 5 returns -1

state.indexOf("i", 5) returns 7

Same idea as Java indexOf in Python, but with method find.

bool startsWith(String prefix)

Returns true if this String object starts with String prefix, and false otherwise.

Example:

"-123".startsWith("-") is true

"downstairs".startsWith("down") is true

"1 - 2 - 3".startsWith("-") is false

bool endsWith(String suffix)

Returns true if this String object ends with String suffix, and false otherwise.

Example:

"-123".endsWith("-") is false

"downstairs".endsWith("airs") is true

"1 - 2 - 3".endsWith("air") is false

Here is one more comparison, with a float/double x:

In String.format the first parameter is used much like a Python format string to which you apply the format method. The % followed by modifiers is used much like the {} in Python format strings. The syntax after the % is a bit different than after a colon inside Python braces:

• Java format modifiers end with a type designation: s prints anything as a string, d is for ints, and f is for doubles.
• A field width can be given after the %.
• You can show field width, padding, and precision for a double, like in Python. A number directly before the decimal point in a float/double format is the minimum field width for the formatted string, with extra blanks included on the left if the string would be too short. With 0 inserted before the fieldwidth, the padding character becomes "0". If the string is longer than the field-width, the field-width value is ignored.
• The Java format component %n is special: It does not format the next parameter. While Java println adds an extra newline, there is no alternate to String.format that automatically inserts a newline.

Examples: Suppose double x is 1.23456 and String st is "help":

String.format("%7.2f", x)

returns "   1.23" (3 spaces)

String.format("%7.3f", x)

returns "  1.235" (2 spaces, rounded)

String.format("%5s", st)

returns " help" (1 space)

String.format("%5.4f", x)

returns "1.2346" (too long for fieldwidth)

String.format("%2s", st)

returns "help" (too long for fieldwidth)

The last two examples ignore the fieldwidth, since the string is too long to fit.

You can also pad with 0's rather than blanks, as with Python (not mentioned before), placing a "0" directly before the fieldwidth:

String.format("%07.2f", x)

returns "0001.23" (3 0's padding)

The embedded formatting language is very large. Only some of the most common bits are illustrated above.

In general you should not use '\n' in Java: In Python, C#, and C++, '\n' is replaced in file output by whatever newline sequence is used by the current operating system. Not so in Java! (Windows and Unix/Mac use different newline conventions.) These days most applications are newline format agnostic, but not all. It may have changed recently, but the classic Windows Notepad does not know what to do with a plain '\n'.

The System.out.format method produces the same string as String.format but the string is directly printed to System.out, not returned. This is more important in Java, since System.out.println and System.out.print can only take a single argument, unlike the allowed parameter list in Python for print.

In jshell try some of the string method examples, trying various things, like I recommended for operators above.

String Op Review Questions

1. What is printed by this fragment?

   String s = "question";
   System.out.println(s.length());
   System.out.println(s[2]);
   System.out.println(s.substring(2, 5));
   System.out.println(s.substring(3));
   System.out.println(s.indexOf("ti"));
   System.out.println(s.indexOf("to"));
   int j = s.indexOf("u"), k = s.indexOf("o");
   System.out.format("%s %s %s", j, k, s.substring(j, k));
   

2. What is printed by this fragment?

   String s = "Word";
   s.toUpperCase();
   System.out.println(s);
   

3. What is printed by this fragment?

   String a = "hi", b = a.toUpperCase();
   System.out.println(a+b);
   

4. Are Strings mutable or immutable: which?

5. Suppose we have a String s and want its length. Is this expression legal, or what should it be?

   s.length
   

6. Which of these expressions are legal in Java? Think of the results. Explain.

   "a" + "b"
   "a" + 'b'
   "a" + 2
   2 + "a"
   "a" + 2 * 3;
   "a" + 2 + 3
   2 + 3 + "a"
   2 + 3 * "a"
   

   Think first; try in jshell; reconsider if necessary.

7. Write a single println statement that would produce output on two separate lines, not just one.

List Notes

Java has various forms of lists. We will use the type ArrayList. Again there must be types for everything in Java, and a list can only contain elements of one type. That type is given in angle brackets, so an ArrayList of Strings called strList, initialized to an empty list would be declared verbosely as

ArrayList<String> strList = new ArrayList<String>();

Unfortunately you cannot use the nice [i] notation of Python to index Java lists. You need named methods. At least the names are reasonable.

While reading and writing to an element of a Python list use the same notation, like w[3], Java has distinct methods, get and set. Here is a comparison of Python and Java list manipulation.

List methods: Suppose w and w2 are lists of strings --

If you want to iterate over w[2:4] and not change anything in the list, w.subList(2,4) is an analog, but it does not create a new list: it is a view of w. The analog of w2 = w[2:4], which copies item references to a new list, is the mouth-full w2 = new ArrayList<String>(w.subList(2,4)).

Compare the Python and Java for copying the upper case version of a list of strings to another list. Note the translation of the for-loop heading: the loop variable must be given a type in Java. First we show Python (a slow way, to be analogous to the Java way, since there are no list literals in Java):

fruit = list()
fruit.append("apple")
fruit.append("pear")
fruit.append("plum")

FRUIT = list()
for item in fruit:
   FRUIT.append(item.upper())

Now Java:

ArrayList<String> fruit = new ArrayList<String>();
fruit.add("apple");
fruit.add("pear");
fruit.add("plum");

ArrayList<String> FRUIT = new ArrayList<String>();
for (String item: fruit)
{
   FRUIT.add(item.toUpperCase());
}

Both versions end up with FRUIT containing, "APPLE", "PEAR", and "PLUM".

In general the for-loop heading for processing items in a sequence, like an ArrayList, is

for ( type itemname : sequence )

In Java, if you want the for-loop body to contain more than one statement, you need to enclose them in braces to make one compound statement. It is good practice to use the braces in general for loop bodies.

I will admit to more than once making a shortcut, omitting the braces, and then editing my program to add a second statement in the loop body - as I imagine it - but without also adding braces: Then, unlike Python, the second statement, even if indented, is not a part of the loop. In java the indentation of the loop body statements is a convention for human readability, but is ignored by the compiler. Only braces allow multiple statements in a loop body.

Always give the element type for an ArrayList in your declaration and creation of new objects! This is one of the few places you do need the wrapper type in place of a primitive type. Strings are already an object type, so there is not an issue, but ArrayList<int> is illegal, and must be modified to ArrayList<Integer>.

On the other hand, method parameters can take advantage of auto-boxing:

ArrayList<Integer> nums = new ArrayList<Integer>(); // not int
nums.add(7);  // int 7 auto-converts to an Integer object

We will see other kind of loops soon.

For more extensive use of Java ArrayLists, you will want to see its documentation, https://docs.oracle.com/javase/11/docs/api/java/util/ArrayList.html.

See also the java.util.Collections class.

Lists are related to another type in Java: arrays.

Array Notes

Arrays in Java have some of the features of Python lists, including indexing, but unlike lists, their number of elements is fixed at creation time, and is unchangeable after that. Arrays are a built-in syntax, simpler than for ArrayLists.

Here is a variation on the fruit snippets above, first Python:

fruit = ["apple", "pear", "plum"]
n = len(fruit)
FRUIT = [None]*n # so list has n None elements
for i in range(n)
   FRUIT[i] = fruit[i].upper()

Now Java, all with arrays

String[] fruit = {"apple", "pear", "plum");

int n = fruit.length;
String[] FRUIT = new String[n]; //n nulls
for (int i = 0; i < n; i++)
{
   FRUIT[i] = fruit[i].toUpperCase();
}

This is a very direct translation, line by line. There are a number of things to elaborate on:

• An array with elements of type T has type T[], so String[] is an array of strings.

• Arrays can be initialized in the declaration statement, much like Python lists, except the initializer is in braces {...}. This sets the fixed length of the array.

• Note the length field (not method) in place of the Python len function.

• Array variables can also be set to a new array, using the new syntax, with the element type, and this time with the size of the array inside square brackets. The size can be an int expression,

  new elementType [ arraySizeExpression ]

• Here we use the second kind of Java for-loop heading. this usage directly corresponding to the range in Python is very common. More variations come later.

• Single element indexing with non-negative indices is just like in Python lists, but you cannot use negative indices like you can with Python lists.

Some more array features:

• An array is a form of sequence, like a list, so it can be used as the sequence in the for-loop heading form with a sequence.
• Like with all Java objects, when an array is created, its full state is set. This is clear with the braces notation, but not with new elementType[size]. There is a standard initialization for all types in a new object that are not explicitly given a value:
  • Numeric types become 0 (or 0.0)
  • This includes the char type: (char)0 is a generally useless character, not the same as '0'. A way to initialize a char array is using String method toCharArray()
  • A boolean value becomes false.
  • Object element type become null, sort of like Python None, but null can only be a value indicating lack of an object. It cannot be assigned to a primitive type.

Examples:

• new boolean[5] sets all 5 elements to false.

• new int[10] sets all 10 elements to 0.

• new String[3] sets all 3 elements to null, not ``""``.

• This prints all the capital letters, one per line:

  char[] letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
  for (char ch: letters)
  {
      System.out.println(ch);
  }
  

• This produces an error:

String[] strArray = new String[10];
System.out.println(strArray[0].toUpperCase());

Here strArray[0] is null. You cannot apply any method to null, including toUpperCase, as if null were an object.

length vs. size

Arrays have a length attribute -- accessed with no parentheses after it. The length of array a is a.length. This is unlike Strings! The length of String s is s.length() (with parentheses of a method). The length cannot be changed for either an array or string.

It is also easy to conflate syntax for list lengths. Lists sizes can be changed: A different method name is used for the (current) length of ArrayList al: al.size().

List and Array Questions

1. Distinguish the cases when you would want to use a list instead of an array, or the other way around.
2. What are comparable features between arrays and lists, but with different syntax?
3. If you delete an element from the middle of a list, what happens to the spot where you removed the element?

Static Function Notes

Java manages the scope of local variables like in Python.

In Python, code and function definitions can exist outside of a class. In Java all code is in a class definition. The closest analog to a Python function is a static method in a class. (We will get to creating instance methods later.)

The required method main is an example, but you can define other static functions. Like all methods, a return type must be given, and the formal parameters names in the heading are preceded by a type designation.

For static functions, you also need the modifier static.

Within the same class, any static function can be called, just with its name and actual parameters.

Here is a function to return a new array containing the squares of the numbers in a passed array:

Here is a Python function to return a new list containing the squares of the numbers in a passed list nums:

def squares(nums):
    int n = nums.length;
    sq = [0]*n
    for i in range(n):
        sq[i] = nums[i]*nums[i]
    return sq

Now for passed array nums in Java, and an array returned:

public static int[] squares(int[] nums)
{
    int n = nums.length;
    int[] sq = new int[n];
    for (int i = 0; i < n; i++) {
        sq[i] = nums[i]*nums[i];
    }
    return sq;
}

If you want the function to be callable from outside its class, you also need the initial modifier public in the method heading, and to reference the function from another class, you must use dot-notation, refering to the class containing the static function. For example, we will later introduce a utility class UI that includes promptLine, an analog of Python's handy input function. To use it from another class you would need to refer to it as UI.promptLine.

Overloading and signatures

In Python there can be only one function within any scope with a particular name. Python does allow some limited flexibility with optional parameters.

Java does allow multiple functions with the same name. Here are simple examples:

System.out.println(3);
System.out.println("Hello");
System.out.println();

Note that the last version has no parameter. (This version just advances to the next line).

Note that since Java as statically typed, the types and number of formal parameters appear in a function definition, in addition to the function name. Java uses all of these features to determine the method signature. It chooses the appropriate function to use based on the signature from the actual parameters when the method is called.

Signatures must be unique, but not function names.

public static void foo(double n)
{
     System.out.println(n);
}

public static void foo(int n)
{
     System.out.println(n*n);
}

Then see what these calls would print!

foo(3);     // prints 9 (3*3)
foo(3.5);   // prints 3.5

Java does more significant things with signatures combined with implicit type conversion: If the foo with int parameter were not defined, both the calls listed above would work, but foo(3) would now produce 3.0: Since in this case there is not a method with the exact signature, Java looks for what the parameter(s) could be converted to implicitly: An int can be implicitly converted to double so the double parameter version would be called. You are not in general recommended to have functions with such close signatures, but here we are illustrating how the compiler works!

Function Review Questions

1. Write the function definition heading for a static function called Q1 which has two int parameters, x and y, and returns a double.

2. The function above must have what kind of a statement in its body?

3. Each of these lines has a call to the function above, Q1. Which are legal? Explain:

   double d = Q1(2, 5);
   
   int x = Q1(2, 5);
   
   double y = Q1(2) + 5.5;
   
   System.out.println(Q1("2", "5"));
   
   System.out.println(Q1(2.5, 5.5));
   
   Q1(10, 20);
   

4. Suppose Q1 does nothing except produce the value to return, like most functions returning a double. Which line in the previous problem is legal, but has no effect?

5. Write the function definition heading for a static function called Q4 which has one string parameter, s, and returns nothing.

6. Which of these lines with a call to the function above, Q4, is legal? Explain:

   Q4("hi");
   
   string t = Q4("hi");
   
   System.out.println(Q4("hi"));
   
   Q4("hi" + "ho");
   
   Q4("hi", "ho");
   
   Q4(2);
   

7. Can you have more than one function/method in the same class definition with the same name?

8. What is a function/method signature? Can you have more than one function/method declared in the same class definition with the same signature?

9. In each part, is this a legal program? If so, what is printed? If not, why not?

   Each version uses the same code, except for different versions of main. Here is the common code with the body of main omitted:

   class Local1
   {
      static int Q(int a)  // 1
      {                    // 2
         int x = 3;        // 3
         x = x + a;        // 4
         return x;         // 5
      }                    // 6
   
      public static void main(String[] args)
      {
         // see each version
      }
   }
   

   1. Insert:

      public static void main(String[] args)
      {
         Q(5);
         System.out.println(x);
      }
      

   2. Insert instead:

      public static void main(String[] args)
      {
         int x= 1;
         Q(5);
         System.out.println(x);
      }
      

   3. Insert instead:

      public static void main(String[] args)  // 7
      {                                       // 8
         int x = 1, y = 2;                    // 9
         y = Q(5);                            // 10
         System.out.println(x + " " + y);     // 11
      }                                       // 12
      

10. In the previous problem consider the common code with part c. Note the line numbers as comments.

    1. In what line(s) is Q being defined?
    2. In what line(s) is Q called?
    3. What is the return type of Q?
    4. What is a formal parameter to Q?
    5. What is used as an actual parameter to Q?
    6. What is the scope of the x in line 3?
    7. What is the scope of the x in line 9?

Dictionary Notes

Just as Python has the dict type, Java has an analog. Rather than the dictionary terminology, Java calls these objects Maps. The one corresponding to a Python dict is a HashMap.

A HashMap has both keys and values, so two types are specified to define a specific type: TreeMap<keyType, valueType>. This needs to occur both when the type is declared and later where the constructor is used, like we did with an ArrayList, only now specifying two types.

Like with lists, Java does not allow square bracket notation here. Named methods must be used. The main ones, get and set are like for lists, except a key is used as a parameter in place of an index number.

Comparisons for Dict/HashMap d:

Python's get can have any other value as second parameter, not just None, to be returned if the key is not in d. When a key is missing in Java's get, the replacement for an actual value is always null.

Java does not have Python's nice dictionary literal notation.

Short-Circuiting Compound Conditions

Follow along with the following silly, but illustrative jshell sequence:

jshell> int x = 5, y = 2, z = 1;

x ==> 5

y ==> 2

z ==> 1

jshell> y/x > z && x != 0

$4 ==> false

jshell> x = 2; y = 5;

x ==> 2

y ==> 5

jshell> y/x > z && x != 0

$7 ==> true

The compound condition includes x != 0, so what happens if we change x to 0 and try the condition again. Will you get false?

jshell> x=0;

x ==> 0

jshell> y/x > z && x != 0

| Exception java.lang.ArithmeticException: / by zero

| at (#9:1)

No, one of the parts involves dividing by zero, and you see the result. What if we swap the two conditions to get the logically equivalent

jshell> x != 0 && y/x > z

$10 ==> false

Something is going on here besides pure mathematical logic. In practive, we do not need to continue processing when we know the final answer already. The && and || operators work the same way, evaluating from left to right. If x != 0 is false, then x != 0 && y/x > z starts off being evaluated like false && ??. We do no need the second part evaluated to know the overall result is false, so Java does not evaluate further. This behavior has acquired the jargon short-circuiting. Many computer languages share this feature (including Python).

It also applies to ||. In what situation do you know what the final result is after evaluating the first condition? In this case you know:

true || ??

evaluates to true. Continuing with the same jshell sequence above (where x is 0, y is 5, and z is 1):

jshell> x == 0 || y/x > z

$11 ==> true

The division by 0 in the second condition never happens. It is short-circuited.

For completeness, try the other order:

jshell> y/x > z || x == 0

| Exception java.lang.ArithmeticException: / by zero

Example: Suppose you want the user to enter a line that you assign to a String s, and then check if the first character is 'y'. You could use the condition s.charAt(0) == 'y'. However if you want to prepare for user errors, you want to consider that the user might just press return, so the line is empty, and return the empty String. Then s.charAt(0) causes an Exception!

To avoid that, we want to be sure s is nonempty. The test cannot be s != "" as in Python, since == and != for objects in Java are like Python is and is not. We can use either condition !s.equals("") or for this special case s.length() != 0. (We can still use == or != with primitives, like numbers.)

The point here is that the empty string test must allow for short-circuiting, coming before the test of the first letter:

!s.equals("") && s.charAt(0) == 'y'

This test should not cause an Exception with any String s.

In general: In situations where you want to test conditionThatWillBombWithBadData, you want to avoid causing an Exception. When there is good data, you want the result to actually come from conditionThatWillBombWithBadData. There are two cases, however, depending on what result you want if the data for this condition is bad, so you cannot evaluate it:

• If you want the result to be false with bad data for the dangerous condition, use

  falseConditionIfDataBad && conditionThatWillBombWithBadData

• If you want the result to be true with bad data for the dangerous condition, use

  trueConditionIfDataBad || conditionThatWillBombWithBadData

Boolean Operators

You may skip this! Java does have the ugly expression syntax:

condition ? trueValue : falseValue

Python recently added a corresponding construction (much more like English!):

trueValue if condition else falseValue

You are not responsible for either (though the Python version is rather nice).

Conditional Review Questions

1. Which of these are boolean expressions? Assume the variables are of type int:

   true
   True
   "false"
   x = 3
   n < 10
   count == 22
   x <= 2 || x > 10
   x == 2 || 3
   1 < y < 10
   

2. What are the values of these expressions? Be able to explain:

   2 < 3 && 4 < 5
   2 < 3 && 4 < 3
   2 < 3 || 4 < 5
   2 < 3 || 4 < 3
   3 < 2 || 4 < 3
   2 < 3 || 4 < 5 && 4 < 3
   

3. Correct the last two entries in the first problem, supposing the user meant "x could be either 2 or 3" and then "y is strictly between 1 and 10".

4. Add parentheses in 2 < 3 || 4 < 5 && 4 < 3 to get a different result.

5. Suppose you have four possible distinct situations in your algorithm, each requiring a totally different response in your code, and exactly one of the situations is sure to occur. Have many times must you have if followed by a condition?

6. Suppose you have four possible distinct situations in your algorithm, each requiring a totally different response in your code, and at most one of the situations will occur, so possibly nothing will happen that needs a response at all. Have many times must you have if followed by a condition?

7. Assume IsBig(x) returns a Boolean value. Remove the redundant part of this statement:

   if (IsBig(x) == true)
      x = 3;
   

8. Write an equivalent (and much shorter!) statement with no if:

   if (x > 7)
      return true;
   else
      return false;
   

9. Write an equivalent (and much shorter!) statement with no if:

   if (x > 7)
      isSmall = false;
   else
      isSmall = true;
   

10. Assume x and y are local int variables. Code fragments are separated by a blank line below. Pairs of the fragments are logically equivalent, but not necessarily with a directly adjacent fragment. Match the pairs. Be sure you understand when different pairs would behave differently. Caution: there is some pretty awful code here, that we would hope you would never write, but you might need to correct/read! Think of pitfalls. In each equivalent pair, which code fragment is more professional?

    if (x > 7) {    //a
       x = 5;
    }
    y = 1;
    
    if (x > 7) {    //b
       x = 5;
       y = 1;
    }
    
    if (x > 7)      //c
       x = 5;
       y = 1;
    
    if (x > 7) {    //d
       x = 5;
    }
    else {
       y = 1;
    }
    
    if (x > 7)      //e
       x = 5;
    else if (x <= 7) {
       y = 1;
    }
    
    if (x > 7) {    //f
       y = 1;
    }
    if (x > 7) {
       x = 5;
    }
    

11. Same situation as the last problem, and same caution, except this time assume the fragments appear in a function that returns an int. In each pair of equivalent fragments, which is your preference?

    y = 1;         //a
    if (x > 7) {
       return x;
    }
    
    if (x > 7) {   //b
       return x;
    }
    y = 1;
    
    if (x > 7) {   //c
       return x;
    }
    else {
       y = 1;
    }
    
    if (x > 7) {   //d
       return x;
       y = 1;
    }
    
    if (x > 7) {   //e
       y = 1;
       return x;
    }
    y = 1;
    
    if (x > 7) {   //f
       return x;
    }
    
    if (x > 7);    //g
       return x;
    
    return x;      //h
    

12. Same situation as the last problem, and same caution:

    if (x > 5)        //a
       if (x > 7)
           return x;
    else
       y = 1;
    
    if (x > 5)  {     //b
       if (x > 7)
           return x;
    }
    else {
       y = 1;
    }
    
    if (x > 7)        //c
       return x;
    if (x <= 5)
       y = 1;
    
    if (x > 7)        //d
       return x;
    if (x > 5)
       y = 1;
    

13. When reading a verbal description of a problem to solve, what are some words or phrases that suggest that some version of an if statement will be useful?

An isDigits Function

Consider this function, that might be useful is determining if a string can be converted to and int:

/** Return true if s contains one or more digits
    and nothing else. Otherwise return false. */
static boolean isDigits(string s)

There are several ways to check if a character is a digit. We could use the contains method, but here is another option: The integer codes for digits are sequential, and since characters are technically a kind of integer, we can compare: The character s.charAt(i) is a digit if it is in the range from '0' to '9', so the condition can be written:

'0' <= s.charAt(i) && s.charAt(i) <= '9'

Similarly the condition s.charAt(i) is not a digit, can be written negating the compound condition:

'0' > s.charAt(i) || s.charAt(i) > '9'

If you think of going through by hand and checking, you would check through the characters sequentially and if you find a non-digit, you might want to remember that the string is not only digits.

One way to do this is have a variable holding an answer so far:

boolean allDigitsSoFar = true;

Of course initially, you have not found any non-digits, so it starts off true. As you go through the string, you want to make sure that answer is changed to false if a non-digit is encountered:

if ('0' > s.charAt(i) || s.charAt(i) > '9') {
    allDigitsSoFar = false;
}

When we get all the way through the string, the answer so far is the final answer to be returned:

/** Return true if s contains one or more digits
    and nothing else. Otherwise return false. */
static bool isDigits (string s)
{
   bool allDigitsSoFar = true;
   for (int i = 0; i < s.length(); i++) {
      if ('0' > s.charAt(i) || s.charAt(i) > '9') {
         allDigitsSoFar = false;
      }
   }
   return allDigitsSoFar;
}

Remember something to always consider: edge cases. In the description it says it is true for a string of one or more digits.

Check examples of length 1 and 0. Length 1 is fine, but it fails for the empty string, since the loop is skipped and the initial answer, true is returned.

There are many ways to fix this. We will know right up front that the answer is false if the length is 0, and we could immediately set allDigitsSoFar to false. We would need to change the initialization so it checks the length and chooses the right value for allDigitsSoFar, true or false. Since we are selecting between two values, an if statement should occur to you:

if (s.length() > 0) {
    allDigitsSoFar = true;
}
else {
    allDigitsSoFar = false;
}

If we substitute this initialization for allDigitsSoFar, the code will satisfy the edge case, and the code will always work. Still, this code can be improved:

Examine the if statement more closely:

See the symmetry: the value assigned to allDigitsSoFar is always the value of the condition.

A much more concise and still equivalent initialization is just:

boolean allDigitsSoFar = (s.length() > 0);

In more generality this conciseness comes from the fact that it is a boolean value that you are trying to set each time, based on a boolean condition: You do not need to do that with an if statement! You just need an assignment statement. If you use an if statement in such a situation, you being verbose and marking yourself as a novice!

It could even be slightly more concise: The precedence of assignment is very low, lower than the comparison >, so the parentheses could be omitted. We think the code is easier to read with the parentheses left in, as written above.

The whole function would be:

/** Return true if s contains one or more digits
    and nothing else. Otherwise return false. */
static bool isDigits (string s)
{
   boolean allDigitsSoFar = (s.length() > 0);
   for (int i = 0; i < s.length(); i++) {
      if ('0' > s.charAt(i) || s.charAt(i) > '9') {
         allDigitsSoFar = false;
      }
   }
   return allDigitsSoFar;
}

Note that we earlier made an improvement by replacing an if-else statement generating a Boolean value by a simple Boolean assignment. In the most recent sample code, there is an if statement setting a Boolean value:

if ('0' > s.charAt(i) || s.charAt(i) > '9') {
    allDigitsSoFar = false;
}

You might be tempted to replace this if statement by a simple Boolean assignment:

allDigitsSoFar = ('0' > s.charAt(i) || s.charAt(i) > '9');  // bad!

Play computer with this change to see for yourself why it is bad, before looking at our explanation below....

The place where we originally said to use a simple Boolean assignment was replacing an if-else statement, that always set a Boolean value. In the more recent correct code for digits, we had a simple if statement, and were only setting the boolean variable to false some of the time: when we had not found a digit. The bad code sets the variable for each character in the string, so it can change an earlier false value back to true for a later digit. The final value always comes from the the last character in the string! We want the function to come up with an answer false if any character is not a digit, not just the last character. The bad code would give the wrong answer with the string "R2D2". If you do not see that, play computer with this string and the bad code variation that sets allDigitsSoFar every time through the loop.

The last correct code is still inefficient. If an early character in a long string is not a digit, we already know the final answer, but this code goes through and still checks all the other characters in the string! People checking by hand would stop as soon as they found a non-digit. We can do that in several ways with Java, too. Since this is a function, and we would know the final answer where we find a non-digit, the simplest thing is to use the fact that a return statement immediately terminates the function (even if in a loop).

Instead of setting a variable to false to later be returned, we can return right away, using the loop:

while (i < s.length()) {
   if ('0' > s.charAt(i) || s.charAt(i) > '9') {
      return false;
   }
   i++;
}

What if the loop terminates normally (no return from inside)? That means no non-digit was found, so if there are any characters at all, they are all digits. There are one or more digits as long as the string length is positive. Again we do not need an if-else statement to check the length and set the Boolean result. Look in the full code for the function:

/** Return true if s contains one or more digits
    and nothing else. Otherwise return false. */
static bool isDigits (string s)
{
   if (s.length() == 0) {
       return false;
   }
   for (int i = 0; i < s.length(); i++) {
      if ('0' > s.charAt(i) || s.charAt(i) > '9') {
         return false;
      }
   }
   return true;
}

Returning out of a loop is a good pattern to remember when you are searching for something, and you know the final answer for your function as soon as you find it. This has the same idea in it as short-circuiting in a compound boolean expression.

Bisection Method

For a very different example we look to scientific computing. In math class you likely learned various ways to find roots of functions f(x) exactly. In practice those methods almost never work beyond low order polynomials. Hence the best we can do usually is to approximate solutions numerically. One broadly useful approach is the bisection method. You just need a continuous function (with an unbroken graph), and you need to first find two places, a and b, where f(a) and f(b) have opposite signs. If f is continuous and goes between positive and negative values, then it must cross 0 somewhere in between, and so there must be a real solution. The question is how to get close to a crossing point efficiently.

As an example we show f(x) = x² − 2, in the range from x = 0 to x = 2. As a first example we choose a simple function where the root can be figured symbolically, in this case the square root of 2. The figure below shows the graph, with extra horizontal and vertical lines that will will be explained.

In the figure a= 0, f(0) < 0, b = 2, f(2) > 0.

The basic idea is to bisect the interval between a and b, finding the midpoint, c = (a+b)/2. If f(c) is 0, you are done. Otherwise f(c) has a sign which must be opposite one of f(a) and f(b).

In the figure the initial interval has the same x coordinates as for the top gray line. Its midpoint is at 1, the x coordinate of the red vertical segment coming down from the top gray line in the figure. Note f(1) < 0, the opposite sign of f(2), so we next consider the half of the original interval from the midpoint 1 to 2, with the next gray line marking this interval. The function still must cross 0 in the smaller interval because of the opposite signs for f on the endpoints. In the iterative procedure, you continue this process, halving the length of the interval, shifting one endpoint or the other to be the middle of the most recent interval, so for each interval, the signs of f on the two ends are opposite. Repeating this procedure, you can home in on as small an interval around a crossing point (root) as you like. The figure show this process for the first 5 steps, halving the interval length each time. You need to look at the output of the code to follow the results for even smaller intervals.

This approach always works, as long as the signs of f at the initial endpoints are distinct. Our bisection functions check, and if this initial requirement is violated, the function returns the special double code value, double.NaN, meaning Not a Number.

There are other approaches to finding roots that may be faster when they work, but many of these methods can also have some chance of completely failing, so root finding algorithms generally have two extra parameters: a maximum number of iterations and a tolerance that indicates how close to a root is close enough.

In the bisection function we use a and b as the endpoints of an interval and c as the midpoint. In each iteration the value of a or b is reset to be the previous midpoint value c.

There are two bisection function versions, controling the central while loop slightly differently: The first passes a tolerance parameter: How close you want the answer to be to the real root.

Since the bisection method always homes in on a real root rapidly, an alternate version specifically for the bisection method finds the best approximation possible with double arithmetic. While you can always halve an interval mathematically, you eventually run out of distinct double values! We can stop when the midpoint (calculated with limited double precision) is exactly the same as a or b:

Of course a production version would not print out all the intermediate data, as the interval shrinks, but we allow it for illustration.

Here is the whole program, with testing code, also in

BisectionMethod1.java:

import java.lang.Math;

class BisectionMethod1  // In this version f is a fixed function
{
   static double f(double x) {  // fixed for now
      return x * x - 2;
      // This should have solution the square root of 2.
   }

   /** This is the basic bisection method.
   *   Requires f(a) and f(b) to have opposite signs,
   *   or else returns NaN.
   *   Returns a value within tolerance of a root in the interval
   *   with endpoints a and b.
   *   Shows steps if verbose.     */
   public static double bisection(double a, double b,
                                  double tolerance, boolean verbose)
   {
      if (f(a) == 0)
         return a;
      if (f(b) == 0)
         return b;
      if (Math.signum(f(a)) == Math.signum(f(b)))
         return Double.NaN;
      if (b < a) {
         double temp = a ;
         a = b;
         b = temp;
      }
      while (true) {
         double c = (a + b) / 2;
         if (verbose)
             System.out.format("a = %f b = %f%n", a, b);
         if (f(c) == 0 || (b - a)/2 < tolerance)
            return c;
         if (Math.signum(f(c)) == Math.signum(f(a)))
            a = c;
         else
            b = c;
      }
   }

   /** This bisection method finds the best possible root approximation.
   *   Requires f(a) and f(b) to have opposite signs,
   *   or else returns NaN.
   *   Shows steps if verbose.     */
   public static double bisection(double a, double b, boolean verbose)
   {
      if (f(a) == 0)
         return a;
      if (f(b) == 0)
         return b;
      if (Math.signum(f(a)) == Math.signum(f(b)))
         return Double.NaN;
      double c = (a + b) / 2; // eventually double numbers cannot get closer
      while (c != a && c != b && f(c) != 0) {
         if (verbose)
             System.out.format("a = %.16f b = %.16f, diff = %g%n", a, b, b-a);
         if ((Math.signum(f(c)) == Math.signum(f(a))))
            a = c;
         else
            b = c;
         c = (a + b) / 2;
      }
      return c;
   }

   public static void main(String[] args)
   {
      double tolerance = 0.001;
      System.out.println("Let f(x) = x^2 - 2.");
      System.out.println("Looking for a root in [0, 2].");
      System.out.format("First have tolerance %f.%n", tolerance);
      double root = bisection(0, 2, tolerance, true);
      if (!Double.isNaN(root)) //Special method: Nan is not equal to itself!
         System.out.println ("An approximate root is " + root);
      else
         System.out.println ("Bad range - not opposite signs at endpoints");
      System.out.println ("\nNow look for the BEST double approximation:");
      root = bisection(0, 2, true);
      if (!Double.isNaN(root)) //Special method: Nan is not equal to itself!
         System.out.format ("Best approximate double root is %.16f%n", root);
      else
         System.out.println ("Bad range - not opposite signs at endpoints");
   }
}

Note the special function checking for double.NaN in main, because double.NaN is not equal to itself!

Here is the output, with some of the lines of the second version omitted:

Let f(x) = x^2 - 2.

Looking for a root in [0, 2].

First have tolerance 0.001000.

a = 0.000000 b = 2.000000

a = 1.000000 b = 2.000000

a = 1.000000 b = 1.500000

a = 1.250000 b = 1.500000

a = 1.375000 b = 1.500000

a = 1.375000 b = 1.437500

a = 1.406250 b = 1.437500

a = 1.406250 b = 1.421875

a = 1.414063 b = 1.421875

a = 1.414063 b = 1.417969

a = 1.414063 b = 1.416016

An approximate root is 1.4150390625

Now look for the BEST double approximation:

a = 0.0000000000000000 b = 2.0000000000000000, diff = 2.00000

a = 1.0000000000000000 b = 2.0000000000000000, diff = 1.00000

(46 lines omitted...)

a = 1.4142135623730923 b = 1.4142135623730994, diff = 7.10543e-15

a = 1.4142135623730923 b = 1.4142135623730958, diff = 3.55271e-15

a = 1.4142135623730940 b = 1.4142135623730958, diff = 1.77636e-15

a = 1.4142135623730950 b = 1.4142135623730958, diff = 8.88178e-16

a = 1.4142135623730950 b = 1.4142135623730954, diff = 4.44089e-16

Best approximate double root is 1.4142135623730950

The current versions have a major limitation: They just work with the one canned version of the function f in the class. You need to edit the source code to use the same process with a different function! There are several ways around this using more advanced Java features. After we introduce interfaces, a more flexible version should make sense. The more advanced version is the main example in Bisection Revisited.

Greatest Common Divisor

The greatest common divisor (gcd) of two non-zero integers is a great example to illustrate the power of loops. Everyone learns about the concept of a greatest common divisor when faced with a fraction that is not in reduced form.

Consider the fraction (2)/(4), which is the same as (1)/(2). The fraction (2)/(4) can be reduced, because the numerator and denominator both have greatest common factor of 2. That is, (2)/(4) = (1⋅2)/(2⋅2). So the factor of 2 can be canceled from both the numerator and the denominator.

There is an obvious (but not efficient) way to code a gcd function for two positive int values, a and b. The largest possible value is the minimum of the two. We can try to see if that number is a common factor, and if not, reduce the number by one, and keep trying.

public static int gcdBrute(int a, int b)
{
   int f = Math.min(a, b);
   while(a % f != 0 || b % f != 0) {
      f--;
   }
   return f;
}

This loop must end, since f = 1 will always work. The number of times through this loop could then be the minimum of a and b.

Euclid (the mathematician from classic times and author of Elements) is credited with having come up with a clever algorithm for how to compute the greatest common divisor efficiently. Here the mathematical notation a mod b means a % b in Java.

gcd(a, b) = gcd(b, a mod b) -- if b is not 0

gcd(a, 0) = a

To gain some appreciation of how the definition always allows you to compute the greatest common divisor, it is worthwhile to try it out for a couple of numbers where you know the greatest common divisor. For example, we already know that the greatest common divisor of 10 and 15 is 5. Let's use Euclid's method to verify this:

• gcd(10, 15) = gcd(15, 10 mod 15) = gcd(15, 10)
• gcd(15, 10) = gcd(10, 15 mod 10) = gcd(10, 5)
• gcd(10, 5) = gcd(5, 10 mod 5) = gcd(5, 0)
• gcd(5, 0) = 5

Notice that in the example above, the first number (10) was smaller than the second (15), and the first transformation just swapped the numbers, so the larger number was first. Thereafter the first number is always larger, and it decreases at each step, so the second, smaller number, must reach 0 eventually.

Not only does Euclid's algorithm work, it is much faster than gcdBrute, shown above, if the integers are large. A data structures class like Comp 271 will focus much more on analysing the efficiency of algorithms and choosing the fastest.

Here is Java code, looping until b is 0, and replacing a and b with b and the remainder r = a % b at each step:

/** Return greatest common divisor
*   of non-negative integers a and b
*   with at least one non-zero.

public static int gcd(int a, int b) // Euclid
{
   while (b != 0) {
      int r = a % b;
      a = b;
      b = r;
   }
   return a;
}

Preview: Recursive GCD

This section is optional. It is a good place to point out that the orginal mathematical statement included what would be in Java:

gcd(a, b) = gcd(b, a % b)

It is saying the result of the function with one set of parameters is equal to calling the function with another set of parameters. If we put this into a Java function definition, it would mean the instructions for the function say to call itself. This is a broadly useful technique called recursion, where a function calls itself inside its definition. We don't expect you to master this technique immediately but do feel that it is important you at least hear about it and see its tremendous power:

/** Return the greatest common divisor of nonnegative numbers,
*   not both 0.                                           */
public static int gcd (int a, int b)
{
   if (b == 0) {              // base
      return a;               //   case
   } else {
      return gcd (b, a % b);  // recursion
   }
}

The recursive version of the gcd function refers to itself by calling itself. Though this seems circular, you can see from the examples that it works very well. The important point is that the calls to the same function are not completely the same: Successive calls have smaller second numbers, and the second number eventually reaches 0, and in that case there is a direct final answer. Hence the function is not really circular.

This recursive version is a much more direct translation of the original mathematical algorithm than the looping version!

The general idea of recursion is for a function to call itself with simpler parameters, until a simple enough place is reached, where the answer can be directly calculated.

Much more on this in Data Structures class!

Savings Exercise

The idea here is to see how many years it will take a bank account to grow to at least a given value, assuming a fixed annual interest. Write a program Savings.java. Prompts the user for three numbers: an initial balance, the annual percentage for interest as a decimal. like .04 for 4%, and the final balance desired. Print the initial balance, and the balance each year until the desired amount is reached. Round displayed amounts to two decimal places, as usual.

The math: The amount next year is the amount now times (1 + interest fraction), so if I have $500 now and the interest rate is .04, I have $500*(1.04) = $520 after one year, and after two years I have, $520*(1.04) = $540.80. If I enter into the program a $500 starting balance, .04 interest rate and a target of $550, the program prints:

500.00

520.00

540.80

563.42

Roundoff Exercise

Write a program, FindEpsilon.java, to complete and test the function with this heading and documentation:

/** Return the largest possible number y, so in Java: x+y = x
*   If x is Double.POSITIVE_INFINITY return Double.POSITIVE_INFINITY.
*   If x is Double.NEGATIVE_INFINITY, return Double.MAX_VALUE.
*   Assume x is not Double.NaN (which is equal to nothing).  */
static double epsilon(double x)

Hint: The non-exceptional case can have some similarity to the bisection in the best root approximation example: start with two endpoints, a and b, where x+a = x and x+b > x, and reduce the interval size by half....

Do-While Loops

Suppose you want the user to enter three integers for sides of a right triangle. If they do not make a right triangle, say so and make the user try again.

One way to look at the while statement rubric is:

set data for condition

while (condition) {

accomplish something

set data for condition

}

As we have pointed out before this involves setting data in two places. With the triangle problem, three pieces for data need to be entered, and the condition to test is fairly simple. (In any case the condition could be calculated in a function.)

A do-while loop will help here. It tests the condition at the end of the loop, so there is no need to gather data before the loop:

int a, b, c;
do {
    System.out.println("Think of integer sides for a right triangle.");
    a = UI.promptInt("Enter integer leg: ");
    b = UI.promptInt("Enter another integer leg: ");
    c = UI.promptInt("Enter integer hypotenuse: ");
    if (a*a + b*b != c*c) {
        System.out.println("Not a right triangle: Try again!");
    }
} while (a*a + b*b != c*c);

The general form of a do-while statement is

Here the block of statement(s) is always executed at least once, but it continues to be executed in a loop only so long as the condition tested after the loop body is true.

A do-while loop, like the example above, can accomplish exactly the same thing as the while loop rubric at the beginning of this section. It has the general form:

do {

set data for condition

if (condition) {

accomplish something

}

} while (condition);

It only sets the data to be tested once. (The trade-off is that the condition is tested twice.)

In the example above note that the declaration of a, b, and c is before the do-while loop. You can try moving the declaration inside the braces for the loop body, and see the compiler error that you get!

Loan Table Exercise

Loans are common with a specified interest rate and with a fixed periodic payment. Interest is charged at a fixed rate on the amount left in the loan after the last periodic payment (or start of the loan for the first payment).

For example, if an initial $100 loan is made with 10% interest per pay period, and a regular $20 payment each pay period: At the time of the first payment interest of $100*.10 = $10 is accrued, so the total owed is $110. Right after the payment of $20, $110 - $20 = $90 remains. That $90 gains interest of $90*.10 = $9 up to the next payment, when $90 + $9 = $99 is owed. After the regular payment of $20, $99 - $20 = $79 is left, and so on. When a payment of at most $20 brings the amount owed to 0, the loan is done.

We can make a table showing

• Payment number (starting from 1)
• The principal amount after the previous payment (or the beginning of the loan for the first payment)
• The interest on that principal up until the next periodic payment
• The payment made as a result.

Continuing the example above, the whole table would look like:

Number Principal   Interest    Payment
     1    100.00      10.00      20.00
     2     90.00       9.00      20.00
     3     79.00       7.90      20.00
     4     66.90       6.69      20.00
     5     53.59       5.36      20.00
     6     38.95       3.90      20.00
     7     22.85       2.29      20.00
     8      5.14       0.51       5.65

In the final line, the principal plus interest equal the payment, finishing off the loan.

Similarly, with a $1000.00 starting loan, 5% interest per pay period, and $196 payments due, we would get

Number Principal   Interest    Payment
     1   1000.00      50.00     196.00
     2    854.00      42.70     196.00
     3    700.70      35.04     196.00
     4    539.74      26.99     196.00
     5    370.73      18.54     196.00
     6    193.27       9.66     196.00
     7      6.93       0.35       7.28

If a $46 payment were specified, the principal would not decrease from the initial amount, and the loan would never be paid off.

There are a couple of wrinkles here: double values do not hold decimal values exactly.

We make the assumption that interest will always be calculated as current principal*rate, rounded to two decimal places. Unfortunately Java only has a function to round a double to an integer of type long: Math.round(someDouble). This suggests keeping monetary amounts in cents principalCents, interestCents, paymentCents stored with long type internally, and only dividing by 100 when formatting the table entries for printing, so interestCents = Math.round(principalCents*rate).

Write Loan_calc.java, completing LoanTable and write a main testing method:

/** Print a loan table, showing payment number, principal at the
*   beginning of the payment period, interest over the period, and
*   payment at the end of the period.
*   The principal is the initial amount of the loan.
*   The rate is fraction representing the rate of interest per PAYMENT.
*   The periodic regular payment is also specified.
*   If the payment is insufficient, merely print "payment too low".  */
public static void LoanTable(double principal, double rate,
                             double payment)

This exercise is much more sophisticated than the savings exercise. Use what ever form of loop makes the most sense to you.

Remember when formatting the printed table, a number right after the % is a field width.

Reading Files

In Python we can just use something like:

fName = 'SomeTextFile.txt'
inFile = open(fName, 'r')

and just start reading. We need a lot more in Java.

Here is a sort of analog:

First at the top of the file:

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

so we do not need the full class names later.

Then inside the method where you want the file use:

String fName = "SomeTextFile.txt";
File inFile;

try {
    inFile = new File("SomeTextFile.txt");
}  catch ( IOException e) {
         System.out.println("Sorry but I was unable to open " + fName);
         System.exit(0); // terminates the program immediately
}

Scanner in = new Scanner(inFile);

and then you can read using the Scanner which I named in, with the same syntax as for reading from the keyboard.

This code needs some discussion!

First we need a File object, which we create with the assignment to inFile.

This creates an association with a file in your file system, but little more.

This code sits in a try-catch block. Here is the reason:

If Java cannot find a file SomeTextFile.txt where it is looking in the file system, then an error is caused, of type IOException.

Some run-time errors can just happen, like division by 0, without special code, the program will abort unceremoniously.

Other types, like IOException need extra code of some sort. We will deal with just one approach: catching such an error.

The body of the try-catch block can have fairly arbitrary code. The intention is somehow repair the error situation, or at least abort gracefully. The code shown inside the braces of the try-catch block above does the latter: First print a warning of what happened, and then terminates the program.

You can treat the try-catch block in the example code above pretty much as boilerplate.

There is much more to Exceptions and try-catch blocks, just this is what we need now. More in the next course, Data Structures.

Then you can go on to read from the file using the next... methods of a Scanner. Since a file is finite, it can be read all the way to the end. In this context the hasNext method makes sense: It check if there is any further token in the file. Also, unmentioned in the book was hasNextLine, if you want to read lines of a file, and you do not know how many there will be. Here is a sample static method:

/** Return all the lines of a file with name fileName
    in an ArrayList, or return null if the file cannot be read.
    Close the file.
*/
public static ArrayList<String> readLines(String fileName)
{
    File inFile;

    try {
        inFile = new File(fileName);
    }  catch ( IOException e) {
          return null;
    }

    Scanner in = new Scanner(inFile);

    ArrayList<String> lines = new ArrayList<String>();
    while (in.hasNextLine()) {
        lines.add(in.nextLine());
    }
    inFile.close();
    return lines;
}

Writing Files

The familiar object used to print to the screen, System.out, is of type PrintWriter. This and many other classes you need to write are in the package java.io. Rather than import all the classes individually, you can import them all with:

import java.io.*;

Then if printFileName is a String variable containing the name you want your output file to have, here is the mouthful of boilerplate to create a PrintWriter named `` out`` that can write to the file:

PrintWriter out;

try {
    out = new PrintWriter(
             new BuferedWriter(
                new File(printFileName) ));
}  catch ( IOException e) {
         System.out.println(
            "Sorry but I was unable to create " + printFileName);
         System.exit(0); // terminates the program immediately
}

Then you can use, the methods println, print and format with the PrintWriter named out, just like you have with System.out.

Similar to Python, when you are done writing to your file you must close it. With the examples above, that would be out.close();.

Optional until end of this section. This part gets deeper into Exceptions than the boilerplate above. This will be discussed in depth in Data Structures, Comp 271.

You may want to write to a file that is specified by the user, who could enter something by mistake. In this case, where the user may have entered a bad name for the file, you might not want the try-catch block to make you abort. Here is a loop variation to keep on until the output file is opened. The catch clause just prints a message, and the loop continues. Let us assume you already have Scanner in able to read from the keyboard:

PrintWriter out = null;
String printFileName;

while (out == null) {
    System.out.print("Enter output filename: ");
    printFileName = in.nextLine();

    try {
        out = new PrintWriter( // if exception, no assignment to out
                 new BuferedWriter(
                    new File(printFileName) ));
    }  catch ( IOException e) {
             System.out.println(
                "Sorry but I was unable to create " + printFileName);
    }
}

Heads or Tails Exercise

Write a Java program TestFlip.java that includes:

1. The completion of the method with this description:

   /** Use the Random object to simulate
   *   a fair coin toss.
   *   Print either "Heads" or "Tails"
   *   with equal liklihood.  */
   public static void flip(Random r)
   

2. In the main method, create a Random object. Then call flip with this Random object as parameter 10 times in a for-loop. (Test by running this program several times to see the different output.)

Command Line Parameter Exercises

1. Write a program Adder.java that calculates and prints the sum of command line parameters, so if you make the command line parameters be 2 5 22 then the program prints 29.

2. Write a program ShowFiles.java that assumes the command line parameters are each a text file name directly readable by the program. For each file named, print out the three heading lines in the format shown, and then each line of the file contents.

   If file q.txt contains

   What is the answer

   to the universe

   and everything?

   and file ans.txt contains

   The answer is

   42.

   Then calling ShowFiles with parameters:

   q.txt ans.txt

   prints:

   ---------------------

   q.txt

   ---------------------

   What is the answer

   to the universe

   and everything?

   ---------------------

   ans.txt

   ---------------------

   The answer is

   42.

   You will need Scanner method hasNextLine for your file reading while-loop.

Also look at my few added notes below for Common Mistakes and Java Documentation Online.