**commit** f99c8574a3a063f67f6d47536d60ed85b871c807
**parent** 32c9a8575315fa4643efa594e8d6cc5c7546f484
**Author:** Agastya Chandrakant <acagastya@outlook.com>
**Date:** Mon, 16 Apr 2018 20:18:45 +0530
add
**Diffstat:**

1 file changed, 24 insertions(+), 1 deletion(-)

**diff --git a/s4/fafl/report.md b/s4/fafl/report.md**
@@ -4,9 +4,32 @@
## Standard TM to compute modulo and division of two natural numbers as well as to check if a given natural number is prime
### STM as a transducer to compute modulo and division
-Consider two numbers `u` and `v`. `u % v = (u - v) % v`, if `u > v` else `u`. Using this, a recursive relation can be established, which is:
+Consider two numbers `u` and `v`. `u % v = (u - v) % v`, if `u` is greater than or equal to `v` else `u`. Using this, a recursive relation can be established, which is:
$\mod(u, v) = \begin{cases} u: u < v\\mod (u - v, v): otherwise\end{cases}$
+Its iteratie code in JavaScript is:
+
+```
+function modulo(u, v) {
+ while(u >= v)
+ u = u - v;
+ return u;
+}
+```
+Repeatedly subtracting yields remainder. However, if we count the number of times subtraction was performed, we get the quotient. Hence, modifying the above code slightly, quotient can be calculated:
+
+```
+function newModulo(u, v) {
+ var quo = 0;
+ while(u >= v) {
+ u = u - v;
+ quo++;
+ }
+ return u;
+}
+```
+In the above code, `quo` variable gives the
+
### 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}$