I want to construct a LOOP-computable program for the integer division (quotient):
x = a DIV b
The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)
I don't know how to do this without a while.
1
-
$\begingroup$ Hint, you have to use if-then-else $\endgroup$喜欢算法和数学– 喜欢算法和数学2018-12-11 22:02:02 +00:00Commented Dec 11, 2018 at 22:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The idea is to implement the following algorithm:
result = 0
while a >= 0:
a = a - b
result = result + 1
end while
return result - 1
As you mention, there is no while. However, since we have an a priori upper bound on the number of rounds, we can simulate the while as follows:
result = 0
repeat a + 1 times:
if a >= 0:
a = a - b
result = result + 1
end if
end repeat
return result - 1
It remains to implement the conditional and subtraction. In fact, you can't really implement the conditional, since all numbers are automatically non-negative. However, this is easy to fix by replacing the condition a >= 0 with the condition a > 0. I'll let you work out the minor changes required to implement this change.
$\begingroup$
$\endgroup$
Look for the unique integer $x$ such that $b x \le a$ and $b(x+1) > a$. With this approach, you don't need a WHILE statement.
