Tag Archives: steps

Efficiency of repeated squaring: another proof

Posted on September 6, 2018 by Brent

In my previous post I proved that the “binary algorithm” (corresponding to the binary expansion of a number ) is the most efficient way to build using only doubling and incrementing steps. Today I want to explain another nice proof, … Continue reading →

Posted in computation, proof | Tagged , , , , , , , , | 3 Comments

Efficiency of repeated squaring: proof

Posted on September 1, 2018 by Brent

My last post proposed a claim: The binary algorithm is the most efficient way to build using only doubling and incrementing steps. That is, any other way to build by doubling and incrementing uses an equal or greater number of … Continue reading →

Posted in computation, proof | Tagged , , , , , , , , | 2 Comments

Efficiency of repeated squaring

Posted on August 24, 2018 by Brent

As you probably realized if you read both, my recent post without words connects directly to my previous post on exponentiation by repeated squaring Each section shows the sequence of operations used by the repeated squaring algorithm to build up … Continue reading →

Posted in computation | Tagged , , , , , , , | 7 Comments