Algorithm that converts numeric amount into Englis

Question

What is the most efficient way to convert numeric amount into English words

e.g. 12 to twelve 127 to one hundred twenty-seven

Answer 1

That didn't take long. This is an implementation written in Java.

http://snippets.dzone.com/posts/show/3685

Code

public class IntToEnglish {
    static String[] to_19 = { "zero",  "one",   "two",  "three", "four",   "five",   "six",
        "seven", "eight", "nine", "ten",   "eleven", "twelve", "thirteen",
        "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
    static String[] tens  = { "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
    static String[] denom = { "",
        "thousand",     "million",         "billion",       "trillion",       "quadrillion",
        "quintillion",  "sextillion",      "septillion",    "octillion",      "nonillion",
        "decillion",    "undecillion",     "duodecillion",  "tredecillion",   "quattuordecillion",
        "sexdecillion", "septendecillion", "octodecillion", "novemdecillion", "vigintillion" };

    public static void main(String[] argv) throws Exception {
        int tstValue = Integer.parseInt(argv[0]);
        IntToEnglish itoe = new IntToEnglish();
        System.out.println(itoe.english_number(tstValue));
        /* for (int i = 0; i < 2147483647; i++) {
            System.out.println(itoe.english_number(i));
        } */
    }
    // convert a value < 100 to English.
    private String convert_nn(int val) throws Exception {
        if (val < 20)
            return to_19[val];
        for (int v = 0; v < tens.length; v++) {
            String dcap = tens[v];
            int dval = 20 + 10 * v;
            if (dval + 10 > val) {
                if ((val % 10) != 0)
                    return dcap + "-" + to_19[val % 10];
                return dcap;
            }        
        }
        throw new Exception("Should never get here, less than 100 failure");
    }
    // convert a value < 1000 to english, special cased because it is the level that kicks 
    // off the < 100 special case.  The rest are more general.  This also allows you to
    // get strings in the form of "forty-five hundred" if called directly.
    private String convert_nnn(int val) throws Exception {
        String word = "";
        int rem = val / 100;
        int mod = val % 100;
        if (rem > 0) {
            word = to_19[rem] + " hundred";
            if (mod > 0) {
                word = word + " ";
            }
        }
        if (mod > 0) {
            word = word + convert_nn(mod);
        }
        return word;
    }
    public String english_number(int val) throws Exception {
        if (val < 100) {
            return convert_nn(val);
        }
        if (val < 1000) {
            return convert_nnn(val);
        }
        for (int v = 0; v < denom.length; v++) {
            int didx = v - 1;
            int dval = new Double(Math.pow(1000, v)).intValue();
            if (dval > val) {
                int mod = new Double(Math.pow(1000, didx)).intValue();
                int l = val / mod;
                int r = val - (l * mod);
                String ret = convert_nnn(l) + " " + denom[didx];
                if (r > 0) {
                    ret = ret + ", " + english_number(r);
                }
                return ret;
            }
        }
        throw new Exception("Should never get here, bottomed out in english_number");
    }
}

Answer 2

Start by solving 1-99, using a list of numbers for 1-20, and then 30, 40, ..., 90. Then add hundreds to get 1-999. Then use that routine to give the number of each power of 1,000 for as high as you want to go (I think the highest standard nomenclature is for decillion, which is 10^33).

One slight caveat is that it's a little tricky to get the blanks right in all cases if you're trying to start and end without an excess blank. The easy solution is to put a blank after every word, and then strip off the trailing blank when you're all done. If you try to be more precise while building the string, you're likely to end up with missing blanks or excess blanks.

Answer 3

.) make a library of all numbers & positions (e.g. 1 has other notation than 10, another than 100 etc) .) make a list of exceptions (e.g. for 12) and be aware, that in your algorythm, the same exception are for 112, 1012 etc.

if you want even more speed, make a cached set of numbers that you need.

Answer 4

This solution doesn't attempt to account for trailing spaces, but it is pretty fast.

typedef const char* cstring;
using std::string;
using std::endl;
std::ostream& GetOnes(std::ostream &output, int onesValue)
{
    cstring ones[] = { "zero", "one", "two", "three", "four", "five", "six", 
           "seven", "eight", "nine" };
    output << ones[onesValue];
    return output;
}

std::ostream& GetSubMagnitude(std::ostream &output, int subMagnitude)
{
    cstring tens[] = { "zeroty", "ten", "twenty", "thirty", "fourty", "fifty", 
         "sixty", "seventy", "eighty", "ninety"};
    if (subMagnitude / 100 != 0)
    {       
        GetOnes(output, subMagnitude / 100) << " hundred ";
        GetSubMagnitude(output, subMagnitude - subMagnitude / 100 * 100);
    }
    else
    {
        if (subMagnitude >= 20)
        {
            output << tens[subMagnitude / 10] << " ";
            GetOnes(output, subMagnitude - subMagnitude / 10 * 10);
        }
        else if (subMagnitude >= 10)
        {
            cstring teens[] = { "ten", "eleven", "twelve", "thirteen",
                        "fourteen", "fifteen", "sixteen", "seventeen", 
                         "eighteen", "nineteen" };
            output << teens[subMagnitude - 10] << " ";
        }
        else 
        {
            GetOnes(output, subMagnitude) << " ";
        }
    }
    return output;
}

std::ostream& GetLongNumber(std::ostream &output, double input)
{
    cstring magnitudes[] = {"", "hundred", "thousand", "million", "billion", 
                           "trillion"};
    double magnitudeTests[] = {1, 100.0, 1000.0, 1000000.0, 1000000000.0, 
                           1000000000000.0 };
    int magTestIndex = 0;
    while (floor(input / magnitudeTests[magTestIndex++]) != 0);
    magTestIndex -= 2;
    if (magTestIndex >= 0) 
    {
        double subMagnitude = input / magnitudeTests[magTestIndex];
        GetSubMagnitude(output, (int)subMagnitude);
        if (magTestIndex) {
            output << magnitudes[magTestIndex] << " ";
            double remainder = input - (floor(input / 
                        magnitudeTests[magTestIndex]) * 
                        magnitudeTests[magTestIndex]);
            if (floor(remainder) > 0) 
            {
                GetLongNumber(output, remainder);
            }
        }
    }
    else
    {
        output << "zero";
    }
    return output;
}

Answer 5

One way to accomplish this would be to use look up tables. It would be somewhat brute force, but easy to setup. For instance, you could have the words for 0-99 in one table, then a table for tens, hundreds, thousands, etc. Some simple math will give you the index of the word you need from each table.

Answer 6

This link provides a detailed explanation of what looks to be a nice approach: http://www.blackwasp.co.uk/NumberToWords.aspx