patternMinor
Time Complexity of Shifting
Viewed 0 times
shiftingcomplexitytime
Problem
I'm developing a IMHO very interesting algorithm for integer division. This algorithm uses boolean shifting(It shifts left for multiplication by 2). I'm wondering if
I've looked at the other questions here, and they are saying it depends on the machine.
I'm using RAM model of computation, but don't want to assign
<< c is $O(c)$ or $O(n)$. I'm hearing it depends on architecture. Algorithms ideally should be architecture independent. So for the purposes of analysing the time complexity of my algorithm, should I consider << c as 1 primitive operation or c primitive operations.I've looked at the other questions here, and they are saying it depends on the machine.
I'm using RAM model of computation, but don't want to assign
<< c a cost of 1 when it may in fact cost c.Solution
Most of architectures use a single instruction for left and right shift.
Usually, this instruction (WLOG we condier only logical shift left) is LSL, the syntax is the following:
where rd is the registry in which load the variable, rs is the registry in which store the result and #offset is the number of bit to shift.
So you could consider the left or right shift operation as taking $O(1)$, because this operation takes only a single CPU's clock.
Usually, this instruction (WLOG we condier only logical shift left) is LSL, the syntax is the following:
lsl $rd,$rs,#$offsetwhere rd is the registry in which load the variable, rs is the registry in which store the result and #offset is the number of bit to shift.
So you could consider the left or right shift operation as taking $O(1)$, because this operation takes only a single CPU's clock.
Code Snippets
lsl $rd,$rs,#$offsetContext
StackExchange Computer Science Q#67973, answer score: 6
Revisions (0)
No revisions yet.