Wednesday, March 30, 2005

Enhanced for Loop

Discussion

EnhancedForStatement =
'for', '(', [VariableModifiers], Type, Identifier, ':', Expression, ')', Statement ;

Enhanced for Loop using Array Type

The following code is what you had to write before.

J2SE 1.4 code:
public class ForLoop {
    public static void main(String[] args) {
        Integer[] integers = {
            new Integer(11), new Integer(28), new Integer(85),                                                                     
            new Integer(37), new Integer(43)
        };

        for (int i = 0; i < integers.length; i++) {
            System.out.println(integers[i].intValue()); // 11 28 85 37 43
        }
    }
}

The following code is what you would write now.

J2SE 1.5 code:
public class EnhancedForLoop {
    public static void main(String[] args) {
        Integer[] integers = { 11, 28, 85, 37, 43 };

        for (int i : integers) {
            System.out.println(i); // 11 28 85 37 43
        }
    }
}

Decompiled Enhanced for Loop

This is basically what the enhanced for loop code does — the code looks pretty much like the old J2SE 1.4 code, however javac does not create separate Integer objects for each value with new Integer(11) Instead, javac use the public static Integer valueOf(int i) { static factory method, so that Integer objects may be cashed and Integer objects with the same value may be reused.

public class Main {
    public static void main(String[] args) {
        Integer[] integers = { 
            Integer.valueOf(11), Integer.valueOf(28), Integer.valueOf(85),
                Integer.valueOf(37), Integer.valueOf(43) 
        };
        
        for (int i = 0; i < integers.length; i++) {
            System.out.println(integers[i].intValue());
        }
    }
}

Enumeration

If you are still trying to write an enhanced for loop using a class that returns an Enumeration instead of an Iterator, I will now put you out of your misery: The enhanced for loop does not work with classes that return Enumeration because such classes does not implement the interface Iterable.

The Expression must be of type Iterable or an array type (JLS3 2005:14.14.2).

This code works:
DefaultMutableTreeNode tree = ...;

for (Enumeration e = tree.postorderEnumeration(); e.hasMoreElements();) {
    System.out.println(e.nextElement()); // do something with the element
}
This code won't work:
DefaultMutableTreeNode tree = ...;

for (DefaultMutableTreeNode element : tree) {
    System.out.println(element);  // do something with the element
}

The above code does not work because the Expression tree is not of type Iterable. It is of the type DefaultMutableTreeNode that does not implement Iterable.

References

Resources

Monday, March 28, 2005

The JLS3 Grammar

Introduction

You may browse the JLS3 grammar at http://www.lykkenborg.no/java/grammar/JLS3.html.

Discussion

The grammar follows The Java Language Specification, Third Edition as closely as possible. The reasons for "rewriting" the grammar are discussed here.

The JLS3 (2005) itself is probably worth a re-read if you're programming with Java 1.5.0 (White 2005). Actually, I would say that it's a must if you don't want to end up as "Tiger" food! A substantial part of the Java grammar has been affected by the proposed changes to the JLS.

The proposed changes include:

(JLS3P 2005; J2SE5 2004)

Errata

Browsing through the grammar (JLS3P 2005), I found the following problems:

Grammar Changes for JLS3 (2005)

The following changes were made for the pre-publication PDF release.

  • Many duplicates of rules are removed, for instance ArgumentList, EnumConstant, InterfaceType, Literal, OctalDigit, TypeName. Only the first instance of a rule is kept.
  • TypeName was changed to TypeDeclSpecifier in rule InterfaceType
  • 2 rules for TypeName was made into one
  • The rule TypeDeclSpecifier was created
  • The rule ClassType was fixed. TypeName replaced by TypeDeclSpecifier
  • The rule TypeParameters was replaced by TypeParameter. The rule TypeParameter is now called from the rule TypeParameters
  • The rules TypeParameters and TypeParameterList was found in 8.1.2 Generic Classes and Type Parameters
  • SimpleTypeName replaced Identifier in the rule ConstructorDeclarator. The nonterminal SimpleTypeName in rule ConstructorDeclarator is still not defined (JLS3 2005), (I renamed SimpleTypeName to Identifier, similar to the rule NormalClassDeclaration.)
  • EnumConstant was replaced by EnumConstantName in rule SwitchLabel
  • Added the rule EnumConstantName
  • All NonWildTypeArguments replaced with TypeArguments in rule ClassInstanceCreationExpression
  • TypeName replaced by ClassOrInterfaceType in rule ArrayCreationExpression

Grammar Errors

  • SimpleTypeName in ConstructorDeclarator is not defined (JLS3P 2005:245). SimpleTypeName is not defined in JLS2 either. (I renamed SimpleTypeName to Identifier, similar to the rule NormalClassDeclaration.)
  • Expression1 and Expression2 in AssertStatement is not defined (JLS3P 2005:369). (I renamed Expression1 and Expression2 to Expression).
  • TypeParameter (JLS3P 2005:65) is never called by any rules and the rule TypeParameters is missing. (I renamed the rule TypeParameter: to TypeParameters:) The rule TypeParameter is now called from the rule TypeParameterList.
  • NonWildTypeArguments should probably be optional for MethodInvocation: TypeName . NonWildTypeArguments Identifier (ArgumentList opt) (JLS3P 2005:435), especially since NonWildTypeArguments is optional everywhere else. (I made NonWildTypeArguments optional.)

Formatting Errors

  • There is no change in the rule VariableDeclaratorId: since JLS2 as indicated (JLS3P 2005:201).
  • The rule Keyword: is not sorted for the keyword goto (JLS3P 2005:37). (I sorted it.)
  • The formatting in 9.6 Annotation Types is not correct because everything is printed in italic (JLS3P 2005:271).

Grammar Clarifications

  • Input and CompilationUnit are goal symbols. It's OK that no rules are calling them.
  • MethodDeclarator is divided into two rules with the same name. This is confusing, but not an error. The division is an attempt to visualize that one of the rules (MethodDeclarator: MethodDeclarator [ ]) is deprecated, but still compatible. (I rewrote the two rules into one).
  • Many rules are identical. This is confusing, but no error. (For instance the rule TypeName is identical to the rule PackageOrTypeName.)
  • MarkerAnnotation in Annotation is defined, but well hidden on page 285.
  • SingleElementAnnotation in Annotation is defined, but well hidden on page 285.
  • CastExpression (JLS3P 2005:476) is clearly missing Dims opt (15.16 Cast Expressions) (I added Dims opt to the rule.)

References

Resources

Friday, March 25, 2005

Document Standard

Introduction

This is the standard for documentation used in this blog.

Discussion

Citing

This is the citing standard used in the blog. Citing in the text follows this pattern:

  Some sentence (AuthorSurname1 & AuthorSurname2 Year:FromPage-ToPage).

Example: Writers should be credited for their work and their writing (Hillard 2004).

or

  AuthorSurname1 & AuthorSurname2 (Year:FromPage-ToPage) some sentence.

Example: Hillard (2004) says that writers should be credited for their work and their writing.

There exists at least as many citing standards as there are university faculties in the world, so I'm relying instead on tables when writing reference lists. References follows this pattern:

Usually, I write from the top of my head. However, I also try my best to check the facts. This is sometimes difficult to do, and if a citation is missing but needed, this will be written as "(citation needed)".

References

Author Hillard, Van E.
Year 2004
Title Citing Sources
Place Durham, NC
Publisher Duke University Libraries
Retrieved Friday, March 25, 2005 from http://library.duke.edu/research/guides/citing/

Author Kernighan, Brian W. & Ritchie, Dennis M.
Year 1988
Title C-programmering: The C Programming Language
Place Englewood Cliffs, N.J.
Publisher Prentice Hall

Document Structure

Documents should follow the structure: Introduction, Methods, Results and Discussion (IMRAD). Each page should consist, at least, of some of these parts:

Introduction
What problem was studied?
Program (Methods)
How was the problem studied? The program is the "materials" and "methods" used.
Output (Results)
What were the findings? The "results" obtained from running the program.
Discussion
What do these findings mean? A conclusion or a summary.
Conclusion
A conclusion or a summary.
References
Reference list.
Resources
Resources are sometimes added for more information elsewhere that could be of interest.

IMRAD Formatting

<h1>Introduction</h1>
<h1>Program</h1>
<h1>Output</h1>
<h1>Discussion</h1> 
<h1>References</h1><ul><li></li></ul>
<h1>Resources</h1><ul><li></li></ul>

Reference Formatting

<table border="0">
  <tr>
    <th class="ezine">Reference</th>
    <td class="ezine"></td>
  </tr>
  <tr>
    <th class="ezine">Author</th>
    <td class="ezine"></td>
  </tr>
  <tr>
    <th class="ezine">Year</th>
    <td class="ezine"><td>
  </tr>
  <tr>
    <th class="ezine">Title</th>
    <td class="ezine"></td>
  </tr>
  <tr>
    <th class="ezine">Place</th>
    <td class="ezine"></td>
  </tr>
  <tr>
    <th class="ezine">Publisher</th>
    <td class="ezine"></td>
  </tr>
  <tr>
    <th class="ezine">Retrieved</th>
    <td class="ezine"></td>
  </tr>
  <tr>
    <th class="ezine">URL</th>
    <td class="ezine"></td>
  </tr>
</table>
<br>

Wednesday, March 23, 2005

How do I read an unsigned byte in Java?

Introduction

Bytes in Java are signed values from -128 to 127. This is a bit of a problem if you need to work with unsigned bytes ranging from 0 to 255, inclusive. There's an explanation why bytes in Java are signed, but why is there no methods for handling unsigned bytes? Anyway, read on and I will explain how to write methods handling unsigned bytes.

Program

public class UnsignedByte {    
    public static void main(String[] args) {
        byte b = -1; // signedByte = -1, unsignedByte = 255
        int i = b & 0xFF; // unsignedInt = signedByte & 0xFF;
        b = (byte) i; // signedByte = (byte) unsignedInt;
        System.out.println(b);
        System.out.println(i);
    }
}

Output

[user]$ java UnsignedByte
-1
255

Discussion

In order to do math operations on unsigned bytes in Java, you should first convert them to ints. This works because:

-1        = 11111111111111111111111111111111
0xFF      = 00000000000000000000000011111111
-1 & 0xFF = 00000000000000000000000011111111 = 255

Conclusion/Summary

If you are going to use this code a lot, it would be better to rewrite the code as methods (NetSpy 2003):

public final class UnsignedByte {
    public static void main(String[] args) {
        byte b = -1;
        int i = 255;
        System.out.println(unsigned(b));
        System.out.println(signed(i));
    }
    
    public static int unsigned(byte b) {
        return b & 0xFF;
    }
    
    public static byte signed(int i) {
        return (byte) i;
    }
}
[user]$ java UnsignedByte
255
-1

References

Author NetSpy
Year 2003
Title NetSpy Version 2.0
Place Holland, MI
Publisher Hope College Department of Computer Science
Retrieved Wednesday, April 13, 2005
URL http://www.cs.hope.edu/netspy/docs_developer/java/NetSpy3/Packets/Header.html
http://www.cs.hope.edu/netspy/docs_developer/Packets/Ethernet.html
http://www.cs.hope.edu/netspy/docs_developer/Packets/DLHeader.html

Monday, March 21, 2005

Binary Numbers

Introduction

The following methods can be used to convert binary numbers in Java:

  • public static String toBinaryString(int i)
  • public static String toBinaryString(long i)
  • public static int parseInt(String s, int radix) throws NumberFormatException
  • public static long parseLong(String s, int radix) throws NumberFormatException

Program

package bloggingjava;

class Main {
    public static void main(String[] args) {
        System.out.println(Integer.toBinaryString(42));
        System.out.println(Integer.parseInt("10101010", 2));
    }
}

Output

[user]$ javac Binary.java
[user]$ java Binary
101010
170

Discussion

According to The Hitchhiker's Guide to the Galaxy, the Ultimate Answer to Life, the Universe, and Everything is 42. "As any digital hardware engineer, or software engineer, can tell you, the number '42' in base ten is equal to '101010' in base two. This alternating pattern of ones and zeros illustrates DEEP Thought's indecision about the Ultimate Question." (http://www.digitalthoughtsw.com/DTS/42/). However, the smallest number of bits a computer can work with is 8 bits, called a byte. 42 in binary is not 101010, but 00101010. The answer, then, should be 10101010 which is 170, not 42. So, the theory about Deep Thought being indecisive about the answer to the Ultimate Question seems to be wrong.

Resources

Saturday, March 19, 2005

CPL

Introduction

CPL (Combined Programming Language) is based on ALGOL 60, and is an ALGOL-like language in both syntax and spirit.

Discussion

CPL was partially implemented on the Titan computer at Cambridge and the Atlas computer at London University. CPL was designed to solve all types of problems, it was designed to be machine-independent, but oriented towards actual computers. (Barron et al. 1963:134-143).

The work on CPL started in 1961 at the University of Cambridge. M. Richards continued work on BCPL, a descendant of CPL, in 1968 (Jones 1999).

References

BCPL

Introduction

BCPL (Basic CPL) is a language designed for writing compilers. BCPL is a descendant from CPL (Combined Programming Language) (Richards & Whitby-Strevens 1980:1).

Discussion

This is a complete program that writes Hello, World in BCPL (Richards & Whitby-Strevens 1980:8):

  GET "LIBHDR"
  LET START() BE WRITES("Hello, World")

References

Author Richards, Martin & Whitby-Strevens, Colin
Year 1980
Title BCPL - the language and its compiler
Place Bristol
Publisher Cambridge University Press
Retrieved
URL

Sunday, March 13, 2005

Writing the createToolBar method

Program

    void createToolBar() {
        JToolBar jToolBar1 = new JToolBar();
        jToolBar1.add(new JButton("jButton1"));
        jToolBar1.add(new JButton("jButton2"));
        jToolBar1.addSeparator();
        jToolBar1.add(new JButton("jButton3"));

        getContentPane().add(jToolBar1, BorderLayout.NORTH);
    }

Writing the createMenuBar method

Program

    void createMenuBar() {
        JMenuItem jMenuItem1 = new JMenuItem("jMenuItem1");
        JMenuItem jMenuItem2 = new JMenuItem("jMenuItem2");
        JMenuItem jMenuItem3 = new JMenuItem("jMenuItem3");

        JMenu jMenu1 = new JMenu("jMenu1");
        jMenu1.add(jMenuItem1);

        JMenu jMenu2 = new JMenu("jMenu2");
        jMenu2.add(jMenuItem2);
        jMenu2.add(jMenuItem3);

        JMenuBar jMenuBar1 = new JMenuBar();
        jMenuBar1.add(jMenu1);
        jMenuBar1.add(jMenu2);

        setJMenuBar(jMenuBar1);
    }

Writing the createStatusBar method

Program

    JPanel createStatusBar() {
        JTextField textField1 = new JTextField("StatusBar");
        textField1.setEditable(false);
        textField1.setBorder(BorderFactory.createLoweredBevelBorder());

        JPanel jPanelStatusBar = new JPanel();
        jPanelStatusBar.setLayout(new BoxLayout(jPanelStatusBar, BoxLayout.X_AXIS));
        jPanelStatusBar.add(textField1);

        return jPanelStatusBar;
    }

Discussion

The StatusBar should be a part of the "Center" in the ContentPane. The StatusBar should not be placed "South" in the Content Pane, because the ToolBar could be moved to the "South" by the user.

Writing the createContentPane method

Program

    void createContentPane() {
        JPanel jPanelCenter = new JPanel();
        jPanelCenter.setLayout(new BorderLayout());
        jPanelCenter.add(createStatusBar(), BorderLayout.SOUTH);

        getContentPane().add(jPanelCenter, BorderLayout.CENTER);
    }

jPanelCenter is placed at the center of the ContentPane because SOUTH, EAST, WEST, NORTH are reserved for jToolBar1.

Example
    void createContentPane() {
        JPanel jPanelCenter = new JPanel();
        jPanelCenter.setLayout(new BorderLayout());
        jPanelCenter.add("North", new JButton("North"));
        jPanelCenter.add("South", new JButton("South"));
        jPanelCenter.add("East", new JButton("East"));
        jPanelCenter.add("West", new JButton("West"));
        jPanelCenter.add("Center", new JButton("Center"));

        getContentPane().add(jPanelCenter, BorderLayout.CENTER);
    }

Typesafe Enums

"Enumeration types are a bit odd, bitfields are odder. The "static" keyword is very strange."
(Dennis Ritchie)

public class Enumerated {
    public enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }
    
    public static void main(String[] args) {
    }
}

The compiler will implicitly produce a new class Day like this: public static final class Day extends Enum { ...

The compiler will also implicitly produce Day objects members.

        public static final Day MONDAY;
        public static final Day TUESDAY;
        public static final Day WEDNESDAY;
        public static final Day THURSDAY;
        public static final Day FRIDAY;
        public static final Day SATURDAY;
        public static final Day SUNDAY;

Obviously, you should now be able to write code such as:

    public static void main(String[] args) {
        Day day = Day.TUESDAY;
        System.out.println(day);
    }

Since Day extends Enum, you will also be able to use a few methods such as:

    public static void main(String[] args) {
        Day day = Day.TUESDAY;
        System.out.println(day.ordinal());
    }
[user]$ javac Enumerated.java
[user]$ java Enumerated
1

More Examples

public class Enumerated {
    
    public enum Color { RED, GREEN, BLUE }

    public enum TrafficLight { RED, YELLOW, GREEN }
    
    // monday is the first day of the week (ISO-8601)
    public enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }

    public enum Month { 
        JANUARY, FEBRUARY, MARCH,
        APRIL, MAY, JUNE, 
        JULY, AUGUST, SEPTEMBER,
        OCTOBER, NOVEMBER, DECEMBER
    }
    
    public enum Compass { 
        NORTH, NORTHEAST, EAST, SOUTHEAST, 
        SOUTH, SOUTHWEST, WEST, NORTHWEST
    }

    public enum Planets { 
        MERCURY, VENUS, EARTH, 
        MARS, JUPITER, SATURN, 
        URANUS, NEPTUNE, PLUTO
    }
    
    public enum Piece { EMPTY, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING }
    
    public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }

    public enum Fish { SALMON, TROUT, TUNA, HADDOCK, SWORDFISH, SHARK }
    
    public enum Gender { MALE, FEMALE }
    
    public static void main(String[] args) {
    }
}

References

Herb Sutter, 2005. The C Family of Languages: Interview with Dennis Ritchie, Bjarne Stroustrup, and James Gosling (http://www.gotw.ca/publications/c_family_interview.htm)

Resources

Saturday, March 12, 2005

Comments

"Real Programmers don't comment their code. If it was hard to write, it should be hard to understand."
(Vleck 1982)

"Document code? Why do you think they call it code?"
(Anonymous)

"Real Programmers don't need comments — the code is obvious."
(Anonymous)

"If a program is useful, it must be changed. If a program is useless, it must be documented."
(Anonymous)

Introduction

Comments are essential and is addressed to the human reader. Comments are also ignored by the compiler (Barron 1977).

Discussion

Comment brackets /* ... */ comes from PL/I, and allows comments to be used where they are meaningful (Barron 1977).

if (n <= 2) /* n == 0, 1, 2 returns 1 for Fibonacci numbers */ return 1; 
/**
 * This is a documentation comment
 */

Documentation intended for the javadoc tool.

References

Variables

Introduction

A running program need to store and refer to values. "A variable is a storage location [...]" (JLS3), that can hold a value.

A variable has a name, so that it is possible to refer to it. A variable has a type, so that it is certain what type of value it contains, and what operators that may be used with the variable. Finally, a variable has a value that it stores, which is the reason why variables are necessary in programs in the first place.

Local Variables

A local variable is a variable inside a method block. All local variables must be declared and initialized before they are used.

public class Main {
public static void main(String[] args) {
  int theAnswer; // declaration
  theAnswer = 42; // initialization
}
}

Here, the type is int, the variable is theAnswer, the operator is = and the value is 42.

The variable is declared and initialized in two steps.

public class Main {
public static void main(String[] args) {
  int theAnswer = 42; // declaration and initialization
}
}

The variable is declared and initialized in one single step.

This is a somewhat simplified grammar rule for the declaration:

LocalVariableDeclaration =
Type, Identifier, '=', Literal ';' ;

Concept: Every variable has a type.

Values

Introduction

Values is what programs work with. A value is data that is represented and stored in the computers memory. Examples of values are numbers and characters.

Program

This is how to write and represent the values 42, 'a' and true in source code:

class Main {
    public static void main(String[] args) {
        System.out.println(42);
        System.out.println('a');
        System.out.println(true);
    }
}

Note: The representation of the values in source code are called literals, and becomes values first when the program is compiled. Literals are used to hard-code data.

Output

42
a
true

Introduction to Programs and Programming

Introduction

Here you will learn how to think about Java programs and programming.

Talking to the Computer

Programs consists of statements, like a book written in English consists of sentences. However, a program look more like a complex instruction manual than it look like a novel. Programs may be written using English words, but programming a computer does not even come close to having a conversation with a human being. The computer will follow the rules of the language blindly, and everything you say to the computer is treated in a mechanical fashion. The computer demands precise communications, and it will never try to second guess what you really meant to say.

There are a few important facts you should know about programs, that will save you a lot of trouble:

  • The computer can process one and only one statement at a time — and no more.
  • The computer will only be concerned about the current statement — and only the current statement.
  • The computer will do exactly what the statements tell it to do — and nothing else.

These three principles are related to the "Parallelism Bug", the "Intentionality Bug" and the "Egocentrism Bug".

Types of Programs

A Java program usually run either as an application, as an applet or as a servlet. Applets are highly specialized programs that run inside HTML pages. Servlets are highly specialized programs that run on Web servers. Applications are stand alone programs, and don't need a browser or a server in order to run. Applications behave similarly to programs written in other languages.

In this tutorial, a Java program refers to both applets, applications and servlets. However, most examples in this tutorial are applications and Swing applications, because applications are more general than applets or servlets. Also, it is difficult to make applets run under different browsers. Applets have limited screen estate and cannot easily resize inside an HTML page. Everything you can do with an applet, you can do with an application, except, of course, run inside an HTML page. You may also run applications using Internet with the Java Web Start Application Manager.

Conclusion

In this tutorial, we will concentrate on writing programs that are applications and Swing applications. When you write programs, keep in mind that programming languages are somewhat limited in how you may express what you want the computer to do.

The HelloWorld Application

Program

The HelloWorld application is a typical "first program" printed in most text books:

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

Output

When you compile and run this program, it will print:

Hello World!

How to read a String from the keyboard

Introduction

You may want to enter text from the keyboard, do something with the text, and then print the result out to the screen. This is how to implement the application in Java:

Discussion

import java.io.*;

public class Keyboard {
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter first number: ");
        int a = Integer.parseInt(stdin.readLine());

        System.out.println("Enter second number: ");
        int b = Integer.parseInt(stdin.readLine());

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

Strongly Typed

Introduction

The Java programming language is a strongly typed language, which means that all types are predefined. Creating new types is not allowed. Strong typing helps detect errors at compile time, because every variable and every expression has a type that is known at compile time.

How to find the width and height of an application

Introduction

Why find the width and height of an application?
A good answer might be: You want the application to run as an applet, using the same width and height as the application.

Program

void createFrame() {
    setTitle(getClass().getName());
    createContentPane();

    addWindowListener(new WindowAdapter() {
        public void windowClosing(WindowEvent e) {
            System.exit(0);
        }
    });

    pack(); // show JFrame
    setVisible(true);

    System.out.println("width: " + getContentPane().getSize().width);
    System.out.println("height: " + getContentPane().getSize().height);
}

Computing Pi using BigDecimal

Introduction

Example program for how to use class java.math.BigDecimal.
See also: Fibonacci Numbers for a program that use the BigDecimal class.

Warning: Source code only compiles with jdk-1_5_0 or later.

Discussion

The program computes π using the Gauss-Legendre Algorithm (Smith 2005).

import java.math.BigDecimal;
import static java.math.BigDecimal.*;

class Pi {
    private static final BigDecimal TWO = new BigDecimal(2);
    private static final BigDecimal FOUR = new BigDecimal(4);
    
    public static void main(String[] args) {
        System.out.println(pi(Integer.parseInt(args[0])));
    }
    
    // Gauss-Legendre Algorithm
    public static BigDecimal pi(final int SCALE) {
        BigDecimal a = ONE;
        BigDecimal b = ONE.divide(sqrt(TWO, SCALE), SCALE, ROUND_HALF_UP);
        BigDecimal t = new BigDecimal(0.25);
        BigDecimal x = ONE;
        BigDecimal y;
        
        while (!a.equals(b)) {
            y = a;
            a = a.add(b).divide(TWO, SCALE, ROUND_HALF_UP);
            b = sqrt(b.multiply(y), SCALE);
            t = t.subtract(x.multiply(y.subtract(a).multiply(y.subtract(a))));
            x = x.multiply(TWO);
        }
        
        return a.add(b).multiply(a.add(b)).divide(t.multiply(FOUR), SCALE, ROUND_HALF_UP);
    }
    
    // the Babylonian square root method (Newton's method)
    public static BigDecimal sqrt(BigDecimal A, final int SCALE) {
        BigDecimal x0 = new BigDecimal("0");
        BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
        
        while (!x0.equals(x1)) {
            x0 = x1;
            x1 = A.divide(x0, SCALE, ROUND_HALF_UP);
            x1 = x1.add(x0);
            x1 = x1.divide(TWO, SCALE, ROUND_HALF_UP);
        }
        
        return x1;
    }
}
[user]$ javac Pi.java
[user]$ java Pi 1000
3.141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
59502445945534690830264252230825334468503526193118817101000313783875288658753320
83814206171776691473035982534904287554687311595628638823537875937519577818577805
321712268066130019278766111959092164202002

Of course, the last few digits are not correct as you may verify by computing more digits. The last 4 digits should be 1989 and not 2002.

The approximation π with 808 places was first obtained by Wrench Ferguson in Sept 1947 using a desk calculator, introducing the calculation of π into the computer age (O'Connor & Robertson 2000).

Square root of 2

Square roots can also be calculated easily. The square root of two can be calculated this way: System.out.println(sqrt(TWO, 1000)); with approximately 1000 places.

1.414213562373095048801688724209698078569671875376948073176679737990732478462107
03885038753432764157273501384623091229702492483605585073721264412149709993583141
32226659275055927557999505011527820605714701095599716059702745345968620147285174
18640889198609552329230484308714321450839762603627995251407989687253396546331808
82964062061525835239505474575028775996172983557522033753185701135437460340849884
71603868999706990048150305440277903164542478230684929369186215805784631115966687
13013015618568987237235288509264861249497715421833420428568606014682472077143585
48741556570696776537202264854470158588016207584749226572260020855844665214583988
93944370926591800311388246468157082630100594858704003186480342194897278290641045
07263688131373985525611732204024509122770022694112757362728049573810896750401836
98683684507257993647290607629969413804756548237289971803268024744206292691248590
52181004459842150591120249441341728531478105803603371077309182869314710171111683
916581726889419758716582152128229518488472

Programming with BigDecimal

You may acces static members by writing import static java.math.BigDecimal.*; This is called static import, and you use it in order to avoid writing BigDecimal.ONE and BigDecimal.ROUND_HALF_UP all over the place. Now, you may just write code such as BigDecimal a = ONE;

You need some constants for 2 and 4 in BigDecimal, so we define them. ONE is already defined (since 1.5):

private static final BigDecimal TWO = new BigDecimal(2);
private static final BigDecimal FOUR = new BigDecimal(4);

You can't use operators and write stuff like x = x * 2; Such code is called syntactic sugar, and would just complicate the language if allowed. Instead, you have to use methods and write x = x.multiply(TWO);

You need to know the number of decimal places, SCALE, when performing division such as BigDecimal b = ONE.divide(sqrt(TWO, SCALE), SCALE, BigDecimal.ROUND_HALF_UP);

The program does not use MathContext objects because it slows the program down as much as 10 times (java version 1.5.0)! You should probably write a.divide(TWO, SCALE, BigDecimal.ROUND_HALF_UP); instead of:

import java.math.MathContext;
...
private static MathContext mc = new MathContext(1000);
...
a.divide(TWO, mc);

Pi to 10000 places

Just to test the code, here is Pi to 10000 places:

3.141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
59502445945534690830264252230825334468503526193118817101000313783875288658753320
83814206171776691473035982534904287554687311595628638823537875937519577818577805
32171226806613001927876611195909216420198938095257201065485863278865936153381827
96823030195203530185296899577362259941389124972177528347913151557485724245415069
59508295331168617278558890750983817546374649393192550604009277016711390098488240
12858361603563707660104710181942955596198946767837449448255379774726847104047534
64620804668425906949129331367702898915210475216205696602405803815019351125338243
00355876402474964732639141992726042699227967823547816360093417216412199245863150
30286182974555706749838505494588586926995690927210797509302955321165344987202755
96023648066549911988183479775356636980742654252786255181841757467289097777279380
00816470600161452491921732172147723501414419735685481613611573525521334757418494
68438523323907394143334547762416862518983569485562099219222184272550254256887671
79049460165346680498862723279178608578438382796797668145410095388378636095068006
42251252051173929848960841284886269456042419652850222106611863067442786220391949
45047123713786960956364371917287467764657573962413890865832645995813390478027590
09946576407895126946839835259570982582262052248940772671947826848260147699090264
01363944374553050682034962524517493996514314298091906592509372216964615157098583
87410597885959772975498930161753928468138268683868942774155991855925245953959431
04997252468084598727364469584865383673622262609912460805124388439045124413654976
27807977156914359977001296160894416948685558484063534220722258284886481584560285
06016842739452267467678895252138522549954666727823986456596116354886230577456498
03559363456817432411251507606947945109659609402522887971089314566913686722874894
05601015033086179286809208747609178249385890097149096759852613655497818931297848
21682998948722658804857564014270477555132379641451523746234364542858444795265867
82105114135473573952311342716610213596953623144295248493718711014576540359027993
44037420073105785390621983874478084784896833214457138687519435064302184531910484
81005370614680674919278191197939952061419663428754440643745123718192179998391015
91956181467514269123974894090718649423196156794520809514655022523160388193014209
37621378559566389377870830390697920773467221825625996615014215030680384477345492
02605414665925201497442850732518666002132434088190710486331734649651453905796268
56100550810665879699816357473638405257145910289706414011097120628043903975951567
71577004203378699360072305587631763594218731251471205329281918261861258673215791
98414848829164470609575270695722091756711672291098169091528017350671274858322287
18352093539657251210835791513698820914442100675103346711031412671113699086585163
98315019701651511685171437657618351556508849099898599823873455283316355076479185
35893226185489632132933089857064204675259070915481416549859461637180270981994309
92448895757128289059232332609729971208443357326548938239119325974636673058360414
28138830320382490375898524374417029132765618093773444030707469211201913020330380
19762110110044929321516084244485963766983895228684783123552658213144957685726243
34418930396864262434107732269780280731891544110104468232527162010526522721116603
96665573092547110557853763466820653109896526918620564769312570586356620185581007
29360659876486117910453348850346113657686753249441668039626579787718556084552965
41266540853061434443185867697514566140680070023787765913440171274947042056223053
89945613140711270004078547332699390814546646458807972708266830634328587856983052
35808933065757406795457163775254202114955761581400250126228594130216471550979259
23099079654737612551765675135751782966645477917450112996148903046399471329621073
40437518957359614589019389713111790429782856475032031986915140287080859904801094
12147221317947647772622414254854540332157185306142288137585043063321751829798662
23717215916077166925474873898665494945011465406284336639379003976926567214638530
67360965712091807638327166416274888800786925602902284721040317211860820419000422
96617119637792133757511495950156604963186294726547364252308177036751590673502350
72835405670403867435136222247715891504953098444893330963408780769325993978054193
41447377441842631298608099888687413260472156951623965864573021631598193195167353
81297416772947867242292465436680098067692823828068996400482435403701416314965897
94092432378969070697794223625082216889573837986230015937764716512289357860158816
17557829735233446042815126272037343146531977774160319906655418763979293344195215
41341899485444734567383162499341913181480927777103863877343177207545654532207770
92120190516609628049092636019759882816133231666365286193266863360627356763035447
76280350450777235547105859548702790814356240145171806246436267945612753181340783
30336254232783944975382437205835311477119926063813346776879695970309833913077109
87040859133746414428227726346594704745878477872019277152807317679077071572134447
30605700733492436931138350493163128404251219256517980694113528013147013047816437
88518529092854520116583934196562134914341595625865865570552690496520985803385072
24264829397285847831630577775606888764462482468579260395352773480304802900587607
58251047470916439613626760449256274204208320856611906254543372131535958450687724
60290161876679524061634252257719542916299193064553779914037340432875262888963995
87947572917464263574552540790914513571113694109119393251910760208252026187985318
87705842972591677813149699009019211697173727847684726860849003377024242916513005
00516832336435038951702989392233451722013812806965011784408745196012122859937162
31301711444846409038906449544400619869075485160263275052983491874078668088183385
10228334508504860825039302133219715518430635455007668282949304137765527939751754
61395398468339363830474611996653858153842056853386218672523340283087112328278921
25077126294632295639898989358211674562701021835646220134967151881909730381198004
97340723961036854066431939509790190699639552453005450580685501956730229219139339
18568034490398205955100226353536192041994745538593810234395544959778377902374216
17271117236434354394782218185286240851400666044332588856986705431547069657474585
50332323342107301545940516553790686627333799585115625784322988273723198987571415
95781119635833005940873068121602876496286744604774649159950549737425626901049037
78198683593814657412680492564879855614537234786733039046883834363465537949864192
70563872931748723320837601123029911367938627089438799362016295154133714248928307
22012690147546684765357616477379467520049075715552781965362132392640616013635815
59074220202031872776052772190055614842555187925303435139844253223415762336106425
06390497500865627109535919465897514131034822769306247435363256916078154781811528
43667957061108615331504452127473924544945423682886061340841486377670096120715124
91404302725386076482363414334623518975766452164137679690314950191085759844239198
62916421939949072362346468441173940326591840443780513338945257423995082965912285
08555821572503107125701266830240292952522011872676756220415420516184163484756516
99981161410100299607838690929160302884002691041407928862150784245167090870006992
82120660418371806535567252532567532861291042487761825829765157959847035622262934
86003415872298053498965022629174878820273420922224533985626476691490556284250391
27577102840279980663658254889264880254566101729670266407655904290994568150652653
05371829412703369313785178609040708667114965583434347693385781711386455873678123
01458768712660348913909562009939361031029161615288138437909904231747336394804575
93149314052976347574811935670911013775172100803155902485309066920376719220332290
94334676851422144773793937517034436619910403375111735471918550464490263655128162
28824462575916333039107225383742182140883508657391771509682887478265699599574490
66175834413752239709683408005355984917541738188399944697486762655165827658483588
45314277568790029095170283529716344562129640435231176006651012412006597558512761
78583829204197484423608007193045761893234922927965019875187212726750798125547095
89045563579212210333466974992356302549478024901141952123828153091140790738602515
22742995818072471625916685451333123948049470791191532673430282441860414263639548
00044800267049624820179289647669758318327131425170296923488962766844032326092752
49603579964692565049368183609003238092934595889706953653494060340216654437558900
45632882250545255640564482465151875471196218443965825337543885690941130315095261
79378002974120766514793942590298969594699556576121865619673378623625612521632086
28692221032748892186543648022967807057656151446320469279068212073883778142335628
23608963208068222468012248261177185896381409183903673672220888321513755600372798
39400415297002878307667094447456013455641725437090697939612257142989467154357846
87886144458123145935719849225284716050492212424701412147805734551050080190869960
33027634787081081754501193071412233908663938339529425786905076431006383519834389
34159613185434754649556978103829309716465143840700707360411237359984345225161050
70270562352660127648483084076118301305279320542746286540360367453286510570658748
82256981579367897669742205750596834408697350201410206723585020072452256326513410
55924019027421624843914035998953539459094407046912091409387001264560016237428802
10927645793106579229552498872758461012648369998922569596881592056001016552563756
78

References

Friday, March 11, 2005

Operator Precedence

Discussion

The operators are listed from highest precedence to lowest, in precedence order. Operators on the same row have equal precedence. Operators with higher precedence are evaluated before operators with lower precedence.

Operators of equal precedence are evaluated in order depending on operator associativity. Left-associative operators are evaluated from left to right. Right-associative operators are evaluated from right to left.

Precedence Operation Group Associativity
[] . (params) array member access method call left-associative
expr++ expr-- ++expr --expr +expr -expr ~expr !expr post increment post decrement pre increment pre decrement ? ? ? ? unary right-associative
new (type)expr creation type cast non-associative
* / % multiplication division remainder multiplicative left-associative
+ - addition subtraction additive left-associative
<< >> >>> left shift right shift right shift shift left-associative
< > <= >= instanceof less than greater than less or equal greater or equal relational left-associative
== != equal not equal equality left-associative
& and bitwise AND left-associative
^ xor bitwise exclusive OR (XOR) left-associative
| or bitwise inclusive OR left-associative
&& and logical AND left-associative
|| or logical OR left-associative
? : conditional conditional right-associative
= += -= *= /= %= &= ^= |= <<= >>= >>>= assign addition subtraction multiplication division remainder and or xor shift shift shift assignment right-associative

Warning: You should avoid writing code that depends on order of evaluation. Such code is a bad programming practice, because it is hard to understand.

Concept: expr-- and ++expr has the same precedence. Java uses the same precedence and associativity of operators as "The C Programming Language" by Kernighan and Ritche.

Consider the program:
class Order {
   public static void main(String[] args) {
       int a = 1;
       int i = ++a + a--;

       System.out.println("i: " + i + ", a: " + a);
   }
}
i: 4, a: 1

If a-- has higher precedence than ++a, it should be executed before ++a and the result should be:

int i = ++a + a--;      // a = 1
i = ++a + 1; a = a - 1; // a = 0
a = a + 1; i = 1 + 1;   // a = 1
i = 2;

i = 2 and a = 1 is not the answer the program got, and it is obvious that a-- does not have higher precedence than ++a.

Type Wrappers

Introduction

A type wrapper is an object that contains an instance variable of the corresponding primitive type. The type wrapper also provide constants and methods useful when dealing with the corresponding primitive type.

Discussion

Corresponding Type Wrappers
Primitive Type Type Wrapper
boolean Boolean
char Character
byte Byte
short Short
int Integer
long Long
float Float
double Double

There are also several wrappers without a corresponding primitive type.

Wrapper Group Type Bits Example
Void Void void n/a n/a
Number Superclass n/a n/a Number n = new Byte((byte) 15);
BigInteger Integer n/a arbitrary-precision java.math.BigInteger bi = java.math.BigInteger.ONE;
BigDecimal Floating-point n/a arbitrary-precision java.math.BigDecimal bd = new java.math.BigDecimal(3.14);

How to write a Swing application

Program

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class SwingApplication extends JFrame {
    public static void main(String[] args) {
        new SwingApplication().createFrame();
    }

    void createFrame() {
        setTitle(getClass().getName());
        createContentPane();
        createMenuBar();
        createToolBar();

        addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });

        pack();
        setVisible(true);
    }

    void createContentPane() {
    }

    void createMenuBar() {
    }

    void createToolBar() {
    }
}

Tautologies

Introduction

A boolean expression that always evaluates to true, is called a tautology.

Using tautologies, it's often possible to simplify complex boolean expressions into simpler ones. This is important because programs may run faster and could be easier to understand. For instance, p & (p | q) could be simplified to p. Similarly, (p | q) & !(p & q) could be simplified to p ^ q, using the Java conditional operator ^ (xor). The boolean variables p and q could also represent complex boolean expressions, but in these examples we use simple expressions like false and true.

Program

Let's take a closer look at one of De Morgan's Laws.

!(p | q)        == (!p & !q);           // De Morgan's Laws

We can easily check if De Morgan's Law is a tautology, just by testing each combinations of p and q with a Java application.

public class Tautologies {
    public static void main(String[] args) {
        System.out.println("De Morgan's Laws");
        boolean p, q, r, A;
        p = false; q = false; A = !(p | q) == (!p & !q); System.out.println(A);
        p = false; q = true;  A = !(p | q) == (!p & !q); System.out.println(A);
        p = true;  q = false; A = !(p | q) == (!p & !q); System.out.println(A);
        p = true;  q = true;  A = !(p | q) == (!p & !q); System.out.println(A);
    }
}

Output

This application produces the following output.

De Morgan's Laws
true
true
true
true

Similarly you may check if (p & (q & r)) == ((p & q) & r) is a tautology. It is, because each test will print true.

        System.out.println("Associative Laws");
        p = false; q = false; r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = false; q = false; r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = false; q = true;  r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = false; q = true;  r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = false; r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = false; r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = true;  r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = true;  r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        System.out.println();

The Laws of Logic

!!p             == p                    // Law of Double Negation
!(p | q)        == (!p & !q);           // De Morgan's Laws
!(p & q)        == (!p | !q)            // De Morgan's Laws
(p | q)         == (q | p)              // Commutative Laws)
(p & q)         == (q & p)              // Commutative Laws)
(p | (q | r))   == ((p | q) | r)        // Associative Laws
(p & (q & r))   == ((p & q) & r)        // Associative Laws
(p | (q & r))   == ((p | q) & (p | r))  // Distributive Laws
(p & (q | r))   == ((p & q) | (p & r))  // Distributive Laws
(p | p)         == p                    // Idempotent Laws
(p & p)         == p                    // Idempotent Laws
(p | false)     == p                    // Identity Laws
(p & true)      == p                    // Identity Laws
(p | !p)        == true                 // Inverse Laws, Law of Excluded Middle
(p & !p)        == false                // Inverse Laws, Law of Contradiction
(p | true)      == true                 // Domination Laws
(p & false)     == false                // Domination Laws
(p | (p & q))   == p                    // Absorption Laws
(p & (p | q))   == p                    // Absorption Laws

More Tautologies

((p | q) & !(p & q)) == (p ^ q)
(p != q) == (p ^ q)

Discussion

Boolean expressions may be simplified using tautologies. Tautologies like (p | (p & q)) == p always evaluates to true. So, both sides of the equality operator always have to give the same result. A complicated boolean expression like p | (p & q) can be replaced by a simpler expression like p.

The program testing for tautologies could perhaps be "simplified" using loops. The program also demonstrates how to convert between boolean and int.

public class Main {
    
    public static void main(String[] args) {
        boolean p, q, r, A;
        
        for (int i = 0; i <= 1; i++) {
            p = i == 0 ? false : true;
            for (int j = 0; j <= 1; j++) {
                q = j == 0 ? false : true;
                for (int k = 0; k <= 1; k++) {
                    r = k == 0 ? false : true;
                    
                    A = ((p | q) & !(p & q)) == (p ^ q); 
                    System.out.println(p + " " + q + " " + r + " = " + A);
                }
            }
        }
    }
}