4
\$\begingroup\$

Inspired by this question on Stack Overflow, I wrote a function that returns the length of a list made of numbers that are divisible by their own sum of digits inside a range:

-- Returns the digits of a positive integer as a list, in reverse order.
-- This is slightly more efficient than in forward order.
digitsRev :: Int -> [Int]
digitsRev i = case i of
    0 -> []
    _ -> lastDigit : digitsRev rest
where (rest, lastDigit) = quotRem i 10

-- Returns the digits of a positive integer as a list.
digits :: Int -> [Int]
digits = reverse . digitsRev

-- Returns the sum of digits of a positive integer
sumDigits :: Int -> Int
sumDigits = sum . digits

-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise.
isDivisibleSumDigits :: Int -> Bool
isDivisibleSumDigits n = n `mod` sumDigits n == 0

-- Returns a range of positive integers in which every element is divisible by 
-- the sum of it's digits. Includes the end of the range.
rangeDivisibleSumDigits :: Int -> Int -> [Int]
rangeDivisibleSumDigits range_start range_end =
    [n | n <- [range_start..range_end], isDivisibleSumDigits n == True]

-- Returns the length of the list returned by rangeDivisibleSumDigits
lengthRangeDivisibleSumDigits :: Int -> Int -> Int
lengthRangeDivisibleSumDigits range_start range_end = 
    length $ rangeDivisibleSumDigits range_start range_end

Then I used this function inside a main function, like this:

main = putStrLn $ show $ lengthRangeDivisibleSumDigits 1 10000000

According to the file generated by profiling the program (compiling like this: ghc -prof -fprof-auto -rtsopts Main.hs and executing like this: ./Main +RTS -p) it took 14.36 seconds to execute main. That's slow.

Do you have ideas on a faster way to perform the task carried out by this function?

Edit

Thanks to @bisserlis 's answer below, now the code reads:

-- Returns the digits of a positive integer as a list.
digits :: Int -> [Int]
digits = map digitToInt . show

-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise
isDivisibleSumDigits :: Int -> Bool
isDivisibleSumDigits n = n `mod` (sum (digits n)) == 0

-- Returns a range of positive integers in which every element is divisible by 
-- the sum of it's digits. Includes the end of the range.
rangeDivisibleSumDigits :: Int -> Int -> [Int]
rangeDivisibleSumDigits start end = filter isDivisibleSumDigits [start..end]
\$\endgroup\$
4
\$\begingroup\$

Compile without profiling, but with optimizations turned on.

bissbook:divSumDigits bisserlis$ ghc -prof -fprof-auto -rtsopts original.hs
[1 of 1] Compiling Main             ( original.hs, original.o )
Linking original ...
bissbook:divSumDigits bisserlis$ ./original +RTS -s
806095
  44,577,697,768 bytes allocated in the heap
      81,431,504 bytes copied during GC
          62,504 bytes maximum residency (2 sample(s))
          23,392 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     85945 colls,     0 par    0.48s    0.57s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time   22.36s  ( 22.79s elapsed)
  GC      time    0.48s  (  0.57s elapsed)
  RP      time    0.00s  (  0.00s elapsed)
  PROF    time    0.00s  (  0.00s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time   22.85s  ( 23.35s elapsed)

  %GC     time       2.1%  (2.4% elapsed)

  Alloc rate    1,993,498,737 bytes per MUT second

  Productivity  97.9% of total user, 95.8% of total elapsed

bissbook:divSumDigits bisserlis$ rm *.hi *.o
bissbook:divSumDigits bisserlis$ ghc -O2 original.hs
[1 of 1] Compiling Main             ( original.hs, original.o )
Linking original ...
bissbook:divSumDigits bisserlis$ ./original +RTS -s
806095
  12,176,087,768 bytes allocated in the heap
       4,273,680 bytes copied during GC
          44,416 bytes maximum residency (2 sample(s))
          21,120 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     23449 colls,     0 par    0.09s    0.11s     0.0000s    0.0001s
  Gen  1         2 colls,     0 par    0.00s    0.00s     0.0002s    0.0002s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    2.87s  (  2.93s elapsed)
  GC      time    0.09s  (  0.11s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    2.96s  (  3.04s elapsed)

  %GC     time       3.0%  (3.7% elapsed)

  Alloc rate    4,237,427,802 bytes per MUT second

  Productivity  97.0% of total user, 94.6% of total elapsed

(Note the Total time lines, 22.85s and 2.96s.)


I can't appreciably increase the performance any further, but I do have a couple stylistic notes.

Data.Char provides a function digitToInt :: Char -> Int, which makes writing digits much easier.

import Data.Char (digitToInt)

digits :: Int -> [Int]
digits = map digitToInt . show

No need to use list comprehensions and boolean double-checking in rangeDivisibleSumDigits, just write it as a filter on the range.

rangeDivisibleSumDigits :: Int -> Int -> [Int]
rangeDivisibleSumDigits start end = filter isDivisibleSumDigits [start..end]

sumDigits and lengthRangeDivisibleSumDigits are unnecessary functions, their names are pretty much as long as their implementations! They clutter up the top-level, they don't do anything surprising or interesting, I'd just use their implementations wherever you need to instead of adding another function to your mental burden.

\$\endgroup\$
2
  • \$\begingroup\$ Stylistic notes are always appreciated. Do you have any ideas on the algorithms part? \$\endgroup\$ – Marcus Vinícius Monteiro Apr 1 '15 at 2:42
  • 1
    \$\begingroup\$ Actually this would be a perfect problem for parallelization, which should give you a linear speedup in the number of processors. I'd have to pull down my copy of Parallel and Concurrent Programming in Haskell for a refresher before taking a stab at it though. \$\endgroup\$ – bisserlis Apr 1 '15 at 3:21
1
\$\begingroup\$

Little addition to bisserlis answer.

It's not necessarily convert a number to a string (or list) to evaluate sum of digits, so try to rewrite your new code as:

-- Returns the sum of digits of a positive integer
sumDigits :: Int -> Int
sumDigits n = let (rest,lastDigit) = quotRem n 10 in if n == 0 then 0 else lastDigit + sumDigits rest

-- Returns True if a number is divisible by the sum of it's digits and False
-- otherwise
isDivisibleSumDigits :: Int -> Bool
isDivisibleSumDigits n = n `rem` (sumDigits n) == 0
\$\endgroup\$
2
  • \$\begingroup\$ Your code didn't work as it was written. I've modified it slightly to this sumDigits :: Int -> Int sumDigits n = if n == 0 then 0 else lastDigit + sumDigits rest where (lastDigit, rest) = quotRem n 10, but my system started to slow down when I ran it, so I stopped the execution. \$\endgroup\$ – Marcus Vinícius Monteiro Apr 1 '15 at 10:05
  • \$\begingroup\$ Oh! I'm sorry, my code has mistake due to my experiments with it. True line is sumDigits n = let (rest,lastDigit) = quotRem n 10 in if n == 0 then 0 else lastDigit + sumDigits rest. Your modification is also right. \$\endgroup\$ – Alexander Razorenov Apr 1 '15 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.