integer-conversion-0.1.1: Conversion from strings to Integer

Safe Haskell | None
Language | Haskell2010

Data.Integer.Conversion

Description

The naive left fold to convert digits to integer is quadratic as multiplying (big) `Integer`s 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).

Synopsis

- textToInteger :: Text -> Integer
- byteStringToInteger :: ByteString -> Integer
- stringToInteger :: String -> Integer
- stringToIntegerWithLen :: String -> Int -> Integer

# Documentation

textToInteger :: Text -> Integer Source #

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 Source #

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 Source #

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 Source #

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