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.
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 wellwritten 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.