home—info—lects—labs—exams—hws
tutor/PIs—Object120 + its docs—java.lang docs—java.util docs
lect05a
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
|
What happens in the last case?
This is actually reminiscent of
3+4*5 —
where arithmetic (and Java) have a special rule:
do all the multiplications-and-divisions (left-to-right),
then go back and
do all the additions-and-subtractions (left-to-right).
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 case1.
-- 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 set2 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.)
Is announcing pubMsg secure, even if there are eavesdroppers?
Let's try it!
A volunteer:
Choose your secret privMsg and write it down, without telling anybody.
Compute pubMsg, and announce it.
Can any of you eavesdroppers figure out the original message?
(You want to just divide by 37, but how to do that in this world of mod-100 arithemetic?)
The original privMsg was …
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 10308 is a ridiculously huge number;
there are “only” 1080 particles
in the universe (electrons, photons, quarks...),
1090 is a ten billion times bigger. So
10308 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_VALUE3
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.
(We won't enforce this in grading for this class though.)
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 ) {
________________
}
|
Hint: % and its complement, integer-division /,
are your friends.
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.
So how do we see if two doubles are practically-equal?
One immediate imponderable is “how close is close enough to
be considered practically equal”?
Well, for the moment4,
let's say being within 0.0003 is close enough:
((y-0.0003 < x) && (x < y+0.0003)) is a start.
This amount 0.0003 is often called the “tolerance”
of the comparison.
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,
-
syntax to declare a function (signature),
-
comments (javadoc),
-
test cases,
-
converting arithmetic formulas into Java,
-
return,
-
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
-
arithmetic issues
1Well, they do, but they're not static,
and they require new which we haven't talked about yet.
And anyway, the built-in conversion functions are tedious to write:
(new Integer( numPizzas )).doubleValue().
↩
2
Well, we haven't talked about classes yet, but
Java also lets you cast one class to another (not just numbers).
However, casting classes is poor style; it indicates your program
isn't correctly mirroring your real-world problem.
↩
3
This is a preview:
Just as there are built-in classes String
and Math,
there is also a class named Integer.
The class Integer is a “wrapper class”
for its little cousin, type int.
We won't go into details, but just keep in mind that while int
and class Integer are related,
the primitive type int is not a class.
↩
4We'll later realize that we really
should compare the relative size of the two numbers:
0.001 might be good for comparing people's height in inches, but not for
the width of two hairs in inches.
↩
home—info—lects—labs—exams—hws
tutor/PIs—Object120 + its docs—java.lang docs—java.util docs