How fast is this Division Algorithm
I wrote an algorithm for integer division. I'm wondering how fast it is asymptotically. I used RAM model myself to asymptotically analyse it, but I found out that:
Elementary CPU instructions like shifting and adding, are not constant as the integers grow arbitrarily large.
So it seems my analysis is wrong. I'd like to know how fast the algorithm is. I'll leave in my original analysis using RAM model of computation.
I think I've found a linear time algorithm to solve this problem. I will attempt to calculate it's time complexity. I hope someone in the community, can point me to where I may have made a mistake. I am assuming the RAM model of computation. In particular, I am making these assumptions.
(1) Addition and subtraction take one primitive operation.
(2) Boolean shifting takes one primitive operation.
(3) Reading from memory takes one primitive operation.
(4) Writing to memory, takes another primitive operation.
(5) Logical comparison takes one primitive operation.
(6) Returning a value takes one primitive operation.
(7) Creating a variable or an array takes one primitive operation.(Irrespective of size of Array)
(8) Assignment takes one primitive operation.
Please correct me if I made any wrong assumptions. I will try to determine the run time complexity of this algorithm. I will use $+i$ to denote a particular piece of code takes $i$ primitive operations and $+k \cdot i$ to denote $ki$ primitive operations. 143
I will attempt to total all the primitive operations. (I will keep a tally at each 'block' of code of total expenditure of that block in the form $T = k$ where $k$ is the total so far)
The section below outlines the algorithm for those who may want to fix, improve, understand, etc.
The Idea of this algorithm, is that $\log_2(2^n) = n$ (Initial growth of the quotient using powers of two.) It attempts to reduce time-complexity of the algorithm, at the expense of space complexity.
Multiplication as far as this algorithm is concerned, will be replaced by use of the binary "<<" operator.
We Know that the rest of the quotient is between $0$ and the previous value of $k$(Because b was lower than k*a). So we run a binary search between 0*a and previous k*a. An array of all powers of two up to the current value of k(That produced k*a > b) are kept. This array is then used to perform a binary search.
$\log_2(2^n-1) = n-1$
$n + n-1 = 2n$ $$f(n) = \Theta(n)$$
compare(x, y) A comparison function, that shall be used to aid binary search.
{
if(x == y) return 0$+1$
else if(x > y) return -1$+1$
else if(y > x) return 1$+1$
}$+1$(for return)
$T = 4$(Whenever this function is called, 4 primitive operations take place.)
a = divisor, b = dividend, q = quotient, r = remainder $+4$ (Creating 4 variables) m = Array size. Set it to whatever you want. Ideally it should be $\ge$ maximum size of input $n$
$state = 1 If the numbers have the same sign 0 otherwise. $+3$(Creating a variable, Logical comparison and assignment)
divide(a, b, &q, &r) q and r are passed to the function by reference. So that both may be returned.
{
convert a and b to unsigned integer types. $+2$ q = 0$+1$
k = 1 This will be the multiplier by which bwill be tested.$+1$
m = 100 (m should be $\ge \log_2(b)$ or n. I'm just arbitrarily picking $100$ Array[m] Initialise all elements with 0 (If it increases time complexity of algorithm, initialise only the first element to 0. $+1$ (Or $+m$ it doesn't matter this is a constant and has no bearing on the asymptotic complexity.)
Array[0] = {0} $+1$
i A variable to be used as a control variable for the array.$+1$
for(i = 0 ; b >= (a << i) ; i++) $+3$(One logical comparison, One increment of $i$ each time loop is executed. 743