Implementing Complex Numbers operation in bytecode

[oulan bator]

hi,

does somebody know how to correctly(efficiently) implement complex
numbers multiplication and division (I will handle for addition and
substraction ;-) ) of complex numbers directly in bytecode (in double
precision of course).

I'm also looking for some reference on how to convert such instructions
into efficient stack operation (with limitation due to the JVM).

thanks

 

[Roedy Green]

does somebody know how to correctly(efficiently) implement complex
numbers multiplication and division (I will handle for addition and
substraction ;-) ) of complex numbers directly in bytecode (in double
precision of course).

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

 

[Chris Smith]

does somebody know how to correctly(efficiently) implement complex
numbers multiplication and division (I will handle for addition and
substraction ;-) ) of complex numbers directly in bytecode (in double
precision of course).

I'm also looking for some reference on how to convert such instructions
into efficient stack operation (with limitation due to the JVM).

I'm unsure what you're asking. Do you mean:

1. How to do it in Java that compiles to bytecode (as opposed to native
code)?

2. How to get the fastest possible bytecode for that set of operations?

3. How to write and build software in a bytecode assembly-ish language?

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Roedy Green]

(I will handle for addition and

If you follow the link I gave you, you can see the calculations you
want to do are pretty simple -- just a fat arithmetic expression.

The compiler should generate that optimally. There is not much that
could be optimised.

Just use Javap or other disassembler to see the byte codes.

See http://mindprod.com/jgloss/jasm.html
http://mindprod.com/jgloss/disassembler.html

 

[oulan bator]

hi,

sorry for answering so late (I was out of office yesterday)...

I'm looking for an efficient way to perform operations over complex
numbers on a JVM. If it is possible to do it directly in Java, it's all
right, but I don't think so.

Roedy, which is the link you gave me ?

What's strikes me is that there are specific instructions in nowaday's
processors for complex numbers operations. There aren't such
instructions in JVM bytecode, how then can I have efficient complex
number operations in JVM ?

 

[IchBin]

hi,
[snip]

Roedy, which is the link you gave me ?

[snip]
He gave you..

http://mindprod.com/jgloss/complex.html
http://mindprod.com/jgloss/jasm.html
http://mindprod.com/jgloss/disassembler.html

--


Thanks in Advance...
IchBin, Pocono Lake, Pa, USA
http://weconsultants.servebeer.com/JHackerAppManager
__________________________________________________________________________

'If there is one, Knowledge is the "Fountain of Youth"'
-William E. Taylor, Regular Guy (1952-)

 

[oulan bator]

thank's,
I did'nt see the first (and most interesting) one !

but this is exactly what I don't want a do ! This is known to be
unefficient ! (see Peng Wu, Sam Midkiff etal "Efficient Support for
Complex Numbers in Java") they have changed the JIT to reach "correct"
performance for Complex Numbers Operations (CNO)

 

[Thomas Weidenfeller]

What's strikes me is that there are specific instructions in nowaday's
processors for complex numbers operations. There aren't such
instructions in JVM bytecode, how then can I have efficient complex
number operations in JVM ?

You assume that we all know and share your definition of "efficient",
and you are surprised that we can't read your mind and guess your problem.

Apparently, your definition of "efficient" requires the existence of
special byte code instructions for complex numbers in the JVM. And as
you noted, there are no such bytecodes in the JVM. So you answered your
own question. By your standards it is apparently impossible to have
efficient operations for complex numbers in Java.

By other people's standards, a typical implementation of complex
arithmetic using normal floating point operations in Java is efficient
enough for these people's tasks and purposes.

We don't know your purpose, but by your standards you apparently want a
FORTRAN compiler with a highly optimized implementation of the complex
data type.

/Thomas

 

[oulan bator]

sorry, if I sound a bit agressive, but I'm really not ...

I'm just looking around for a solution to have "efficient" complex
numbers computation.
I don't know yet how much efficient it must be.
Indeed, the best still a good FORTRAN compiler.
The worst beeing IMO a classical Complex class in java ( that lead to a
lot of object instanciation).

In the middle I'm wondering :
how much it costs to used normal floating point operation to perform
complex number operations versus hardware call ?

Is there a hope that JIT could "recognize" coupled floating point
operations ?

and last interogation: which the best algorithm to perform complex
multiplication and division using usual floating point operation only ?
(this was my initial question)

 

[Thomas Weidenfeller]

I don't know yet how much efficient it must be.

Why not find that out first instead of thinking about premature
optimization?

The worst beeing IMO a classical Complex class in java ( that lead to a
lot of object instanciation).

If you want to do it in standard Java, then you are faced with what you
just qualified as "the worst". So why do you go for Java at all, if
you think it doesn't work for you?

In the middle I'm wondering :
how much it costs to used normal floating point operation to perform
complex number operations versus hardware call ?

Count the number of floating point operations needed per complex number
arithmetic operation and you have a good indication. I don't think
anyone here is inclined to do the counting for you.

Is there a hope that JIT could "recognize" coupled floating point
operations ?

What do you want to hear? Some probability like "a 0.0003% chance"? What
would that help you? If you want to rely on such behavior you have to
study different VMs and settle on one VM which does it all the time - if
you manage to find one at all.

and last interogation: which the best algorithm to perform complex
multiplication and division using usual floating point operation only ?
(this was my initial question)

Which actually has been answered. But in more detail, It depends on the
format in which you store your numbers. The math is different if you
make the unusual decision to model your numbers in goniometric form
instead of arithmetic form. But in all cases, there are no huge
algorithms involved. Any math textbook will give you the formulas. Did
you even look up the formulas before asking about an algorithm?

/Thomas

 

[Chris Smith]

and last interogation: which the best algorithm to perform complex
multiplication and division using usual floating point operation only ?
(this was my initial question)

The word "best" has no definition in that sentence. Best for what? For
some kinds of calculations, it's best to represent floating point
numbers in polar coordinates, for example; and for others, in cartesian
coordinates. Obviously, the implementations will differ greatly
depending on the underlying representation.

Assuming cartesian coordinates (since they are fairly normal), complex
number arithmetic is just an algebraic problem. You end up with:

(a + ib) * (c + id) = (ac - bd) + i(bc + ad)
(a + ib) / (c + id) = ((ac + bd) + i(bc - ad)) / (c^2 + d^2)

Even division involves only 11 floating point operations. It's a bit
too straight-forward to use the word "algorithm" as you do above.

Incidentally, if the underlying processor has the capability to perform
these calculations in fewer instructions, then it is possible that the
JIT will recognize this during optimization and generate the more
efficient code. It depends on the compiler, of course.

As for object instantiation, *if* this becomes a problem then you can
tweak the design... for example by adding operate-and-replace operations
that place the results of a calculation directly into one of the
operands and avoid any object instantiation. However, keep in mind that
short-lived object instantiation in a garbage collected language is
cheap. This may not be a concern.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Chris Uppal]

As for object instantiation, *if* this becomes a problem then you can
tweak the design...

Or wait to see how well the new stuff in 1.6 works. If the claims I've seen
that 1.6 will have escape analysis in the JIT, with a concomitant ability to
avoid heap-allocation of "very temporary" objects, turn out to be correct, then
I'd guess that could have quite a significant effect on some complex-heavy
applications written in "natural" (for Java) style.

-- chris

 

[Roedy Green]

Roedy, which is the link you gave me ?

the one in my first answer http://mindprod.com/jgloss/complex.html

 

[Roedy Green]

What's strikes me is that there are specific instructions in nowaday's
processors for complex numbers operations.

What machine are you thinking of? I have never encountered hardware
complex. It is just built up out of ordinary floating point
arithmetic.

 

[Roedy Green]

they have changed the JIT to reach "correct"
performance for Complex Numbers Operations

the problem with Java is not in the calculation with complex, but with
the use of separate objects for every complex value. An array of 1000
complex requires 1000 separate little objects like bubbles hanging off
it.

An efficient complex implementation treats complex like primitives, so
you can have arrays of complex without needing any objects.

That could be done by adding a complex primitive to Java, or by
something more far-reaching, allowing you to inline any small object.

 

[Roedy Green]

and last interogation: which the best algorithm to perform complex
multiplication and division using usual floating point operation only ?
(this was my initial question)

and it has already been answered. Please read the materials given to
you.

 

[Roedy Green]

(a + ib) / (c + id) = ((ac + bd) + i(bc - ad)) / (c^2 + d^2)

c^2 can be replaced by c*c, but other than that, there is simply no
wiggle room in there for optimisation. If there were something
simpler, mathematicians would likely have found it since 1572 when the
rules for manipulating complex numbers were first published.

In java doing complex arithmetic with just double primitives is
inconvenient but in principle just as fast an any other language. If
you bundle them up into Complex object pairs, you will take a big
performance hit.

 

[oulan bator]

I've read that SSE3 instructions set, extends the x86
architecture...and contains complex numbers instructions. see
(http://www.intel.com/technology/itj/2004/volume08issue01/art01_microarchitecture/p06_sse.htm)
I'm not a specialist, but it seems that in P4 at least there are
complex number support (I migh be wrong )

I've read (not the first time since I still can't see the link to
complex.html in the first answer) all the materials, but this is not
what this is all about.

I'm almost building a FORTRAN compiler for JVM/bytecode (it's not
exactly a FORTRAN compiler, but in the concern of complex numbers, and
the four operations, it's not different ), It must be in bytecode (
otherwise I would use an existing one), and the most efficient it is
the richer I'll get (;-) it's a joke, the better my app will be)

I was wondering if the best implementation in bytecode will still 10
times slower than FORTRAN ? (and which was this best implementation
....)

((ac + bd) + i(bc - ad)) / (c*c + d*d), is not enough (for me) to
define the right algorithm.

first it's more correct to write :
ans_re = (ac + bd)/ (c*c + d*d) ;
ans_im = (bc - ad) / (c*c + d*d) ;
and obviously (c*c + d*d) is duplicated (that is easy ... but it was
just z1/z2)
what about (z1*z2*z3) /( (z1+z2)(z2+z3)) (for instance) ??

I know I was'nt clear in my question (but it's hard to be clear in this
case)

 

[Roedy Green]

I've read that SSE3 instructions set, extends the x86
architecture...and contains complex numbers instructions.

This is the SIMD extension -- the Intel floating point co-processor
for vector operations.

I don't know if Java currently uses this at all.

the instructions added: Complex arithmetic (addsubps, addsubpd,
movsldup, movshdup, movddup)

are apparently useful in complex arithmetic even if they don't
implement mult/div directly.

 

[Roedy Green]

I've read (not the first time since I still can't see the link to
complex.html

what is happening when you try
http://mindprod.com/jgloss/complex.html
?