Fast Exponentiation, revisited


Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent n to perform O(\log_2 n) products to compute x^n.

While discussing this algorithm in class, a student asked a very interesting question: what’s special about base 2? Couldn’t we use another base? Well, yes, yes we can.

Read the rest of this entry »

Walk Count like an Egyptian (Part I)


The strangest aspect of the Ancient Egyptian’s limited mathematics is how they wrote fractions. For example, they could not write \frac{5}{7} outright, they wrote

\displaystyle \frac{5}{7}=\frac{1}{2}+\frac{1}{5}+\frac{1}{70},

and this method of writing fractions lead to absurdly complicated solutions to trivial problems—at least, trivial when you can write a vulgar fraction such as \frac{3}{5}. But how much more complicated is it to write \frac{1}{2}+\frac{1}{5}+\frac{1}{70} rather than \frac{5}{7}?

Read the rest of this entry »