bwakell / huldra Goto Github PK

Outperforming BigInteger since 2015. Possibly providing the fastest available arbitrary-precision arithmetic integer classes purely written in Java. Because performance matters (and we like Java)!

License: Other

Java 28.92% HTML 64.03% CSS 7.04%

huldra's Introduction

Huldra

A project to provide efficient Java primitives, mainly pertaining arbitrary-precision integer arithmetic. Let's smash the pathetic BigInteger class! (And let's learn how to code a proper bignum class. As of version 0.7 the BigInt class contains the basic operations, addition, subtraction, multiplication and division, making it a suitable entry point for people who want to learn as it is not cluttered with more advanced functions.)

The structure may look daunting but I just thought that I should be cool and use stuff like Maven and Git (which I apparently do not fully get), which causes the overflow of folders (though they might come in handy should I decide to add other stuff). The only thing doing something useful (apart from benchmarking and test code) is the BigInt file file, so check it out!

Since this is an early version I can almost guarantee that there are some bugs present, so let's track 'em down together!

Installation

Just copy and compile the BigInt file and you're ready to go (if you remove the package line). You could also just grab the jar file in the target directory and import org.huldra.math.BigInt (obviously you have to sort out dependencies and classpaths yourself).

Documentation

Of course there is a Javadoc file and a Maven site (which doesn't contain much useful). So check it out!

Benchmark

Below follows a comparison of the Huldra project's BigInt class with the Java library's BigInteger class, Apfloat's Apint class, and JScience's LargeInteger class. This somewhat simple comparison was done using the Benchmark.java code in the benchmark folder using Java 7 and my shitty computer (1.65 Ghz Dual Core and 6GB RAM).

Run #1 of Addition
Numbers generated
-
BigInteger parsing 1.392s
BigInteger add 6.425s
-
BigInt parsing 0.365s
BigInt add 3.033s
-
Apint parsing 0.471s
Apint add 27.956s
-
LargeInteger parsing 0.97s
LargeInteger add 6.495s
-
BigInteger toString() 4.006s
BigInt toString() 1.439s
Apint toString() 0.067s
LargeInteger toString() 3.496s
-
BigInt Check: true 100005 100005
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Addition
Numbers generated
-
BigInteger parsing 1.255s
BigInteger add 6.394s
-
BigInt parsing 0.32s
BigInt add 3.006s
-
Apint parsing 0.011s
Apint add 27.279s
-
LargeInteger parsing 0.576s
LargeInteger add 6.322s
-
BigInteger toString() 3.795s
BigInt toString() 0.78s
Apint toString() 0.009s
LargeInteger toString() 3.353s
-
BigInt Check: true 100005 100005
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #1 of Subtraction
Numbers generated
-
BigInteger parsing 1.072s
BigInteger sub 5.829s
-
BigInt parsing 0.299s
BigInt sub 2.392s
-
Apint parsing 0.473s
Apint sub 24.677s
-
LargeInteger parsing 0.845s
LargeInteger sub 6.101s
-
BigInteger toString() 3.989s
BigInt toString() 1.43s
Apint toString() 0.067s
LargeInteger toString() 3.494s
-
BigInt Check: true 100000 100000
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Subtraction
Numbers generated
-
BigInteger parsing 0.961s
BigInteger sub 5.618s
-
BigInt parsing 0.241s
BigInt sub 2.243s
-
Apint parsing 0.01s
Apint sub 24.35s
-
LargeInteger parsing 0.467s
LargeInteger sub 6.026s
-
BigInteger toString() 3.775s
BigInt toString() 0.78s
Apint toString() 0.01s
LargeInteger toString() 3.368s
-
BigInt Check: true 100000 100000
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #1 of Multiplication
Numbers generated
-
BigInteger parsing 0.007s
BigInteger mul 2.659s
-
BigInt parsing 0.01s
BigInt mul 2.31s
-
Apint parsing 0.342s
Apint mul 40.825s
-
LargeInteger parsing 0.34s
LargeInteger mul 3.331s
-
BigInteger toString() 33.61s
BigInt toString() 8.387s
Apint toString() 0.082s
LargeInteger toString() 30.197s
-
BigInt Check: true 299432 299432
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Multiplication
Numbers generated
-
BigInteger parsing 0.002s
BigInteger mul 2.676s
-
BigInt parsing 0.001s
BigInt mul 2.259s
-
Apint parsing 0.003s
Apint mul 40.433s
-
LargeInteger parsing 0.001s
LargeInteger mul 3.176s
-
BigInteger toString() 33.061s
BigInt toString() 6.357s
Apint toString() 0.026s
LargeInteger toString() 29.826s
-
BigInt Check: true 299432 299432
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #1 of many tiny multiplications
Factorial limit set to 50000
-
BigInteger tinymul 10.564s
BigInt tinymul 1.572s
Apint tinymul 37.248s
LargeInteger tinymul 7.353s
-
BigInteger toString() 17.365s
BigInt toString() 5.85s
Apint toString() 0.081s
LargeInteger toString() 15.696s
-
BigInt Check: true 213237 213237
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of many tiny multiplications
Factorial limit set to 50000
-
BigInteger tinymul 10.683s
BigInt tinymul 1.468s
Apint tinymul 35.535s
LargeInteger tinymul 6.879s
-
BigInteger toString() 16.912s
BigInt toString() 4.614s
Apint toString() 0.029s
LargeInteger toString() 15.116s
-
BigInt Check: true 213237 213237
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #1 of Big Multiplication
Numbers generated (length: 300000 decimal digits each)
-
BigInteger parsing 12.177s
BigInteger mul 4.392s
-
BigInt parsing 3.027s
BigInt mul 0.659s
-
Apint parsing 0.549s
Apint mul 0.91s
-
LargeInteger parsing 5.479s
LargeInteger mul 1.441s
-
BigInteger toString() 134.003s
BigInt toString() 28.98s
Apint toString() 0.103s
LargeInteger toString() 120.294s
-
BigInt Check: true 599999 599999
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Big Multiplication
Numbers generated (length: 300000 decimal digits each)
-
BigInteger parsing 11.696s
BigInteger mul 4.435s
-
BigInt parsing 3.06s
BigInt mul 0.468s
-
Apint parsing 0.027s
Apint mul 0.252s
-
LargeInteger parsing 5.055s
LargeInteger mul 0.495s
-
BigInteger toString() 133.728s
BigInt toString() 25.477s
Apint toString() 0.05s
LargeInteger toString() 119.81s
-
BigInt Check: true 599999 599999
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #1 of Big Multiplication
Numbers generated (length: 500000 decimal digits each)
-
BigInteger parsing 34.19s
BigInteger mul 12.115s
-
BigInt parsing 8.385s
BigInt mul 0.873s
-
Apint parsing 0.552s
Apint mul 0.755s
-
LargeInteger parsing 14.387s
LargeInteger mul 2.265s
-
BigInteger toString() 378.415s
BigInt toString() 75.228s
Apint toString() 0.149s
LargeInteger toString() 333.47s
-
BigInt Check: true 999999 999999
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Big Multiplication
Numbers generated (length: 500000 decimal digits each)
-
BigInteger parsing 31.602s
BigInteger mul 12.332s
-
BigInt parsing 8.497s
BigInt mul 0.655s
-
Apint parsing 0.049s
Apint mul 0.289s
-
LargeInteger parsing 14.054s
LargeInteger mul 1.266s
-
BigInteger toString() 377.726s
BigInt toString() 69.578s
Apint toString() 0.074s
LargeInteger toString() 332.906s
-
BigInt Check: true 999999 999999
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #1 of Division
Numbers generated
-
BigInteger parsing 10.739s
BigInteger div 9.936s
-
BigInt parsing 2.622s
BigInt div 7.558s
-
Apint parsing 0.491s
Apint div 297.022s
-
LargeInteger parsing 4.859s
LargeInteger div 3239.432s
-
BigInteger toString() 0.0s
BigInt toString() 0.0s
Apint toString() 0.001s
LargeInteger toString() 0.031s
-
BigInt Check: true 362 362
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Division
Numbers generated
-
BigInteger parsing 10.282s
BigInteger div 9.764s
-
BigInt parsing 2.736s
BigInt div 7.6s
-
Apint parsing 0.018s
Apint div 306.271s
-
LargeInteger parsing 4.49s
... This takes too much time so let's just give up...
--------------------------------------

Run #1 of Big Division
Numbers generated (length: 400000 and 200000 decimal digits)
-
BigInteger parsing 13.776s
BigInteger div 3.3s
-
BigInt parsing 3.274s
BigInt div 2.714s
-
Apint parsing 0.473s
Apint div 1.682s
-
LargeInteger parsing 5.989s
LargeInteger div 6.307s
-
BigInteger toString() 16.286s
BigInt toString() 4.255s
Apint toString() 0.078s
LargeInteger toString() 13.505s
-
BigInt Check: true 200000 200000
Apint Check: true
LargeInteger Check: true
--------------------------------------

Run #2 of Big Division
Numbers generated (length: 400000 and 200000 decimal digits)
-
BigInteger parsing 12.406s
BigInteger div 3.647s
-
BigInt parsing 3.411s
BigInt div 2.536s
-
Apint parsing 0.027s
Apint div 0.563s
-
LargeInteger parsing 5.587s
LargeInteger div 5.335s
-
BigInteger toString() 15.874s
BigInt toString() 2.903s
Apint toString() 0.017s
LargeInteger toString() 13.298s
-
BigInt Check: true 200000 200000
Apint Check: true
LargeInteger Check: true
--------------------------------------

huldra's People

Contributors

Stargazers

Watchers

Forkers

psbs free-language winitzki rzel adoadoado aaime maarufmahmud rohitmazumder lebecki norbert-gaulia bremac liturner

huldra's Issues

Add bit operations to BigInt class

It would be very useful to have the bit-oriented operations (that java.math.BigInteger has) in the BigInt class as well (things like and(), or(), xor(), not(), andNot(), setBit(), clearBit(), flipBit(), testBit(), shiftLeft(), shiftRight()) - could these be added?

Add constructor that accepts a signum and byte[]

BigInteger bi = new BigInteger(1,bytes)

This is essential in cryptography functions.

Can be added?

Add sqrt() function to BigInt

Your class BigInt is so nice!

Would you mind to add a sqrt() function to BigInt? It should work as in the similar Java-BigInteger sqrt() method.

Regards, Andreas

Crash during realloc

In uassign at line 374
len = 2;
if(dig.length<2) realloc(2);

The realloc crashes if you had created the BigInt with an int (len = 1) and then assign a long as the new len is used inside realloc for System.arraycopy while dig is still of length 1.

The fix is to move down "len = 2" to after the realloc:
if(dig.length<2) realloc(2);
len = 2;

BigInt#divRem using O(n²) algorithm?

The divRem( final BigInt div) operation is essentially the arithmetic modulo operation. Two suggestions:

rename the method to modulo, for more clarity
implement the much simpler subtraction-based Euclidean algorithm, as in

function gcd(a, b)
while a ≠ b
if a > b
a := a − b;
else
b := b − a;
return a;

(See image for Euclid's original source, formulated geometrically as Euclid was wont to do.)
If 2. is decided upon, I am willing to provide an implementation plus a unit test for the implementation plus a perf test comparing it side-by-side to the existing implementation.

benchmarks

You can't benchmark like that. Just changing the order will also change the results.
If you want to benchmark properly, use a profiler, or create a randomizer that changes the order randomly thousands of times, and also changes the jobs to be done randomly, thousands of times.
For example of a proper jvm optimization agnostic test, see:
http://stackoverflow.com/questions/8894258/fastest-way-to-iterate-over-all-the-chars-in-a-string/11876086#11876086

Incorrect multiplication if multiplier.len == 2

Test script to reproduce:
BigInt a = new BigInt("1000000000000000");
BigInt b = new BigInt("1000000000000000");
a.mul(b);

Result is 2764541310000000000000000 instead of 1000000000000000000000000000000.

Could be fixed by casting operand to long at line 1157:
else if(mul.len==2) umul( (long) mul.dig[1]<<32|(mul.dig[0]&mask));

Error thrown from usubMag() when trying to assign dig[1]=0

Found now error (?) in usubMag(). I tried to apply changes to make it more similar to uaddMag(). Hopefully I am right.
See: my fork

isZero is not working properly

When you have 0 in BigInt and add(0L) it is resized thus isZero is not working. It should probably be:
public boolean isZero() {
for (int i = 0; i < len; i++) {
if (dig[i] != 0) {
return false;
}
}
return true;
}

Incorrect result in BigInt.xor()

The following test suggests there's a problem with the xor algorithm:

The following fails:

final BigInteger facit = BigInteger.valueOf(-1).xor(BigInteger.valueOf(Long.MAX_VALUE));
final BigInt a = new BigInt(-1);
a.xor(new BigInt(Long.MAX_VALUE));
assertEquals(facit.toString(), a.toString());

I'm trying to understand the algorithm in order to find why there is a problem with Long.MAX_VALUE, but there is no problem with Integer.MAX_VALUE.

The following passes:

final BigInteger facit = BigInteger.valueOf(-1).xor(BigInteger.valueOf(Integer.MAX_VALUE));
final BigInt a = new BigInt(-1);
a.xor(new BigInt(Integer.MAX_VALUE));
assertEquals(facit.toString(), a.toString());

BasicTest compile failure

The testMod method does not compile as BigInt lacks a "mod" method. Replacing the call to "mod" with "rem" or "divRem" results in test failures.

Add License to project

I do not see any licensing information thus I cannot use it even if I would like.

Missing License information

Hi,

Thanks for the great project! Could I talk you into adding the License to your POM? I guess looking at your existing LICENSE file (and https://spdx.org/licenses/) something like the following should do the trick.

<project>
  ...
  <licenses>
    <license>
      <name>BSD 2-Clause "Simplified" License</name>
      <url>https://opensource.org/licenses/BSD-2-Clause</url>
      <distribution>repo</distribution>
    </license>
  </licenses>
  ...
</project>

This would give Maven (specifically the "license-maven-plugin") the information needed to automatically document the licenses more completely, and would probably help many people in commercial project to be able to track (and carry out) their license obligations much more easily.

Again, thanks for the great project!

Kind Regards,
Luke

uaddMag() error when increasing "len" from 1 to 2

Happens when you increase the (positive) BigInt number via adding a positive long.
While adding and "len" should cross the barrier 1->2 this actually does not happen.
Instead "len" remains one.
This fix tries to solve it.

Incorrect adding of negative integer

I am getting ArrayIndexOutOfBoundsException using this very simple test.

Test:

    BigInt acc = new BigInt();
    acc.add(-1L);

    Assert.assertEquals("-1", acc.toString());

Error:
java.lang.ArrayIndexOutOfBoundsException: 1

Fix (?):

     public void usub(final long a) //Fix parameter name
     {
         if(sign>0)
         {
             final long ah = a>>>32, al = a&mask;
-            if(len>2 || (dig[1]&mask)>ah || (dig[1]&mask)==ah&&(dig[0]&mask)>=al)
+            if(len>2 || (len == 2 && ((dig[1]&mask)>ah || (dig[1]&mask)==ah&&(dig[0]&mask)>=al)))
             {
                 usubMag(a); return;
             }

Bug within divRem()

There is likely to be a bug within the divrem() method. For example:

BigInt p = new BigInt(104608886616216589L), q = new BigInt(104608886616125069L);
System.out.println(p.divRem(q).toString());

The printed result says 104608886616216589, which is the value of p, instead of 91520, which is the right answer.

Intrinsics and other performance issues

Hi Simon,
I love your project, but I'ld like to point out that it is not beating Java's BigInteger in every respect.

Since Java 8, BigInteger may use intrinsics, say optimized assembler code, and that is hard to beat.

With intrinsics, BigInteger.multiplyToLen() is about twice as fast as your "naive multiplication" implementation.

BigInteger.squareToLen() has been prepared for intrinsics in Java8, but on my platform (x86, Windows) the assembler code has not been added before Java9. If intrinsics are present, the squaring code is even better than the multiplication intrinsics.

It seems to be possible to call the intrinsic methods by reflection without notable performance loss. But since your implementation is little-endian and Java uses big-endian encoding, reverting arrays before and after the invocation is required.

Another performance issue is division. Java's BigInteger implements the Burnikel-Ziegler algorithm for larger arguments, and my tests suggest that it is better than your Knuth implementation for inputs > 10000 bits.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.