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)))

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.