Moduleinteger-conversion-0.1.1Haskell2010

Data.Integer.Conversion

The naive left fold to convert digits to integer is quadratic as multiplying (big) Integers is not a constant time operation.

This module provides sub-quadratic algorithm for conversion of Text or ByteString into Integer.

For example for a text of 262144 9 digits, fold implementation takes 1.5 seconds, and textToInteger just 26 milliseconds on my machine. Difference is already noticeable around 100-200 digits.

In particular read is correct (i.e. faster) than List.foldl' (better complexity), stringToInteger is a bit faster than read (same complexity, lower coeffcient).

4 values

Packageinteger-conversion-0.1.1
Exports4
LanguageHaskell2010
LicenceBSD-3-Clause
SourceConversion.hs

valuetextToInteger :: Text -> Integer

Convert Text to Integer.

Semantically same as T.foldl' (acc c -> acc * 10 + toInteger (ord c - 48)) 0, but this is more efficient.

Example1 expression

>>> textToInteger "123456789"123456789

For non-decimal inputs some nonsense is calculated

Example1 expression

>>> textToInteger "foobar"6098556

valuebyteStringToInteger :: ByteString -> Integer

Convert ByteString to Integer.

Semantically same as BS.foldl' (acc c -> acc * 10 + toInteger c - 48) 0, but this is more efficient.

Example1 expression

>>> byteStringToInteger "123456789"123456789

For non-decimal inputs some nonsense is calculated

Example1 expression

>>> byteStringToInteger "foobar"6098556

valuestringToInteger :: String -> Integer

Convert String to Integer.

Semantically same as List.foldl' (acc c -> acc * 10 + toInteger c - 48) 0, but this is more efficient.

Example1 expression

>>> stringToInteger "123456789"123456789

For non-decimal inputs some nonsense is calculated

Example1 expression

>>> stringToInteger "foobar"6098556

valuestringToIntegerWithLen :: String -> Int -> Integer

Convert String to Integer when you know the length beforehand.

Example1 expression

>>> stringToIntegerWithLen "123" 3123

If the length is wrong, you may get wrong results. (Simple algorithm is used for short strings).

Example1 expression

>>> stringToIntegerWithLen (replicate 40 '0' ++ "123") 4512300

Example1 expression

>>> stringToIntegerWithLen (replicate 40 '0' ++ "123") 441200

Example1 expression

>>> stringToIntegerWithLen (replicate 40 '0' ++ "123") 4212