• It should be an Assembly program, written entirely from scratch by you,
satisfying the requirements specified below.
• It is very important that you write easily readable, well-designed, and fully
commented code [You must organize your code using procedures].
• Use the MARS emulator to run your code. MARS homepage:
• Work in a group of at most three students.
• Submit your project (code) on Ritaj as a reply to this message.
• The discussion of the project will be on the copy sent on Ritaj
Square-Root Implementation & Performance Comparisons Square root operation is considered difficult to implement in hardware, in this project, you must Write and test a MIPS assembly language program to implement three algorithms of an 8-bit integer square root.
Background: In mathematics, a square root (√) of a number x is a number r such that r 2 = x, or, in other words, a number r whose square (the result of multiplying the number by itself, or r × r) is x. Some of the algorithms for calculating square roots of a positive Integer number N are shown below:
- Newton Raphson Method The Newton Raphson method was first used in Gray-
- The iterative method starts with an initial (guess) value and improves the accuracy of the result with each iteration. Assuming that X the original number the iterative equation for calculating the reciprocal of its square root is:
Yi+1 = Yi (3 – X (Yi)^2)
Once Y has been calculated, one can get the square root by multiplying with X. This algorithm has quadratic convergence. In each iteration multiplications and additions or subtractions are needed. In order to speed up the multiplier, there must be a special an algorithm such as the Wallace tree to get the partial production and use a carry propagate adder to get the production, because the multiplier requires a rather large number of gates counts, it is not so practical to place many multipliers on FPGA. Also, it is hard to get an exact remainder of the square root. The Radix-2 SRT-Redundant and Non-Redundant Algorithm The Radix-2 SRT-Redundant and Non-Redundant methods are similar. Since them, both based on recursive relation. In each iteration, they will be one digit shift left and addition. The determination of a function is rather complex, especially for a high radix SRT algorithm. The implantations are not capable of accepting a square root on every clock cycle. Also notice that these two methods may generate a wrong resulting value at the last digit position.
- The Non-Restoring Algorithm The operation at each iteration is simple: addition or subtraction based on the result bit generated in the previous iteration. The remainder of the addition or subtraction is fed via registers to the next iteration directly even it is negative. At the last iteration, if the remainder is non-negative, it is a precise remainder. Otherwise, we can obtain a precise remainder by an addition operation.