# Difference between revisions of "TADM2E 1.28"

// 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;

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)
{
}
else
}
else
{
RID rid = new RID(x,(y+y));
if(rid.rX<y)
{
}
else
{
}
}

// account for negative*positive
if(flip)
{
}
}
}

and the recursive step:

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



#include <climits>
#include <iostream>

using namespace std;

int neg(int a, int b, int r) {
return ((a < 0) ^ (b < 0)) ? -r : r;
}

// O(n)
int division_naive(int num, int den) {
if (den == 0) {
return INT_MAX;
}
else {
int abs_num = abs(num);
int abs_den = abs(den);

int quo = 0;
while (abs_num >= abs_den) {
abs_num -= abs_den;
quo++;
}

return neg(num, den, quo);
}
}

// O(log(n))
int division_optimized(int num, int den) {
if (den == 0) {
return INT_MAX;
}
else {
int abs_num = abs(num);
int abs_den = abs(den);

int quo = 0;
int bits = 0;
while (abs_num >= abs_den) {
bits = 0;
// double ads_den by shift the bit left
while ( abs_num >= abs_den<<bits ) {
abs_num -= abs_den<<bits;
quo += 1<<bits;
bits++;
}
}

return neg(num, den, quo);
}
}

int main(int argc, char* argv[])
{
int a = atoi(argv);
int b = atoi(argv);

cout << "Doing naive way ..." << endl;
int q = division_naive(a, b);
cout << "a / b = " << q << endl;

cout << "Doing optimized way ..." << endl;
int r = division_optimized(a, b);
cout << "a / b = " << r << endl;

return 0;
}

--~~~~