StackOverFlow while counting digits

Question

Hi,

I am trying to count the number of digits in a number in Clojure as follows: I get a StackOverflowError even for 2 digit numbers

(defn num-digits [n]
   (if (= 0 n)
   0
   (inc (num-digits (/ n 10)))))
(println (num-digits 93))

But if I replace / with unchecked-divide then it works for at least 93. But neither of the techniques works for:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

First, I would like to know how to perform division the C-style in Clojure. Whenever I do (/ x y) I get a Ratio and not a Integer. What is the way to do it?

Secondly, is there a way API to convert this Number into a vector of digits and call count on it.

Thanks,
Ajay G

Answer 1

According to this page, you can perform integer division in Clojure using quot:

(quot n 10)

Answer 2

Clojure attempts to "do the right thing" with numeric operations and never lose precision. so when you device say 17/10 the result is the fraction 17/10 (seventeen tenths) not 1. By default no information will be lost in any of the numerical operations. In cases like this you can explicitly throw away the extra precision with (quote x 10) or you can cast the result to an int (int (/ 17 10))

for the second question here's a little hack:

(count (str 257))

A good way to keep from blowing the stack with recursion in Clojure is to use other higher order functions instead of recursion.

(count (take-while pos? (iterate #(quot % 10) 257))))

Answer 3

There's no tail-call optimisation in Clojure. You have to use the recur special form.

E.g.:

(defn num-digits [n]
  (loop [n n
         cnt 0]
    (if (= 0 n)
      cnt
      (recur (quot n 10) (inc cnt)))))

But in answer to your second question: yes, and this is how:

(defn num-digits [n] (count (str n)))

Answer 4

This is why you're having a problem:

user> (take 10 (iterate #(/ % 10) 10923))

(10923 10923/10 10923/100 10923/1000 10923/10000 10923/100000 10923/1000000 10923/10000000 10923/100000000 10923/1000000000)

This is the fix:

user> (take 10 (iterate #(quot % 10) 10923))

(10923 1092 109 10 1 0 0 0 0 0)

This is the expression you're looking for:

user> (count (take-while #(not (zero? %)) (iterate #(quot % 10) 10923)))
5

This is cheating:

user> (count (str 10923))
5

This is the function you were trying to write (but careful, it will stack overflow for large numbers):

user> (defn num-digits [n]
        (if (= 0 n)
          0
          (inc (num-digits (quot n 10)))))

#'user/num-digits
user> (num-digits 10923)
5

However, it is up to the challenge:

user> (num-digits 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000)

158

This version of that function will not blow stack:

user> (defn num-digits-tail-recursion 
        ([n count]
           (if (= 0 n)
             count
             (recur (quot n 10) (inc count))))
        ([n] (num-digits-tail-recursion n 0)))
#'user/num-digits-tail-recursion
user> (num-digits-tail-recursion 10923)
5

All versions are interesting in their own way. Good question!