Approximate Squaring
June 8, 2021
Here is a function to perform approximate squaring:
(define (asq x)
(define (sq x) (* x (ceiling x)))
(let loop ((x (sq x)) (xs (list x)))
(if (integer? x)
(reverse (cons x xs))
(loop (sq x) (cons x xs)))))
> (asq 8/7)
(8/7 16/7 48/7 48)
> (asq 10/6)
(5/3 10/3 40/3 560/3 104720/3 3655461040/3
1484710602474311520)
And here we build a table of iterations with a common denominator:
(define (asq-table d)
(do ((n (+ d 1) (+ n 1))) ((= n (+ d d)))
(let ((xs (asq (/ n d))))
(display n) (display " ")
(display (- (length xs) 1)) (display " ")
(display (car (reverse xs))) (newline))))
> (asq-table 6)
7 2 7
8 2 8
9 1 3
10 6 1484710602474311520
11 3 220
> (asq-table 8)
9 4 2268
10 3 60
11 9 732080866432229367801083417675404689703681113835718829583758556242941523077452534455211024511178371450604417810705361050
12 1 3
13 2 13
14 2 14
15 2 15
Already you can see the chaotic nature of approximate squaring. If you want to see some really big numbers, look at the table for 5 or 7.
You can run the program at <a href=”https://ideone.com/31ZGUO”>https://ideone.com/31ZGUO</a>.
Programming Praxis 
Nifty little drill. I suppose some people have way too much time on their hands, writing papers like this!
Here is my take on this using Julia: https://pastebin.com/TtiyB0Wu
Here’s a Haskell version.
import Data.Ratio (denominator, numerator) import System.Environment (getArgs) approxSq :: Rational -> Rational approxSq x = x * toRational (ceiling x :: Integer) iterApproxSq :: Rational -> Integer iterApproxSq = numerator . head . iterateUntil isInteger approxSq where isInteger = (== 1) . denominator iterateUntil p f = dropWhile (not . p) . drop 1 . iterate f main :: IO () main = do rs <- getArgs mapM_ (print . iterApproxSq . read) rsLisp:
(defun approximate-square (number)
(loop
for n = number then (* n (ceiling n))
when (integerp n)
do (return n)))
Here’s a solution in Python.
def approx_squaring(n, d): while n % d: n *= (n + d - 1) // d return n // d print(approx_squaring(8, 7)) print(approx_squaring(10, 6)) print(approx_squaring(6, 5))Output:
Here’s a solution in C using GMP.
// $ gcc -o approx_squaring approx_squaring.c -lgmp #include <stdlib.h> #include <gmp.h> int main(int argc, char* argv[]) { if (argc != 3) return EXIT_FAILURE; mpz_t n; mpz_init(n); mpz_set_str(n, argv[1], 10); mpz_t d; mpz_init(d); mpz_set_str(d, argv[2], 10); mpz_t q; mpz_init(q); while (!mpz_divisible_p(n, d)) { mpz_cdiv_q(q, n, d); mpz_mul(n, n, q); } mpz_divexact(n, n, d); gmp_printf("%Zd\n", n); mpz_clear(n); mpz_clear(d); mpz_clear(q); return EXIT_SUCCESS; }Example usage:
[…] is to write a program that iterates approximate squaring. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments […]