Databases
StackOverflow2013
Postsdbo
POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
    primarykey
    data
    text
    <p>While solving a problem, I had to calculate the divisors of a number. I have two implementations that produce all divisors > 1 for a given number.</p> <p>The first is using simple recursion:</p> <pre><code>divisors :: Int64 -&gt; [Int64] divisors k = divisors' 2 k where divisors' n k | n*n &gt; k = [k] | n*n == k = [n, k] | k `mod` n == 0 = (n:(k `div` n):result) | otherwise = result where result = divisors' (n+1) k </code></pre> <p>The second one uses list processing functions from the Prelude:</p> <pre><code>divisors2 :: Int64 -&gt; [Int64] divisors2 k = k : (concatMap (\x -&gt; [x, k `div` x]) $! filter (\x -&gt; k `mod` x == 0) $! takeWhile (\x -&gt; x*x &lt;= k) [2..]) </code></pre> <p>I find that the first implementation is faster (I printed the whole list returned, so that no part of the result remains unevaluated due to laziness). The two implementations produce differently ordered divisors, but that is not a problem for me. (In fact, if k is a perfect square, the square root is output twice in the second implementation - again not a problem).</p> <p>In general are such recursive implementations faster in Haskell? Also, I would appreciate any pointers to make either of these codes faster. Thanks!</p> <p>EDIT:</p> <p>Here is the code I am using to compare these two implementations for performance: <a href="https://gist.github.com/3414372" rel="nofollow">https://gist.github.com/3414372</a></p> <p>Here are my timing measurements:</p> <p><strong>Using divisor2 with strict evaluation ($!)</strong></p> <pre><code>$ ghc --make -O2 div.hs [1 of 1] Compiling Main ( div.hs, div.o ) Linking div ... $ time ./div &gt; /tmp/out1 real 0m7.651s user 0m7.604s sys 0m0.012s </code></pre> <p><strong>Using divisors2 with lazy evaluation ($):</strong></p> <pre><code>$ ghc --make -O2 div.hs [1 of 1] Compiling Main ( div.hs, div.o ) Linking div ... $ time ./div &gt; /tmp/out1 real 0m7.461s user 0m7.444s sys 0m0.012s </code></pre> <p><strong>Using function divisors</strong></p> <pre><code>$ ghc --make -O2 div.hs [1 of 1] Compiling Main ( div.hs, div.o ) Linking div ... $ time ./div &gt; /tmp/out1 real 0m7.058s user 0m7.036s sys 0m0.020s </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USdonatello
    1. USdonatello
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
      1. USAbizern
      1. VTFavorite
    3. VO
      singulars
      1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think it has something to do with Haskell being Tail Call Optimised, so recursion isn't as big a hit as it would be with other languages. But I don't know **exactly** how this helps, so I'm leaving this as a comment instead of an answer.
      singulars
      1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
      1. USAbizern
    2. CONope, tail call optimization does not generally affect the performance of a Haskell program, and tail call optimization is very seldom even used by the compiler in Haskell, since it is a lazily evaluated language and doesn't need it most of the time.
      singulars
      1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
      1. USdflemstr
    3. CO@dflemstr As I said - I wasn't sure. Thanks for putting me right :)
      singulars
      1. POTwo simple codes to generate divisors of a number. Why is the recursive one faster?
      1. USAbizern
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload