7 ms·

Bsdnt – A BSD-licensed bignum library

78 points by wbhart 13y ago

anonymouz 13y ago
Are there advantages of this over MPIR or GMP? (If I don't care about the different licenses).
- wbhart 13y ago
  Simplicity and code size are important. With a large complex project like MPIR (which, being derived from GMP is certainly faster) it is very difficult for newcomers to make contributions. This typically means you are already contributing to GMP (or MPIR) or not at all. So we might hope to develop a larger community around bsdnt because of the lower barrier to entry. On a more technical level, the divide-and-conquer integer division algorithm in BSDNT is brand new, as is the basecase division. There are also technical improvements in the mullo, mulmid and mulhi interfaces, with 2 words overflows. The FFT I hope to include in the next version also represents significant improvements from only a couple of years ago (though it is already in MPIR). There are lots of other innovations, such as a dramatically simplified build system, on account of the inline assembly. The zz0 interface is a new idea; it allows one to use light weight signed multiprecision integers in the low level multiprecision natural number interface (nn). And we also test that our pseudorandom generator yields the same values on all systems by taking the sha1 hash of a long stream of output.
raverbashing 13y ago
Congrats It's good to have some competition in this area. I used mostly NTL (which can use GMP) http://www.shoup.net/ntl/ http://www.shoup.net/ntl/ and it provides some good resources, maybe it's too high level for the goals of this project, but you can always take some idea. But the downside is that NTL is GPL as well.
- wbhart 13y ago
  We already have 220,000 lines of (GPL) C code competing with NTL: http://flintlib.org/ http://flintlib.org/ :-)
riffraff 13y ago
I am completely unqualified to comment on these so feel free to correct me, but isn't libtommath a liberally licensed (WTFPL) that also provides efficient bignums?
- wbhart 13y ago
  I'd be interested to see a performance comparison. :-)
tehwalrus 13y ago
This looks very cool, I will keep an eye on it, thanks!
gioele 13y ago
> It is not a goal to insanely optimise where that would make the code less readable and maintainable. > Future improvements: * Unroll assembly loops :)
- wbhart 13y ago
  Nicely spotted. Though to be fair MPIR's assembly was improved using a superoptimiser and many more complex algorithms have assembly versions. It could take days for an inexperienced person to understand them. I hope to avoid that complexity (at the obvious loss of some performance) in bsdnt.
arianvanp 13y ago
It's really annoying that any non-LGPL haskell project you release needs to be dynamically linked to libgmp instead of statically linked because of the LGPL restrictionss. We have a similar discussion about it going on here: http://www.reddit.com/r/haskell/comments/1twtvm/the_problem_with_integer/ http://www.reddit.com/r/haskell/comments/1twtvm/the_problem_... Might make a haskell FFI libray to this library.
- wbhart 13y ago
  I took a look at that discussion. It looks to me like he might be comparing the mpz interface in GMP against a lower level interface. Of course GMP has the latter too, and it's likely much faster than the one he is writing. It sounds like he switches to single word arithmetic when he can. We do that in flint, and it is faster. But it's more like a factor of two, which makes me very suspicious of the benchmarking there. There was a Scheme implementation which once beat GMP for very large integer multiplication, and Magma was also once faster. But those days are long gone. GMP beats what a compiler can do by a factor of 4-12 depending on the compiler version and their high level algorithms are insanely technical. I simply don't believe someone can beat 20 years of GMP development in a few days with a Haskell compiler.
  - jerf 13y ago
    If you look through that thread, you'll find much of the community is pretty skeptical too (including me, same name). Even my citing of 1.5x - 2x was intended to be quite conservative; I'd be happy with rough-factor-of-magnitude. Being willing to add primops is a bit of a wildcard, though; since that means changing what the compiler outputs it means that with enough work, you could juts theoretically convince the compiler to emit the same code an optimized library does. It's not just "Haskell of today" that you're looking at (which I think we'd all trivially agree could not come close in performance on this particular task), it's "Haskell of tomorrow with newly-added features for this task" that we're looking at, and that's harder to guess what its performance could be. (That's nothing to do with Haskell, of course; any language implementation that went that route would see hard-to-predict performance jumps.)
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.
thu 13y ago
I don't know well the subject hence the question: isn't there a bignum library within OpenSSL (Apache-style license)?
- wbhart 13y ago
  Yes, but for crypto you only need to optimise for small "bignums". So performance is not satisfactory for larger stuff, at least not last time I looked. Which was a while ago.
  - wbhart 13y ago
    I should add that crypto is a whole 'nuther ballgame. You often need your algorithms to not leak information. That often means going to pretty insane lengths to ensure that. The standard in good crypto software is also so much more exacting. You don't want to be 99.9% sure it has no exploitable bugs. You want to be 99.999% sure. I'm absolutely no kind of crypto expert. I'm a number theorist. In no way would bsdnt be suitable for use in crypto applications!
luckydude 13y ago
Has anyone compared this to libtommath?
crististm 13y ago
For each of these projects that herald the BSD license as a feature, I ask myself - what's wrong with GPL? In fact, if it wasn't for GNU and GPL, the world would be a very different place than it is now. I would claim that there would be no such abundance of free software that we find today. So why do some people route around GPL?
- wbhart 13y ago
  I develop GPL software too. Quite a lot of it, actually. I'm not sure what you mean by "route around GPL". I chose BSD because it will maximise usability in certain BSD licensed programming languages. You can always fork the code, put the GPL on it and distribute it under those terms if you want.
  - protomyth 13y ago
    > You can always fork the code, put the GPL on it and distribute it under those terms if you want. They can GPL their changes, but your original copyright and license stands[1]. If it was any other way, the GPL would be no protection. 1) unless you go public domain or grant the ability to change the license which the BSD does not.
    - wbhart 13y ago
      There is a difference between the license under which a project is distributed and the license of individual contributions. Any GPL project can use BSD contributions. The overall license of the project remains GPL. The opposite is not true. A BSD licensed project cannot incorporate GPL code, otherwise the project becomes a GPL project, not a BSD one.
      - protomyth 13y ago
        A mixed project's source files are BSD & GPL, it has to obey both. The BSD requirements[1] have to be honored as well as the GPL and any other licensed used. 1) such as "Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution."

78 points by wbhart 13y ago

anonymouz 13y ago

Are there advantages of this over MPIR or GMP? (If I don't care about the different licenses).

wbhart 13y ago
Simplicity and code size are important. With a large complex project like MPIR (which, being derived from GMP is certainly faster) it is very difficult for newcomers to make contributions. This typically means you are already contributing to GMP (or MPIR) or not at all. So we might hope to develop a larger community around bsdnt because of the lower barrier to entry. On a more technical level, the divide-and-conquer integer division algorithm in BSDNT is brand new, as is the basecase division. There are also technical improvements in the mullo, mulmid and mulhi interfaces, with 2 words overflows. The FFT I hope to include in the next version also represents significant improvements from only a couple of years ago (though it is already in MPIR). There are lots of other innovations, such as a dramatically simplified build system, on account of the inline assembly. The zz0 interface is a new idea; it allows one to use light weight signed multiprecision integers in the low level multiprecision natural number interface (nn). And we also test that our pseudorandom generator yields the same values on all systems by taking the sha1 hash of a long stream of output.

raverbashing 13y ago

Congrats It's good to have some competition in this area. I used mostly NTL (which can use GMP) http://www.shoup.net/ntl/ http://www.shoup.net/ntl/ and it provides some good resources, maybe it's too high level for the goals of this project, but you can always take some idea. But the downside is that NTL is GPL as well.

wbhart 13y ago
We already have 220,000 lines of (GPL) C code competing with NTL: http://flintlib.org/ http://flintlib.org/ :-)

riffraff 13y ago

I am completely unqualified to comment on these so feel free to correct me, but isn't libtommath a liberally licensed (WTFPL) that also provides efficient bignums?

wbhart 13y ago
I'd be interested to see a performance comparison. :-)

tehwalrus 13y ago

This looks very cool, I will keep an eye on it, thanks!

gioele 13y ago

> It is not a goal to insanely optimise where that would make the code less readable and maintainable. > Future improvements: * Unroll assembly loops :)

wbhart 13y ago
Nicely spotted. Though to be fair MPIR's assembly was improved using a superoptimiser and many more complex algorithms have assembly versions. It could take days for an inexperienced person to understand them. I hope to avoid that complexity (at the obvious loss of some performance) in bsdnt.

arianvanp 13y ago

It's really annoying that any non-LGPL haskell project you release needs to be dynamically linked to libgmp instead of statically linked because of the LGPL restrictionss. We have a similar discussion about it going on here: http://www.reddit.com/r/haskell/comments/1twtvm/the_problem_with_integer/ http://www.reddit.com/r/haskell/comments/1twtvm/the_problem_... Might make a haskell FFI libray to this library.

wbhart 13y ago
I took a look at that discussion. It looks to me like he might be comparing the mpz interface in GMP against a lower level interface. Of course GMP has the latter too, and it's likely much faster than the one he is writing. It sounds like he switches to single word arithmetic when he can. We do that in flint, and it is faster. But it's more like a factor of two, which makes me very suspicious of the benchmarking there. There was a Scheme implementation which once beat GMP for very large integer multiplication, and Magma was also once faster. But those days are long gone. GMP beats what a compiler can do by a factor of 4-12 depending on the compiler version and their high level algorithms are insanely technical. I simply don't believe someone can beat 20 years of GMP development in a few days with a Haskell compiler.
- jerf 13y ago
  If you look through that thread, you'll find much of the community is pretty skeptical too (including me, same name). Even my citing of 1.5x - 2x was intended to be quite conservative; I'd be happy with rough-factor-of-magnitude. Being willing to add primops is a bit of a wildcard, though; since that means changing what the compiler outputs it means that with enough work, you could juts theoretically convince the compiler to emit the same code an optimized library does. It's not just "Haskell of today" that you're looking at (which I think we'd all trivially agree could not come close in performance on this particular task), it's "Haskell of tomorrow with newly-added features for this task" that we're looking at, and that's harder to guess what its performance could be. (That's nothing to do with Haskell, of course; any language implementation that went that route would see hard-to-predict performance jumps.)

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.

thu 13y ago

I don't know well the subject hence the question: isn't there a bignum library within OpenSSL (Apache-style license)?

wbhart 13y ago
Yes, but for crypto you only need to optimise for small "bignums". So performance is not satisfactory for larger stuff, at least not last time I looked. Which was a while ago.
- wbhart 13y ago
  I should add that crypto is a whole 'nuther ballgame. You often need your algorithms to not leak information. That often means going to pretty insane lengths to ensure that. The standard in good crypto software is also so much more exacting. You don't want to be 99.9% sure it has no exploitable bugs. You want to be 99.999% sure. I'm absolutely no kind of crypto expert. I'm a number theorist. In no way would bsdnt be suitable for use in crypto applications!

luckydude 13y ago

Has anyone compared this to libtommath?

crististm 13y ago

For each of these projects that herald the BSD license as a feature, I ask myself - what's wrong with GPL? In fact, if it wasn't for GNU and GPL, the world would be a very different place than it is now. I would claim that there would be no such abundance of free software that we find today. So why do some people route around GPL?

wbhart 13y ago
I develop GPL software too. Quite a lot of it, actually. I'm not sure what you mean by "route around GPL". I chose BSD because it will maximise usability in certain BSD licensed programming languages. You can always fork the code, put the GPL on it and distribute it under those terms if you want.
- protomyth 13y ago
  > You can always fork the code, put the GPL on it and distribute it under those terms if you want. They can GPL their changes, but your original copyright and license stands[1]. If it was any other way, the GPL would be no protection. 1) unless you go public domain or grant the ability to change the license which the BSD does not.
  - wbhart 13y ago
    There is a difference between the license under which a project is distributed and the license of individual contributions. Any GPL project can use BSD contributions. The overall license of the project remains GPL. The opposite is not true. A BSD licensed project cannot incorporate GPL code, otherwise the project becomes a GPL project, not a BSD one.
    - protomyth 13y ago
      A mixed project's source files are BSD & GPL, it has to obey both. The BSD requirements[1] have to be honored as well as the GPL and any other licensed used. 1) such as "Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution."