Monday, June 14, 2010

Digits

We’ve had a lot of problems involving digit manipulation and so far have implemented ad-hoc string parsing solutions.  But this approach is generally pretty slow.  For primitive integer types (int32 and int64), we can gain two to three times speed increase using arithmetic methods.  On the other hand, generating a sequence of digits from a bigint is actually faster using the former method.  The following module provides type optimized conversions between digit sequences and numbers.

    module Digits =
        //at least twice as fast as fastParse
        let fromInt64 (n:int64) =
            if n = 0L then Seq.singleton 0
            else
                let mutable n = if n < 0L then (abs n) else n
                let mutable powten = 0
                
                while (n/(pown 10L powten) >= 10L) do
                    powten <- powten+1
                    
                let darr = Array.create (powten+1) 0
                let mutable i = 0
                while (powten >= 0) do
                    let d = n/(pown 10L powten)
                    darr.[i] <- d |> int
                    n <- n - d*(pown 10L powten)
                    i <- i + 1
                    powten <- powten-1
                    
                Seq.readonly darr
                            
        let fromInt (n:int) = fromInt64 (n |> int64)
        
        ///parse a positive or negative number string.  if other characters (besides leading '-'
        ///and integers) are present results will be unpredictable.
        let uncheckedParse (nstr:string) =
            if nstr.[0] = '-' then //fast with least num checks
                nstr
                |> Seq.skip 1
                |> Seq.map (fun c -> (c |> int) - 48)
                |> Seq.cache
            else
                nstr
                |> Seq.map (fun c -> (c |> int) - 48)
                |> Seq.cache
        
        ///filter out non-digits
        let parse nstr = 
            uncheckedParse nstr
            |> Seq.filter (fun n -> n >= 0 && n <= 10)
        
        //not sure if using fromString here is faster than direct map string |> parse
        let fromBigInt (n:bigint) = n |> string |> uncheckedParse
                
        let toInt64 (digs:seq<int>) = 
            digs
            |> Seq.fold 
                (fun (e, sum) d -> let e = e-1 in (e, Checked.(+) sum ((d |> int64)*(pown 10L e))))
                (Seq.length digs, 0L)
            |> snd
                    
        ///note: (System.Int32.MinValue) |> Digits.fromInt |> Digits.toInt results
        ///in overflow exceptions since abs(int.MinValue) > int.MaxValue
        let toInt (digs:seq<int>) = 
            digs
            |> Seq.fold 
                (fun (e, sum) d -> let e = e-1 in (e, Checked.(+) sum (d*(pown 10 e))))
                (Seq.length digs, 0)
            |> snd
        
        open System.Text
        let toBigInt (digs:seq<int>) = 
            bigint.Parse(
                digs 
                |> Seq.fold (fun (sb:StringBuilder) d -> ignore <| sb.Append(d) ; sb) (StringBuilder())
                |> string
            ) //not sure if actually fast for bigint

No comments:

Post a Comment