When computing 3²⁰, our divide-and-conquer algorithm reduced the number of multiplications from 19 to 5.

In general, when computing xⁿ, our divide-and-conquer algorithm reduces the number of multiplications from Θ(n) to Θ(lg n).

Let's see how much difference that makes when computing 3¹⁰⁰⁰⁰⁰.

To benchmark the divide-and-conquer algorithm against the obvious Θ(n) algorithm, we have to translate those algorithms into some programming language. I'm going to use Scheme instead of Racket, because there are implementations of Scheme that run faster than any implementation of Racket.