This post is about a solution for the exercise 1-28 from the book The Algorithm Design Manual.

[1-28] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.
Skiena, The Algorithm Design Manual

My solution

The exercise asks to write a method (or function) to perform a division operation without the use of classical programming language operators / and *. Let's start simply by write the method prototype that has two integer parameters, let's say a, b \in Z, and returns an integer c \in Z.

int divide(int a, int b)

To get the solution figure out the division meaning. Do you remember the cake and its slices? The statement c = a / b means how many slice of size b you can fit in a. So, just start to remove a slice of size b, then remove another slice of size b and so on. I just count the number of whole slices that I eat :-). Therefore, the algorithm just use the subtract operetor. So, this is my solution:

public int divide(int a, int b) {
    int count = 0;
    while ( a > 0 ) {
        a = a - b;
        count++;
    }
    return count;
}

Correctness

So, I've the solution but its not the end. I must be sure that it works for every integer number :-D. So, my idea is to create a table with the input ranges and expected output.
(will continue ... :-)

Rate this post

Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>