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 2200,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:

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:

Any other messages probably indicate bugs in the program.

Example

Given a Mersenne prime p (i.e., a prime number of the form 2n-1), a perfect number can be computed by p(p+1)/2. We can express this in terms of n as (2n-1)(2n-1). For example, 231-1 is a Mersenne prime. We may compute the perfect number (231-1)(231-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 2n-1 is computed, and two more copies are pushed onto the stack; thus, the stack then contains three copies of 2n-1. The top two of these are added and replaced by their sum, 2n. 1 is then pushed, then 2n is replaced by 2n-1. Finally, 2n-1 and 2n-1 are replaced by their product, (2n-1)(2n-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

As long as you have the JavaTM SE Runtime Environment (which can be downloaded from the Oracle® Software Downloads page) installed, there are two ways to install the program:
  1. The simplest way to install the program on your machine is to click one of the following links: When running the program in this way, the program has restricted access to the system clipboard. In particular, it can no longer be accessed via the standard keyboard shortcuts. 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 system). 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, a warning will be displayed asking 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.
  2. If you wish to install the program manually, first download calculator.jar. If this file is downloaded, it may be run simply by double-clicking on its icon in most operating systems, or by issuing the command
    java -jar calculator.jar
    
    on any operating system on which the JavaTM runtime 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:
    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:

Bug Reports

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

Related Materials


Copyright © Rod Howell, 2001, 2002. All rights reserved.


Last updated November 25, 2010.

Rod Howell (howell@cis.ksu.edu)


Oracle and Java are registered trademarks of Oracle and/or its affiliates. Other names may be trademarks of their respective owners.