The goal of this assignment was to write RISC-V code from scratch for several common loop (primality check) and recursive (calculating fibonacci numbers) questions.

Primality check-----------------------------

(Check primality.s) The code will return true for prime numbers and false for the composite numbers as well as 1 (which is neither prime nor composite) and 0.

Time complexity: O(sqrt(n)) Runs upto the highest posiible 32 bit number (2147483647).

KEYPOINT: While checking whether x=sqrt(n) is reached or not, we kept increasing x and checked if x^2 exceeds n or not. However, in case x is between 46340^2 and 2^32, it will check until x=46340, which will cause overflow since 46341^2 is not a 32 bit number (signed). Which causes the program to run indefinitely. Hence we had to limit x to 46340.

edge cases: 0 1 2 4 (to check the sq root condition)

large prime numbers upto 32 bit: 65521 (16 bit prime number) 5000011 50000017 200000033 500000003 1000000007 2000000011 2100000011 2140000007 2147000041 2147480009 2147483029 2147483629 2147483647 (aka the Mersenne Prime, largest possible prime for 32 bit checking)

large composite numbers: square of prime numbers upto 46340 17648401 (42014201) 25030009 (50035003) 100140049 (1000710007) 2143782601 (4630146301) 1906806889 (46337*46337)

fibonacci using recurrsion (without memoisation)------------------------------------:

base cases: fib(0) fib(1)

Time complexity: Exponential (verified by stress testing across various testcases below, the time for which rise exponentially).

Time taken accross various test cases in fast execution mode of RIPES i.e without updating UI : fib(10) fib(15) fib(20) fib(25) (33 secs) fib(26) (50 secs) fib(27) (1 min and 28 secs ) fib(28) (2 min and 16 secs) fib(29) (4 min and 14 secs) fib(30) (~10 mins)

We can see why this is inefficient. To caculate every fibonacci number, n, we are calculating fib(n-1) and fib(n-2) from scratch which is clearly not efficient as we are repeating several calculations, multiple times. Also, every fib calls 2 other fibs, which is the reason for the exponential time complexity.

Fibonacci using memoisation---------------------------------------------------:

base cases: fib(0) fib(1) fib(2)

Time complexity: O(n). Once we calculate a particular fib(n) we store it in memory, and reuse it when needed.

Time taken accross various test cases in fast execution mode of RIPES i.e without updating UI : fib(25) ran within a sec fib(30) ran within a sec fib(35) ran within a sec fib(40) ran within a sec fib(45) ran within a sec fib(46) ran within a sec fib(46) is the highest possible n for which it can be calculated because beyond that the fib(n)s exceed the 32 bits. fib(n) where n>46 gives fib(n) mod 2^(32) (unsigned) as expected (checked till n=60) The time taken doesn't rise significantly. We checked the linear time by testing under 1ms clock cycle in ripes, Time taken across vairous test cases in 1ms clock cycle in RIPES: fib(10) 7.3 sec fib(20) 14.71 sec fib(30) 22 sec This clearly shows the O(n) time complexity for calculating fib(n) using memoization.