# Difference between revisions of "TADM2E 1.28"

Codewarrior (Talk | contribs) |
Codewarrior (Talk | contribs) |
||

Line 231: | Line 231: | ||

--~~~~ | --~~~~ | ||

</pre> | </pre> | ||

+ | |||

+ | |||

+ | --[[User:Codewarrior|Codewarrior]] ([[User talk:Codewarrior|talk]]) 04:43, 19 March 2016 (EDT) | ||

<pre> | <pre> | ||

int divide(int dividend, int divisor) | int divide(int dividend, int divisor) |

## Revision as of 08:43, 19 March 2016

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

--Codewarrior (talk) 04:43, 19 March 2016 (EDT)

int divide(int dividend, int divisor) { bool negative = ((dividend ^ divisor) >> 31) & 0x1 == 1; unsigned int a = dividend < 0 ? -dividend : dividend; unsigned int b = divisor < 0 ? -divisor : divisor; unsigned int quotient = 0; while (a >= b) { unsigned int k = 0; for (; a >= b << k && b << k <= (0x80000000 >> 1); ++k); quotient |= 1 << (a < b << k ? --k : k); a -= b << k; } return negative ? -quotient : quotient > INT_MAX ? INT_MAX : quotient; }