7 ms·
How Mandelbrot set images are affected by floating point precision
- repelsteeltje 3y agoIronic that the last two letters in the tittle are truncated, "Mandelbr". Must be a floating point rounding error.
- deleted 3y ago[deleted]
- efitz 3y agoThe document ("What Every Computer Scientist Should Know About Floating-Point Arithmetic") linked from the article was IMO even more interesting than the article: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.h...
- zokier 3y agoIt's definitely an evergreen article https://news.ycombinator.com/item?id=23665529 https://news.ycombinator.com/item?id=23665529 https://xkcd.com/1053/ https://xkcd.com/1053/
- deleted 3y ago[deleted]
- DRAGONERO 3y agoAnother way to explore floating point representation can also be to compare rounding modes, as this can impact a lot of what is generated for floating point operations. Most systems are round to nearest even, but round to zero, round towards positive and round towards negative also exist. Bonus points if you also check results for x87 floats.
- zokier 3y agoafaik all ieee floating point systems allow configuring rounding mode, for example with fesetround or equivalent https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/fenv.h.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/fe...
- Sesse__ 3y agoFor Mandelbrot, presumably you can do exact rational arithmetic (all it needs is multiplications and add, and you presumably start with a floating-point coordinate, which is eminently rational). It will be very slow with many iterations, of course, since the fractions will rapidly spin out of control. Edit: I see the supplementary material addresses this: “One could attempt to avoid the problem by using arbitrary-precision floating point representation, or rational representation (using two integers, for numerator and denominator, i.e., keep everything as fractions), but that quickly leads to so many significant digits to multiply in every iteration that calculations become enormously slow. For many points in a Mandelbrot Set Image, the number of significant digits in a trajectory tends to double with each iteration, leading to O(n^2) time complexity for evaluating one point with n iterations. Iterations must then be kept very low (e.g., 20-30 on a modern PC!), which means that many higher-iteration points cannot be evaluated. So accumulated round-off error is hard to avoid.” 20-30 sounds crazy low even for O(n²), though. Edit 2: This part seems wrong: “Cycle detection would work if floating point quantities could be compared exactly, but they cannot.” They certainly can. If you detect a cycle, you will never escape _given your working precision_. Floats can cycle just as well as fixed-point numbers can. But I suppose true cycles (those that would be cycles even in rationals) are extremely unlikely.
- groby_b 3y ago"20-30 sounds crazy low even for O(n²), though." I mean, 30 means 2^30 sig digits. That means any operation on those are a bit expensive in pure memory throughput. Squaring that, let's use an FFT then it's just O(n log n) for the next step, with n being number of digits here. Or 30 * 2^30 ops, let's call it 2^35 ops. We're at 32 MFlops for a single dot. Let's only do a 1280*768 image, that's 32 GFlops to compute that image. That's a perfectly nice rate, let's pretend it's half a second because all memory access was just perfectly sequential. (It's not, it's more). Each additional step more than doubles the time spent. Which means even at 6 more iterations, we're staring at half a minute compute time. Nobody waits half a minute for anything. (Unless it's a web page downloading JS) Now add the fact that I lied, memory access can't be fully sequential here. But even if it was, we're at least spilling into L3 cache, and that means some 40 cycles penalty every time we do. We'll do that a lot. So multiply time with 10 or so (I'm still hopelessly optimistic we have some efficiencies.), and suddenly even 30 iterations cost you 5 seconds. And so, yes, it's really expensive even for modern PCs. If you have a GPU, you can shuffle it off to the GPU, they're pretty good at FFTs - but even that's going to buy you, if we're really really optimistic, another 20 or so iterations before it bogs down. Doubling digits every cycle will make any hardware melt quickly.
- Retr0id 3y agoA related question I've wondered is, can you rearrange the formulae to reduce precision loss, without having to actually use more bits of precision in the data type?
- zokier 3y agoMandelbrot specifically, or computations in general? For the latter, absolutely yes. See Herbie for automated tool for doing it https://herbie.uwplse.org/ https://herbie.uwplse.org/
- Retr0id 3y agoThe former
- nimos 3y agoLong time since I looked at this but you might be interested in: https://mathr.co.uk/blog/2021-05-14_deep_zoom_theory_and_practice.html https://mathr.co.uk/blog/2021-05-14_deep_zoom_theory_and_pra... IIRC it is calculating a few points at high precision and then estimating the rest.
- captaincrowbar 3y agoSome people, when they have a problem, think, “I know, I’ll use floating point.” Now they have 1.9999998 problems.
- deleted 3y ago[deleted]
- markab21 3y agoI bet you have been waiting years to pull that one out of your pocket. Well played sir! Nice shot man! :D
- recursive 3y agoSome numbers can be precisely represented using IEEE-754 floats. Two (2) is one of them.
- beezle 3y agoFunny story from today while briefly on hold for a support rep. Got the standard 'we'll call you back if you want blah blah' followed by - I kid not - "you're estimated wait time for the next representative is 0.58333333 minutes" At the end of the call I suggested if she can log a problem for IT to include this and that they should either round up or use seconds (I suspect it was 35 seconds)
- weinzierl 3y agoThe second[1] C program I read in my life was Fractint[2]. It is called that way because it calculated fractals with integer math[3]. At that time integer math was not only faster than floating point, but the only thing available to most of us. Processors like the 80386 did not come with any floating point facilities whatsoever. The FPU was a separate unit (aptly called a coprocessor at the time) which was expensive and hard to obtain where I lived. [1] The first one was DKBTrace, which lives on as POVRay. Thank you David K. Buck, where ever you are now. I learned a lot from you. [2] https://fractint.org/ https://fractint.org/ [3] Technically we should call it fixed point I guess, but in the end it was all done with the integer instructions of the CPU. So integer math is not completely wrong.
- deleted 3y ago[deleted]
- samstave 3y agoWow! I used to use fractint ages ago, and I thought "tint" was for colors...
- IncreasePosts 3y agoI think he's in Ontario, but you can ask him yourself: david at simberon dot com ;)
- gerdesj 3y ago"Processors like the 80386 did not come with any floating point facilities whatsoever." The 80286 needed a 80287 - I bought one to run AutoCAD (1MB RAM!) I can't quite remember the exact order of events but either or both 80386 and 80486 had a co-pro initially. Then Intel re-invented the IBM magic screwdriver. They dropped the 80 prefix and added SX or DX and an i prefix for a laugh. SX had no co-pro or it was disabled and DX was the full fat model. They really started to screw the punter with the 586 ... Pentium. The trend has continued - Core iBollocks.
- weinzierl 3y agoI had an 80386DX (or maybe i386DX, but DX for sure) and it definitely had no FPU. Always wanted one so badly.
- terlisimo 3y agoMandelbrot set calculation is a curious intersection of math and computer science. I went down that rabbit hole once :) Naive implementation is easy, but there are many ways to improve performance.
- tantalor 3y agoStrange thing to say since CS is a sub-field of math.
- Etheryte 3y agoI wouldn't really say that's a universally held notion, especially in the modern world. Historically, yes, but these days it stands more on its own. In similar vein, you could say biology is a subfield of physics, but most people don't think of them that way.
- ks2048 3y agoOf course these terms aren’t well-defined, but some (me) would say both math and CS are subfields of “formal systems” (but “formal systems” could be named CS, which would put it at the top of the hierarchy)
- anthk 3y agoThe Joy computer language and Scheme with SICP are prime examples. Reading SICP it's the 'easy way' and the Joy docs plus trying to code even simple as a quadratic eqn solver it's a deep, hard task which requires lots of knowledge on cathegory theory.
- couchand 3y agoAll fields are subfields of polymathy.
- MrYellowP 3y agoI thought you're joking, but nope. https://en.wikipedia.org/wiki/Polymath https://en.wikipedia.org/wiki/Polymath
- stabbles 3y agoComputing the color of a pixel is computing the (averaged) integral of some iteration counting function. It looks like there are areas where this function is pretty chaotic -- isn't the problem very ill-conditioned? If so adding more precision may not even help?
- BlueTemplar 3y agoSeems like this algorithm does not do that ? https://github.com/ProfJski/FloatCompMandelbrot/blob/master/FloatCompMset.md#perhaps-obvious-but-also-no-supersampling https://github.com/ProfJski/FloatCompMandelbrot/blob/master/... > [...] Instead, we put pixels in a one-to-one relation to the points they represent. You can think of this as mapping some imaginary point on the pixel, such as its center or corner, onto the complex plane, and making the whole pixel represent that value.
- stabbles 3y agoI don't get the point of the project. So they show that rounding errors are amplified because a problem is ill-conditioned. Yeah, of course. The higher precision computation they do is probably equally wrong then. Averaging / smoothing can sometimes help to make a problem better conditioned, so I expected they'd do something like that to get an accurate solution regardless.
- shaun_arundell 3y agoThis reminds me of the issues with calculating the zeros of the Riemann zeta equation - your code design quickly becomes dominated by numerical implementation considerations
- pictureofabear 3y agohttps://www.youtube.com/watch?v=aP0Y1uAA-2Y https://www.youtube.com/watch?v=aP0Y1uAA-2Y A good lecture by John L. Gustafson on beyond floating points?
- zeitgeistcowboy 3y agoDid anyone else think it was interesting that the difference between the two floating point images looked like a Julia set? It’s probably trivial, but I liked that.
- rkevingibson 3y agoFrom a cursory look at the code, I don't see any use of fused-multiply-add (FMA) which would likely help with precision issues in a number of places with the float version. The "problem in more detail"[1] readme specifically calls out computation of `x^2 - y^2` as a source for error, and that has methods that dramatically reduce error with FMAs[2]. [1] https://github.com/ProfJski/FloatCompMandelbrot/blob/master/FloatCompMset.md https://github.com/ProfJski/FloatCompMandelbrot/blob/master/... [2] https://pharr.org/matt/blog/2019/11/03/difference-of-floats https://pharr.org/matt/blog/2019/11/03/difference-of-floats
- jacobolus 3y agoI wish someone made up a better explicit FMA syntax than std::fma(-c, d, cd) ... maybe something along the lines of ((-c * d + cd)) with special brackets or (-c) ⊠ d + cd with a special multiplication symbol. And if only we could effectively use FMAs from javascript...
- fanf2 3y agoThe author needs to learn about techniques for rendering deep zooms into the Mandelbrot set. Since 2013 it has been possible to render images that are 2^-hundreds across using mostly double precision arithmetic, apart from a few anchor points calculated with multiprecision (hundreds of bits) arithmetic. The deep zoom mathematics includes techniques for introspecting the iterations to detect glitches, which need extra multiprecision anchor points to be calculated. https://mathr.co.uk/blog/2021-05-14_deep_zoom_theory_and_practice.html https://mathr.co.uk/blog/2021-05-14_deep_zoom_theory_and_pra... https://dirkwhoffmann.github.io/DeepDrill/docs/Theory/MandelbrotSet.html https://dirkwhoffmann.github.io/DeepDrill/docs/Theory/Mandel... In my experience of non-deep-zoom rendering, and contrary to the authors arguments, period detection works well for speeding up renders. It appeared to be fairly safe from false positives. https://dotat.at/@/2010-11-16-interior-iteration-with-less-period-pain.html https://dotat.at/@/2010-11-16-interior-iteration-with-less-p... https://dotat.at/prog/mandelbrot/cyclic.png https://dotat.at/prog/mandelbrot/cyclic.png
- firebot 3y agoI've had some great success using posits for fractals. Unfortunately, soft(ware) posits so rather slow. But mathematically the results were great.
- PaulHoule 3y agoIn Hamiltonian Chaos you draw Poincaré sections of systems like this one https://mathworld.wolfram.com/Henon-HeilesEquation.html https://mathworld.wolfram.com/Henon-HeilesEquation.html and see these chaos zones that look like a field of random dots that probably miss a lot of the structure. The reason why we know those areas are dense with unstable periodic orbits is because they are also dense with periodic orbits. It doesn’t seem feasible to accurately track a system for long enough to believe those.
- anthk 3y agoCode from "The Computational Beauty of Nature" managed to crash CWM under GNU/Linux+X. No issues with FVWM. WIth LibdieHard I managed to avoid the crash. Maybe some ANSI C code from the 90's doesn't like current layouts... On FP precision, sh has almost none, AWK often has up to 20 bit and 53 with gawk and the math library. Ditto with bc -l. Calc has an arbitrary decimal precision and it's really fast. https://github.com/lcn2/calc https://github.com/lcn2/calc
- hansonpeter 3y ago[dead]
- hedora 3y agoIf you need to use 128-bit floats for something, note that your processor probably supports them natively and that there are standard C/C++ types for them. (The boost thing the article links says their quad precision type is “functionally equivalent” to standard types, but uses a different bit layout.)
- andrewf 3y agoI've read this a few places recently but I can't figure out how? https://godbolt.org/z/Mbjs73qar https://godbolt.org/z/Mbjs73qar -- using doubles I get AVX instructions but using 128-bit floats calls some very hefty runtime support functions.
- gpderetta 3y agoThere is no true quad support on x86. GCC implements double-double quads[1] via software emulation on many targets. [1] https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format#Double-double_arithmetic https://en.wikipedia.org/wiki/Quadruple-precision_floating-p...
- fanf2 3y agoYour processor probably doesn’t support quad precision floats in hardware unless it’s an IBM mainframe. https://en.m.wikipedia.org/wiki/Quadruple-precision_floating-point_format#Hardware_support https://en.m.wikipedia.org/wiki/Quadruple-precision_floating...
- aragilar 3y agoPower also supports it, and https://www.raptorcs.com/ https://www.raptorcs.com/ aren't mainframes.
- guenthert 3y agoWhich prompts the question, what is quad precision floating point arithmetic needed for that IBM considered it prudent to implement it in hardware of a mainframe? Who are the customers paying for such? Naively perhaps, I would expect that financial calculations (ought to) rely on fixed-point arithmetic and afaiu simulations of physical systems get away with double precision, if one is careful.
- em3rgent0rdr 3y ago25 years ago I did Mandelbrot with fixed-point integer, and I remember zooming in enough and eventually hit the end of the fractal due to limited resolution.
- thesimp 3y agoI fondly remember Fractint (https://www.fractint.org/ https://www.fractint.org/). And these days I'm amazed at what it could calculate with the very limited CPU cycles at that time. I'm not sure how to compare a 386 running at 25MHz with my AMD 5950x that I have now.
- eru 3y agoFractint did a lot of clever tricks, especially for the Mandelbrot fractal. For example, I remember they exploited that the Mandelbrot set is connected. So that means that if you found that the border of any rectangle is either completely inside or completely outside the set, you don't have to check the inside.
- hkmaxpro 3y agoThis post prompted me to look into the theoretical question of the computability of the Mandelbrot set. And I found this excellent answer: https://math.stackexchange.com/q/4611850 https://math.stackexchange.com/q/4611850
- scoopr 3y agoAnd thats why I only use `fractint`! ;)
- deleted 3y ago[deleted]
- FabHK 3y agoIrrelevant nostalgic note: I implemented the Mandelbrot on the ZX81. Took just a quarter hour or so for the full glorious 64x48 pixels... :-)
- fredcy 3y agoThe popular Mandelbrot zoom-in videos all seem to develop rotational symmetry before long, and the order of that symmetry only increases over time. I've assumed that this is artifact of precision errors compounding.
- fanf2 3y agoIt’s because they usually zoom in on a high-order hyperbolic component https://en.wikipedia.org/wiki/Mandelbrot_set#Hyperbolic_components https://en.wikipedia.org/wiki/Mandelbrot_set#Hyperbolic_comp...
- comonoid 3y agoIt is equally instructive to compute the set on CPU and on GPU.
- cutterx2202 3y ago[dead]