Logo by Trifox - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Did you know ? you can use LaTex inside Postings on fractalforums.com!
 
*
Welcome, Guest. Please login or register. September 18, 2019, 11:09:31 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: 1 2 [3] 4 5 6   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: The Mandelbrot Polynomial Roots Challenge  (Read 11110 times)
0 Members and 1 Guest are viewing this topic.
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #30 on: November 24, 2015, 08:24:23 PM »

Perhaps this (excellent) paper is of interest for this programme: http://webserver2.tecgraf.puc-rio.br/~lhf/ftp/doc/ij.pdf
Logged

Adam Majewski
Fractal Lover
**
Posts: 221


WWW
« Reply #31 on: November 24, 2015, 08:26:17 PM »

@ JArtherton
What do you think aboout atom domain :
http://mathr.co.uk/blog/2014-11-02_practical_interior_distance_rendering.html
https://commons.wikimedia.org/wiki/File:Mandelbrot_Atom_Domains_Animation.gif
?

See also :
https://en.wikibooks.org/wiki/Fractals/Iterations_in_the_complex_plane/Mandelbrot_set/centers
« Last Edit: November 24, 2015, 08:38:46 PM by Adam Majewski, Reason: new link » Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #32 on: November 24, 2015, 10:06:50 PM »

people, i would like to collect the roots and store them in a public useable database provided here through a forum api, the mandelbrot roots serve very interesting aspects, for once the roots make nice julia sets wink

regarding webspace and api programming i am totally available in doing so (at least for a while - 1gig mysql database space available here), a realtime rendering for julia seeds of that root locations could provide interesting explorations, or importing the roots into other programs like ultrafractal or kalles fractaller (remember to go deep into the 0,0 location of that julia sets wink )
Logged

---

divide and conquer - iterate and rule - chaos is No random!
Adam Majewski
Fractal Lover
**
Posts: 221


WWW
« Reply #33 on: November 26, 2015, 06:07:48 PM »

@ cKleinhuis

Great idea.

The mininal set of data is : period, cx, cy

but it could be extended to :
* radius see : https://en.wikibooks.org/wiki/Fractals/Computer_graphic_techniques/2D/plane#radius
* angled internal addresses
* angles of rays landing on the root points of such component
* ....


Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #34 on: November 26, 2015, 08:19:11 PM »

correct, the roots database could contain pretty much information, grouped by location, depth, i hope this does not explode too early wink we can chat in private about setting up a minimal api, where you could send solutions to, each solution is then marked as new, some ways to determine the correctness could be to save versions corresponding to program names, versions and dates that suggested them

the thing is going to be handling of the huge arbitrary precision logic in that database
Logged

---

divide and conquer - iterate and rule - chaos is No random!
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #35 on: November 26, 2015, 08:50:55 PM »

cKleinhuis
Posts: 6666

 evil
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #36 on: November 29, 2015, 12:45:15 PM »

Hi,
I've implemented my mandelbrot polynomial roots finder in c++ (attached) but there is someting I really don't undestand:
- when compilling with -O3 it takes 6.8s to compute the 8192 roots of the 14th mandelbrot polynomial on i7 processor.
- When compiling with -Ofast it takes only 0.3s seconds.
Why such a difference in speed?
When using float or long double instead of double, -Ofast doesn't improve computation speed. Sceptical
I'm using GCC 5.2.0
It looks like the compiler doesn't use hardware fp unless one uses doubles and -Ofast switch... strange!


I did once something similar. See attached evaldraw scripts.

* mandelroots.zip (3.9 KB - downloaded 78 times.)
* MBminPeriod.zip (2.87 KB - downloaded 69 times.)
Logged
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #37 on: November 29, 2015, 01:36:54 PM »

Perhaps this (excellent) paper is of interest for this programme: http://webserver2.tecgraf.puc-rio.br/~lhf/ftp/doc/ij.pdf

Hahaha, and of course the mighty Knighty jumps in with not just interval arithmetic, but affine arithmetic! What a legend  afro
Logged

knighty
Fractal Iambus
***
Posts: 819


« Reply #38 on: November 29, 2015, 03:39:26 PM »

 afro  embarrass
Logged
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #39 on: November 29, 2015, 06:00:13 PM »

Quote
When using float or long double instead of double, -Ofast doesn't improve computation speed.
one thing is that long double is going to use the 80bit fpu and as such cant be vectorized.  not sure why there would be no difference with single precision float though.  do you use any other compiler options?

Quote
Why such a difference in speed?
ffast-math (brought in by Ofast) is where it's at for floating point performance  grin  if you want speed and don't need strict IEEE compliance definitely use fast relaxed math options whenever you can get away with it.

i ran a few tests of your code on my haswell system, gcc 5.2:

Code:
O3                               0.02602
O3 std=gnu++14                   0.02560
O3 march=haswell                 0.02420
O3 march=haswell std=gnu++14     0.02462
Ofast                            0.00838
Ofast std=gnu++14                0.00854
Ofast march=haswell              0.00805
Ofast march=haswell std=gnu++14  0.00803

of course running them 300 times and averaging the results would be a more useful benchmark if one was so inclined  smiley

PS.  theres some really good stuff happening in c++ land in recent years.  c++98 is nearing 20 years old now.  let's start writing some modern c++  cheesy
« Last Edit: November 29, 2015, 06:13:02 PM by quaz0r » Logged
Adam Majewski
Fractal Lover
**
Posts: 221


WWW
« Reply #40 on: November 29, 2015, 07:19:49 PM »

g++ -Ofast -std=c++11 m.cpp -Wall // time taken : 0.007739 s
  g++ -Ofast -march=haswell -std=gnu++14 m.cpp -Wall // m.cpp:1:0: error: bad value (haswell) for -march= switch
  g++ -Ofast -march=native -std=c++1y m.cpp -Wall // time taken : 0.026236 s
Logged
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #41 on: November 29, 2015, 07:52:25 PM »

adam, gross!  old version of gcc i guess  cry

as a followup to my last post, ffast-math also (SHOULD) greatly affect the performance of std::complex.  in fact this is where the majority of the overall performance difference is coming from here.  unfortunately this is not currently the case for non-gcc users.  there was a rather eye-opening presentation on this issue at CppCon 2015:

<a href="http://www.youtube.com/v/he&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/he&rel=1&fs=1&hd=1</a>

to illustrate this on knighty's code:

Code:
gcc-5.2   Ofast march=haswell std=gnu++14   0.00803
clang-3.7 Ofast march=haswell std=gnu++14   0.02023

clang you turd, get your shit together!  and micros~1, well, just die in a fire.   angel
« Last Edit: November 29, 2015, 08:04:25 PM by quaz0r » Logged
Adam Majewski
Fractal Lover
**
Posts: 221


WWW
« Reply #42 on: November 29, 2015, 09:37:46 PM »

What about small modification :
Code:
void saveThem(int period){
       
       
       
       std::string name= std::to_string(period) + ".txt"; // C++11 for std::to_string

        ofstream SaveFile(name);

        switch (sizeof(T)){
            case 4 : {SaveFile.precision(8); break;}
            case 8 : {SaveFile.precision(16); break;}
            case 10:
            case 12: {SaveFile.precision(20); break;}
            case 16: {SaveFile.precision(25); break;} //__float128. doesn't work ... need more info
        default : SaveFile.precision(16);// should not happen :/
        }
        SaveFile.setf(ios::fixed);
        for (unsigned int i = 0; i < m_tab.size() /*m_cIndex*/; i++){
            SaveFile << m_tab[i].real() << "\t" << m_tab[i].imag() << endl;
        }
    }
Logged
Adam Majewski
Fractal Lover
**
Posts: 221


WWW
« Reply #43 on: November 29, 2015, 09:42:25 PM »

adam, gross!  old version of gcc i guess  cry

gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04
not the latest gcc 5.2  version
Logged
zebastian
Conqueror
*******
Posts: 121



« Reply #44 on: November 29, 2015, 10:43:18 PM »

when we are getting down on performance, i thought i could just throw in some openmp pragmas to make use of multicore.
binary is by factor  (~2 / 5 * core count) faster, but calculates wrong and crashes from time to time cheesy
probably some thread unsafety...

the main part is:

if(depth <= 2)
            {
               #pragma omp parallel for
               for(int i = 0; i < 4; i++){
                  findRootsRecurse(cc + complex<T>(-hw + (i / 2) * hw,-hw + (i % 2) * hw), hw, depth + 1);
               }
            }
            else{
               findRootsRecurse(cc + complex<T>(-hw,-hw),hw, depth + 1);
               findRootsRecurse(cc + complex<T>( hw,-hw),hw, depth + 1);
               findRootsRecurse(cc + complex<T>( hw, hw),hw, depth + 1);
               findRootsRecurse(cc + complex<T>(-hw, hw),hw, depth + 1);
            }

if someone is interested, full source code in attachment.
dont forget to put -fopenmp as compiler flag!

* mandelroots.cpp.zip (4.16 KB - downloaded 63 times.)
Logged
Pages: 1 2 [3] 4 5 6   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Rhyming challenge Fractal Humor Zedsquared 4 1942 Last post February 10, 2008, 02:42:08 PM
by David Makin
Roots of real polynomial x▓+x Mandelbrot & Julia Set stigomaster 13 2550 Last post February 09, 2010, 12:43:58 AM
by Timeroot
Polynomial Roots, degree 7, coeff {-10, -9, ..., 10} \ {0}, centered at 1i Images Showcase (Rate My Fractal) johandebock 3 1364 Last post June 23, 2010, 09:01:17 PM
by kram1032
Mandelbrot Challenge General Discussion decayer 2 2694 Last post August 17, 2011, 01:54:49 PM
by decayer
Fractal Fun: Tweet-a-Program Mandelbrot Code Challenge Competitions and Contests Geonat 0 1026 Last post November 18, 2014, 12:06:17 PM
by Geonat

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.13 seconds with 29 queries. (Pretty URLs adds 0.01s, 2q)