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. 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
bwas lower thank*a). So we run a binary search between0*aand previousk*a. An array of all powers of two up to the current value ofk(That producedk*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., one shift operation)
{//Note that a*k is the same as a << i $i$ is $\log_2(k)$
Array[i] = k //Stores powers of 2 in their corresponding index. These will be used later on in a binary search.$+1$
(k << 1) //Doubling k$+1$
}$T = 5$(Loop takes 4 primitive operations whenever called)
q += Array[i-1] //Previous value of k$+1$
b -= (a << (i-1)) //b - (a * previous value of k) $+1$
if(b < a)$+1$(b will be less than k if q is the quotient)
{
r = b $+1$
return 0 //Function returns with a value, r and q are the values of the variables passed into the function.
}
else if(b > a) //b is between 0 and Array[i-1]*a. Time to perform a binary search using Array[]. q is between 0 and Array[i-1]$+1$
j = i-2$+1$
while(true) //This loop runs a maximum of $(log(2^{(n-1)}))$ times. I.e $(n-1)$ times.
{
det = compare((a << j), b) Comparing b versus some power of 2 times a$+5$(compare takes 4 operations, and assignment takes 1)
if(j != 0)$+1$
{
if(det == 0)$+1$
{
r = 0$+1$
q += Array[j]$+1$
return 0
}$T = 3$
else if(det == 1)$+1$
{
q += Array[j]$+1$
b -= (a << j)$+1$
j -= 1$+1$
}$T=4$
else if(det == -1)$+1$
{
j -= 1$+1$
}
}$+6$(Only one of the selective code blocks will execute. The costliest, is the second one +1 for the outer block, +1 for testing the first block. +4 for second block.)
else if(j == 0)$+1$
{
if(det == 0)(No remainder Array[0] = 1 it will be treated as such.).$+1$
{
r = 0$+1$
q += 1$+1$
return 0
}$T = 3$
else if(det == 1)(b > a, means that there's a remainder(b-a))$+1$
{
q += Array[j]$+1$
b -= (a)$+1$
r = b$+1$
return 0
}$T = 4$
else if(det == -1)(b is less than a. Mean current q is quotient, and current b is remainder.)$+1$
{
r = b$+1$
return 0
}$T = 2$
$+1$(For final return)
}$T = 6$(Same reason as above)
}$T = 12$(det takes 5, both loops take 6, the second also has the comparison of the first, so that's +1 5 +7 =12)
q = ($state == 0)?-q:q$+2$
I will ignore the sum of the constants, since they are irrelevant to the asymptotic complexity.
The time complexity $f(n)$ of the algorithm is given by: $f(n) = O(M_1\cdot5 + M_2\cdot12)$
Where: $M_1 = $ number of times the first loop ran.
$M_2 = $ number of times the second loop ran.
$M_1 = \log(2^{n+1}) = n+1$ (Worst case when a is 1 Loop runs until k > b)
$M_2 = \log(2^{n-1}) = n-1$ (Worst case when b is $2^n-1$. Loop performs a binary search.)
$f(n) = O((n+1)\cdot5 + (n-1)\cdot12)$
$f(n) = O(5n + 5 + 12n -12)$
$f(n) = O(17n - 7)$
$$f(n) = \Theta(n)$$
Please tell me what the run time complexity of this algorithm is. Especially as $n$ gets large.
