Divide operation using increment, loop, assign, zero

Question

We're only allowed to use the following operations:

incr(x) - Once this function is called it will assign x + 1 to x

assign(x, y) - This function will assign the value of y to x (x = y)

zero(x) - This function will assign 0 to x (x = 0)

loop X { } - operations written within brackets will be executed X times

How can I implement divide operation?

Answer 1

While Sarid's answer is correct, it's possible to compute floor(x / y) more efficiently as follows:

divide(x, y) {
    x = incr(x)

    z = 0

    loop x {
        x = sub(x, y)
        l = isTrue(x)
        z = add(z, l)
    }

    return z
}

The add and sub functions have been previously defined here:

Subtraction operation using only increment, loop, assign, zero

The isTrue function is defined as follows:

isTrue(x) {
    y = false
    loop x { y = true }
    return y
}

Note that we've previously defined true and false as follows:

false = 0
true  = incr(false)

The only problem with this function is that divide(n, 0) returns n + 1 instead of an error.

Answer 2

This question combines two other posts that were already answered in SO:

1. Relational operations
2. Subtraction operation

From these questions we can see how to implement sub(x,y) , gt(x,y) , lte(x,t) and add(x,y).
By using those, we can implement the divide operation - both ceil(x/y) and floor(x/y):

Ceil(x/y)

div_ceil(x,y){
    r = 0
    loop x{
        z = 0
        l = gt(x,z)
        r = add(r,l)
        x = sub(x,y)
    }
    return r
}

Explanation:
We loop x times and each time we subtract y from x and we count the number of times it takes until x no longer greater than 0. When it is greater than 0 we add 1 to our result.

Why is the loop running x times?
Because it is the maximum needed times in order to get to the result. This is given when y == 1, subtracting 1 x times - we will get r == x.

---

Floor(x/y)

div_floor(x,y){ 
    r = 0
    t = 0
    loop x{
        t = add(t,y)
        l = lte(t,x)
        r = add(r,l)
    }
    return r
}

Or, if you want, by simply using div_ceil method above we can also get floor(x/y):

div_floor(x,y){
    z = div_ceil(x,y)
    k = div_ceil(incr(x),y)
    l = eq(z,k)
    z = sub(z,l)
    return z
}

Simply comparing the results of x/y and x+1/y. If they are equal meaning we did a round up (ceiling) in dev(x,y) so we need to subtract 1 to get the floor result. If they are not equal, the results should stay the same.

---

Testing & Notes

Please see the correctness of these methods running live here.
I implemented all functions in C++ so they will behave exactly the same (by using only allowed operations).

I assumed that dividing by 0 is an undefined behavior. Those methods will return some value instead of an error in case of y==0.