🎴 Flashcard Mode
IBM Cognos Report Studio & Algorithms Quiz
Card1 / 20
Mastered0
Review0
QuestionClick to flip
How many multiplications do you need to perform if you use Repeated Squaring technique to calculate n^1000. (Ignore the problem of storing such a large number in variable assume you can store infinitly large number in basic data types)
AnswerClick to flip back
A
14
💡 Explanation:
Repeated squaring (exponentiation by squaring) computes n^1000 by decomposing the exponent into binary. 1000 in binary is 1111101000 (base-2), which has 10 bits requiring 9 squarings, and Hamming weight of 6 ones requiring 5 extra multiplications. Total: 9 + 5 = 14 multiplications. This is dramatically fewer than 1000 for naive multiplication.