# Difference between revisions of "TADM2E 1.28"

Smallllama (Talk | contribs) |
|||

Line 35: | Line 35: | ||

return quotient | return quotient | ||

+ | </pre> | ||

+ | |||

+ | --[[User:Smallllama|Smallllama]] ([[User talk: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: | ||

+ | <pre> | ||

+ | |||

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

+ | } | ||

+ | } | ||

+ | } | ||

+ | |||

</pre> | </pre> |

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