Due date: Thu 3/6 11:00 pm
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.)
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 5You 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" : stringand 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
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.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)
Copyright © 1993, 1994, 1995, 1996,
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