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).

Documentation

textToInteger :: 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.

>>> textToInteger "123456789"
123456789

For non-decimal inputs some nonsense is calculated

>>> textToInteger "foobar"
6098556

byteStringToInteger :: ByteString -> Integer

Convert ByteString to Integer.

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

>>> byteStringToInteger "123456789"
123456789

For non-decimal inputs some nonsense is calculated

>>> byteStringToInteger "foobar"
6098556

stringToInteger :: String -> Integer

Convert String to Integer.

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

>>> stringToInteger "123456789"
123456789

For non-decimal inputs some nonsense is calculated

>>> stringToInteger "foobar"
6098556

stringToIntegerWithLen :: String -> Int -> Integer

Convert String to Integer when you know the length beforehand.

>>> stringToIntegerWithLen "123" 3
123

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

>>> stringToIntegerWithLen (replicate 40 '0' ++ "123") 45
12300

>>> stringToIntegerWithLen (replicate 40 '0' ++ "123") 44
1200

>>> stringToIntegerWithLen (replicate 40 '0' ++ "123") 42
12