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&gt;.

Pages: 1 2

5 Responses to “Approximate Squaring”

  1. Zack said

    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

  2. Globules said

    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) rs
    
    $ ./approxsq 8%7 3%2 5%2 7%2 9%2 11%2 13%2 15%2 17%2 19%2 3%3 4%3 5%3
    48
    3
    60
    14
    268065
    33
    2093
    60
    1204154941925628
    95
    1
    8
    1484710602474311520
    
  3. Jared said

    Lisp:
    (defun approximate-square (number)
    (loop
    for n = number then (* n (ceiling n))
    when (integerp n)
    do (return n)))

    > (mapcar #'approximate-square '(8/7 3/2 5/2 7/2 9/2 11/2 13/2 15/2 17/2 19/2 3/3 4/3 5/3))
    (48 3 60 14 268065 33 2093 60 1204154941925628 95 1 8 1484710602474311520)
    
  4. Daniel said

    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:

    48
    1484710602474311520
    9532960047385704656...9010186950239453184
    
  5. Daniel said

    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:

    $ ./approx_squaring 8 7
    48
    $ ./approx_squaring 10 6
    1484710602474311520
    $ ./approx_squaring 6 5
    9532960047385704656...9010186950239453184
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: