How to optimize this haskell snippet

Question

Hi guys!

I'm trying to create a small module for doing decimal-based calculations. A number is stored as an integer mantisse, with a precision value specified by an int:

data APNum =
  { getMantisse :: Integer
  , getPrecision :: Int }

For instance:

APNum 123 0 -> 123
APNum 123 1 -> 1.23
APNum 123 2 -> 12.3
...

(negative precision is not allowed).

Now I wrote this function, which adjusts the precision automatically by stripping as many trailing zero's as possible:

autoPrecision :: APNum -> APNum
  autoPrecision x@(APNum m p) = if p > maxPrecision
    then autoPrecision $ setPrecision x maxPrecision
    else autoPrecision' m p where
    autoPrecision' m p = let (m',r) = m `divMod` 10 in
      if r /= 0 || p <= 0 then APNum m p else autoPrecision' m' (pred p)

(MaxPrecision and setPrecision are obvious, I think).

The problem is, this snippet has a very bad performance, specially n numbers with more then 10000 digits. Are there any simple optimizations?

Answer 1

You can use binary search to find the highest power of 10 which divides m, instead of trying all consecutive values.

import Numeric.Search.Range
import Data.Maybe

data APNum = APNum{getMantisse :: Integer, getPrecission :: Int} deriving Show

setPrecision (APNum m _) x = APNum m x
maxPrecission = 200000

findDiv x = pred $ fromJust $ searchFromTo (p x) 0 maxPrecission where
    p x n = x `mod` 10^n /= 0

autoPrecision :: APNum -> APNum
autoPrecision x@(APNum m p)
= if p > maxPrecission then
    autoPrecision $ setPrecision x maxPrecission else APNum m' p'
where d = min (findDiv m) p
        p' = p - d
        m' = m `div` 10^d

I'm using the binary-search package here which provides searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a. This should give you a big speedup.

Answer 2

also x mod 10 == 0 implies x mod 2 == 0, and that is cheaper to test for

Answer 3

Looks like even straightforward string operation is still faster:

maxPrecision = 2000000

autoPrecision (APNum m p) =
   let p' = min p maxPrecision
       (n',ds) =  genericDropNWhile (=='0') p' $ reverse $ show m
   in APNum (read $ reverse ds) n'
   where
     genericDropNWhile p n (x:xs) | n > 0 && p x = genericDropNWhile p (n-1) xs
     genericDropNWhile _ n xs = (n,xs)

Test with this:

main = print $ autoPrecision $ APNum (10^100000) (100000-3)

EDIT: Oops, faster only for numbers with lots of zeroes. Otherwise this double conversion is definitely slower.