Fast power and Hanoi

Questions 1 to 5 of 8

1. 1. In fast_power_rec(x, n), each call passes n / 2 to the next call. Roughly how many levels deep do the recursive calls go when n is 1,000,000,000?

   About 1,000,000,000, one level per multiplicationAbout 1,000,000, one level per thousandAbout 43, one level per squaringAbout 30, because n is halved on each level
2. 2. The Towers of Hanoi program prints one line per move. How many lines does it print for 20 disks?

   Type a number.

3. 3. What does this program print? ``cpp #include <cstdint> #include <iostream> using namespace std; long long multiplications = 0; uint64_t fast_power(uint64_t x, uint64_t n) { uint64_t result = 1; uint64_t base = x; while (true) { if (n & 1) { result = result * base; multiplications++; } n >>= 1; if (n == 0) break; base = base * base; multiplications++; } return result; } int main() { cout << "3^13 = " << fast_power(3, 13) << "\n"; cout << "multiplications = " << multiplications << "\n"; } ``

   3^13 = 1594323 multiplications = 53^13 = 1594323 multiplications = 63^13 = 1594323 multiplications = 133^13 = 1594323 multiplications = 8
4. 4. What does this program print? ``cpp #include <iostream> void hanoi(int n, char from, char to, char spare) { if (n == 0) { return; } hanoi(n - 1, from, spare, to); std::cout << "Move disk " << n << " from " << from << " to " << to << "\n"; hanoi(n - 1, spare, to, from); } int main() { hanoi(2, 'A', 'B', 'C'); } ``

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to CMove disk 1 from A to C Move disk 2 from A to B Move disk 1 from B to CMove disk 2 from A to B Move disk 1 from A to C Move disk 1 from C to BMove disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B
5. 5. Fill in the blank: in fast_power_rec, when n is odd, the result is the squared power of n / 2, then multiplied by ___ once more.

   Type your answer.