Bsdnt – A BSD-licensed bignum library
github.com
github.com
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
Edit: python's built-in bignums for reference:
100 0.000125
1000 0.000290
10000 0.00518
100000 0.292
1000000 26.1
10000000 longHere 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
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
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
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.
mpz fmpz
digits = 10: 4.24e-06 s 1.2e-06 s
digits = 100: 1.28e-05 s 3.3e-06 s
digits = 1000: 8e-05 s 2.7e-05 s
digits = 10000: 0.001 s 0.0006 s
digits = 100000: 0.017 s 0.013 s
digits = 1000000: 0.25 s 0.23 s
digits = 10000000: 4.32 s 4.08 s
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 sI'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.
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.
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.
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.
The addition timings don't seem realistic. GMP can add 1000 small integers in 10 uS without even getting out the assembly primitives.
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.
It is also more secure for the user of an computer system.
So why do some people route around 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.
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?
IF by "does not care as much about the user's freedoms" you mean "imposes fewer ideologically-based requirements on those using licensed software", then we already largely have -- while the GPL and its relatives (LGPL, AGPL, etc.) are still around -- there are lots of major FOSS projects with active communities around non-GPL, more permissively-licensed software. (And even many projects that use the GPL -- such as Perl and Linux -- advertise a less-restrictive interpretation of its terms than the FSF states.)
I think the trend in the FOSS community in general is to prefer to less restrictive terms, which is exactly the opposite of the FSF's direction.
There is little chance that GPL can be made into anything that would allow such behavior. I for once would ask what the point would be. If you do not want that legal protection, then you don't have to. There is no helmet law for software developers.
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.
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.
"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".
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.
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."
1: The license choice is a political one. Picking the BSD license (or GPL) is equal to doing a political message.
2: The key feature of the project is defined by the circumstances that permission is granted to use, copy, and distribute.
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.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.
However, I stand behind my statement regarding BSD. Because of the restrictive nature of the GPL, one cannot take open code with it, and combine it with code written under other Free licenses, such as the CDDL. One risks being sued, etc, for that. Look at the problems that arose over cdrtools, for example. There are much less restrictive ways to solve what the GPL purports to fix, such as the Apache license.
If a company or person takes apache licensed code and distribute it under new terms, they are in legal right to sue their users if any dare to do modification, run modifications, or share the program. If you license a program under a permissive license, one have to accept that some people might end up in jail for wanting to do changes to your code. The GPL protection is there if you want it, but no author is forced to use it. As I said in a above comment, there is no helmet law for developers.
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.
> Future improvements: * Unroll assembly loops
:)
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.
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!