Big Number Integer Arithmetic

revised May 2006

1 Introduction

1.1 Resources Required

A PC type computer and the freely available Tcl interpreter are required. A small slow computer is adequate for this project for a small group of students. Any of the UNIX, Windows or Mac OS's can be used and the product will port and run on all these systems.

1.2 Prerequisite knowledge

The students should already be familiar with the basic concepts of Tcl. They should be familiar with the basics of integer arithmetic and have The Art of Computer Programming Vol. 3 - Seminumerical Algorithms. Copies of Section 4.3.1 should be made available.

2 Lesson 1 - Design the Integer Format and Procedures

Consider the way that the integer is going to held in some "normal" form. A normal form means that if a and b are in normal form then a != b means the integer value of a is not the same as the integer value of b. Another way to define normal form is to have a normal function which is a good idea anyway. If a and b are any two valid integers then normal(a)=normal(b) iff the integer value of a = the integer value of b. Possibilities are the obvious simple string of digits with optional - in front. But other options are a product of factors, and Knuth suggests some other ways of managing large integers.

You can also look at the ::math::bignum library in Tcllib and decide for yourself if this is an adequate provision. Of course you can look at the Tcl code used in the ::math::bignum procedures in the ActiveState distribution, by using for instance:

[info body ::math::bignum::add]

Note that ::math::bignum may not be available in your plugin distribution.

3 Lesson 2 - Addition and Subtraction

Write the procedures for addition and subtraction. Look at making addition accept more than two arguments. Does this make things easier or more complicated? Consider alternative algorithms. Cutting the integers into chunks the size of a computer word and adding these components, or perhaps dividing the integers into halves recursively until chunks the size of computer words are reached. Which method is used by ::math::bignum ?

4 Lesson 3 - Multiplication

Write the procedures for muliplication.

5 Lesson 4 - Division

Write the procedures for division. Division will require some careful study of Knuth as it uses a heuristic algorithm. There is no simple formula. Students may discover why they had difficulty learning long division when they try this part of the project.

6 Lesson 5 - Application

Now that we have these procedures we need to place in a context where they are readily accessible. There are two possibilities here.

Put them into a calculator like the simple calculator but with some extract functions pertinent to large integers. This is done most simply by writing a general binary_operation procedure that adds, mulitplies, etc two large integers. Then slotting this single general procedure into the right places in the calculator. If the calculator was well-written in the first place this should happen automatically.
Another option is to write a Tcl [integer] procedure that evaluates arithmetic expressions. We define a syntax for expressions based solely on integers. We write an expression parser and attach the arithmetic procedures to it. This creates a single [integer] commmand in Tcl. This part of the project is about something quite different. Computer language constructs and programming. It is an excellent introduction to this topic.

expr ::= phrase | simple

sub_item ::= phrase "-" phrase

phrase ::=  "(" simple ")"
simple ::= mult | div | mod | sum | add
list ::= sub_list | add_list | mult_list
mult ::= atom "*" atom
div ::= atom "/" atom
mult_list ::= mult | div | mult_list "*" atom 
mod ::= atom "%" atom
sum_phrase ::= sum | sum_list | sum_list sub_tail | sub | sub sub_tail
sum ::= atom "+" atom
sum_list ::= sum | sum_list "+" atom
sub ::= atom "-" atom
sub_list ::= sub | sub_list "-" atom
sub_tail ::= "-" atom | sub_tail "-" atom
atom ::= number | phrase

7 Lesson 6 - Extension to Quotient Arithmetic

It is a small jump from big number integer arithmetic to quotient arithmetic. The normal form of a quotient is typically an integer plus a proper fraction. This is three numbers which can all be abitrarily huge. Addition, subtraction and multiplication will be achieved by combinations of the integer procedures already written. Division may require some extra work. Take care with the signs of the various parts. Again design a "normal form" which is easy to use and apply.

©2000 - 2006 WEBSCOOL This page last updated 20 May 2006. All rights reserved - including copying or distribution of any portion of this document in any form or on any medium without authorisation. For more regarding the copyright.