{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 iterated square root.md

Last active Jun 29, 2020

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

### souenzzo commented Jun 22, 2020

(letfn [(stop? [x]
(>= (int x) 2))
(sqrt [x] (Math/sqrt x))
(iter-sqrt-stackless
[x]
(loop [x x
n 0]
(if (stop? x)
(recur (sqrt x)
(inc n))
n)))
(iter-sqrt-stack
[x]
(count (take-while
stop?
(iterate sqrt x))))]

(map (juxt iter-sqrt-stack
iter-sqrt-stackless)
[1 2 256]))

### ninjure commented Jun 22, 2020

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

### KingCode commented Jun 22, 2020 • edited

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


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