Difference between revisions of "TADM2E 1.28"

Latest revision as of 13:32, 23 July 2020

// 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 ? 0-quotient : quotient > INT_MAX ? INT_MAX : quotient;
}

#include <iostream>
using namespace std;

int division_new(int numerator, int denominator){
    int result = 0;
    for(int i = denominator; i <= numerator; i++){
        if(i%denominator==0){
            result++;
        }
    }
    return result;
}
int main(int argc, char* argv[])
{
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);

    cout << "Doing normal way..." << endl;
    int q = a/b;
    cout << "a/b = " << q  << endl;
    
    int module = division_new(a,b);
    cout << "a%b = " << module << endl;
    
    return 0;
}

-- jarrettcoggin - 20:30, 25 July 2018 (PDT) This is in Python 3.6.5. It consists of two files, one that has the actual functions and the other than is unit tests for the functions. As long as the two files are in the same directory, you should be able to invoke it with the following command:

python -m unittest test_script.py

script.py

def divide(a, b, max_decimal_places=4, current_decimal_places=0, increment_value=1):
    if a < 0:
        return 0
    elif (a - b) == 0:
        return increment_value
    elif a < b:
        if current_decimal_places < max_decimal_places:
            if str(b).startswith("0."):
                b = float(str(b).replace("0.", "0.0"))
            else:
                b = float("0.{}".format(str(b)))
            if str(increment_value).startswith("0."):
                increment_value = float(str(increment_value).replace("0.", "0.0"))
            else:
                increment_value = float("0.{}".format(str(increment_value)))
            return divide(a, b, max_decimal_places, current_decimal_places + 1, increment_value)
        else:
            return 0
    else:
        return increment_value + divide(a-b, b, max_decimal_places, current_decimal_places, increment_value)


def divide_iterative(a, b, max_decimal_places=4):
    total = 0
    increment_value = 1
    current_decimal_places = 0
    while a > 0 and current_decimal_places <= max_decimal_places:
        if (a - b) >= 0:
            total += increment_value
            a -= b
        elif a < b:
            current_decimal_places += 1
            if current_decimal_places <= max_decimal_places:
                if str(b).startswith("0."):
                    b = float(str(b).replace("0.", "0.0"))
                else:
                    b = float("0.{}".format(str(b)))
                if str(increment_value).startswith("0."):
                    increment_value = float(str(increment_value).replace("0.", "0.0"))
                else:
                    increment_value = float("0.{}".format(str(increment_value)))
    return float(str(format(total, ".{}f".format(max_decimal_places))))

test_script.py

from script import divide, divide_iterative
import unittest


class Test(unittest.TestCase):

    def test_6_divided_by_2(self):
        expected = 3
        actual = divide(6, 2)
        assert actual == expected

    def test_7_divided_by_2(self):
        expected = 3.5
        actual = divide(7, 2)
        assert actual == expected

    def test_22_divided_by_7(self):
        expected = 3.14285
        actual = divide(22, 7, max_decimal_places=5)
        assert actual == expected

    def test_6_divided_by_2_iterative(self):
        expected = 3
        actual = divide_iterative(6, 2)
        assert actual == expected

    def test_7_divided_by_2_iterative(self):
        expected = 3.5
        actual = divide_iterative(7, 2)
        assert actual == expected

    def test_22_divided_by_7_iterative(self):
        expected = 3.14285
        actual = divide_iterative(22, 7, max_decimal_places=5)
        assert actual == expected


if __name__ == "__main__":
    Test.main(verbosity=2)