Programming Languages
Lisp Programming Project
Due Monday, October 22nd, 5:00 p.m.
Arbitrary Precision Real Numbers
For our lisp project, we will be manipulating arbitrary precision real numbers. Since lisp does not handle real numbers (lisp uses rational numbers instead) we will be using lists to represent real numbers. We will represent a real number as a list of digits, containing exactly one decimal point. Each digit can be in the range 0-9, and we will use the atom 'pt' to represent the decimal point. Consider the following examples:
Number Representation
34291.0 (3 4 2 9 1 pt 0)
22.560 (2 2 pt 5 6 0)
3.14159 (3 pt 1 4 1 5 9)
984. (9 8 4 pt)
All valid numbers must contain exactly one decimal point. Thus, (3 4 5) is not a legal representation of a number.
The Assignment
Your assignment is to write functions that will add, subtract, and multiply arbitrary precision real numbers, using the above list-based number representation. You are allowed (but not required) to have leading zeroes or trailing zeroes in your results. If you subtract a larger number from a smaller number, the result should be zero.
Examples:
(add ‘(3 2 pt 4) '(5 1 pt 2)) ==> (8 3 pt 6) ; 32.4 + 51.2 = 83.6
(add ‘(9 9 9 pt 9) '(0 pt 1)) ==> (1 0 0 0 pt 0) ; 999.9 + 0.1 = 1000.0
(subtract ‘(5 1 pt 4) '(2 0 pt 2)) ==> (3 1 pt 2) ; 51.4 – 20.2 = 31.2
(subtract ‘(1 0 0 0 pt) '(9 9 9 pt)) ==> (0 0 0 1 pt) ; 1000. – 999. = 1.
(subtract ‘(3 2 pt) '(5 4 pt)) ==> ((0 pt) ; 32. – 54. = 0 no negatives!
(multiply ‘((1 0 pt)) '(3 pt 4)) ==> ((3 4 pt 0) ; 10. * 3.4 = 34.0
(multiply ‘(3 pt 4) (5 1 pt 9) ==> (1 7 6 pt 4 6) ; 3.4 * 51.9 = 176.46
In addition to the four above functions, you will need to write several other helper functions. Remember, good program decomposition makes you life easier!
Programming Restrictions
· Your are required to write this program using "pure functional lisp". In other words, you are not allowed to use any programming construct that does not appear in this handout or the lisp handout unless you clear it with me first. When in doubt, ask!
· You should not assume that the built in representation allows arbitrarily large integers. If your code is executed on a lisp interpreter that stores numbers as simple integers, your code should still work for all possible lists. Therefore, converting the list representation of arbitrary precision reals into a built-in representation, doing your calculations, and then converting back is not acceptable. Be careful! Be sure that your code does not require arbitrarily large built-in numbers in any of your functions.
Adding Reals
Remember back when you first learned how to add two large numbers together? First, add the least-significant digits to get the least-significant digit of the answer, then add then next least significant digit (with a possible carry) and so on. Thus to add 947.01 and 95.12, we would do something like:
1110 0 <- carry bits
947.01
95.12
------
1042.13
Our list representation of numbers is most-significant digit – least-significant digit, which is inconvenient for adding. What can we do? Reverse the numbers we want to add (to get them into least-significant to most-significant order), do the addition, and then reverse the result back again. What about adding numbers with different numbers of digits to the right of the decimal, like 143.132 and 61.4 ? We need to line up the decimal point – which is easily done by padding one of the numbers with zeroes:
143.132
64.400
-------
207.532
Multiplying Reals
Recall how to multiply two long numbers together by hand:
1423
492
----
2846
128070
569200
------
800016
Your multiply code will work in much the same way. You will need to write a function that multiplies a single digit and a sequence of digits, and use this function repeatedly (along with an add function) to get the final result. How can we deal with the decimal point? Ignore it while doing the multiplication, then add it back in. Thus, to multiply 14.23 and .492, first multiply 1423 and 492 to get 800016, and then add the decimal point 5 spaces from the end to get 8.00016
Extra lisp functions
The following built-in functions should help you write your functions:
(reverse lst) ; returns the reverse of lst. So (reverse '(1 2 3 4)) ==> (4 3 2 1)
(mod x y) ; remainder of (/ x y). Same as (rem x y) when using positive numbers
(floor x) ; returns the truncated value of x. If you type something like
; > floor (/ 3 2))
; then the interpreter will spit back
; 1 ; 1/2
; Don’t worry about the 1/2, it will be ignored. So,
; > (+ (floor (/ 3 2) 0)
; will just return a simple 1
So you can easily define a function div to do integer division:
; div takes two integers a and b as input, and returns the truncated result of dividing a by b
(defun div (a b)
(floor (/ a b))
A Few Hints
· Adding can be a pain when the numbers are represented from most-significant to least-significant digit. Consider reversing the numbers, doing your calculations, and then reversing the result
· Adding can also be a pain when the numbers don't have the same number of digits to the right of the decimal. Consider padding one of the numbers with zeroes.
· It is probably easier when multiplying two numbers to ignore the decimal point, and multiply the numbers as if neither had a fractional part. Then, go back and add in the decimal point to the correct location
· Good functional decomposition will make your life much easier. Break the problem into smaller, more manageable chunks, and solve (and test!) those smaller problems before going on.
What to turn in
· A hardcopy of your source code is due by 5:00 p.m. on Monday, October 22nd. Be sure to add comments to all of your functions, telling what each of the input parameters are, and what the function returns. I should be able to use any of your functions after looking only at the introductory comment! You do not need to turn in any sample output for this program.
· A electronic copy, copied to the submit folder for the class. The filename for your electronic submission should be "prog2.lsp". Use that exact filename, so that my automatic grading system will work. Do not use subfolders, and make sure permissions are set correctly. If you use a different filename, a subfolder, or have the permissions set incorrectly, I will take off points!
Extra Credit
You can receive up to 20 extra credit points for expanding your code to:
· Handle negative numbers. A negative number will be signified by the atom neg at the front of the list. So, -45.0 would be represented as (neg 4 5 pt 0). All of your functions should work with negative numbers, so (add '(neg 5 pt) '(2 pt)) should return (neg 3 pt), and '(multiply '(neg 1 pt) '(neg 1 pt)) should return (1 pt). Note that (neg neg 1 pt) is not a valid number!
· Add the division function (divide num1 num2). This one is pretty tough. There are several interesting issues (like how many digits to include in (divide '(1 pt 0) '(3 pt 0)). I'd be happy to discuss strategies for getting divide to work properly – come by my office if you are interested in doing this portion of the extra credit.