Instantly share code, notes, and snippets.

# ericnormand/00 iterated square root.md

Last active June 29, 2020 16:23

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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn iter-sqrt [n] (if (< n 2) 0 (let [l2 (Math/log 2)] (long (inc (Math/floor (/ (Math/log (/ (Math/log n) l2)) l2)))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn iter-sqrt ([n] (iter-sqrt n 0)) ([n acc] (if (< n 2) acc (recur (Math/pow n 1/2) (inc acc)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; 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))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn iter-sqrt [n] (let [nth-pow (iterate #(* % %) 2N)] (count (take-while #(>= n %) nth-pow))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; 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)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn iter-sqrt [n] (->> n (iterate #(Math/sqrt %)) (take-while #(<= 2.0 %)) count))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))

### KingCode commented Jun 23, 2020 • edited

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


### KingCode commented Jun 24, 2020 • edited

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

### bfortz commented Jun 26, 2020 • edited

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.