ITEC 120 2012fall dbraffitt ibarland

home—info—lects—labs—exams—hws
tutor/PIs—breeze (snow day)
Object120 + its docs—java.lang docs—java.util docs

lect05b
arithmetic
and, bad arithmetic

Discuss: hw03b test cases for max, median.

Last time, we saw boolean operators for (resp.) and, or, not: &&, ||, !. We could then work out, step-by-step,

/* Three local variables -- declare and initialize */
boolean healthy = true;
boolean wealthy = true;
boolean wise = false;

(healthy ||  wealthy) && wise      
 healthy || (wealthy  && wise)

/* Same expression but w/o parentheses */
healthy || wealthy && wise

Add explicit parentheses to (part of) the following if condition, without changing the meaning:

/** @return a message to stick in a fortune cookie
 */
String fortuneCookieMessage() {
  int cholesterol = 160;
  double netWorth = 23456.78;
  boolean startHomeworksEarly = true;
  
  if ((cholesterol < 200) && (networth > 1000000) || startHomeworksEarly) {
    return "You are happy.";
    }
  else {
    return "Life is bleak.";
    }
  }

Arithmetic

• 3+4*5. Compare to some alien arithmetic 3@4$5, where @ and $ are operators you can look up in a table (just like you can with +,*). We say, *,/ have higher precedence than +,- (and they are both “left-associative”).
• Java has the remainder-function as a built-in operator: type 5 % 3, and you'll get the remainder after dividing 5 by 3. Try also: 4 % 3 and 6 % 3. (Maybe ... 0 % 3 and -1 % 3, too.)
• Note that % and integer-division complement each other:
  For all ints p and q where q != 0, we have p == (p/q)*q + (p%q).
• What is 6 * 7 % 3? (That is, what is the precedence of %, compared with the other operators?)
  Upshot: You can count on *,/ (and %) happening before +,-, and furthermore it's left-to-right within each category.
  But: % isn't the only new operator Java has; there are 46 operators with 13 levels of precedence in Java. Nobody memorizes all the precedence rules; once you're beyond basic arithmetic, use parentheses to make your operations clear. (Even if you know the precedence of some obscure operator, other people reading your code might not.)
• Evaluate 2/3.
  Huh? What about 4/3? 5/3? 6/3?
  What's going on?
  There isn't a problem when we say 4.0 / 3.0 (well, not much of a problem).
  It turns out: There are two different functions, each named /: real division, and integer division (quotient).
  Why Java decided to give those two fairly different beasts the same name is a bit of a mystery. At any rate, beware the pitfall. Explain why the following is wrong, even though tier2fee is declared as a double:

  double tier2fee = (salePrice - 25) * 3 / 100 ;

• What do you do if you have two ints, and you want to do floating-point division on them? Well, if you have int literals like 4 and 3, you could write 4.0 / 3.0. But what if you had two int variables, like numPizzas and numPeople?

  The solution is that we must call a function to convert an int into a double. One sensibly-named function is Object120.intToDouble( int n ). What if we we didn't have Object120 to make life easy for us? Surely there is a built-in function to do so. It turns out, that's not the case¹. -- Java has a whole special syntax for calling this particular conversion function, called casting. You write (double) in front of the int expresion:

  ((double) numPizzas) / ((double) numPeople)

  Note that two outer sets of parentheses are for clarity. The parentheses around the word double are required.

  Casting is the only time you use the name of a type even though you aren't introducing a new name to the Java compiler. It is conceptually annoying that Java has a whole special syntax just for this small set² of conversion functions.

  Java calls these conversion functions for you all the time, behind your back. For instance, Math.sqrt(25) is silently re-written as Math.sqrt( (double) 25 ), since Math.sqrt's documentation shows it requires a double as input.

  Beware that casting can induce arithmetic errors (discussed below).

Review

• Order of precedence for boolean and other operators: Use parentheses, if it's at all ambiguous.
• Order of precedence for arithmetic: you can assume everybody knows: first all multiplication/divisons (left-to-right), then all addition/subtractions (left-to-right). (Still, sometimes parentheses can add clarity.)
• / can either mean “call the built-in function integer-division”, or “call the built-in function floating-point-division”, depending on context.
• Casting: a whole special syntax, just to call a function which takes a double and returns a nearby int, and vice versa:

  (double) 5 int m = 13; int n = 5; ((double) m) / ((double) n)

  Also note that behind your back, Java is often converting doubles to ints. (For instance, 3/5.2 and Math.sqrt(4).)
• % is remainder; it is the complement to quotient. I always have to look up (or, type in) how % works with negative numbers.

(Optional) An application of %: public key cryptography

Web traffic is sent on postcards. How to securely communicate your credit-card number to amazon, without any pre-arrangement? “Inconceivable!”?

Amazon might say on their web page:

Our public key pubKey = 37. If you want to send us a secret message privMsg (a two-digit number), multiply your secret number by our public key, and tell us the last two digits (only) of the result: That is, tell us (privMsg * pubKey) % 100. (We can name this result pubMsg.)

Note that this used no pre-arrangement between the sender and the receiver. This is called “public key cryptography”, since eavesdroppers know as much about breaking the code as the sender.

You could break this code, if you could divide by 37 mod 100. (Or more precisely: find the multiplicative inverse of 37, mod 100.) Project: read about the extended Euclidean algorithm for calculating muliplicative inverses. Break this code!

Although this particular scheme is easy to break with a bit of math knowledge (this Extended Euclidean algorithm), the example is to motivate how a public-key system is even conceivable.

Arithmetic errors

• What is 200-110? What about 2.00-1.10?
• What is 7/25*25?
  How about
  7.0/25.0*25.0
  14.0/25.0*25.0
  21.0/25.0*25.0
  Beware, round-off error! It seems small, but sometimes small errors can really add up. (Next time you fly home for thanksgiving, you might give some thought to whether the software controlling the plane is using doubles.)

• We also have the issue of overflow with doubles. Try 1e308 + 1e308. Double.MAX_VALUE. (Keep in mind that 10³⁰⁸ is a ridiculously huge number; there are “only” 10⁸⁰ particles in the universe (electrons, photons, quarks...), 10⁹⁰ is a ten billion times bigger. So 10³⁰⁸ is a number that doesn't correspond to any reasonable physical amount.

  There is another twist to this: we might try to compute numbers which are so close to 0 they can't be represented by a double: Double.MIN_VALUE. Try Double.MIN_VALUE/2. As before, we have a trade-off between float vs double.

• 2000000000 + 2000000000 (?!) What's going on? For int, the computer only keeps about 10 places total (more accurately, 32 binary bits); the biggest and smallets legal int values are Integer.MAX_VALUE and Integer.MIN_VALUE³ When int isn't big enough, there is another type long.
  How about Long.MAX_VALUE (10 quintrillion). What is the trade off? There is also Short.MAX_VALUE and Byte.MAX_VALUE. (Notice that the digits roughly double.)
• It's not that computers can't do grade-school arithmetic. If nothing else, you could write a program which takes two (long) strings of digits, and adds them exactly. Some languages have precise arithmetic built-in; Mathematica and Lisp are two examples.

  Aside: Java does have a way to do exact arithmetic, but it takes some extra typing:

  java.math.BigInteger ratherLarge1 = new java.math.BigInteger( "987654321098765432109876543210" ); java.math.BigInteger ratherLarge2 = new java.math.BigInteger( "012345678901234567890123456789" ); (ratherLarge1.add(ratherLarge2)).toString();

  (This is a teaser to next week, when we'll talk about state, constructor-methods, and calling constructors with new.)

• We mentioned, that casting raises the specter of silent overflow issues: If casting an int to a double, you are throwing away accuracy. But worse, if you cast a large double to an int, and that double is bigger than Integer.MAX_INT, the cast will silently succeed, with a wildly incorrect value!

  (int) 7e35 // Size of the universe, in nanometers... whereas 2billion nanometers ~ 6ft.

  I'd prefer the computer meekly raise its hand and indicate there might be an error, rather than claim that the universe is 6ft across because of its insistence on only keeping fifteen digits of accuracy.

Edict of Programming: When possible, using int is preferred to double. For instance, the price of an item is often best given in integer cents, rather than double dollars. This will avoid accumulation of small errors, as in 2.00-1.10 vs. 200-110.

Example

Exercise for the reader: Write the following, using / and %:

/** Return a nicely formatted String representing a price in dollars.
 * @param cents An amount of money (in cents).
 * @return A String representing cents, in dollars.
 * Examples:
 *   dollarAmount(167) = "1 dollar and 67 cents"
 *   dollarAmount(43) = "0 dollars and 43 cents"
 *   dollarAmount(__) = ______
 */
static String dollarAmount( int cents ) {
  ________________
  }

Note that really, we're relying on the fact that when Java sees + with a String on one side and an int on the other, then it is calling (behind our back) an int-to-String conversion function.

Comparing doubles

Beware numerical inaccuracies: (2.0 - 1.1 == 0.9), or ( (7.0/25.0)*25.0 == 7.0 ).

double x = 2.0 - 1.1;
double y = 0.9;

x == y
// huh?  That's an unexpected answer.  How to debug?

x
// Oh, now it's clear what happened.

Edict of Programming: Do not use == with doubles.

It's likely that your code might have many different places where it wants to compare two doubles within the given tolerance. Rather than repeat something like ((y-0.0003 < x) && (x < y+0.0003)) is a start. many many times, what would we do?
Yes -- write your own helper function to avoid repeated code! So you might write double approxEqual(double a, double b).

Actually, we should look at an relative difference between two terms, rather than an absolute difference.

Review

We have covered many topics over the last 4 weeks:

• types,
• syntax to call a function,
• test cases,
• converting arithmetic formulas into Java,
• return,
• syntax to declare a function (signature),
• local variables (initializing and declaring) to give a name to sub-computations so that you can use that sub-result later;
• if-else statements
• if-else-if statements
• (mentioned only briefly): javadoc, for comments: @param and @return before each function; @author and @version before the class (and, if you like, before specific functions).
• arithmetic issues
• casting, as way of calling conversion functions

home—info—lects—labs—exams—hws
tutor/PIs—breeze (snow day)
Object120 + its docs—java.lang docs—java.util docs

©2012, Ian Barland, Radford University Last modified 2012.Oct.03 (Wed)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu