Math in Java

[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

 

[Jeremy Watts]

Does the 15 to 20 seconds include start up time for the java virtual
machine? If it does, that could be a big part of your problem.

Well, I'm using the IDE called 'BlueJ', and have the program represented as
a class which then within it have the methods needed to represent the
various 'sub-routines' of the program. I'm assuming the JVM is up and
running when I open BlueJ and run the class. Maybe it isnt I dont know

Another

issue is that Java just isn't going to compete well with a program that
runs in 20 to 30 seconds. Java uses a runtime compiler that optimizes the
code while it runs. You aren't going to get the benefit of these
optimizations for jobs that only last 20 to 30 seconds.

If you post your code online somewhere that we can take a look it, we
might be able to give you better advice about how to get the performance
you would like.

I could post it I guess but it would be quite a large text file (about
180k). The algorithm being used is the 'Berlekamp-Hensel' algorithm, and
does use BigInteger and BigDecimal throughout (yep I know this can reduce
speed in itself, but with these algorithms use a lot of number theory and so
often require large integers)

Speaking of which, is 20 to 30 seconds too long? If it

 

[Jeremy Watts]

We don't know the OP's hardware, we don't know the server's hardware, we
don't know the various optimization parameters (undoubtedly the server
uses the '-server' flag), we don't know what effect BlueJ has on the speed
of JVMs under its aegis, we don't have an SSCCE of the OP's code to see if
there are any inefficiencies or errors in it, and we are concluding the
causes for the phenomenon?

Good point I'm running my program on an ordinary laptop (a Sony Vaio),
I'm afraid jargons defeated me for the rest...

 

[Jeremy Watts]

It has to start a new instance of the JVM to run the program in. That's
probably a big part of your time. If you are going to run this program
10,000 times or something, you try to do so without restarting it each
run. Have it run once, but process the algorithm 10,000 times.

Now if you only need to run it one time, then just wait the 20 seconds
for it to get done.

I think you're probably right. I wrapped a for...next loop around the
method call, so that the whole program would execute 10 times. The first
run of the program took several seconds (I tested it on a polynomial of
degree 14), but subsequent runs were almost instantaneous, with the
exception of the odd one or two which stalled a little while, but that may
have been due to the hard drive kicking up at the same time.

 

[Jeremy Watts]

On Thu, 29 May 2008 09:23:58 -0400, Lew wrote:

[snip]

and we are
concluding the causes for the phenomenon?

A first run at possible issues, yes.

Not much more than a guess, but that's why I suggested posting the code
up on a web page where we could look at it.

Any suggestions for a site I could use to display a text file?

 

[Jeremy Watts]

On Thu, 29 May 2008 09:23:58 -0400, Lew wrote:

[snip]

and we are
concluding the causes for the phenomenon?

A first run at possible issues, yes.

Not much more than a guess, but that's why I suggested posting the code
up on a web page where we could look at it.

Any suggestions for a site I could use to display a text file?

OK I've used esnip, its at :-

http://www.esnips.com/web/jwatts1970sStuff

 

[Jeremy Watts]

Before half the people reading comp.lang.java.programmer start digging
through your source to see if we can get it to go faster, have you
thought about whether it really needs to go faster?

I mean if it is already fast enough, do we need to spend time on this?

Well I get the suspicion the main reason for the 'slowness' is as you said,
the time the JVM takes to load. But anyway have a look at it and run it
yourself, see how it runs with whatever IDE you use. I've only ever used
BlueJ really.

 

[Jeremy Watts]

If it is just one text file, post it in this thread. If it is more than
one text file... hmm? Don't really know. I just sort of assumed you had
access to a web server somewhere.

Worst case, I'll post it for you, send it to me with something in big
bold letters in the subject so I don't throw it away thinking it is
spam..

Oh and don't mention Viagra in the mail either.

I've put it in an esnips thing Kenneth a few posts up

 

[Roedy Green]

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&

try it under Jet or Beta Jet. it does some very good static
optimisation.

see http://mindprod.com/jgloss/jet.html

 

[Arne Vajhøj]

Does the 15 to 20 seconds include start up time for the java virtual
machine? If it does, that could be a big part of your problem.

No.

JVM startup does take some time.

But not enough to make it a big part of 15-20 seconds.

> Speaking of which, is 20 to 30 seconds too long? If it
> isn't then I wouldn't worry about it. What would be "fast enough"?

A difference of factor 30-40 indicates a difference in algorithm, which
could be relevant.

Arne

 

[Arne Vajhøj]

Probably true. The original poster posted the code. Why don't you take
a look at it.

I may.

But it is 3500 lines of code, so definitely not today !

Arne

 

[Jeremy Watts]

No.

JVM startup does take some time.

But not enough to make it a big part of 15-20 seconds.


A difference of factor 30-40 indicates a difference in algorithm, which
could be relevant.

There are several algorithms that will factor univariates, the best and most
modern being the Berlekamp-Hensel (sometimes called Berlekamp-Zassenhaus),
which is what I'm using. The other main one is the LLL algorithm, which is
possibly what the site is using.

Technically speaking the LLL is more modern and is a superior algorithm, but
not significantly so, and I doubt that even if it was using it this would
explain the time difference.

But Kenneth does seem to have a point. I have tried running the algorithm 10
times in succession and the first run always takes several seconds, whereas
later ones seem to go instantaneously almost.

 

[Jeremy Watts]

try it under Jet or Beta Jet. it does some very good static
optimisation.

see http://mindprod.com/jgloss/jet.html

Many thanks, have you used this yourself?

 

[Jeremy Watts]

I may.

But it is 3500 lines of code, so definitely not today !

I was reluctant to post it... yep its a biggie...

 

[Jeremy Watts]

There are several algorithms that will factor univariates, the best and
most modern being the Berlekamp-Hensel (sometimes called
Berlekamp-Zassenhaus), which is what I'm using. The other main one is the
LLL algorithm, which is possibly what the site is using.

Technically speaking the LLL is more modern and is a superior algorithm,
but not significantly so, and I doubt that even if it was using it this
would explain the time difference.

But Kenneth does seem to have a point. I have tried running the algorithm
10 times in succession and the first run always takes several seconds,
whereas later ones seem to go instantaneously almost.

But yeah, I'm not denying algorithm difference could well be a factor, but
my initial suspicion was simply language choice - I'm running java, its
running... whatever its running in I suspect C# or something, anyone
know? I'm pretty sure the servers doing the processing and its running
pure machine code.

 

[Boris Stumm]

OK I've used esnip, its at :-

http://www.esnips.com/web/jwatts1970sStuff

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. Use a profiler to find out where the time is used
in your code.

 

[Tom Anderson]

But yeah, I'm not denying algorithm difference could well be a factor, but
my initial suspicion was simply language choice - I'm running java, its
running... whatever its running in I suspect C# or something, anyone
know? I'm pretty sure the servers doing the processing and its running
pure machine code.

In any JVM released this century, so is java.

tom

 

[Axel Kramer]

But yeah, I'm not denying algorithm difference could well be a factor, but
my initial suspicion was simply language choice - I'm running java, its
running... whatever its running in    

...
Hi

Did you already looked into some Java libraries and contacted the
authors, how they tried to solve similar algorithms?

Java Algebra System (JAS):
* http://krum.rz.uni-mannheim.de/jas/
jscl - java symbolic computing library
* http://jscl-meditor.sourceforge.net/

 

[Jeremy Watts]

But yeah, I'm not denying algorithm difference could well be a factor, but
my initial suspicion was simply language choice - I'm running java, its
running... whatever its running in

....
Hi

Did you already looked into some Java libraries and contacted the
authors, how they tried to solve similar algorithms?

Java Algebra System (JAS):
* http://krum.rz.uni-mannheim.de/jas/
jscl - java symbolic computing library
* http://jscl-meditor.sourceforge.net/


interesting, thanks

 

[Dexter]

--

Kenneth P. Turvey <[email protected]>http://www.electricsenator..net

  The United States is a nation of laws: badly written and randomly
  enforced.
        -- Frank Zappa

Yet it is has the best criminal justice system in the World.