Description
Please check all the given vectors at the endDr. Tolga Soyata
© George Mason University, Department of ECE
tsoyata@gmu.edu
ECE445 Computer Organization
Lab7 (4 points)
In this lab, you will be using the QtSpim simulator to write MIPS assembly code and will be testing it.
Submission and grading of this lab will follow the guidelines under
Lab Instructions → ECE445 QtSpim Lab Submission and Grading
Lab7 Description:
Write a MIPS assembly program that asks a user to enter two integer numbers, a and b as follows:
Please enter a (the base):
o Please enter b (the exponent):
o
It calculates its modular exponent in mod 97, i.e.,
•
•
The base (a) must be a number between 1 and 1,000,000 (including 1 and 1,000,000). If the user
enters a number outside this range, print an appropriate error and ask to enter the number again.
There are three types of errors, depending on what the user enters.
If the user enters 0, the error is:
•
If the user enters a negative number, the error is:
•
If the user enters a number greater than 1,000,000, the error is:
•
The exponent (b) must also be a positive number, between 1 and 1000 (1 and 1000 are included).
If the user enters a number outside this range, issue errors identical to the previous errors, with the
exception that the upper value is different (i.e., 1000).
•
If the user enters an a or b that is not accepted, print the error and go back to asking for the number again; do not calculate the result. Only when the user enters both numbers correctly, print the
result as follows (red numbers denote the user entry):
•
The number cannot be zero.
The number cannot be negative.
The number cannot be greater than 1,000,000.
Please enter a (the base): 25870
Please enter b (the exponent): 461
25870 ** 461 mod 97 = 17
Dr. Tolga Soyata
© George Mason University, Department of ECE
tsoyata@gmu.edu
It is very easy to verify this result if you have a computer that has Python installed.
Simply go to the IPython console (Spyder IDE) and
type 25870 ** 461 % 97, you will get 17
The % symbol in Python is “remainder when divided”, which acts as
the mod operator.
You can also put these numbers in variables
a=25870
b=461
r=a**b % 97
Lab7 Implementation Strategy:
If we want to calculate 25870 ** 461 mod 97, it will end up being an enormously large number, which
MIPS will not be able to handle. However, elementary number theory tells us that before even do any computation, we can substantially reduce the magnitude of the first number by calculating its mod 97, in other
words, ≡ . Therefore:
≡ ≡ ( )
≡ ( ) ≡
You see how much the base number collapsed ? This is good news. The story gets better. We can also reduce the exponent’s magnitude substantially by using number theory:
≡ ( ) ≡ ( ) ≡
Attention: to reduce the exponent, we need mod 96, however for the base, we need mod 97.
In other words, calculating 25870**461 mod 97 is the same thing as calculating 68**77 mod 97!
This is the beauty of modular arithmetic in that you can make these initial drastic simplifications and the
numbers you end up with are far more manageable. To summarize, the reduced base number will be between [0…96] since we calculate its mod 97 and the exponent will be between [0…95] due to mod 96. Although these are galaxies smaller than the original numbers, we still have to calculate 68 **77 mod 97. How
can we do this?
Let us yet do another reformulation. When we look at 77 as a binary number, we see that 77=0x4D.
In binary terms, 77 decimal = “0100 1101” binary. Let us write the exponent as a sum of powers of two by
looking at its binary representation. We see that:
Dr. Tolga Soyata
© George Mason University, Department of ECE
tsoyata@gmu.edu
= + + + = + + +
Our goal is to compute 68**77, how does this help us? Check this out:
= ( + + + ) = ( ⋅ ⋅ ⋅ )
Observing that 68**1 and 68**4 can be calculated one after the other, let
=
Once we have the “first power” of 68 on our hand, we can re-write the above computation as follows:
≡ ≡
≡ ≡
≡ ≡
⋯
≡ ⋅ ≡ ( ) ⋅ ( )
To rephrase, we can keep squaring it and continuously apply mod 97 and calculate the next power from a
previously known power of 2. You can apply mod 97 to the base as many times as you want.
For example, if we wanted to compute 68**3, we can multiple x and y and take mod 97.
( ⋅ ⋅ ⋅ ) ≡ ( ) ⋅ ( ) ⋅ ( ) ⋅ ( )
The fact that we take mod 97 at every step continuously keeps the numbers small and does not allow the
multiplication results exceed the range of the MIPS multu instruction.
To write an algorithm that computes this result, simply take the exponent and shift to the right and determine the bits of the exponent. If you see a “1”, you need to multiply by your original x, if not, keep shifting;
in the meantime, keep calculating the next square In other words, you are first calculating x, and x^2, and
x^4, then x^8, … at every step immediately take the resulting value’s mod 97 to avoid numbers getting out
of hand.
Of course, you need to use a few registers to keep track of the exponent vs. what you are shifting now. I
can’t explain more, since I would be giving the result away.
LAB7 GRADING RUBRIC:
• Submit your code along with all of the functions in it as a single file named
Lab7_YourLastName.asm
• Proper error messages
1 point
• Proper user entry and output reporting
1 point
• Correct computations
2 points
Some test vectors are provided on the next page:
Dr. Tolga Soyata
© George Mason University, Department of ECE
Test Vector 1:
Please enter a (the base): 1000000
Please enter b (the exponent): 1000
1000000 ** 1000 mod 97 = 96
Test Vector 2:
Please enter a (the base): 1
Please enter b (the exponent): 1000
1 ** 1000 mod 97 = 1
Test Vector 3:
Please enter a (the base): 456789
Please enter b (the exponent): 862
456789 **862 mod 97 = 36
Test Vector 4:
Please enter a (the base): 999999
Please enter b (the exponent): 999
999999 ** 999 mod 97 = 52
Test Vector 5:
Please enter a (the base): 1000000
Please enter b (the exponent): 1
1000000 ** 1 mod 97 = 27
Test Vector 6:
Please enter a (the base): 85000
Please enter b (the exponent): 770
85000 ** 770 mod 97 = 8
Test Vector 7:
Please enter a (the base): 4096
Please enter b (the exponent): 512
4096 ** 512 mod 97 = 1
Test Vector 8:
Please enter a (the base): 16
Please enter b (the exponent): 16
16 ** 16 mod 97 = 61
Test Vector 9:
Please enter a (the base): 652381
Please enter b (the exponent): 825
652381 ** 825 mod 97 = 52
tsoyata@gmu.edu
Purchase answer to see full
attachment
We offer the bestcustom writing paper services. We have done this question before, we can also do it for you.
Why Choose Us
- 100% non-plagiarized Papers
- 24/7 /365 Service Available
- Affordable Prices
- Any Paper, Urgency, and Subject
- Will complete your papers in 6 hours
- On-time Delivery
- Money-back and Privacy guarantees
- Unlimited Amendments upon request
- Satisfaction guarantee
How it Works
- Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
- Fill in your paper’s requirements in the "PAPER DETAILS" section.
- Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
- Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
- From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.
