nie-ii-year

commit 9c80370585ba560640ed71ac2f628466970f9392
parent c6b9e58c6fb7da3d1d0b6cc5f9ac7b4a596db46d
Author: Agastya Chandrakant <acagastya@outlook.com>
Date:   Mon, 16 Apr 2018 20:55:07 +0530

add
Diffstat:
M
s4/fafl/report.md
 | 
10
++++++++--

1 file changed, 8 insertions(+), 2 deletions(-)
diff --git a/s4/fafl/report.md b/s4/fafl/report.md
@@ -30,7 +30,7 @@ function newModulo(u, v) {
 ```
 In the above code, `quo` variable gives the quotient. Noting that repeated subtraction yields remainder, and count of subtraction yields quotient, state transition diagram of a STM with infinite memory (in theory) can be drawn.
 
-__Refer figure for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__
+__Refer figure 1 for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__
 
 ### STM to check if entered natural number is prime or not
 
@@ -43,8 +43,14 @@ Consider a natural number `num`. If it is a composite number, it has atleast one
 
 ### Performance analysis
 #### For calculation of remainder and quotient
-#### To find if the number is prime
 
+#### To find if the number is prime
+For an input `num`, the first step is to make a copy of $\lfloor\dfrac{num}{2}\rfloor$ start reading the tape from the beginning.
+1. For every second `1` encountered, mark it as `D`.
+2. Move right until `B` is found.
+3. Update `B` as `1`.
+4. Move right and add `B` to the array.
+5. Repeat steps 1 - 4 until instruction pointer reaches `0`. The complexity is observed to be $O(n)$.
 ### Output
 #### Result #1
 #### Result #2