2017-03-11

Parsing a number into digits

blogentry, programming

banner

title: Parsing a number into digits date: "2017-03-11" banner: ./images/featured-image-2017.03.11-parse.jpg published_at: "2017-03-11T17:00:43.000Z" tags: "blogentry, programming" author: Sung M. Kim

Featured Image - "Miss South Carolina Powerset Parse" by official_powerset, used under BY SA / Dropped Quality to 80% from original

I've run into situations where I had to parse a number into digits.

An easy way to do this is to convert a number into a string and returns a character array, and then convert each character into a number

When dealing with large sets of long numbers, it simply is not optimal.

There is a simple way to convert a number into digits, which requires a simple math.

Given an integer  "val =213", one might consider converting it to a string, breaking it to a character array and convert each character into an integer (it's so simple in LINQ, it's just tempting to implement it this way).

1private static List<int> GetDigitsUsingConversion(int val)2{3    return val.ToString().ToCharArray().Select(c => (int) c).ToList();4}

The cost of type conversion from an integer to a string, to an array, and then back to integer is too high.

Now let's take a look at another way using a simple math.

Given an integer 213, if you

  1. divide it by 1 and mod 10, you get 3
  2. divide it by 10 and mod 10, you get 1
  3. divide it by 100 and mod 10, you get 2

If you look at the returned result, it's each digit returned in reverse order. There is a useful data structure, for holding data in reverse order, Stack.

An algorithm is fairly simple.

While the given number is greater than 0, divide it by 10^digit, put the digit into a stack, and lastly return the stack as a list.

1private static List<int> GetDigits(int val)2{3	Stack<int> stack = new Stack<int>();4
5	int number = val;6	while (number > 0)7	{8		var digit = number % 10;9		stack.Push(digit);10
11		number /= 10;12	}13
14	return stack.ToList();15}

During each iteration, "number" is divided by 10 so it is equivalent to dividing by 10^digit.

I did a simple benchmarking (contrived but works for a simple demo) and the one requiring a type conversion to a string ran about 2x as long.

1private const int UPTO = 1000000;2
3public static void Main(string\[\] args)4{5int val = 123456789;6
7    Stopwatch watch = new Stopwatch();8
9    watch.Start();10    for (int i = 0; i < UPTO; i++)11    {12    	List<int> digits = GetDigits(val);13    }14    watch.Stop();15    Console.WriteLine("GetDigit took {0}ms", watch.ElapsedMilliseconds);16
17    watch.Start();18    for (int j = 0; j < UPTO; j++)19    {20    	List<int> digits2 = GetDigitsUsingConversion(val);21    }22
23    watch.Stop();24    Console.WriteLine("GetDigitsUsingConversion took {0}ms", watch.ElapsedMilliseconds);25
26}27
28Result:29
30GetDigit took 754ms31GetDigitsUsingConversion took 1468ms

The source code is available on GitHub.

Conclusion

By using simple math, you can extract digits from a number.

It requires no type conversion thus saving run time.