Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Integer Algorithm Performance

Note that these tests are carefully designed to test performance of the underlying algorithms and not memory allocation or variable copying. As usual, performance results should be taken with a healthy dose of scepticism, and real-world performance may vary widely depending upon the specifics of the program. In each table relative times are given first, with the best performer given a score of 1. Total actual times are given in brackets, measured in seconds for 500000 operations.

Table 1.34. Operator +

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.23704 (0.0274266s)

1.09358 (0.0383278s)

1.26645 (0.0558828s)

1.32188 (0.0916899s)

cpp_int(fixed)

1.62044 (0.0359271s)

1.5277 (0.053543s)

1.73059 (0.076363s)

1.71537 (0.118983s)

gmp_int

1.87515 (0.0415741s)

1.21699 (0.042653s)

1.15599 (0.0510088s)

1 (0.0693631s)

tommath_int

1 (0.0221711s)

1 (0.035048s)

1 (0.0441255s)

1.04441 (0.0724435s)


Table 1.35. Operator +(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0155377s)

1 (0.0209523s)

1 (0.0306377s)

1 (0.043125s)

cpp_int(fixed)

1.31904 (0.0204948s)

1.76211 (0.0369203s)

1.52941 (0.0468577s)

1.60412 (0.0691778s)

gmp_int

1.96204 (0.0304855s)

2.02569 (0.0424428s)

2.11505 (0.0648002s)

2.65993 (0.114709s)

tommath_int

14.0654 (0.218543s)

10.8239 (0.226786s)

7.76691 (0.23796s)

6.10039 (0.263079s)


Table 1.36. Operator +(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.026624s)

1 (0.0291407s)

1 (0.0373209s)

1 (0.0464919s)

cpp_int(fixed)

1.31378 (0.034978s)

1.54897 (0.045138s)

1.53649 (0.0573431s)

1.27833 (0.0594319s)

gmp_int

25.5775 (0.680974s)

24.0117 (0.699717s)

19.5633 (0.730121s)

16.8939 (0.785432s)

tommath_int

19.4694 (0.518354s)

18.4246 (0.536907s)

14.7715 (0.551288s)

12.3637 (0.574812s)


Table 1.37. Operator +=(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.18405 (0.0196905s)

1.22304 (0.0206476s)

1.25861 (0.0217397s)

1.29525 (0.0220829s)

cpp_int(fixed)

1 (0.0166298s)

1 (0.0168822s)

1 (0.0172728s)

1 (0.0170492s)

gmp_int

39.9082 (0.663668s)

39.4584 (0.666147s)

38.5504 (0.665873s)

39.2231 (0.668722s)

tommath_int

30.6219 (0.509238s)

30.4135 (0.513447s)

30.9077 (0.533863s)

32.3086 (0.550835s)


Table 1.38. Operator -

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.06986 (0.0296064s)

1 (0.0381508s)

1.05932 (0.053186s)

1.1766 (0.0844721s)

cpp_int(fixed)

1.3304 (0.0368163s)

1.44506 (0.0551303s)

1.4431 (0.0724545s)

1.57255 (0.112898s)

gmp_int

1.48072 (0.0409761s)

1.19003 (0.0454007s)

1.0794 (0.0541942s)

1 (0.0717934s)

tommath_int

1 (0.0276731s)

1.10891 (0.0423057s)

1 (0.0502076s)

1.08479 (0.0778811s)


Table 1.39. Operator -(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0147372s)

1 (0.0170001s)

1 (0.0232882s)

1 (0.0310734s)

cpp_int(fixed)

1.4267 (0.0210256s)

1.98887 (0.0338109s)

1.83788 (0.0428009s)

1.81269 (0.0563264s)

gmp_int

2.07504 (0.0305803s)

2.40928 (0.0409579s)

2.58711 (0.0602493s)

3.26438 (0.101435s)

tommath_int

13.5424 (0.199577s)

12.1793 (0.207048s)

9.28855 (0.216314s)

7.49327 (0.232842s)


Table 1.40. Operator -(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0277377s)

1 (0.0296807s)

1 (0.0372392s)

1 (0.0455855s)

cpp_int(fixed)

1.19867 (0.0332484s)

1.48639 (0.0441169s)

1.43253 (0.0533464s)

1.27697 (0.0582111s)

gmp_int

24.1794 (0.670683s)

22.9073 (0.679904s)

18.8758 (0.702922s)

16.5837 (0.755975s)

tommath_int

18.149 (0.503413s)

17.4116 (0.516787s)

14.0411 (0.52288s)

11.8237 (0.538987s)


Table 1.41. Operator -=(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.26896 (0.0203467s)

1.25722 (0.0206147s)

1.36108 (0.0225485s)

1.18351 (0.0226161s)

cpp_int(fixed)

1 (0.0160342s)

1 (0.0163971s)

1 (0.0165667s)

1 (0.0191094s)

gmp_int

41.1339 (0.659547s)

40.3982 (0.662411s)

39.925 (0.661425s)

34.636 (0.661874s)

tommath_int

31.1543 (0.499533s)

31.0303 (0.508806s)

30.7699 (0.509756s)

27.7054 (0.529434s)


Table 1.42. Operator *

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.11839 (0.0757577s)

1.61061 (0.207951s)

1.4501 (0.696912s)

1.72796 (2.64108s)

cpp_int(fixed)

1.01115 (0.0684934s)

1.28687 (0.166152s)

1 (0.480595s)

1 (1.52844s)

gmp_int

1 (0.0677384s)

1 (0.129113s)

1.09011 (0.523902s)

1.03374 (1.58s)

tommath_int

1.6322 (0.110562s)

2.71751 (0.350866s)

2.05222 (0.986288s)

2.0644 (3.15531s)


Table 1.43. Operator *(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.01611 (0.0229536s)

1.12175 (0.0298152s)

1.16413 (0.0416439s)

1.31747 (0.0666043s)

cpp_int(fixed)

1.30215 (0.0294152s)

1.669 (0.0443606s)

1.72395 (0.0616701s)

1.88315 (0.095202s)

gmp_int

1 (0.0225897s)

1 (0.0265791s)

1 (0.0357725s)

1 (0.0505547s)

tommath_int

10.8281 (0.244603s)

10.1516 (0.26982s)

8.76424 (0.313519s)

8.04364 (0.406644s)


Table 1.44. Operator *(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0570721s)

1 (0.0856141s)

1 (0.143279s)

1 (0.252785s)

cpp_int(fixed)

1.10857 (0.0632686s)

1.2951 (0.110878s)

1.20827 (0.173121s)

1.18463 (0.299456s)

gmp_int

12.0605 (0.68832s)

8.13434 (0.696415s)

5.21762 (0.747577s)

3.11601 (0.787681s)

tommath_int

10.0524 (0.57371s)

7.33116 (0.627651s)

4.85202 (0.695193s)

3.35808 (0.848871s)


Table 1.45. Operator *=(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

111.27 (7.43118s)

67.7078 (7.34138s)

43.3851 (7.4075s)

25.3089 (7.55455s)

cpp_int(fixed)

1 (0.0667848s)

1 (0.108427s)

1 (0.170738s)

1 (0.298493s)

gmp_int

46.3718 (3.09693s)

28.4639 (3.08626s)

18.1719 (3.10264s)

10.5223 (3.14083s)

tommath_int

276.674 (18.4776s)

169.146 (18.34s)

108.491 (18.5236s)

63.3261 (18.9024s)


Table 1.46. Operator /

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

2.68035 (0.595251s)

2.04702 (0.707471s)

1.62314 (0.921536s)

1.43112 (1.38811s)

cpp_int(fixed)

1 (0.222079s)

1 (0.34561s)

1 (0.567748s)

1 (0.969945s)

gmp_int

3.79283 (0.842308s)

2.73668 (0.945824s)

1.86649 (1.05969s)

1.32141 (1.2817s)

tommath_int

13.2531 (2.94324s)

11.2054 (3.87271s)

9.83293 (5.58262s)

13.0164 (12.6252s)


Table 1.47. Operator /(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

4.06026 (0.225473s)

3.45732 (0.340049s)

3.00195 (0.547957s)

2.80587 (0.978029s)

cpp_int(fixed)

2.43766 (0.135367s)

2.56264 (0.252052s)

2.44011 (0.445402s)

2.38009 (0.829617s)

gmp_int

1 (0.0555316s)

1 (0.0983563s)

1 (0.182534s)

1 (0.348566s)

tommath_int

35.9988 (1.99907s)

27.1024 (2.66569s)

21.8333 (3.98531s)

25.8066 (8.99528s)


Table 1.48. Operator /(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.50505 (0.705756s)

1.39347 (1.58556s)

2.63348 (3.57438s)

4.75451 (8.52733s)

cpp_int(fixed)

1 (0.468925s)

1.12378 (1.27869s)

2.29966 (3.12128s)

4.4844 (8.04288s)

gmp_int

2.17234 (1.01866s)

1 (1.13785s)

1 (1.35728s)

1 (1.79352s)

tommath_int

4.74612 (2.22557s)

2.70088 (3.07319s)

3.65634 (4.96268s)

6.79408 (12.1853s)


Table 1.49. Operator /=(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.76281 (0.0574966s)

1.76471 (0.0604224s)

1.56085 (0.0716403s)

1.31422 (0.124043s)

cpp_int(fixed)

1 (0.0326164s)

1 (0.0342393s)

1 (0.0458981s)

1 (0.0943852s)

gmp_int

20.2862 (0.661664s)

19.4043 (0.664389s)

14.4881 (0.664976s)

7.14238 (0.674135s)

tommath_int

32.9555 (1.07489s)

30.1525 (1.0324s)

22.8324 (1.04796s)

11.7456 (1.10861s)


Table 1.50. Operator %

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.8501 (0.364131s)

1.46527 (0.476653s)

1.27509 (0.689738s)

1.20064 (1.11769s)

cpp_int(fixed)

1 (0.196817s)

1 (0.325301s)

1 (0.540932s)

1 (0.930916s)

gmp_int

3.2533 (0.640305s)

2.15441 (0.700832s)

1.47898 (0.800029s)

1.07439 (1.00016s)

tommath_int

15.3501 (3.02116s)

12.1106 (3.9396s)

11.0689 (5.98752s)

13.5535 (12.6172s)


Table 1.51. Operator %(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.82761 (0.104331s)

2.01496 (0.202512s)

2.10004 (0.389523s)

2.17252 (0.768097s)

cpp_int(fixed)

1.78851 (0.102099s)

1.96844 (0.197838s)

2.02956 (0.376451s)

2.07257 (0.73276s)

gmp_int

1 (0.057086s)

1 (0.100505s)

1 (0.185483s)

1 (0.353552s)

tommath_int

36.3018 (2.07233s)

26.3075 (2.64402s)

21.9525 (4.07183s)

25.6759 (9.07775s)


Table 1.52. Operator construct

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.40211 (0.0026854s)

1 (0.00278639s)

1 (0.00322813s)

1 (0.0027185s)

cpp_int(fixed)

1 (0.00191526s)

1.40721 (0.00392103s)

1.90346 (0.00614463s)

2.14621 (0.00583447s)

gmp_int

98.705 (0.189046s)

68.9726 (0.192184s)

58.8994 (0.190135s)

70.0525 (0.190438s)

tommath_int

105.602 (0.202255s)

74.1994 (0.206748s)

63.6455 (0.205456s)

76.8935 (0.209035s)


Table 1.53. Operator construct(unsigned)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.73436 (0.00348927s)

1 (0.00263476s)

1 (0.0027009s)

1 (0.00318651s)

cpp_int(fixed)

1 (0.00201185s)

1.36851 (0.0036057s)

2.07362 (0.00560064s)

1.66856 (0.00531688s)

gmp_int

97.2414 (0.195635s)

76.3759 (0.201232s)

72.7396 (0.196462s)

63.8129 (0.20334s)

tommath_int

210.112 (0.422713s)

162.652 (0.42855s)

158.33 (0.427634s)

134.626 (0.428987s)


Table 1.54. Operator construct(unsigned long long)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

2.34403 (0.00739542s)

1.66376 (0.00713834s)

1.22989 (0.0074969s)

1.23708 (0.00711417s)

cpp_int(fixed)

1 (0.00315501s)

1 (0.00429049s)

1 (0.00609561s)

1 (0.0057508s)

gmp_int

222.866 (0.703144s)

164.331 (0.705059s)

115.363 (0.70321s)

122.347 (0.703596s)

tommath_int

218.681 (0.689941s)

163.796 (0.702765s)

114.57 (0.698376s)

122.422 (0.704027s)


Table 1.55. Operator gcd

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.16358 (2.74442s)

1.39847 (8.11559s)

1.64677 (22.2518s)

1.95096 (64.4961s)

cpp_int(fixed)

1 (2.35859s)

1.30986 (7.60133s)

1.67681 (22.6577s)

2.0895 (69.0758s)

gmp_int

1.03392 (2.4386s)

1 (5.80319s)

1 (13.5124s)

1 (33.0586s)

tommath_int

5.25978 (12.4057s)

4.4619 (25.8932s)

4.15577 (56.1542s)

3.91192 (129.323s)


Table 1.56. Operator powm

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

2.50722 (2.91621s)

3.5561 (13.406s)

4.37066 (73.483s)

4.88831 (473.91s)

cpp_int(fixed)

1.93385 (2.24931s)

3.18107 (11.9922s)

4.20753 (70.7403s)

4.8158 (466.88s)

gmp_int

1 (1.16313s)

1 (3.76986s)

1 (16.8128s)

1 (96.9476s)

tommath_int

1.44081 (1.67584s)

1.8794 (7.08507s)

2.19115 (36.8394s)

2.17186 (210.557s)


Table 1.57. Operator str

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.17175 (0.00160006s)

1.41999 (0.00329476s)

1.40856 (0.00813784s)

1.52964 (0.0229767s)

cpp_int(fixed)

1 (0.00136554s)

1 (0.00232027s)

1 (0.00577741s)

1.14754 (0.0172372s)

gmp_int

1.50501 (0.00205515s)

1.52968 (0.00354926s)

1.01989 (0.0058923s)

1 (0.015021s)

tommath_int

12.2161 (0.0166816s)

16.9577 (0.0393463s)

18.7474 (0.108311s)

22.7368 (0.341528s)


Table 1.58. Operator |

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0301617s)

1 (0.0423404s)

1 (0.0522358s)

1 (0.0813156s)

cpp_int(fixed)

1.0638 (0.0320861s)

1.22566 (0.0518951s)

1.28515 (0.0671305s)

1.16118 (0.094422s)

gmp_int

1.76553 (0.0532514s)

1.51489 (0.0641408s)

1.70708 (0.0891706s)

1.77346 (0.14421s)

tommath_int

4.37637 (0.131999s)

3.46212 (0.146587s)

2.91875 (0.152463s)

4.19621 (0.341217s)


Table 1.59. Operator |(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0289129s)

1 (0.0351119s)

1 (0.0406779s)

1 (0.0525891s)

cpp_int(fixed)

1.06091 (0.030674s)

1.25979 (0.0442336s)

1.36194 (0.0554009s)

1.37438 (0.0722772s)

gmp_int

4.92854 (0.142498s)

4.34687 (0.152627s)

3.71442 (0.151095s)

2.981 (0.156768s)

tommath_int

10.9847 (0.317598s)

9.37065 (0.329021s)

8.53651 (0.347248s)

11.2155 (0.589813s)


Table 1.60. Operator ^

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0305149s)

1 (0.04217s)

1 (0.0525977s)

1 (0.0816632s)

cpp_int(fixed)

1.01544 (0.0309861s)

1.24872 (0.0526585s)

1.26661 (0.066621s)

1.15965 (0.0947007s)

gmp_int

1.64675 (0.0502505s)

1.47181 (0.0620663s)

1.66038 (0.0873322s)

1.67895 (0.137108s)

tommath_int

4.30668 (0.131418s)

3.45859 (0.145849s)

2.91462 (0.153303s)

4.15538 (0.339342s)


Table 1.61. Operator ^(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.01566 (0.0296088s)

1 (0.0356634s)

1 (0.0401898s)

1 (0.0514097s)

cpp_int(fixed)

1 (0.0291524s)

1.2393 (0.0441976s)

1.38556 (0.0556856s)

1.38899 (0.0714075s)

gmp_int

4.68027 (0.136441s)

4.15243 (0.14809s)

3.74237 (0.150405s)

3.0483 (0.156712s)

tommath_int

10.919 (0.318314s)

9.16311 (0.326788s)

8.62554 (0.346659s)

11.6212 (0.597442s)


Table 1.62. Operator &

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.0346 (0.0303431s)

1 (0.0427309s)

1 (0.0535587s)

1.06945 (0.0828084s)

cpp_int(fixed)

1 (0.0293284s)

1.10435 (0.04719s)

1.05262 (0.0563769s)

1 (0.0774309s)

gmp_int

1.86057 (0.0545675s)

1.58432 (0.0676995s)

1.69164 (0.0906018s)

1.86625 (0.144505s)

tommath_int

4.4157 (0.129506s)

3.60396 (0.154s)

2.95985 (0.158525s)

4.4032 (0.340944s)


Table 1.63. Operator &(int)

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1.05874 (0.038946s)

1 (0.0483903s)

1 (0.063842s)

1 (0.100361s)

cpp_int(fixed)

1 (0.0367853s)

1.05827 (0.0512099s)

1.09114 (0.0696605s)

1.09432 (0.109826s)

gmp_int

3.92298 (0.144308s)

2.99447 (0.144903s)

2.228 (0.14224s)

1.42296 (0.142809s)

tommath_int

8.79208 (0.323419s)

7.02288 (0.339839s)

5.65271 (0.36088s)

6.27104 (0.629365s)


Table 1.64. Operator <<

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0248801s)

1.23196 (0.04s)

1 (0.0424149s)

1 (0.060157s)

cpp_int(fixed)

1.08931 (0.027102s)

1.40572 (0.0456418s)

1.3475 (0.0571542s)

1.24573 (0.0749397s)

gmp_int

1.05561 (0.0262636s)

1 (0.0324686s)

1.09914 (0.0466199s)

1.16315 (0.0699719s)

tommath_int

1.60497 (0.0399319s)

2.13048 (0.0691737s)

2.31219 (0.0980712s)

2.74695 (0.165248s)


Table 1.65. Operator >>

Backend

128 Bits

256 Bits

512 Bits

1024 Bits

cpp_int

1 (0.0213349s)

1.02127 (0.0295019s)

1 (0.0327116s)

1.13168 (0.0433804s)

cpp_int(fixed)

1.13514 (0.0242181s)

1.16938 (0.0337803s)

1.46999 (0.0480859s)

1.60077 (0.061362s)

gmp_int

1.26614 (0.0270129s)

1 (0.0288873s)

1.42219 (0.0465221s)

1 (0.0383329s)

tommath_int

12.0066 (0.25616s)

10.2837 (0.297067s)

9.99696 (0.327017s)

16.0943 (0.616942s)


Test code was compiled with Microsoft Visual Studio 2010 with all optimisations turned on (/Ox), and used MPIR-2.3.0 and MPFR-3.0.0. The tests were run on 32-bit Windows Vista machine.

Linux x86_64 results are broadly similar, except that libtommath performs much better there.


PrevUpHomeNext