. The basic algorithm for computing 3k, for k a positive integer, is to repeated
ID: 3281552 • Letter: #
Question
. The basic algorithm for computing 3k, for k a positive integer, is to repeatedly multiply by 3, k - 1 times. So for example, 3100 can be computed in 99 multiplication steps using this method. However, there are more efficient methods for computing 3100 in terms of the number of multiplication steps required. For example, we can use the fact that 3k.332k, to get 32, 34, 38, 316, 332, and 364, in six multiplication steps by repeated squaring. In this problem, we can reuse a number that we have already computed as many times as we want in future computations, without adding to our count of multiplication steps. Continuing, 3100-34, 332, 364 in two more multiplication steps, for a total of 8 multipiication steps. Please answer the following: a) Use the above idea to describe an efficient algorithm for computing 3k. b) Show that this algorithm has optimal efficiency, in terms of fewest multiplication steps, for computing 310 c) Find a value of k for which this algorithm is not the most efficient. d) Can 3100 be computed in fewer than 8 steps?Explanation / Answer
(a).we can also lssimplify the above given term 3k in simple multiplication steps that is
3k=3(k/2).3(k/2).--->(1)
We can also write this algorithm as
3k=3(3k/4).3(k/4).--->(2)
3k=3(2k/3).3(k/3).---->(3)
Using above algorithms depending on the values of k,we can simplify multiplication to two parts only.
(b). Above algorithm has few steps for finding the value of 310.So,This algorithm has optimal efficiency.
Now from first step ,310=3(10/2).3(10/2)=35.35.
(c). For larger values of k,above algorithms are not efficient.
Let us take first algorithm
3k=3k/2.3k/2
This algorithm not efficient for k=3,5,7..... For odd values of k.
Algorithm (3) also not efficient for odd values of k.
Algorithm (2) also not efficient for odd values of k.
(d).3100=3(100/2).3(100/2)=350.350.
3100=375.325.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.