2110206 Project 2
S2 calculator
It is a "statistical" calculator with many useful functions.
Besides ordinary + - * / (basic four functions), it has random, x^2,
x^y, x!, mod, gcd, fib, x^2+y^2, sum, average. Surprisingly
it has these additional ten functions!
You are to write these functions, called f0..f9
f0 rng
f1 sq(x)
f2 x!
f3 fib(x)
f4 x^y
f5 x mod y
f6 gcd(x,y)
f7 x^2+y^2 (sum square)
f8 sum(a1..an,n)
f9 average(a1..an,n)
f0 has no argument. f1,f2,f3 have one argument. f4,f5,f6,f7 have two
arguments. f8,f9 have n+1 arguments.
How to use this
calculator
The basic calculator will take a line of input, performs the
computation and outputs the result. The sequence of input is
similar to a conventional four functions calculator. The "keys"
of the calculator consist of:
numeric 0..9
basic functions + - * / =
special functions f0..f9
For example:
>22
+ 33 - 1 =
54
>f0 =
14873
>f1 4 =
16
>f8 1 2 3 =
6
All the calculation will be done as 32-bit integer (no decimal
point). I will implement the calculator and will upload it by the
end of this week. (Friday 9 February 2007).
The definition of
special functions
f0 rng
rng
random number generator
based on linear congruent method
x[i] = (a*x[i-1] + c) mod M
Random number generator by linear congruent method
x_i = (ax_i-1 + c) mod M
generate a random sequence of number (x1...xk) of length M over the
interval [0, M-1]. Starting value x_0 is called "seed". The
coefficients a and c should be chosen very carefully.
Magic value of coefficient for a good RNG. a = 16,807 c = 0
M = 2,147,483,647 (or 0x07fffffff, 31 bits of 1)
(read more on Random Number and Monte Carlo
method from www.physics.odu.edu/~godunov/teaching/notes/CP10_random.pdf
)
The current x is stored at a global variable XRNG at the address
900. The first seed is initialised by the calculator.
The above formula can be written as
x = (16807 * XRNG) mod
2147483647
XRNG = x
return x
The difficulty is how you will put the large number such as 2147483647
into a register. (Hint: break it into two parts and use shift,
or, to join them)
f1 square
sq(x)
return x * x
f2 factorial
fac(x)
if x == 0 return 1
else return n * fac(x-1)
Factorial can be written without recursion as
if x < 1 return 1
f = 1
for(i=1; i<=x; i++)
f = f * i
return f
f3 fibonacci serie
fib(x)
if x < 3 return 1
else return fib(x-1) +
fib(x-2)
Fibonacci serie is 1 1 2 3 5 8 13 21 ... Start with fib(1) = 1
This can be written without recursion as
if x < 3 return 1
f1 = 1
f2 = 1
for(i=3; i<=x; i++)
f3 = f1
+ f2
f1 = f2
f2 = f3
return f3
f4 x power to y
pow(x,y)
if y == 0 return 1
else return x * pow(x,y-1)
This can be written as
p = 1
for(i=1; i<=y; i++)
p = p * x
return p
f5 x mod y
mod(x,y)
return x-((x/y)*y)
f6 x gcd y
gcd(x,y)
if y == 0 return a
else return gcd(y, x mod
y))
This is gcd (greatest common divisor) based on Euclid method. It
is based on a simple fact: gcd(x,y) = gcd(y,(x mod y)). (Prove
it!)
It can be written without recursion as
gcd(x,y)
Euclid method
r = x mod y
while r != 0
x = y
y = r
r = x mod y
return y
f7 sum square
sumsq(x,y)
return (x*x) + (y*y)
f8 sum
sum(a1..an,n) where a1..an
are pushed into the evaluation stack
s = 0
for(i=1; i<=n; i++)
s = s +
pop where pop gets a value from the eval stack
return s
f9 average
average(a1..an,n) where a1..an
are pushed into the evaluation stack
s = 0
for(i=1; i<=n; i++)
s = s +
pop where pop gets a value from the eval stack
s = s / n
return s
The parameters to a function will be passed via the evaluation stack.
The stack pointer of the evaluation stack is r28.
How to write assembly
language for special functions
By convention, the arguments of a function will be pushed on the
evaluation stack (its stack pointer is r27), for example,
fun(1,2,3) will push 1 first then 2 and 3. Your subroutine
will find arguments to the function there. f0..f7 will know how
many arguments. f8 and f9 will be passed an extra number, n, on
top the eval stack to indicate the number of arguments. There is
another stack for you to use for saving/restoring registers, with r31
as the stack pointer.
Usage of registers
r31 stack pointer
r30 do not use
r29 link register
r28 returned value
r27 evaluation stack pointer
Do not use any global variable. Use registers as local
variables. Start your subroutine at address 1000. (The
calculator will relocate it automatically when loaded). See the
following "skeleton" of your program.
.code
1000
:f1 ;;
label your functions
save all registers that
you are going to use
get the arguments
do your work
mv r28 the result
restore all registers
ret r29
Here are the examples how I write the basic four functions.
:fadd
push r31 r1
push r31
r2 ;; save r1 r2
pop r27 r2
pop r27
r1 ;; get arguments from eval stk
add r28 r1 r2
pop r31 r2
pop r31
r1 ;; restore r1 r2
ret r29
:fsub
push r31 r1
push r31 r2
pop r27 r2
pop r27 r1
sub r28 r1 r2
pop r31 r2
pop r31 r1
ret r29
fmul and fdiv are similar to the functions above. The main
"interpreter" loop of the calculator composed of scanning the input
line to get numbers and operators. It pushes all numbers to the
evaluation stack and call the corresponding subroutines of the
operators, then print the result to the screen.
When you are writing and testing your subroutine, you need to write a
unit" test program to try out your subroutine. It must push the
appropriate value to the evaluation stack and then call your
subroutine. You develop your subroutine until it is correct and
then load your fx.obj into the calculator to try it out. Your
object file must be named according to its function number f0.obj
f1.obj ...
The major lesson learn from this project is how to write a part of a
large program. You must be strict to some convention so that all
members of the programming team can co-ordinate their codes and become
successful in running the large program. You learn how to
contribute your part and how to incorporate it into the final program.
How to write the unit
test
Assuming your subroutine is f1. It needs one argument.
;;
unit test for function f1
.code 0
mv r27 #2000
;; set eval stk to 2000
mv r31 #3000
;; set stk to 3000
mv r1 #20
push r27 r1
jal r29
f0 ;; call your subroutine
mv r30 r27
trap
1 ;; display the ret
value
trap 0
.code
1000 ;; start at ads 1000
:f1
your code
ret r29
.end
How to run the
calculator
Start the calculator. It has four basic functions, try them.
c:>cal
>1 + 2 =
3
load your special function object code using "ld" the object
file, for example f1 (the square)
>ld
f1.obj
>f1 20 =
400
>
You can load as many function as you like (so you can try out your
friend's function as well). The calculator knows only
f0..f9. It will link correctly with these objects.
Assignment of project
Each student will do one function. The number of function f0..f9
will be assigned to students by student_id mod 10. In other word, your
five digits ID, takes the last digit (0..9), it is the number of
function assigned to you.
How to submit your
report
Please write the subroutine, test it and make sure it is correct.
Try it with the calculator. I will post all the correct functions
on the web so other can try them. Your report must include the
following.
1 Pseudo code, how you write your subroutine (at high level)
2 register assignment
3 your S2 assembly code for the subroutine
4 your unit test program
5 the result of trying your function on the calculator
Please submit your report and attach the object file via email to this
address: asm2110206 at hotmail dot
com Iin the title, show your id.
number so that I know whose submission it is. I will
acknowledge all the submission so that you know your submission reach
me.
Deadline
The deadline for the project 2 is Monday 19 February 2007 at 4pm.
Suggestion
Can any body write a javascript to be GUI for this project?
last update 7 Feb 2007