How to count number of digits?

Question

1. (CountDigits n) takes a positive integer n, and returns the number of digits it contains. e.g.,

   (CountDigits 1) → 1
   (CountDigits 10) → 2
   (CountDigits 100) → 3
   (CountDigits 1000) → 4
   (CountDigits 65536) → 5
   

I think I'm supposed to use the remainder of the number and something else but other then that im really lost. what i tried first was dividing the number by 10 then seeing if the number was less then 1. if it was then it has 1 digit. if it doesnt then divide by 100 and so on and so forth. but im not really sure how to extend that to any number so i scrapped that idea

(define (num-digits number digit) (if (= number digit 0) 1

Answer 1

Stumbled across this and had to provide the log-based answer:

(define (length n)
    (+ 1 (floor (/ (log n) (log 10))))
)

Edit for clarity: This is an O(1) solution that doesn't use recursion. For example, given

(define (fact n)
  (cond
    [(= n 1) 1]
    [else (* n (fact (- n 1)))]
  )
)

(define (length n)
  (+ 1 (floor (/ (log n) (log 10))))
)

Running (time (length (fact 10000))) produces

cpu time: 78 real time: 79 gc time: 47
35660.0

Indicating that 10000! produces an answer consisting of 35660 digits.

Answer 2

I know this is old but for future reference to anyone who finds this personally I'd write it like this:

(define (count-digits n acc)
  (if (< n 10)
    (+ acc 1)
    (count-digits (/ n 10) (+ acc 1))))

The difference being that this one is tail-recursive and will essentially be equivalent to an iterative function(and internally Racket's iterative forms actually exploit this fact.)

Using trace illustrates the difference:

(count-digits-taylor 5000000)
>(count-digits-taylor 5000000)
> (count-digits-taylor 500000) 
> >(count-digits-taylor 50000)
> > (count-digits-taylor 5000)
> > >(count-digits-taylor 500)
> > > (count-digits-taylor 50)
> > > >(count-digits-taylor 5)
< < < <1
< < < 2
< < <3
< < 4
< <5
< 6
<7
7

(count-digits 5000000 0)
>(count-digits 5000000 0)
>(count-digits 500000 1)
>(count-digits 50000 2)
>(count-digits 5000 3)
>(count-digits 500 4)
>(count-digits 50 5)
>(count-digits 5 6)
<7
7

For this exercise this doesn't matter much, but it's a good style to learn. And of course since the original post asks for a function called CountDigits which only takes one argument (n) you'd just add:

(define (CountDigits n) 
  (count-digits n 0)) 

Answer 3

After some discussion in the comments, we figured out how to take a number n with x digits and to get a number with x-1 digits: divide by 10 (using integer division, i.e., we ignore the remainder). We can check whether a number only has one digit by checking whether it's less than 10. Now we just need a way to express the total number of digits in a number as a (recursive) function. There are two cases:

1. (base case) a number n less than 10 has 1 digit. So CountDigits(n) = 1.
2. (recursive case) a number n greater than 10 has CountDigits(n) = 1+CountDigits(n/10).

Now it's just a matter of coding this up. This sounds like homework, so I don't want to give everything away. You'll still need to figure out how to write the condition "n < 10" in Scheme, as well as "n/10" (just the quotient part), but the general structure is:

(define (CountDigits n)                       ; 1
  (if [n is less than 10]                     ; 2
      1                                       ; 3
      (+ 1 (CountDigits [n divided by 10])))) ; 4

An explanation of those lines, one at a time:

1. (define (CountDigits n) begins the definition of a function called CountDigits that's called like (CountDigits n).
2. In Racket, if is used to evaluate one expression, called the test, or the condition, and then to evaluate and return the value of one of the two remaining expressions. (if test X Y) evaluates test, and if test produces true, then X is evaluated and the result is returned, but otherwise Y is evaluated and the result is returned.
3. 1 is the value that you want to return when n is less than 10 (the base case above).
4. 1+CountDigits(n/10) is the value that you want to return otherwise, and in Racket (and Scheme, and Lisp in general) it's written as (+ 1 (CountDigits [n divided by 10])).

It will be a good idea to familiarize with the style of the Racket documentation, so I will point you to the appropriate chapter: 3.2.2 Generic Numerics. The functions you'll need should be in there, and the documentation should provide enough examples for you to figure out how to write the missing bits.