Difference between revisions of "TADM2E 1.28"

Revision as of 18:40, 8 May 2015

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

#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 abs_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[1]);
    int b = atoi(argv[2]);

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