Monthly Archives: September 2018

Quickly recognizing primes less than 100

Posted on September 16, 2018 by Brent

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

Primality testing: recap

Posted on September 10, 2018 by Brent

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

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