New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Make Newton basin plotting fun and easy #11837
Comments
Attachment: newton_basins.spyx.gz VERY rough draft of eventual file - not a Mercurial patch |
comment:1
Here is how I envision one using the current file.
With this code, the next picture attached gives at least something recognizable after a few minutes. It needs MUCH more efficient use of Cython, primarily; the algorithm is right, as far as I can tell, except maybe the counter can be ditched or needs to be improved. |
What you get with this slow implementation - at least it works! |
comment:2
Attachment: cubicbasin.png The picture is of the fractal associated with
Note that the documentation in the spyx file is all wrong. This is VERY rough, as noted above. Feedback welcome! |
comment:3
If you evaluate the contents of your spyx file in a %cython cell in the notebook, you will find two links just below the cell. The first contains the c-file created from the cython code. The second is the annotated version of the code. I suggest to look at the annotated code. The lines of the cython code are individually coloured in different shades of yellow. If a line is very dark then the single cython line corresponds to many c-lines. By clicking on the line number, you can see how each line is translated into c. You will find that your code is mostly dark yellow. If you want to make it fast, the lines that are most frequently executed should be white. Another tool: Use %prun on your functions (but it could be that it will only work on the command line - I tried in the notebook, but it didn't work). It will show you the internal Python function calls that took the most time (I think it can not show you calls to Cython functions). So, %prun may give you an idea what part of your code needs work most urgently. Using
on the command line, where I had replaces
So, it seems to me that most time is spent for internal calls to the complex interval field, and to the function In other words, it would be worth while to find out how your code uses complex interval fields and algebraic numbers, and to rewrite it such that only "usual" complex doubles are used. It may very well be that the algebraic numbers arise in a coercion happening behind the scenes. |
comment:4
Simon, Thanks for the prun tip - I had forgotten about that. I'm certainly aware of the yellow html :) but unfortunately it was nearly ALL yellow and I'm not sure how to effectively Cythonize much of it, hence my email to sage-devel/edu. Just adding cdefs is, in my experience, a recipe for disaster. Also interesting about the prun. This is mostly just taken from the complex plot stuff, but prunning (?) that shows just a couple calls to complex intervals. I assume it is mostly happening in the Thank you! |
comment:5
Replying to @kcrisman:
That's true. One first needs to have a good guess what yellow code is most frequently executed. %prun might indicate where the problem is hidden, and the annotation indicates how to get rid of it.
It makes sense to try that separately. I.e., %prun one call to
Yes. They are irritating. I am rather sure that
Sorry, |
comment:6
Here are some more detailed remarks on the code:
when trying to create
So, it would make sense to first convert the given roots to complex doubles. If that isn't good enough, one may even cdef them as such. And, in addition, cythonise the innermost loop. I'll soon test if it helps... |
Changed author from Karl-Dieter Crisman to Karl-Dieter Crisman, SImon King |
comment:7
I just attached attachment: newton_basins_more_cython.spyx, which improves the timing by a factor of almost 100: With the original version of the code together with the
With the code that I just attached, I get
How is that done? Apparently, the optimization should mainly take place in Originally, the function f1 is a lambda function (slow!) that calls the Python function Inside
|
comment:8
This is great work, Simon. I'll try it out over the weekend. All of these ideas make a lot of sense, but it would have taken me many, many hours of stumbling to do things like this. The only one I did after I posted last night was to make Even the list of roots all being complex doubles is very sensible and should have occurred to me immediately, but never did - and I wouldn't have know how to Cythonize that in any case, I only knew about the most basic Cython types. There are all kinds of optimizations in this code of that kind, and I doubt I would have ever gotten there on my own. But it makes a GREAT case study in how to use Cython, because there are so many places things are improved. Thanks. |
With Simon's improvements |
comment:9
Attachment: Betterfractal.png Okay, this is great.
is here. It only takes 20 seconds. Still not ideal, but usable for this kind of detail. I still feel like there are possible speedups - especially in terms of doing something smarter than just searching through all the roots each time looking for whether they are close enough. But I think that this is probably sufficient for turning into a patch. I would want to base it on the long-suffering #11273, which I need to finally finish reviewing, and which has modularized the color plotting a bit. Thank you VERY much for this teamwork. |
With Simon's Cython and naive keeping track of iterations needed to converge |
comment:10
Attachment: WithIterations.png Okay, now I have something very naive with iterations. Picture (same code) here and code here. Caveats:
But it does work, and even looks somewhat decent. Can't compete with Java yet, but it would be really nice to have this in Sage. |
comment:11
Outch! I just saw that my code had a bug: In the loop for |
Put more cython into the basins |
comment:12
Attachment: newton_basins_more_cython.spyx.gz Just updated my patch. I hope that this change does not alter the pictures too much. |
comment:13
Here is another slowness of the current code: |
Attachment: newton_basins_with_iterations.spyx.gz Incorporates Simon's improvements and adds naive keeping track of iterations |
Attachment: newton_basins_with_iterations_and_double.spyx.txt Naive keeping track of iterations, using a simplified distance test |
comment:14
Thanks for catching that! |
comment:15
I have attached attachment: newton_basins_with_iterations_and_double.spyx.txt. I am sorry that I have not been aware of Windows' automatic name extension (I don't usually write texts under windows), and also I hope that it did not use any fancy format. Also I just noticed that the first line of the file contains %cython - of course that needs to be removed if you want to attach it. Anyway. The trick is to define Here are the data on sagenb:
The same computation with the first "iteration" code takes |
Changed author from Karl-Dieter Crisman, SImon King to Karl-Dieter Crisman, Simon King |
comment:17
Possibly also related: a "pure Python" GPU (I guess?) implementation by "kriskda" on github. |
comment:18
Probably related: #23257 |
A version of "newton_basins_with_iterations_and_double.spyx.txt (8.7 KB) - added by SimonKing" minimally updated to work with SageMath 8.2 |
comment:19
Attachment: newton_basins_with_iterations_and_double.spyx.gz Replying to @simon-king-jena:
I found this ticket when googling for Sage functionality to plot Newton basins. I guess this ticket has been abandoned, but just in case it's useful to anyone else that finds this, I've just attached attachment: newton_basins_with_iterations_and_double.spyx which updates this (mainly by adding / changing the imported modules) so that it works with my SageMath 8.2 (in the jupyter notebook on Mac OS X 10.13.4). |
comment:20
Tickets are never abandoned, only forgotten ... that is great news. If you would like to, we would appreciate a "formal" review of the code and attaching it as a branch. Basically, one wants someone to verify that the code is correct and that things work, and especially that there are sufficient tests and examples for people to use. Simon, if you're listening, thoughts? No one person has to vouch for the entire package, it can be a review of previous people's work too. |
comment:21
Replying to @kcrisman:
Indeed. Even after reading the attachment that I supplied, I don't recognise that I wrote it. So, total amnesia.
What would be the plan? The fact that the attachment is a .spyx file means that it used to be an experimental piece of code that people could play with by attaching it. In order to create a proper branch, it would be needed to find a folder in sage/src/ where the code could fit. And so far I am not sure where it could belong. It could perhaps be classified as "educational". But do we have a dedicated folder for educational stuff? |
comment:22
Actually I think it could fit in a few different folders. The dynamics may be appropriate - indeed, see this file which may duplicate some or all of this (it's quite likely). Weird things have landed in src/sage/calculus as well. However, what I meant by asking you was whether you had already reviewed some of the code in said .spyx file. If not, that is fine, just checking. |
One of the best fractals for actually finding out new things is looking at Newton basins - see David Joyce's beautiful generator, for instance.
This is not yet in Sage. It should be, and isn't that hard to get a rough mockup by modifying the complex plot code.
CC: @jasongrout @sagetrac-evandel @rbeezer
Component: graphics
Keywords: fractal newton complex plot
Author: Karl-Dieter Crisman, Simon King
Issue created by migration from https://trac.sagemath.org/ticket/11837
The text was updated successfully, but these errors were encountered: