Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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.

(defn iter-sqrt [n]
(if (< n 2)
0
(let [l2 (Math/log 2)]
(long (inc (Math/floor (/ (Math/log (/ (Math/log n) l2)) l2)))))))
(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)))))
(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)))))
(defn iter-sqrt
([n]
(iter-sqrt n 0))
([n acc]
(if (< n 2)
acc
(recur (Math/pow n 1/2) (inc acc)))))
(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))))
;; 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))))
(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)))))
(defn iter-sqrt [n]
(let [nth-pow (iterate #(* % %) 2N)]
(count (take-while #(>= n %) nth-pow))))
;; 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)))))
(defn iter-sqrt [n]
(->> n (iterate #(Math/sqrt %)) (take-while #(<= 2.0 %)) count))
(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)))
@bfortz
Copy link

bfortz commented Jun 26, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment