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)))
@souenzzo
Copy link

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
Copy link

ninjure commented Jun 22, 2020

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

@KingCode
Copy link

KingCode commented Jun 22, 2020

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
Copy link

KingCode commented Jun 23, 2020

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
Copy link

KingCode commented Jun 24, 2020

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