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