# TADM2E 1.28

Jump to: navigation, search
// Note: This only works for positive values!
int divide(int numerator, int denominator) {
int quotient = 0;

while(numerator >= denominator) {
numerator -= denominator;
quotient++;
}

return quotient;
}


-- Vale.rho 00:02, 25 Feb 2015

Initially I also thought the previous solution, but the final sentence of the text made me suspicious ("Find a fast way to do it."), so this is my solution:

def divide(num, den):
quotient = 0
quot_accumulator = 1
den_accumulator = den

while num >= den:
if num < den_accumulator:
den_accumulator = den
quot_accumulator = 1

num = num - den_accumulator
quotient = quotient + quot_accumulator
quot_accumulator = quot_accumulator + quot_accumulator
den_accumulator = den_accumulator + den_accumulator

return quotient


--Smallllama (talk) 21:03, 15 March 2015 (EDT)

I figured that the only time that it would not be fast would be when very large numbers of the divisor fit inside the numerator. i.e. 5/2 is fast regardless of how you code it but 50001/2 is not. My solution was to use recursion to increase the divisor at each step. (I doubled the divisor at each step but I imagine that the best solution is to be more aggressive and maybe octuple it or something to counterbalance the fact that recursion is slow.)

Example: base case is that the numerator < (divisor+divisor), in which case return 1 if numerator is bigger than divisor and 0 otherwise. Recursive step is to pass numerator and (divisor+divisor) to the function to try again. The recursion is passing back both the totalSoFar AND (numerator - divisor). When a recursion receives data from a further recursion, it doubles the totalSoFar that was returned and uses the (numerator - divisor) that was returned to compare against its own divisor.

Here is the code in Java:


public class RecursiveIntegerBaseCase {
static boolean flip=false;
static int answer;
static int addOn;

public static void main(String[] args)
{
System.out.println(recursiveBase(7,2));
System.out.println(recursiveBase(63,2));
System.out.println(recursiveBase(70,21));

}

public static int recursiveBase(int x, int y)
{
//error checking on inputs
if(y==0)
{
System.out.println("Divide by zero error.  Y cannot be zero.");
}
if(x<0 && y>0)
{
x=-x;
flip = true;
}
if(y<0 && x>0)
{
y=-y;
flip = true;
}
if(x<0 && y<0)
{
x=-x;
y=-y;
}

if(x<y+y)
{
if(x<y)
{
answer= 0;
}
else
answer= 1;
}
else
{
RID rid = new RID(x,(y+y));
if(rid.rX<y)
{
addOn = 0;
}
else
{
addOn=1;
}
answer = rid.answer + rid.answer + addOn;
}

// account for negative*positive
if(flip)
{
answer = -answer;
}
return answer;
}
}

and the recursive step:

public class RID
{
// really I should not have these public but should use getters and setters
public int rX;
public int answer;
public int stepAnswer;
public RID(int newX, int newY)
{
int doubleNewY = newY+newY;
if(newX<doubleNewY)
{
if(newX<newY)
{
stepAnswer=0;
}
else
{
stepAnswer = 1;
}
answer = stepAnswer;
rX=newX-newY;
}
else
{
RID rid = new RID(newX,doubleNewY);
rX=rid.rX - newY;
if(rid.rX<newY)
{
stepAnswer=0;
}
else
{
stepAnswer=1;
}
answer = rid.answer + rid.answer + stepAnswer;
}
}
}