{"id":732,"date":"2012-01-30T20:22:09","date_gmt":"2012-01-30T20:22:09","guid":{"rendered":"http:\/\/41j.com\/blog\/?p=732"},"modified":"2012-02-03T08:32:34","modified_gmt":"2012-02-03T08:32:34","slug":"string-to-int-conversion-string-to-int-conversion-string-to-int-conversion-string-to-int-conversion","status":"publish","type":"post","link":"https:\/\/41j.com\/blog\/2012\/01\/string-to-int-conversion-string-to-int-conversion-string-to-int-conversion-string-to-int-conversion\/","title":{"rendered":"string to int conversion"},"content":{"rendered":"

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:<\/p>\n\n\n\n\n\n\n
Method<\/td>\nSummary<\/td>\n<\/tr>\n
Pow<\/td>\nmy initial pow based solution (after converting a position to an in calculating 10^val)<\/td>\n<\/tr>\n
Mul<\/td>\nRather than using pow generating powers of 10 in the loop (multiplier = multipler*10)<\/td>\n<\/tr>\n
Table<\/td>\nJust use a lookup table for the multipliers<\/td>\n<\/tr>\n
Case<\/td>\nMore of less the same as table, but encode the table in a switch statement (very ugly!)<\/td>\n<\/tr>\n<\/table>\n

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:<\/p>\n\n\n\n\n\n\n
Method<\/td>\nUser time<\/td>\n<\/tr>\n
Pow<\/td>\n43.67s<\/td>\n<\/tr>\n
Mul<\/td>\n28.21s<\/td>\n<\/tr>\n
Table<\/td>\n28.22s<\/td>\n<\/tr>\n
Case<\/td>\n29.13s<\/td>\n<\/tr>\n<\/table>\n

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.<\/p>\n

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. <\/p>\n

Pow:<\/p>\n

\n#include <string>\n#include <iostream>\n#include <math.h>\n#include <stdlib.h>\n\nusing namespace std;\n\nint string_to_int(string s) {\n\n  int output=0;\n\n  for(int n=0;n<s.size();n++) {\n    int cval = s[n]-'0';\n    output += cval*pow(10,s.size()-n-1);\n  }\n\n  return output;\n}\n\nint main() {\n\n  \/\/ Simple tests\n  cout << "1 is: " << string_to_int("1") << endl;\n  cout << "10 is: " << string_to_int("10") << endl;\n  cout << "14532 is: " << string_to_int("14532") << endl;\n\n  int rsum=0;\n  for(int i=0;i<10000000;i++) {\n    string s;\n    int numlen = rand()%11;\n    for(int n=0;n<numlen;n++) {\n      int rval;\n      if((numlen==10) && (n==0)) { rval = rand()%2;  }\n                           else  { rval = rand()%10; }\n      s.push_back('0'+rval);\n    }\n    int v = string_to_int(s);\n    rsum += v;\n  }\n  cout << rsum << endl;\n}\n<\/pre>\n
Mul:<\/p>\n
\n#include <string>\n#include <iostream>\n#include <math.h>\n#include <stdlib.h>\n\nusing namespace std;\n\nint string_to_int(string s) {\n\n  int output=0;\n\n  int mul=1;\n  for(int n=s.size()-1;n>=0;n--) {\n    int cval = s[n]-'0';\n    output += cval*mul;\n    mul = mul * 10;\n  }\n\n  return output;\n}\n\nint main() {\n\n  \/\/ Simple tests\n  cout << "1 is: " << string_to_int("1") << endl;\n  cout << "10 is: " << string_to_int("10") << endl;\n  cout << "14532 is: " << string_to_int("14532") << endl;\n\n  int rsum=0;\n  for(int i=0;i<10000000;i++) {\n    string s;\n    int numlen = rand()%11;\n    for(int n=0;n<numlen;n++) {\n      int rval;\n      if((numlen==10) && (n==0)) { rval = rand()%2;  }\n                           else  { rval = rand()%10; }\n      s.push_back('0'+rval);\n    }\n    int v = string_to_int(s);\n    rsum += v;\n  }\n  cout << rsum << endl;\n}\n<\/pre>\n
Table:<\/p>\n
\n#include <string>\n#include <iostream>\n#include <math.h>\n#include <stdlib.h>\n\nusing namespace std;\n\nconst int powtable [] = { 1,\n                          10,\n                          100,\n                          1000,\n                          10000,\n                          100000,\n                          1000000,\n                          10000000,\n                          100000000,\n                          1000000000\n                        };\n\nint string_to_int(string s) {\n\n  int output=0;\n\n  for(int n=s.size()-1;n>=0;n--) {\n    int cval = s[n]-'0';\n    output += cval*(powtable[s.size()-n-1]);\n  }\n\n  return output;\n}\n\nint main() {\n\n  \/\/ Simple tests\n  cout << "1 is: " << string_to_int("1") << endl;\n  cout << "10 is: " << string_to_int("10") << endl;\n  cout << "14532 is: " << string_to_int("14532") << endl;\n\n  int rsum=0;\n  for(int i=0;i<10000000;i++) {\n    string s;\n    int numlen = rand()%11;\n    for(int n=0;n<numlen;n++) {\n      int rval;\n      if((numlen==10) && (n==0)) { rval = rand()%2;  }\n                           else  { rval = rand()%10; }\n      s.push_back('0'+rval);\n    }\n    int v = string_to_int(s);\n    rsum += v;\n  }\n  cout << rsum << endl;\n}\n<\/pre>\n
Case:<\/p>\n
\n#include <string>\n#include <iostream>\n#include <math.h>\n#include <stdlib.h>\n\nusing namespace std;\n\nint string_to_int(string s) {\n\n  int output=0;\n\n  int pos=0;\n  for(int n=s.size()-1;n>=0;n--) {\n    int cval = s[n]-'0';\n\n    switch(pos) {\n      case 0:\n        output += cval*1;\n        break;\n      case 1:\n        output += cval*10;\n        break;\n      case 2:\n        output += cval*100;\n        break;\n      case 3:\n        output += cval*1000;\n        break;\n      case 4:\n        output += cval*10000;\n        break;\n      case 5:\n        output += cval*100000;\n        break;\n      case 6:\n        output += cval*1000000;\n        break;\n      case 7:\n        output += cval*10000000;\n        break;\n      case 9:\n        output += cval*100000000;\n        break;\n      case 10:\n        output += cval*1000000000;\n        break;\n    }\n\n    pos++;\n  }\n\n  return output;\n}\n\nint main() {\n\n  \/\/ Simple tests\n  cout << "1 is: " << string_to_int("1") << endl;\n  cout << "10 is: " << string_to_int("10") << endl;\n  cout << "14532 is: " << string_to_int("14532") << endl;\n\n  int rsum=0;\n  for(int i=0;i<10000000;i++) {\n    string s;\n    int numlen = rand()%11;\n    for(int n=0;n<numlen;n++) {\n      int rval;\n      if((numlen==10) && (n==0)) { rval = rand()%2;  }\n                           else  { rval = rand()%10; }\n      s.push_back('0'+rval);\n    }\n    int v = string_to_int(s);\n    rsum += v;\n  }\n  cout << rsum << endl;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-732","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-bO","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/732","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=732"}],"version-history":[{"count":5,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/732\/revisions"}],"predecessor-version":[{"id":737,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/732\/revisions\/737"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=732"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=732"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=732"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}