383 - PurelyFunctional.tv Newsletter https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-383-replace-body-with-callback/

00 iterated square root.md

iterated square root

If you iteratively apply the square root, you will eventually get a number strictly less than two. Write a function that figures out how many times you have to apply the square root it results in a number less than two.

Examples

(iter-sqrt 1) ;=> 0 (since 1 is already less than 2)
(iter-sqrt 2) ;=> 1 (since the square root of 2 is less than 2)
(iter-sqrt 256) ;=> 4

Bonus: Write it in a way that uses stack frames and in a way that doesn't.

Thanks to this site for the challenge idea where it is considered Medium level in Python.

Email submissions to eric@purelyfunctional.tv before June 28, 2020. You can discuss the submissions in the comments below.

Bernard Fortz.clj

(defn iter-sqrt [n]
  (if (< n 2) 
    0
    (let [l2 (Math/log 2)]
      (long (inc (Math/floor (/ (Math/log (/ (Math/log n) l2)) l2)))))))

Daniel Gaspani.clj

(defn iter-sqrt-no-stack1 [n]
  (if (< n 2)
    0
    (->> (iterate #(Math/sqrt %) n)
         (take-while (partial < 2))
         (count)
         (inc))))

(defn iter-sqrt-no-stack2 [n]
  (if (< n 2)
    0
    (loop [n' n count 1]
      (let [result (Math/sqrt n')]
        (if (< result 2)
          count
          (recur result (inc count)))))))

(defn iter-sqrt-with-stack [n]
  (if (< n 2)
    0
    (+ 1 (iter-sqrt-with-stack (Math/sqrt n)))))

Eric Normand.clj

(defn iter-sqrt [n]
  (->> n
       (iterate #(Math/sqrt %))
       (take-while #(<= 2.0 %))
       count))

(defn iter-sqrt [n]
  (if (< n 2.0)
    0
    (inc (iter-sqrt (Math/sqrt n)))))

(defn iter-sqrt [n]
  (loop [n n count 0]
    (if (< n 2.0)
      count
      (recur (Math/sqrt n) (inc count)))))

Frantisek Kobzik.clj

(defn iter-sqrt
  ([n]
   (iter-sqrt n 0))
  ([n acc]
   (if (< n 2)
       acc
       (recur (Math/pow n 1/2) (inc acc)))))

JF Rompre.clj

(ns functional-tv-puzzles.-2020.iterated-sqroot-383)

(defn iter-sqrt- [n]
  (->> n (iterate #(Math/sqrt %))
       (take-while #(<= 2 %))
       count))

(defn iter-sqrt+ [n]
  (if (< n 2)
    0
    (inc (iter-sqrt+ (Math/sqrt n)))))

;; shell
(defn iter-sqrt [n & [use-stack?]]
  (if (neg? n)
    :invalid
    (let [impl (if use-stack? iter-sqrt+ iter-sqrt-)]
      (impl n))))

Mark Champine.clj

;; loop/recur
(defn iter-sqrt [n]
  (loop [v n ct 0] (if (< v 2.0) ct (recur (Math/sqrt v) (inc ct)))))

;; recursion
(defn iter-sqrt [n]
  (if (< n 2.0) 0 (inc (iter-sqrt (Math/sqrt n)))))

;; recursion w/ multi-arity
(defn iter-sqrt 
  ([n] (iter-sqrt n 0))
  ([n x] (if (< n 2.0) x (iter-sqrt (Math/sqrt n) (inc x)))))

;; iterate
(defn iter-sqrt [n]
  (count (take-while #(>= % 2.0) (iterate #(Math/sqrt %) n))))

Neil McCallum.clj

(defn iter-sqrt
  [n]
  "so this is the number of bits used in the radix 2 expression of the base 2 log"
  (-> n
      Math/log10
      (/ (Math/log10 2))
      Integer/toBinaryString
      count))

(defn iter-sqrt
  [n]
  (loop [c 0
         n n]
    (if (< n 2)
      c
      (recur (inc c) (Math/sqrt n)))))

ninjure.clj

(defn iter-sqrt [n]
  (let [nth-pow (iterate #(* % %) 2N)]
    (count (take-while #(>= n %) nth-pow))))

Paul A Roush.clj

;; Here's my first take on how to compute the
;; number of square-roots needed to get below 2:

(defn log2 [n]
  (/ (Math/log10 n) (Math/log10 2)))

(defn iter-sqrt [n]
  (if (< n 2)
    0
    (inc (int (log2 (log2 n))))))

;;
;; However, since you specified an "iterative" approach,
;; here's one that's iterative.
;;

(defn iter-sqrt
  ([n] (iter-sqrt 0 n))
  ([cnt n]
   (if (< n 2)
     cnt
     (recur (inc cnt) (Math/sqrt n)))))

Steffan Westcott.clj

(defn iter-sqrt [n]
  (->> n (iterate #(Math/sqrt %)) (take-while #(<= 2.0 %)) count))

Viktor P.clj

(defn iter-sqrt [n]
  (if (< n 2)
    0
    (inc (iter-sqrt (Math/sqrt n)))))

(defn iter-sqrt'
  [n]
  (letfn [(f [n acc]
            (if (< n 2)
              acc
              (recur (Math/sqrt n) (inc acc))))]
     (f n 0)))

(defn iter-sqrt [n]
  (let [nth-pow (iterate #(* % %) 2N)]
    (count (take-while #(>= n %) nth-pow))))

Here is a naive interpretation, followed by more sensible ones:

(defn iter-sqrt [n & [with-stack?]]
  (let [step (fn step [iter n]
               (let [n' (Math/sqrt n)]
                 (if (< n 2)
                   iter
                   (if with-stack?
                     (step (inc iter) n')
                     (recur (inc iter) n')))))]
    (step 0 n)))

(defn iter-sqrt- [n]
  (->> n (iterate #(Math/sqrt %))
       (take-while #(<= 2 %))
       count))

(defn iter-sqrt+ [n]
  (if (< n 2)
    0
    (inc (iter-sqrt+ (Math/sqrt n)))))

;; shell
(defn iter-sqrt [n & [use-stack?]]
  (let [impl (if use-stack? iter-sqrt+ iter-sqrt-)]
    (impl n)))

Properties test:

(ns .... (:require my_ns :as sut)
            [clojure.test.check.properties :as prop]
            [clojure.test.check.generators :as gen]
            [clojure.test.check.clojure-test :as tct :refer [defspec]]))

(let [alias-str "sut"
      sym (symbol (str alias-str "/iter-sqrt"))]
  (def iter-sqrt (resolve sym)))

(defn gen-opts 
  ([] (gen-opts {}))
  ([m]
   (merge {:infinite? false :NaN? false} m)))

(defn gen-doubles [& {:keys [min max]}] ;; min <= x < max
  (let [opts (gen-opts (merge 
                        (if min {:min min} {})
                        (if max {:max (- max (* 0.001 (rand)))} {})))]
    (gen/double* opts)))

(defspec result-is-impl-agnostic
  (prop/for-all [v (gen-doubles)]
                (= (iter-sqrt v) (iter-sqrt v :use-stack))))

(defn <2-after-exactly? [steps down-from]
  (let [[v>=2 v<2] 
        (drop (- steps 2) (repeatedly steps 
                             (let [a (atom down-from)]
                               (fn []
                                 (swap! a #(Math/sqrt %))))))]
    (and v<2 v>=2 
         (>= v>=2 2)
         (< v<2 2)
         (pos? v<2))))

(defspec is-0-for-input<2
  (prop/for-all [v (gen-doubles :max 2.0)]
                (zero? (iter-sqrt v))))

(defspec is-1-for-range-2-4
  (prop/for-all [v (gen-doubles :min 2.0 :max 4.0)]
                (= 1 (iter-sqrt v))))

(defspec is-accurate-for-4+
  (prop/for-all [v (gen-doubles :min 4.0)]
                (<2-after-exactly? (iter-sqrt v) v))

Since iter-sqrt must use some logic to test for a threshold, and several solutions here (including mine) use a smaller type threshold value to check the floating point value resulting from Math/sqrt, there is a risk of logic-spoling numeric type friction, e.g.:

(< 2 2.0)
;; => false
(> 2 2.0)
;; => false
(= 2 2.0)
;; => false
(>= 2 2.0)
;; => true ;; ?? Neither of > or =, but yes to both!!

Of course, since 2 and 2.0 are in different numeric types, they can't be compared reliably. I was using as a logic gate (if (< n 2)... in my own solution, but should have been (if (< n 2.0) ...).(In functions that accept any numeric type where the input is compared to a reference value, probably the best approach is to up cast (non-lossy cast) the input to that of the largest accepted type.)

The math underlying my solution (Bernard Fortz.clj): the square root of n is so taking k times the square root gives . We want to find k such that . Taking the log in base n, this leads to , or . Taking the log again, we get . The rest of the code follows easily from appropriate rounding and dealing with the degenerate case n < 2. This leads a constant time solution.