Bsdnt – A BSD-licensed bignum library

https://github.com/wbhart/bsdnt/tree/v1.0

by wbhart • 13 years ago

78 49 13 years ago

anonymouz• 13 years ago

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

wbhart12• 13 years 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• 13 years 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/ 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.

wbhart12• 13 years ago

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

riffraff• 13 years 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?

wbhart12• 13 years ago

I'd be interested to see a performance comparison. :-)

tehwalrus• 13 years ago

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

gioele• 13 years ago

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

wbhart12• 13 years 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• 13 years 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_...

Might make a haskell FFI libray to this library.

wbhart12• 13 years 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• 13 years 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.)

jordigh• 13 years 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.

You should note that the FSF's opinion is that statically or dynamically linking does not alter the status of the result being derivative work or not.

dragonwriter3• 13 years ago

You should note that the FSF's opinion is that statically or dynamically linking does not alter the status of the result being derivative work or not.

Dynamic linking may or may not create a derivative work on applicable copyright law (on which matter the FSF's opinion is merely the FSF's opinion), but static linking involves directly embedding the libraries code into the final product, which is unmistakably within the exclusive rights of copyright.

In any case, the FSF's opinion on this issue actually makes the GPL more problematic than the alternative would make it.

comex• 13 years ago

Yes, but if you statically link, the LGPL requires providing a way for a user to switch to a modified version of the library (e.g. a .a of the rest of the application), which is more hassle than just using dynamic linking.

fdej4• 13 years ago

As a benchmark, I tested computing exp(1) using the binary splitting algorithm (gmp/mpir code: https://gist.github.com/fredrik-johansson/8198480 -- bsdnt code: 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_P2• 13 years 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?

fdej4• 13 years 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.

zhemao3• 13 years 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.

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.

fdej4• 13 years ago

A possible explanation is that libtommath has a slow division algorithm. You could check what happens if you disable the final division.

luckydude2• 13 years ago

Any chance we can see results for 10 digits as well? The reason I ask is I'm guessing that a lot of work will actually be with smaller numbers of digits.

Is it possible to design a math lib that uses native ints/floats for stuff that fits and switches in the big num stuff on overflow? I believe ruby does this, do any of the libs do it?

I think the ruby approach is to cast the 32 bit items to 64 bit, do the operation into a 64 bit, see if any of the top 32 bits are set, if so, switch to bignum, if not, use the result. If tommath or any of the others do that, then I don't really care that much (for my purpose which is scripting langs that use tommath) about the big num perf. Faster is better but the high order bit for me, at least, is perf on the smaller numbers.

thu• 13 years ago

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

wbhart12• 13 years 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.

wbhart12• 13 years 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!

luckydude2• 13 years ago

Has anyone compared this to libtommath?

crististm3• 13 years 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?

wbhart12• 13 years 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.

protomyth2• 13 years 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.

crististm3• 13 years ago

You can't fork a BSD project and relicense it as GPL unless you are the copyright owner.

"Route around GPL" is the tendency to avoid GPL license on new projects (or to change the license on existing projects - see VLC and jquery). Since project owners are free to do that anyway, the question is why is the BSD license trumpeted as a feature of the product?

Let's take the example of LLVM: there is no problem using GCC on MACs since GCC itself can be used to build proprietary systems. However, LLVM is promoted as "this is your dream compiler - fast, feature full and free from GPL restrictions".

justin66• 13 years ago

So why do some people route around GPL?

Because they can't use it in their commercially or BSD/MIT/Apache licensed code. It's not a mystery, it's the GPL doing what it was intended to do.

dragonwriter3• 13 years ago

For each of these projects that herald the BSD license as a feature, I ask myself - what's wrong with GPL?

Using the GPL restricts licensees more in the ideological interest of the licensor. If, as a licensor, I'm not interested in restricting licensees to serve my ideological interests (or if my ideological interests don't align with those in the GPL), why would I use it?

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? That GNU and the GPL were influential in spreading the idea of FOSS, and even that there might have been a time when the GPLs restrictions were necessary to establish critical mindshare for FOSS, does not mean that the GPL -- whether the same version that existed then or the current version, or anything in between -- is the right license for any particular project now.

So why do some people route around GPL?

Because it doesn't do what those people want.

crististm3• 13 years ago

This confirms my suspicion that GPL does not cater to proprietary products and that the root issue comes from ideology.

Is it possible that GNU ideology was necessary just for booting? Can we bootstrap from GPL into something that does not care as much about the user's freedoms?

Sanddancer2• 13 years ago

Because the GPL has a set of restrictions and political baggage that can act as a hindrance to a lot of applications. GPL-encumbered software, for example, cannot be linked to software written under the Eclipse license, so creating a static analysis plugin that links to GCC is not possible. A more open license allows much greater freedom to use a work in the greater Free software community.

belorn5• 13 years ago

A quite irrelevant statement. If you pick BSD, you get its set of restrictions and political baggage.

However, you are quite wrong about Eclipse plug-ins, and I suggest that one reads the eclipse legal FAQ before going at the license flame war.

  For clarity, merely interfacing or interoperating with
  Eclipse plug-in APIs (without modification) does not make
  an Eclipse plug-in a derivative work.

- http://www.eclipse.org/legal/eplfaq.php

Making a Eclipse plug-ins does not make it a derivative of Eclipse. As such, you can have any license on the plug-in. Any. Only derivative works of eclipse will have to be under the Eclipse license, and only in those cases will the work license be incompatible with GPL (since both licenses has their unique requirements).

A less protective license such as BSD might allow for different use cases than GPL, but some users of that BSD work will be faced with the fact that they are going to get sued if they try to modify or share the program. Be that because of the person who happened to distribute it, or patents, or DRM. The greater freedom you are talking about is then the "freedom" to get sued for doing hacker-worthy programming.

Bsdnt – A BSD-licensed bignum library

Related Stories