Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
8  
It is called "algorithm for converting strings into numbers". How else would it be called? –  BЈовић Apr 5 '12 at 14:48
1  
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
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.