Implementing Complex Numbers operation in bytecode

Discussion in 'Java' started by oulan bator, Dec 1, 2005.

  1. oulan bator

    oulan bator Guest

    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
    oulan bator, Dec 1, 2005
    #1
    1. Advertising

  2. oulan bator

    Roedy Green Guest

    On 1 Dec 2005 05:03:04 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >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

    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 1, 2005
    #2
    1. Advertising

  3. oulan bator

    Chris Smith Guest

    oulan bator <> wrote:
    > 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
    Chris Smith, Dec 1, 2005
    #3
  4. oulan bator

    Roedy Green Guest

    On Thu, 1 Dec 2005 12:31:25 -0700, Chris Smith <>
    wrote, quoted or indirectly quoted someone who said :

    >(I will handle for addition and
    >> substraction ;-) ) of complex numbers directly in bytecode (in double
    >> precision of course).


    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
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 1, 2005
    #4
  5. oulan bator

    oulan bator Guest

    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 ?
    oulan bator, Dec 2, 2005
    #5
  6. oulan bator

    IchBin Guest

    IchBin, Dec 2, 2005
    #6
  7. oulan bator

    oulan bator Guest

    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)
    oulan bator, Dec 2, 2005
    #7
  8. oulan bator wrote:
    > 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
    --
    The comp.lang.java.gui FAQ:
    ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
    Thomas Weidenfeller, Dec 2, 2005
    #8
  9. oulan bator

    oulan bator Guest

    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)
    oulan bator, Dec 2, 2005
    #9
  10. oulan bator wrote:
    > 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
    --
    The comp.lang.java.gui FAQ:
    ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
    Thomas Weidenfeller, Dec 2, 2005
    #10
  11. oulan bator

    Chris Smith Guest

    oulan bator <> wrote:
    > 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 Smith, Dec 2, 2005
    #11
  12. oulan bator

    Chris Uppal Guest

    Chris Smith wrote:

    > 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
    Chris Uppal, Dec 2, 2005
    #12
  13. oulan bator

    Roedy Green Guest

    On 2 Dec 2005 00:28:39 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >Roedy, which is the link you gave me ?


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

    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #13
  14. oulan bator

    Roedy Green Guest

    On 2 Dec 2005 00:28:39 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >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.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #14
  15. oulan bator

    Roedy Green Guest

    On 2 Dec 2005 01:06:12 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >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.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #15
  16. oulan bator

    Roedy Green Guest

    On 2 Dec 2005 06:03:13 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >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.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #16
  17. oulan bator

    Roedy Green Guest

    On Fri, 2 Dec 2005 10:36:47 -0700, Chris Smith <>
    wrote, quoted or indirectly quoted someone who said :

    >(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.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #17
  18. oulan bator

    oulan bator Guest

    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)
    oulan bator, Dec 2, 2005
    #18
  19. oulan bator

    Roedy Green Guest

    On 2 Dec 2005 14:55:42 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >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.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #19
  20. oulan bator

    Roedy Green Guest

    On 2 Dec 2005 14:55:42 -0800, "oulan bator" <> wrote,
    quoted or indirectly quoted someone who said :

    >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
    ?
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Dec 2, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. news.amnet.net.au
    Replies:
    1
    Views:
    570
    =?UTF-8?b?TMSByrtpZSBUZWNoaWU=?=
    Apr 13, 2004
  2. david ullua
    Replies:
    13
    Views:
    661
  3. raan
    Replies:
    2
    Views:
    446
  4. Buzz Lightyear
    Replies:
    10
    Views:
    1,113
    Alexander Bartolich
    Aug 12, 2009
  5. bhargava.ram

    Implementing division operation.

    bhargava.ram, Feb 18, 2010, in forum: VHDL
    Replies:
    0
    Views:
    1,119
    bhargava.ram
    Feb 18, 2010
Loading...

Share This Page