How does this integer division work?

50 Views Asked by At

In "Theory of Computation: Formal Languages, Automata, and Complexity" Spanish ed. (p.220) it says that:

$$ div(x, y) = μt[((x + 1) \dot{-} (mult(t, y) + y)) = 0] $$

Where $mult$ is the integer multiplication.

Defines a division $\left[ \frac{x}{y} \right]$ for $y \ne 0$.

However if I try to operate div(4, 2) I get that not $t$ natural exists:
$((4 + 1) \dot{-} (mult(t, 2) + 2))$
$(5 \dot{-} (mult(t, 2) + 2))$
$t: (5 = (t*2 + 2))$
$t: (3 = t*2)$
$t: (3/2 = t)$

2

There are 2 best solutions below

0
On BEST ANSWER

$$\mu t[((x+1)\dot-(\operatorname{mult}(t,y)+y))=0] $$ is the smallest $t\in\Bbb N_0$ with $((x+1)\dot-(\operatorname{mult}(t,y)+y))=0$, i.e., the smallest $t$ with $ty+y\ge x+1$, i.e., the smallest $t$ with $(t+1)y>x$, hence (as $y>0$) the greatest $t$ with $ty\le x$, as desired.

0
On

$$\mu t(x)=\lceil x \rceil=\min \{x\in \mathbb N_0 : x\ge t\}$$

which gives the answer as $2$.