Back to Main List
Back to Book List

Notes and Reflections on Books and Media

by Hannah Leitheiser

Petzold's Sqrt(2) Efficiency

#turingmachine #alanturing #charlespetzold

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

Charles Petzold



This was just because I could, mostly -- empirically O(n^3.8) operations per digit fits the chart. Efficient square root algorithms use Newton's method and fancy multiplication methods, much harder to implement.