# Tag Archives: efficiency

## Efficiency of repeated squaring: another proof

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 | | 3 Comments

## Efficiency of repeated squaring: proof

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 | | 2 Comments

## Efficiency of repeated squaring

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 | | 7 Comments

## Fast and slow machines

In my previous post, I presented three hypothetical machines which take a positive integer as input and give us something else as output: a factorization machine gives us the complete prime factorization of ; a factor machine gives us one … Continue reading

Posted in computation, number theory, primes | | 1 Comment