Programming Project 3

Due date: Thu 3/6 11:00 pm

Introduction

In this assignment you will implement functions to handle addition and multiplication of arbitrary size integers in ML. We will call these big integers. To simplify matters you may assume that the numbers are greater or equal to 1. These operations (and others) for long integers are needed for various applications, for example encryption and decryption with the RSA system.

You should represent a big integer as list of integers where each element of the list represents one digit. It is convenient to represent the integer lists reversed. Thus 123 should be represented by the list [3,2,1]. (Of course we could use a larger base for a digit to save space and time but for simplicity and uniformity of projects we ask you to use base 10 as in the example.)

Your Task

You should implement the following 4 functions where t stands for int list

fromInt: int -> t;
toString: t -> string;
plus: t * t -> t;
mult: t * t -> t;

fromInt takes an integer and converts it into the int list representation. toString takes an int list representing a number and returns a string representation of the number in correct order. So for the number above the string ``123'' should be returned (this will basically be our mechanism to check your results.)

The functions plus and mult perform addition and multiplication on integers in this format. You should use the standard ``school algorithms'' for these functions. Thus plus should add the numbers digit by digit passing carry as needed. The function mult should multiply the first number by the digits of the second and add them, as in

      1 2 3
        2 5
    --------
      6 1 5
    2 4 6
    --------
    3 0 7 5
You must use this algorithm or an algorithm that is at least as fast as this one. Slow implementations that multiply, e.g. a x b by adding a to a sum b times are not acceptable.

Here are two examples of using your functions. The code

val a = fromInt(123);
val b = fromInt(25);
val c = mult(a,b);
val d = toString(c);
produces the following response:
val a = [3,2,1] : int list
val b = [5,2] : int list
val c = [5,7,0,3] : int list
val d = "3075" : string
and the code:
val a = fromInt(1234567);
val b = fromInt(654321);
val c = mult(a,b);
val d = mult(c,c);
val e = toString(d);
produces the following response:
val a = [7,6,5,4,3,2,1] : int list
val b = [1,2,3,4,5,6] : int list
val c = [7,0,0,4,1,1,3,0,8,7,0,8] : int list
val d = [9,4,0,6,9,5,9,3,2,6,0,4,...] : int list
val e = "652545870999406239596049" : string

Summary of Requirements

  1. Implement all 4 functions as described above. You may use as many ``helper functions'' as you need.
  2. Use an accumulator in at least one of these functions.
  3. Put all your code including your functions and at least 2 example runs (different from the above) in a file pp3.sml. Make sure that the code in pp3.sml runs smoothly in the system (that is, no errors should occur if we try sml < pp3.sml).
  4. Make sure that your code is easily readable and well documented. The grade will be based both on correctness and on readability.

Submitting your program

Assuming your code is in the current directory on one of the local Sun machines, you should submit by typing provide comp80 pp3 pp3.sml.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation -no_images -dir TEMPHTML pp3.tex

The translation was initiated by Roni Khardon on 2008-02-25


Roni Khardon 2008-02-25