Algorithms

Question

Comments

think O(n) . use shift operation.

---

what about karatsuba's algorithm ?

---

Both binary numbers are perfect powers of $2$, so their powers can be found by continuous division by $2$ in $O(log_{2}(n))$ time. Now, Muliplying two numbers is equivalent to adding their powers.

So, it can be done in $\tt O(log(n))$ time.

---

why not O(1)??

---

asking worst case of best algorithm.

explain proceedure for O(1).

---

no. i dont know i'm just asking ques..

---

In my above approach, if we find the the power of numbers by using $log_{2}$ function instead of continuous division and consider that $log_{2}(x)$ is implemented as $O(1)$ operation in our computer. It can be done in $\tt O(1)$

---

@Gabbar @Anirudh One more approach that i could come up with is :

• We are given binary numbers in which are perfect powers of $2$ i.e., only $1$ bit is set. ex- $0001000 = 2^3$ (valid), $0001010 = 2^1 + 2^3$ (not a perfect power of $2$)
• All we need to do is find the position of $set-bit$, when we know that there is only $1$ set bit. Position of set bit can be found in $\log(n)$ time using binary search (or) in $\tt O(n)$ using bit shift operation, where $n \rightarrow$ length of binary number. [if this could be reduced to $O(1)$ then we have O(1) algorithm]
• Suppose we know set bit postion of $1^{st}$, number as $4$ and of $2^{nd}$ one to be $3$ (numbers are 8, 2 and product = 16($10000$) bit position of product $ = (4+2) -1 = 5$

---

manish

ya for 8 bit it will take only O(1). you apply binary search only on sorted list 00000100 is not sorted .

for n bit you need O(n) time to find position of 1.

---

for $n-bit$ number bit position can be found by using shift operation  in $O(n)$ time(only $1$ bit is set). But the best way i think is using $log_2()$ function given by programming language to find the power of $2$ in number in $O(1)$, however large number is.

But, we have to consider that $log_2()$ provided  is $O(1)$ function. (which we generally assume for any provided function)

Ex-$ log_{2}(2^{49}) = 49$  ($O(1)$ operation) ---> means $50^{th}$ bit is set.

---

In the perfect power of 2 there will be only bit that has value 1, hence binary search cannot be used, bcoz we cannot know whether 1 is on left or right, so O(n) for scanning number, hence A must be the answer.

---

what to do after finding the bit positions of 1 in both the numbers??will we convert them into decimal and then multiple??

what is the use of finding the bit position of 1??

and is'nt the time complexity O(n²) for multiplying two n- bit numbers because each bit of multiplicant is multiplied with multipier??

---

Since it is a perfect power the answer will have only one bit set. We can add the positon in which bit is set in both numbers and add them to get the resultant bit postion which will be set in the answer which can be done in O(1) time hence O(n) is the answer which is used for scanning number.

Answer 1

#Booth's algorithm can be used to multiple 2 signed binary numbers. It works by shifting and adding bits. This shifting and adding happens for  n(no.bits in multiplicand + no. bits in multiplier). Assuming that adding and shifting takes constant time, we can say that upper bound is O(n).

Comments

we can convert binary to decimal in O(n) time for n bit number

after that multiply and check for the perfect power of 2 which takes O(1) hence in total its : O(n)

for 8 bit number it should be O(1)

Answer 2

BOOTH Algorithm

step 1:i=0 s=0|B    (upper n bit| lower n bit)

do{

step 2:is(s0)Sh =+A (sh=upper bit as in booth takes only in n bit ,after it gots ASR)

step 3:s=s/2;

i++

}while(i<=n)

 

 

for n bit=O(n)

but for 8 bit=O(1)

please correct me if i am wrong