string to int conversion

January 30, 2012, 8:22 pm

I was recently asked to write a string to int conversion function (without using library functions). I initially came up with a solution using the pow function (which is quite expensive). I had a think about it and found there were a surprising number of solutions. Briefly I came up with the following methods:

Method	Summary
Pow	my initial pow based solution (after converting a position to an in calculating 10^val)
Mul	Rather than using pow generating powers of 10 in the loop (multiplier = multipler*10)
Table	Just use a lookup table for the multipliers
Case	More of less the same as table, but encode the table in a switch statement (very ugly!)

Results are probably compiler/CPU/platform dependent. But on my Atom Z530 (1.6GHz) based netbook using GCC 4.3.3 I obtained the following results when performing the conversion 10 million times:

Method	User time
Pow	43.67s
Mul	28.21s
Table	28.22s
Case	29.13s

There’s a big difference between the pow method and the others, but I was reasonably surprised that multiplier and table based methods performed similarly. It would be interesting to look at the assembler generated for these.

For reference, source code follows (note I sum and output the converted values to prevent the call to string_to_int from being optimised away). I was slightly concerned that something funky /might/ be going on in string::size() however benchmarked with this in and outside the loop and didn’t observe any difference. Note: Following programs don’t process signs, but in terms of benchmarking I don’t believe this should be relevant.

Pow:

#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
 
int string_to_int(string s) {
 
  int output=0;
 
  for(int n=0;n<s.size();n++) {
    int cval = s[n]-'0';
    output += cval*pow(10,s.size()-n-1);
  }
 
  return output;
}
 
int main() {
 
  // Simple tests
  cout << "1 is: " << string_to_int("1") << endl;
  cout << "10 is: " << string_to_int("10") << endl;
  cout << "14532 is: " << string_to_int("14532") << endl;
 
  int rsum=0;
  for(int i=0;i<10000000;i++) {
    string s;
    int numlen = rand()%11;
    for(int n=0;n<numlen;n++) {
      int rval;
      if((numlen==10) && (n==0)) { rval = rand()%2;  }
                           else  { rval = rand()%10; }
      s.push_back('0'+rval);
    }
    int v = string_to_int(s);
    rsum += v;
  }
  cout << rsum << endl;
}

Mul:

#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
 
int string_to_int(string s) {
 
  int output=0;
 
  int mul=1;
  for(int n=s.size()-1;n>=0;n--) {
    int cval = s[n]-'0';
    output += cval*mul;
    mul = mul * 10;
  }
 
  return output;
}
 
int main() {
 
  // Simple tests
  cout << "1 is: " << string_to_int("1") << endl;
  cout << "10 is: " << string_to_int("10") << endl;
  cout << "14532 is: " << string_to_int("14532") << endl;
 
  int rsum=0;
  for(int i=0;i<10000000;i++) {
    string s;
    int numlen = rand()%11;
    for(int n=0;n<numlen;n++) {
      int rval;
      if((numlen==10) && (n==0)) { rval = rand()%2;  }
                           else  { rval = rand()%10; }
      s.push_back('0'+rval);
    }
    int v = string_to_int(s);
    rsum += v;
  }
  cout << rsum << endl;
}

Table:

#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
 
const int powtable [] = { 1,
                          10,
                          100,
                          1000,
                          10000,
                          100000,
                          1000000,
                          10000000,
                          100000000,
                          1000000000
                        };
 
int string_to_int(string s) {
 
  int output=0;
 
  for(int n=s.size()-1;n>=0;n--) {
    int cval = s[n]-'0';
    output += cval*(powtable[s.size()-n-1]);
  }
 
  return output;
}
 
int main() {
 
  // Simple tests
  cout << "1 is: " << string_to_int("1") << endl;
  cout << "10 is: " << string_to_int("10") << endl;
  cout << "14532 is: " << string_to_int("14532") << endl;
 
  int rsum=0;
  for(int i=0;i<10000000;i++) {
    string s;
    int numlen = rand()%11;
    for(int n=0;n<numlen;n++) {
      int rval;
      if((numlen==10) && (n==0)) { rval = rand()%2;  }
                           else  { rval = rand()%10; }
      s.push_back('0'+rval);
    }
    int v = string_to_int(s);
    rsum += v;
  }
  cout << rsum << endl;
}

Case:

#include <string>
#include <iostream>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
 
int string_to_int(string s) {
 
  int output=0;
 
  int pos=0;
  for(int n=s.size()-1;n>=0;n--) {
    int cval = s[n]-'0';
 
    switch(pos) {
      case 0:
        output += cval*1;
        break;
      case 1:
        output += cval*10;
        break;
      case 2:
        output += cval*100;
        break;
      case 3:
        output += cval*1000;
        break;
      case 4:
        output += cval*10000;
        break;
      case 5:
        output += cval*100000;
        break;
      case 6:
        output += cval*1000000;
        break;
      case 7:
        output += cval*10000000;
        break;
      case 9:
        output += cval*100000000;
        break;
      case 10:
        output += cval*1000000000;
        break;
    }
 
    pos++;
  }
 
  return output;
}
 
int main() {
 
  // Simple tests
  cout << "1 is: " << string_to_int("1") << endl;
  cout << "10 is: " << string_to_int("10") << endl;
  cout << "14532 is: " << string_to_int("14532") << endl;
 
  int rsum=0;
  for(int i=0;i<10000000;i++) {
    string s;
    int numlen = rand()%11;
    for(int n=0;n<numlen;n++) {
      int rval;
      if((numlen==10) && (n==0)) { rval = rand()%2;  }
                           else  { rval = rand()%10; }
      s.push_back('0'+rval);
    }
    int v = string_to_int(s);
    rsum += v;
  }
  cout << rsum << endl;
}

Category: Uncategorized | Comment (RSS) | Trackback

41J Blog