Multiplications in fast exponentiation

You compute a45a^{45} by left-to-right binary (square-and-multiply) exponentiation, run exactly as follows: read the exponent's bits from the most significant down; initialize the running result to aa, which consumes the leading 11-bit for free (no multiply); then for each remaining lower bit, square the running result, and — only where that bit is 11 — also multiply by aa. Counting every squaring and every multiply-by-aa, exactly how many multiplications does the whole computation take?

Show hints (2)+
  1. Write 45=101101245 = 101101_2: count its bit-length and its number of 11-bits.
  2. Squarings =(bits1)= (\text{bits}-1); extra multiplies =(set bits1)= (\text{set bits}-1); add them.

Answer

Reveal answer →

8

Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.

Asked at: Jane Street, Two Sigma

Related questions