Math in Java

[Arne Vajhøj]

I had a quick look at it, and saw that it uses a lot of
three-dimensional arrays. To my experience, this is never
a good idea in java if you really want best performance.
I remember a case where I got around 30% performance improvement
just by using 1-dimensional arrays instead. Depending on
how often the arrays are accessed, you might get similar
numbers.

That is a good explanation of a +30% overhead.

But we are looking for +3000% overhead.

Arne

 

[Roedy Green]

Many thanks, have you used this yourself?

Yes. All my internal stuff is Jet. I suppose I could distribute some
apps as Jet, but then they would be separate distros for Windows and
Linux and they would be huge.

 

[Jeremy Watts]

Can the algorithm be implemented so as to take advantage of multiple
CPUs? If so, it could be simply that the site has 40x the CPU power
devoted to the problem than you do.

Quite likely yes, parallel computing with this sort of thing is common

 

[Jeremy Watts]

How do you know that the site is not using something like GNU GMP,
which is highly optimized C & assembly, and would be 10 to 20 times

I think it does, I was looking at it yesterday and clicked on a link on that
site and it mentioned using GNU.

But another factor is one I only realised yesterday. Within the program
theres a routine that carries out the finding of greatest common divisors of
polynomials. My code to do this is pretty naive - just uses a straight
forward Euclidean algorithm to accomplish it.

I had my reasons at the time for using this, but in hindsight its a poor
choice of algorithm. Yeah it always gets the right answer, but theres a
problem of 'coefficient growth'. Even for small examples sometimes the
algorithm can produce HUGE numbers as it proceeds. I think this could well
be a factor too, and a better algorithm for this is needed .

Even so though I still think mine would be significantly slower compared to
'factoris'. Can only put it down to predominantly the fact its usuing
optimized C, and the fact its running on a server maybe exploiting parallel
processing.

But my program is fine for examples of degree no more than 50. After that
it takes around 20seconds, over 100 about a minute, over 150 forget it...

 

[Tom Anderson]

How do you know that the site is not using something like GNU GMP, which
is highly optimized C & assembly, and would be 10 to 20 times faster (in
some cases 100s of times faster) than Java's BigInteger and Big Decimal?

If GMP is 10 or 100 times faster than BigInteger, it's not because it's in
C or assembler, it's because it's using better algorithms. Calling it via
JNI would be one way to get a speed boost; findind out what algorithms it
uses and copying them would be another!

tom

 

[Jeremy Watts]

Anyone interested in improving BigInteger and BigDecimal performance
should see this thread

http://forums.java.net/jive/thread.jspa?threadID=37416&tstart=0

Apparently, the person who is working on BigInteger received no
feedback from Sun.

Thanks for that. Reading through those discussions I'm amazed that
BigInteger doesnt use Karatsuba multiplication. It seemingly uses ordinary
arithmetic thoughout. As someone said on the discussion its an easy
algorithm to implement too.

 

[Jeremy Watts]

Hi,

I've written a series of math programs in Java, the one I'm currently
concerned with factors univariate polynomials (polynomials of one variable
only) with integer coefficients.

I've been timing its execution speed on larger sized polynomials, this one
in particular has degree (the highest value amongst the exponents of the
terms) of 53.

My program takes around 15 - 20s to factor this, but this site here:-
http://wims.unice.fr/wims/wims.cgi?lang=en&module=tool/algebra/factor.en&cmd=new&

does the same polynomial in under half a second.

Would you say the main factor explaining the difference between the
execution speeds, is the fact that I am running Java and the site is
likely running native machine code on a server (if that indeed is what it
is doing) ?

(I'm pretty sure we're both running the same algorithms to accomplish the
factorizations.)

Jeremy Watts

I think actually I have found the main culprit, it does seem to be the
algorithm choice. Berlekamp/Hensel has exponential complexity (what I'm
using), whereas LLL has polynomial. I've only just read that snippet of
info...

 

[Mark Thornton]

Thanks for that. Reading through those discussions I'm amazed that
BigInteger doesnt use Karatsuba multiplication. It seemingly uses ordinary
arithmetic thoughout. As someone said on the discussion its an easy
algorithm to implement too.

You may have noticed that Karatsuba doesn't pay off until the integers
are quite big. The current major use of BigInteger's is in the form of
BigDecimal used for currency and the like. Or more generally by people
wish to avoid (binary) floating point.

Mark Thornton