High-Performance Arbitrary precision numerical calculations in Java (Mandelbrot Set!)
Matthew Kerle
mikeb01
about the performance of the GMP library for arbitrary precision
math. It's C based so you will need JNI. There is a wrapper here:
http://bitbucket.org/dfdeshom/gmp-java/src/
On Mar 25, 3:15 am, Matthew Kerle <mattke...@gmail.com> wrote:
> TL;DR we're writing a Mandelbrot set viewer and need to dive deeper.
> BigDecimal sucks. help!
>
> So... My friend wrote a mandelbrot set viewer in Java (with Netbeans =D )
> using floats, it's pretty nice and lets you pan around and zoom and the
> performance is not too bad, but after a while you hit the precision limit of
> float (image pixellates out) so we swapped over to double and got a bit
> deeper.
>
> The problem is now we want to go deeper than double lets us (step 6
> here<http://en.wikipedia.org/wiki/Mandelbrot_set#Image_gallery_of_a_zoom_s...>).
> We tried implementing with BigDecimal but the performance absolutely crapped
> out, like 100x worse, you die waiting for a single frame to render even with
> precision turned way down (God help if you don't set a MathContext!!). After
> googling around it looks like the problem is BigDecimal, it's optimised for
> precision over speed. we don't care very much about precision, we just need
> enough to get our pretty colours :-) Speed is more of a concern, although
> obviously we're not realistically expecting float/double type speed from
> arbitrary-precision arithmetic, but a slowdown of 2-5x would be fine, 10x +
> starts getting depressing though...
>
> Other methods of performance tuning we're looking at:
> - firstly progressive rendering (eg, do 100 iterations, draw an image, then
> next 100 and so on to limit)
> - scale-dependant implementation (eg go from float to double to ? as you
> zoom in)
> - multi-threading (split the image up and hand each portion off to a core,
> not sure best way to configure this, thread per core?)
> - caching (not sure best strategy for this, store result for each point with
> iteration count or image directly? cache would get HUGE, but don't care...)
>
> I've found the ApFloat library <http://www.apfloat.org/apfloat_java/> which
> looks pretty cool. but haven't had a chance to run some comparison runs with
> it against BD yet (darn day job!!).
>
> Just wondering if anyone else has any experience with this domain or any
> pointers? it's been a few years since uni and my number theory is a bit
> rusty (one of the reasons we're playing with this...). mandelbrot uses
> T(n+1) = n^2 + first term, so maybe we can do some optimisations by using
> operating on integers and storing the precision separately? (obviously this
> is what BD does already, but we only want a narrow slice of what it does...)
>
> incidentally, found Fast Fractal, it's a closed-source
> windows-only<http://www.fastfractal.com/>program which purports to
Matthew Kerle
--
You received this message because you are subscribed to the Google Groups "The Java Posse" group.
To post to this group, send email to java...@googlegroups.com.
To unsubscribe from this group, send email to javaposse+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/javaposse?hl=en.
Matthew Kerle
John Muir
implementation of the game of life may have something to teach - it's
really blindingly fast!
enjoy,
John
On Mar 25, 4:15 am, Matthew Kerle <mattke...@gmail.com> wrote:
> TL;DR we're writing a Mandelbrot set viewer and need to dive deeper.
> BigDecimal sucks. help!
>
> So... My friend wrote a mandelbrot set viewer in Java (with Netbeans =D )
> using floats, it's pretty nice and lets you pan around and zoom and the
> performance is not too bad, but after a while you hit the precision limit of
> float (image pixellates out) so we swapped over to double and got a bit
> deeper.
>
> The problem is now we want to go deeper than double lets us (step 6
> here<http://en.wikipedia.org/wiki/Mandelbrot_set#Image_gallery_of_a_zoom_s...>).
> We tried implementing with BigDecimal but the performance absolutely crapped
> out, like 100x worse, you die waiting for a single frame to render even with
> precision turned way down (God help if you don't set a MathContext!!). After
> googling around it looks like the problem is BigDecimal, it's optimised for
> precision over speed. we don't care very much about precision, we just need
> enough to get our pretty colours :-) Speed is more of a concern, although
> obviously we're not realistically expecting float/double type speed from
> arbitrary-precision arithmetic, but a slowdown of 2-5x would be fine, 10x +
> starts getting depressing though...
>
> Other methods of performance tuning we're looking at:
> - firstly progressive rendering (eg, do 100 iterations, draw an image, then
> next 100 and so on to limit)
> - scale-dependant implementation (eg go from float to double to ? as you
> zoom in)
> - multi-threading (split the image up and hand each portion off to a core,
> not sure best way to configure this, thread per core?)
> - caching (not sure best strategy for this, store result for each point with
> iteration count or image directly? cache would get HUGE, but don't care...)
>
> I've found the ApFloat library <http://www.apfloat.org/apfloat_java/> which
> looks pretty cool. but haven't had a chance to run some comparison runs with
> it against BD yet (darn day job!!).
>
> Just wondering if anyone else has any experience with this domain or any
> pointers? it's been a few years since uni and my number theory is a bit
> rusty (one of the reasons we're playing with this...). mandelbrot uses
> T(n+1) = n^2 + first term, so maybe we can do some optimisations by using
> operating on integers and storing the precision separately? (obviously this
> is what BD does already, but we only want a narrow slice of what it does...)
>
> incidentally, found Fast Fractal, it's a closed-source
> windows-only<http://www.fastfractal.com/>program which purports to
Tom Hawtin
outside of, er, [-2, 2] (it's a long time since my second year maths
project). There also isn't much point in specially handling values
much smaller. So even long would get you a few more bits than double.
Unfortunately Java (or most other 3GLs, such as C) are much cop at
handling arithmetic split across multiple "integer" types.
mikeb01
> used to be painful slow, but that's like 4 major releases ago, and
> been upgraded since then...
From my experience down calls (Java -> Native) are very fast now (up
calls Native -> Java, not so much). However, most of my recent
experience is with a C-based messaging library (albeit a high
performance one), which would have a lower call frequency than the
rendering of a Mandelbrot set.
Matthew Kerle
--
Matthew Kerle
michaelm
I made some benchmarking on a few OS java libraries a few months ago.
The test consists of running two geometric computation methods
involving additions, substraction and multiplications
- isCounterClockWise
- isInCircle
For 1 000 000 operations I get
double 104 ms
DoubleDouble 4334 ms
BigDecimal 29975 ms
Real 36058 ms
Dfp10 61128 ms
Apfloat 98966 ms
This is a very partial test which does not take into account what each
library can really do (floating point vs arbitrary precision,
including/not including transcendantal functions...)
http://tsusiatsoftware.net/
http://real-java.sourceforge.net/Real.html
http://dfp.sourceforge.net/
http://www.apfloat.org/apfloat_java/
Michaël
Matthew Kerle
--