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.