commit4c7890b0094f81212c5452def5bcc4757851583cparent6bda1c6ae43e82ec17a83cbdba0d90505e4fecb0Author:Agastya Chandrakant <acagastya@outlook.com>Date:Tue, 17 Apr 2018 10:41:28 +0530 addDiffstat:

M | s4/fafl/report.md | | | 18 | +++++++++--------- |

1 file changed, 9 insertions(+), 9 deletions(-)diff --git a/s4/fafl/report.md b/s4/fafl/report.md@@ -36,7 +36,7 @@ __Refer figure 1 for TM1 which acts as a transducer to find remainder and quotie Consider a natural number `num`. If it is a composite number, it has atleast one factor between two and $\frac{num}{2}$, both inclusive. -What the TM is doing can be summed up in the following JavaScript code snippet: +What the STM is doing can be summed up in the following JavaScript code snippet: ``` function checkPrime(num) { var div = Math.floor(num/2); @@ -50,7 +50,7 @@ function checkPrime(num) { return 1; } ``` -The above code requires modulo function, which is defined in the above secion, and the steps are provided in the Performance analysis section. A state transition diagram for the above logic can be drawn. +The above code requires modulo function, which is defined in the above secion, and the steps are provided in the Analysis section. A state transition diagram for the above logic can be drawn. __Refer figure 2 for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__ @@ -59,12 +59,12 @@ __Refer figure 2 for TM1 which acts as a transducer to find remainder and quotie // to be added tomorrow ``` -### Performance analysis +### Analysis #### 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)$. +Implementing this in STM subtracting `1` from a number takes linear time. 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__) @@ -84,7 +84,7 @@ Since calculation of modulo is subtracion of `v` from `u` until `u` is strictly - Move right until current cell is `X`. - Make current cell as `1`. - Goto right until current cell is `B`. - - Make `B` as `1`. Repeat these four sub-steps until instruction pointer reaches `B` on the right hand side. + - Make `B` as `1`. Repeat these four sub-steps until instruction pointer reaches `B` on the right hand side (or in other words, all `X` has been converted to `1`). To find quotient, a small tweak should suffice. That is, "_Having travelled two right from reading `1`, if current cell is `X`, one subtraction is finished._" Make use of a different symbol in the array to distinguish second number from quotient (use another symbol, say `i` -- personal choice, really does not matter). After making all `X` as `1`, go right until current cell is `B`. Make `B` as `1`. Move right, make current symbol as `B`. Go left until current cell is `0`. Goto step #2. @@ -96,14 +96,14 @@ For an input `num`, the first step is to make a copy of $\lfloor\dfrac{num}{2}\r 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)$. +5. Repeat steps 1 - 4 until instruction pointer reaches `0`. The complexity is observed to be linear time, ie $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. +1. Now, to compute modulo, follow the modulo 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, dercement `div` by one, which takes linear time (traversing till the end of tape, marking it as `B`, and coming back, which was mentioned in the preious section). 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(uv)$). Hence, overall time complexity of the machine to declare weather the given number is prime or not takes $O(n^3)$. +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 depends on size of `div` as well as `num`. ### Output #### Result #1