Arbitrary-precision Integer Calculators

Important Note: The software posted on this page is for demonstration purposes only. Although the author is unaware of any bugs, the software has undergone very little testing. In particular, the algorithms performing aribitrary-precision arithmetic in the LargeInteger class are quite complicated, and hence error-prone.

Exhibit 1: An arbitrary-precision integer calculator using EDU.ksu.cis.calculator.LargeInteger.

Exhibit 2:An arbitrary-precision integer calculator using java.math.BigInteger.

Assuming the applets are running correctly, the two calculators above will appear to be identical. If you browser won't run them, you may want to download the program and run it as an application.

The two calculators are, in fact, functionally very nearly the same. However, the calculator on the left uses an arbitrary-precision integer arithmetic written by Rod Howell, the author of this page, whereas the one on the right uses the java.math.BigInteger library written by Josh Bloch and Michael McCloskey of Sun Microsystems, Inc. They are posted here so that you may compare their performance (see below for a user's guide). I have found that computing 2^200,000 is sufficient to demonstrate the difference in performance. You may need to adjust the value of the exponent depending on how fast your machine is.

So is this a fair comparison of the two arbitrary-precision integer libraries? In a word, no. To see why, take a look at my comparison of the two libraries.

User's Guide

We describe here the operation of the above applets. We then describe how to run the program as an application.

Both calculators use RPN (Reverse Polish Notation) data entry. The computational model is stack-based, with operations taking their arguments from the top of the stack and replacing them with their results. The value in the display is always the value at the top of the stack. The size of the stack is bounded only by the available memory.

Data entry

Data may be entered using the ten buttons labeled with digits, and/or the keyboard. Data may be copied from the system clipboard using the "Paste" operation as defined by the system look-and-feel (Ctrl-V on Windows). The text caret may be moved with the mouse, the cursor arrow keys, and/or the "Home" and "End" keys. "Backspace", "Delete", and/or the "Cut" operation (Ctrl-X on Windows) may be used to correct typing errors. Valid characters depend upon the value of the Base: if the base has value b, the first b of the following characters are valid digits:

0123456789abcdefghijklmnopqrstuvwxyz

In addition, "-" may be inserted as the first character. Valid digits may be inserted anywhere except to the left of a "-". Invalid characters are ignored, no matter how they are entered. Upper-case letters are automatically translated to their lower-case equivalents.

Operations

Operations may be entered only by pressing a button other than a digit or by selecting a different value in the "Base" menu. Entering an operation terminates the entry of any data to be used for that (or a subsequent) operation. Thus, whatever is in the display at the time the operation is entered is at the top of the stack if and when the operation attempts to acquire data from the stack. If a single "-" has been entered, or if digits have been entered but subsequently deleted, the value at the top of the stack is taken to be 0. If the operation requires more operands than are present on the stack, a "Stack Underflow" error occurs. Note that an empty display may indicate one of two possibilities: either the stack is empty (as occurs initially or after a "CS" operation has been performed) or data has been entered and deleted, resulting in a 0.

Individual operations are as follows:

Base menu - Selecting a new value causes any data in the display to be converted to the new base. If the stack is empty, no error is reported. In either case, subsequent data are interpreted in this new base.
CS - Empties the stack, including the display.
Up - Navigates up the stack by removing the bottom element and placing it on top, so that it appears in the display.
Down - Navigates down the stack by removing the top element and placing it on the bottom.
Rem - Divides the second element by the top element and replaces them by the remainder of the division.
x^y - Raises the second element to the power of the top element and replaces them by the result.
2^x - Raises 2 to the power of the top element and replaces that element by the result.
10^x - Raises 10 to the power of the top element and replaces that element by the result.
/ - Divides the second element by the top element and replaces them by the result of the division.
* - Multiplies the top two elements and replaces them by the result.
- - Subtracts the top element from the second element and replaces them by the result.
+ - Adds the top two elements and replaces them by the result.
+/- - Replaces the top element by its negation.
Pop - Removes the top element.
Enter - If nothing has been input since the completion of the last operation, a copy of the top element is placed on the top of the stack; otherwise, the input is simply terminated (to facilitate entry of a new data item).

Displayed Results

After a result has been displayed, it may not be edited directly. Any attempt to delete characters from it is ignored. Any valid characters inserted will replace the entire result in the display; the value will be retained as the second element on the stack. Editing of computed results may be accomplished by first selecting the entire result (Ctrl-A on Windows), then copying and pasting it (Ctrl-C Ctrl-V on Windows). This has the effect of inserting an editable copy into the display, above the original on the stack.

Sticky Bases

Below the display, to the right of the Base Menu, is a checkbox labeled, "Sticky". If this option is checked (the default), values in the display will always be shown in the most recently selected base. Otherwise, each value will be displayed in the base in which it was originally entered or computed, and the Base menu will automatically be updated to reflect the current base.

Note: In the calculator using the java.math.BigInteger class, bases are always sticky; unchecking this option has no effect.

Errors

When an error occurs, a message will be displayed in a dialog box and the stack will be restored to its contents prior to the offending operation. The following messages may occur:

Stack Underflow - An operation required more data items than were present on the stack.
Invalid Operand - An attempt was made to divide by 0 or use a negative exponent.
Insufficient Memory for Operation - The Java Virtual Machine does not have enough memory available to perform the operation.

Any other messages probably indicate bugs in the program.

Example

Given a Mersenne prime p (i.e., a prime number of the form 2ⁿ-1), a perfect number can be computed by p(p+1)/2. We can express this in terms of n as (2^n-1)(2ⁿ-1). For example, 2³¹-1 is a Mersenne prime. We may compute the perfect number (2^31-1)(2³¹-1) with the following series of keystrokes:

31 [Enter] 1 [-] [2^x] [Enter] [Enter] [+] 1 [-] [*]

Thus, n = 31 is first pushed onto the stack, followed by 1. The difference is then computed (n-1). Then 2^n-1 is computed, and two more copies are pushed onto the stack; thus, the stack then contains three copies of 2^n-1. The top two of these are added and replaced by their sum, 2ⁿ. 1 is then pushed, then 2ⁿ is replaced by 2ⁿ-1. Finally, 2^n-1 and 2ⁿ-1 are replaced by their product, (2^n-1)(2ⁿ-1).

If you are patient and/or have a reasonably fast machine, you might try computing the 37th even perfect number by using n = 3021377.

Downloading and Running the Program

There are two main ways to download and run the program as a stand-alone application. The preferred method is to use Java^TM Web Start. If you have Java Web Start installed, downloading and running the calculator is as simple as clicking on a link. This is a much safer way of running downloaded applications, because they are run in a "sandbox" with restricted access to your system resources. After the program has been run the first time, it may be launched from the Web Start Application Manager, even if you are offline. Before running the program, Web Start will attempt to see if an update is available, and if so, will automatically load it. This way, you can always have the most up-to-date version of the program.

Alternatively, you can manually download the program. The program can then be run from a command prompt (or by double-clicking its icon in Windows). Running the program in this way is more dangerous, because there is no "sandbox" in which the program runs. As the author of the program, I claim that it does not access any local or network files; it does, however, access the system clipboard.

Using Java^TM Web Start

To launch the calculator, click one of the following links:

Calculator using EDU.ksu.cis.calculator.LargeInteger (shown on the left above)
Calculator using java.math.BigInteger (shown on the right above)

When running under Web Start, the program has restricted access to the system clipboard. In particular, it can no longer be accessed via the standard keyboard shortcuts (i.e., Ctrl-X, Ctrl-C, and Ctrl-V in Windows). In order to provide access to the system clipboard, a popup menu has been attached to the calculator's display. This popup menu is accessed via the mouse in a way defined by the particular system look-and-feel (right-click on most systems, including Windows). This menu contains "Cut", "Copy", and "Paste" entries, which provide access to the system clipboard in a controlled way. Specifically, when you try to access the clipboard via one of these menu items, Web Start will display a warning and ask you to confirm. You then have the option to disable this warning, but it will appear on any program execution the first time you try to write to the clipboard and the first time you try to read the clipboard. This mechanism is in place to protect you from accidentally losing or sharing information in your system clipboard by running a program you've downloaded. Because new versions are automatically downloaded, any time you run the program you are potentially downloading and running a new program.

Manual Download

The entire program is found in the file, calculator.jar. If this file is downloaded, it may be run simply by double-clicking on its icon in windows, or by issuing the command

java -jar calculator.jar

on any operating system on which the Java runtime, version 1.3 or later, is installed.

When the program is run in this way, the user interface is slightly different. An "Edit" menu with "Select All", "Cut", "Copy", and "Paste" entries is present, and the "Sticky" checkbox is in a menu called "Options". The purpose of the "Edit" menu is to provide a uniform mechanism for accessing the system clipboard across platforms. However, these menu items actually result in inconsistent behavior on the various platforms. The interface described above is therefore preferred.

To use the interface described above, or to use the calculator model based on java.math.BigInteger, one or two command-line arguments must be supplied to the java command given above.

java -jar calculator.jar ModelLocation

will run the calculator using the calculator model defined by ModelLocation, which must be a package name terminated by a period. The currently-implemented possibilities are:

EDU.ksu.cis.calculator.defaultmodel. - An RPN calculator using our LargeInteger class. This is the default.
EDU.ksu.cis.calculator.javamodel. - An RPN calculator using Sun's BigInteger class.

java -jar calculator.jar ModelLocation UIName

will run the calculator using the calculator model defined by ModelLocation (described above) and the user interface defined by UIName, which must be a Java class implementing EDU.ksu.cis.calculator.CalculatorUI. The currently-implemented possibilities are:

EDU.ksu.cis.calculator.DefaultUI - The user interface with "Edit" and "Options" menus. This is the default.
EDU.ksu.cis.calculator.JNLPCompatibleUI - The user interface used by the applets above. This is the same as the user interface used when run under Web Start, except that there is no popup menu on the display.

Bug Reports

Please send any bug reports to Rod Howell. Please include the following information:

The operating system you are running under (e.g., Windows 98).
Whether you were running the program as an applet or a stand-alone application.
If you were running the program as an applet, which browser you were using (e.g., Internet Explorer).
If you were running the program as a stand-alone application, the version of Java you were using and any command-line arguments (if applicable). You can obtain the version information by entering
```
java -version
```
from the command-line.
A description of the erroneous behavior with enough details so that I can reproduce it.

Related Materials

Last updated January 15, 2003.

Rod Howell (howell@cis.ksu.edu)

Java and all Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the U.S. and other countries.