commit 0b5f58496174b3033311558e8530bebeb1c74bb7
parent 4e3383ad67d75a58eb4c5f483451c21c25ecbd75
Author: Agastya Chandrakant <acagastya@outlook.com>
Date: Mon, 16 Apr 2018 22:29:56 +0530
add
Diffstat:
1 file changed, 4 insertions(+), 1 deletion(-)
diff --git a/s4/fafl/report.md b/s4/fafl/report.md
@@ -63,6 +63,9 @@ __Refer figure 2 for TM1 which acts as a transducer to find remainder and quotie
#### For calculation of remainder and quotient
+Consider two numbers `a` and `b`, given that `a > b`, to perform `a - b`, keep decrementing `b` by one and `a` by one till `b` becomes `0`.
+Implementing this in STM subtracting `1` from a number takes linear time; subtracting `b` from the number takes $O(ab)$.
+
Since calculation of modulo is subtracion of `v` from `u` until `u` is strictly smaller than `v`, procedure to obtain modulo by repeated subtraction, ie `u - v` is as follows: (__Assumption: Instruction pointer points to index 1__)
1. While current cell value is not `0`, move right.
@@ -98,7 +101,7 @@ 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)$.
+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(uv)$). Hence, overall time complexity of the machine to declare weather the given number is prime or not takes $O(n^3)$.
### Output
#### Result #1
