256 Math library is done.

Performance Tuning
#1

I finally done a library for Java with support of 256 bit integer arigthmetic, and other operations. Actually I did also 128 bit one. These have support for both signed and unsigned numbers.
So some results

add 101 - 150 ms
sub simillar
div between 10 s - 19 s
mul 1300 ms

All tested for 1000000 itereations. Thus for example add is aprox up to 250 cycles.

I know I should post it in anoncements, but I would like to know if I didn’t missed any algorithms that could speed things up.

#2

Rather hard to know if you have missed any better algorithms without knowing which ones you have actually used. It certainly possible to improve on the classical algorithms for multiplication and division.

#3

For multiplication, I used the standard algorithm

q[0] = a[0] * b[0]

q[1] = a[0] * b[1] + a[1] * b[0]

and so on

For example 10 * 22
q[0] = 0 * 2
q[1] = 0 *2 + 1 * 2
…

For division, I used the algorithm with a subtraction and a bitshift.

#4

Have a look at section 4.3.3 of Knuth’s “The Art of Computer Programming” volume 2 (Seminumerical Algorithms).

#5

I’m probably missing the point, but doesn’t BigInteger cover this stuff already?

#6

The point would be performance. Is it possible to create a class that, for 256 bit values, is significantly faster than BigInteger?

#7

[quote=“Mark Thornton,post:6,topic:24784”]
::slight_smile: Why didn’t I think of that?

[quote=“Mark Thornton,post:6,topic:24784”]
That was kind of my next question. How do those performance figures compare to doing the same thing with BigInteger?

Edit:
It might also be intersting to compare against other math libs like apfloat (first one I encountered while googling on BigInteger performance).

#8

In comparison to the MutableBigInteger? Dunno multiplication would be same. MutableBigInteger is spawning new array for outcome, while my library doesn’t create any new object after inicialization.
I have better subtraction, because MutableBigInteger used too much mathematically rigorous algorithm.

The biggest problem with these libraries is, they can’t access carry flag from Java. So they are running sometimes at half speed.