A Spigot-Algorithm for Square-Roots: Explained and Extended

2023/12/23 by Mayer Goldberg, Goldberg, Mayer
Agricultural and Biological Sciences · Computer Science · #Discrete Mathematics (cs.DM) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Leaf Properties and Growth Measurement

paper · pdf · doi:10.48550/arxiv.2312.15338

openalex publication_date 2023/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This work presents and extends a known spigot-algorithm for computing square-roots, digit-by-digit, that is suitable for calculation by hand or an abacus, using only addition and subtraction. We offer an elementary proof of correctness for the original algorithm, then present a corresponding spigot-algorithm for computing cube-roots. Finally, we generalize the algorithm, so as to find r-th roots, and show how to optimize the algorithm for any r. The resulting algorithms require only integer addition and subtraction.

Related

• A Fast Algorithm for Determining the Existence and Value of Integer Roots of N
• A square root algorithm faster than Newton's method for multiprecision numbers, using floating-point arithmetic
• An iterative algorithm for approximating roots of integers
• Algorithm to Compute Squares of 1st N Natural Numbers Without Using Multiplication
• On Calculating Square Roots in GF(p)