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