# What is this algorithm for converting strings into numbers called?

I've been doing some work in Parsec recently, and for my toy language I wanted multi-based fractional numbers to be expressible. After digging around in Parsec's source a bit, I found their implementation of a floating-point number parser, and copied it to make the needed modifications.

So I understand what this code does, and vaguely why (I haven't worked out the math fully yet, but I think I get the gist). But where did it come from? This seems like a pretty clever way to turn strings into floats and ints, is there a name for this algorithm? Or is it just something basic that's a hole in my knowledge? Did the folks behind Parsec devise it?

Here's the code, first for integers:

``````number' :: Integer -> Parser Integer
number' base =
do { digits <- many1 ( oneOf ( sigilRange base ))
; let n = foldl (\x d -> base * x + toInteger (convertDigit base d)) 0 digits
; seq n (return n)
}
``````

So the basic idea here is that `digits` contains the string representing the whole number part, ie `"192"`. The `foldl` converts each digit individually into a number, then adds that to the running total multiplied by the base, which means that by the end each digit has been multiplied by the correct factor (in aggregate) to position it.

The fractional part is even more interesting:

``````fraction' :: Integer -> Parser Double
fraction' base =
do { digits <- many1 ( oneOf ( sigilRange base ))
; let base' = fromIntegral base
; let f = foldr (\d x -> (x + fromIntegral (convertDigit base d))/base') 0.0 digits
; seq f (return f)
``````

Same general idea, but now a `foldr` and using repeated division. I don't quite understand why you add first and then divide for the fraction, but multiply first then add for the whole. I know it works, just haven't sorted out why.

Anyway, I feel dumb not working it out myself, it's very simple and clever looking at it. Is there a name for this algorithm? Maybe the imperative version using a loop would be more familiar?

-
It is called "algorithm for converting strings into numbers". How else would it be called? – BЈовић Apr 5 '12 at 14:48
Write one and name it for yourself, of course! – Michael K Apr 5 '12 at 14:58
+1 not sure why you got downvoted on a valid question that you obviously put some effort into – seand Apr 5 '12 at 15:25

It's not actually that clever, but rather just a consequence of how the decimal system works. It may look a bit unusual in Haskell because the loops are expressed as folds, but the basic algorithm is pretty much the most straightforward way one could possibly go about this (except for hard-coding digit factors, which is ugly and bad in so many ways).

So I doubt anyone has bothered naming this algorithm, really.

-

This is an application of Horner's method for evaluating polynomials. It is based on the observation that a number abcdef in a positional numeral system with base k is the polynomial `a*x^5+b*x^4+...+f*x^0` evaluated at `x=k`.

As to why there is an asymmetry between the integer and the fractional parts, this simply mirrors the asymmetry between the exponents 0, 1, 2, ... on the one side and -1, -2, ... without the zero on the other.

-

My Haskell is very rusty, but, from what I can see, this is the usual quick-and-easy method of converting a string to a floating-point number. Quick and easy, but not a good method for production code that needs accurate numbers. Each division for each digit in the fraction causes a potential loss of, IIRC, 1/2 of the least-significant bit of the mantissa in accuracy. I'm not familiar with the internals of Unix and Windows libraries, but I remember seeing the microfiche for portions of the VAX/VMS math libraries back in the 1980s and they used, again if I remember correctly, software-implemented 128-bit arithmetic (which was not supported at that time in the hardware) to ensure the accuracy of their results as computations progressed.

-