Monthly Archives: September 2018

Quickly recognizing primes less than 100

Recently, Mark Dominus wrote about trying to memorize all the prime numbers under . This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a … Continue reading

Posted in arithmetic, computation, primes | Tagged , , , | 16 Comments

Primality testing: recap

Whew, this is developing into one of the longest post series I’ve ever written (with quite a few tangents and detours along the way). I thought it would be worth taking a step back for a minute to recap what … Continue reading

Posted in computation, number theory, primes | Tagged , , , | 2 Comments

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