Difference between revisions of "TADM2E 1.28"

Revision as of 01:03, 16 March 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;
		}
	}
}