# 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? Commented Apr 5, 2012 at 14:48
• Write one and name it for yourself, of course! Commented Apr 5, 2012 at 14:58
• +1 not sure why you got downvoted on a valid question that you obviously put some effort into Commented Apr 5, 2012 at 15:25

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