6 ms·

As a benchmark, I tested computing exp(1) using the binary splitting algorithm (gmp/mpir code: https://gist.github.com/fredrik-johansson/8198480 https://gist.gi

by fdej 13y ago

As a benchmark, I tested computing exp(1) using the binary splitting algorithm (gmp/mpir code: https://gist.github.com/fredrik-johansson/8198480 https://gist.github.com/fredrik-johansson/8198480 -- bsdnt code: https://gist.github.com/fredrik-johansson/8198432 https://gist.github.com/fredrik-johansson/8198432). digits mpir bsdnt 100 0.0000126 0.0000176 1000 0.0000803 0.000113 10000 0.000945 0.0015 100000 0.0171 0.037 1000000 0.266 1.19 10000000 4.37 40.52 Not bad for 1.0! Edit: python's built-in bignums for reference: 100 0.000125 1000 0.000290 10000 0.00518 100000 0.292 1000000 26.1 10000000 long

NAFV_P 13y ago
I noticed your gists used time.h. Coincidentally I have just been fooling around with sys/time.h because I find the former to be unreliable. From what I have read on the web many other hackers share the same sentiment. I'm surprised to see you using it in code like this, or have I missed something?
- fdej 13y ago
  I just copied the profile code from bsdnt. I guess the reason it uses it is that it simpler and/or more portable. In this case, it does not matter much. I use the functions from sys/time.h when I do more serious profiling.
  - NAFV_P 13y ago
    > I guess the reason it uses it is that it simpler and/or more portable. After more fooling around I see what you mean. The Open Group has one version of it, my Linux man pages serve me another. I skimmed over the GNU C website, they say that the struct timezone type is obsolete and should be avoided. Happy days.
zhemao 13y ago
A bunch of people have been asking for benchmarks of LibTommath for comparison. I've ported this benchmark to tommath at https://gist.github.com/zhemao/8204404 https://gist.github.com/zhemao/8204404. Here are the runs on my machine BSDNT digits = 100: 2.43242e-05 s digits = 1000: 0.000143717 s digits = 10000: 0.0016644 s digits = 100000: 0.0378964 s digits = 1000000: 1.20317 s digits = 10000000: 40.1549 s GMP digits = 100: 1.64086e-05 s digits = 1000: 0.000117272 s digits = 10000: 0.00113377 s digits = 100000: 0.0175584 s digits = 1000000: 0.284023 s digits = 10000000: 4.96335 s TOMMATH digits = 100: 4.90092e-05 s digits = 1000: 0.000302586 s digits = 10000: 0.00548351 s digits = 100000: 0.368923 s digits = 1000000: 36.7576 s digits = 10000000: longer than I was willing to wait I have no idea why libtommath gets so slow for larger numbers. Would anyone care to comment? I think something must be wrong in the way I ported the benchmark.
- fdej 13y ago
  A possible explanation is that libtommath has a slow division algorithm. You could check what happens if you disable the final division.
  - zhemao 13y ago
    I tried that. It's an improvement, but libtommath is still much slower than the other two. digits = 100: 4.31597e-05 s digits = 1000: 0.000249898 s digits = 10000: 0.00252304 s digits = 100000: 0.0618554 s digits = 1000000: 5.24447 s digits = 10000000: 703.01 s
    - wbhart 13y ago
      Certainly he has only basecase division, which explains the original benchmark timings. I'm not very familiar with libtommath, though I had a passing experience with it back in about 2004-2005. However, looking through the code, he does seem to have toom3 (I have both toom3 and toom32, which may or may not be relevant here -- the latter is for unbalanced multiplication). But more obvious is that libtommath seems to check for errors after every operation, even internally. I think this is some kind of exception mechanism. I also recall there being a libtomcrypt at some point. Maybe it still exists. That suggests that Tom is possibly focusing on the much more difficult area of crypto, where your code needs to much, much more defensive. Also, libtommath claims to be 100% C, which bsdnt is not. We use some assembly language, which gives us 5-30% speedup (we could get about another factor of 2 if we unrolled the loops like the C compiler we are comparing against). Those are a few of the things I can see. But performance isn't everything. It has never been my intention to be compared with GMP performance-wise for example. You simply cannot beat GMP without being as technical as GMP. The focus here is simplicity and reliability (not to the extremes required for crypto though), and it always will be. Roughly, my goals with this project were to eventually be much faster than say Python bignums, maybe within a factor of 2 or so of GMP on generic problems, but with code that could be maintained by language designers themselves, without being bignum experts.

by fdej 13y ago

NAFV_P 13y ago

I noticed your gists used time.h. Coincidentally I have just been fooling around with sys/time.h because I find the former to be unreliable. From what I have read on the web many other hackers share the same sentiment. I'm surprised to see you using it in code like this, or have I missed something?

fdej 13y ago
I just copied the profile code from bsdnt. I guess the reason it uses it is that it simpler and/or more portable. In this case, it does not matter much. I use the functions from sys/time.h when I do more serious profiling.
- NAFV_P 13y ago
  > I guess the reason it uses it is that it simpler and/or more portable. After more fooling around I see what you mean. The Open Group has one version of it, my Linux man pages serve me another. I skimmed over the GNU C website, they say that the struct timezone type is obsolete and should be avoided. Happy days.

zhemao 13y ago

A bunch of people have been asking for benchmarks of LibTommath for comparison. I've ported this benchmark to tommath at https://gist.github.com/zhemao/8204404 https://gist.github.com/zhemao/8204404. Here are the runs on my machine BSDNT digits = 100: 2.43242e-05 s digits = 1000: 0.000143717 s digits = 10000: 0.0016644 s digits = 100000: 0.0378964 s digits = 1000000: 1.20317 s digits = 10000000: 40.1549 s GMP digits = 100: 1.64086e-05 s digits = 1000: 0.000117272 s digits = 10000: 0.00113377 s digits = 100000: 0.0175584 s digits = 1000000: 0.284023 s digits = 10000000: 4.96335 s TOMMATH digits = 100: 4.90092e-05 s digits = 1000: 0.000302586 s digits = 10000: 0.00548351 s digits = 100000: 0.368923 s digits = 1000000: 36.7576 s digits = 10000000: longer than I was willing to wait I have no idea why libtommath gets so slow for larger numbers. Would anyone care to comment? I think something must be wrong in the way I ported the benchmark.

fdej 13y ago
A possible explanation is that libtommath has a slow division algorithm. You could check what happens if you disable the final division.
- zhemao 13y ago
  I tried that. It's an improvement, but libtommath is still much slower than the other two. digits = 100: 4.31597e-05 s digits = 1000: 0.000249898 s digits = 10000: 0.00252304 s digits = 100000: 0.0618554 s digits = 1000000: 5.24447 s digits = 10000000: 703.01 s
  - wbhart 13y ago
    Certainly he has only basecase division, which explains the original benchmark timings. I'm not very familiar with libtommath, though I had a passing experience with it back in about 2004-2005. However, looking through the code, he does seem to have toom3 (I have both toom3 and toom32, which may or may not be relevant here -- the latter is for unbalanced multiplication). But more obvious is that libtommath seems to check for errors after every operation, even internally. I think this is some kind of exception mechanism. I also recall there being a libtomcrypt at some point. Maybe it still exists. That suggests that Tom is possibly focusing on the much more difficult area of crypto, where your code needs to much, much more defensive. Also, libtommath claims to be 100% C, which bsdnt is not. We use some assembly language, which gives us 5-30% speedup (we could get about another factor of 2 if we unrolled the loops like the C compiler we are comparing against). Those are a few of the things I can see. But performance isn't everything. It has never been my intention to be compared with GMP performance-wise for example. You simply cannot beat GMP without being as technical as GMP. The focus here is simplicity and reliability (not to the extremes required for crypto though), and it always will be. Roughly, my goals with this project were to eventually be much faster than say Python bignums, maybe within a factor of 2 or so of GMP on generic problems, but with code that could be maintained by language designers themselves, without being bignum experts.