commit 4e6b08aa750d2c791662e84fb8f2fb382d5b3824
parent 9c80370585ba560640ed71ac2f628466970f9392
Author: Agastya Chandrakant <acagastya@outlook.com>
Date: Mon, 16 Apr 2018 21:07:37 +0530
add
Diffstat:
1 file changed, 12 insertions(+), 1 deletion(-)
diff --git a/s4/fafl/report.md b/s4/fafl/report.md
@@ -34,7 +34,9 @@ __Refer figure 1 for TM1 which acts as a transducer to find remainder and quotie
### STM to check if entered natural number is prime or not
-Consider a natural number `num`. If it is a composite number, it has atleast one factor between two and $\frac{num}{2}$
+Consider a natural number `num`. If it is a composite number, it has atleast one factor between two and $\frac{num}{2}$, boh inclusive.
+
+__Refer figure 2 for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__
### Source code
```
@@ -45,12 +47,21 @@ Consider a natural number `num`. If it is a composite number, it has atleast one
#### For calculation of remainder and quotient
#### 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)$.
+
+Let the number copied towards the right-had side be called `div`.
+
+1. Now, to compute modulo, follow the procedure described in the previous section, perform `num % div`. If result of modulo is zero, stop. The number is not prime.
+2. If the result of modulo was not zero, drcement `div` by one, which takes linear time (traversing till the end of tape, marking it as `B`, and coming back). Repeat the above step till `div` is greater than one. If `div` becomes one, `num` is prime.
+
+The worst case is if `num` was a prime number. In that case, modulo has to be calculated from $\lfloor\dfrac{num}{2}\rfloor$ down to two, both inclusive. And computation of modulo is also of linear order of growth (as mentioned in the previous section, $O(u + v)$). Hence, overall time complexity of the machine to declare weather the given number is prime or not takes $O(n^2)$.
+
### Output
#### Result #1
#### Result #2
