in reply to Re: Determining the minimum representable increment/decrement possible?
in thread Determining the minimum representable increment/decrement possible?
Basically, to determine what the smallest delta for a given floating-point, decompose that value's ieee representation into sign, fraction, and exponent. My perl's NV is double-precision (53bit precision): from MSB to LSB, sign bit, 11 exponent bits, and 52 fractional bits (plus an implied 1), for sign*(1+fract_bits/2^52)*(2**exp), where (which my perl's NV is), the smallest change would be 2**(-52+exp). So you should just need to know your exp for the current representation (not forgetting to subtract 1023 from the 11bit exponent number). If your NV is more precise (lucky you), just adjust it appropriately.
That's a nice insight. Thankyou. If I need to go this route, that is almost certainly the way to do it.
However, I'm not certain of this yet, but I think my OP question may not actually be required. The problem appears to be -- I'm still struggling with x64 assembler to try and confirm this -- that I'm encountering a lot of denormal numbers; and if I can avoid them, the underlying problem that my OP was an attempt to solve, goes away.
And the problem with avoiding denormal numbers is that the purpose of the code that is generating them is a Newton-Raphson iteration to converge on zero. The exact place where denormals raise their ugly heads. The solution may be (maybe?) to add a constant (say 1 or 2) to both sides of the equations and converge to that number instead. (Not sure about that; but it might work :)
I started work on a module that will expand an ieee754 double-precision float into sign*(1+fract)*2^exp, based on the internal representation.
You might find Exploring IEEE754 floating point bit patterns. (and as you're working with 5.6 , the version at Re^2: Exploring IEEE754 floating point bit patterns.) interesting or even useful.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^3: Determining the minimum representable increment/decrement possible?
by pryrt (Abbot) on Jun 15, 2016 at 23:35 UTC | |
Wow! Your convergence criteria are a lot more stringent than mine ever have been, if you're trying to get below a 1bit shift for a 53-bit precision number. (In anything I've tried to converge, I've never cared about less than ~1ppm.) Your offset technique to avoid the denormals sounds promising. And thanks for the links; I'll keep them bookmarked when I get a change to work on my module more. | [reply] |
by BrowserUk (Patriarch) on Jun 16, 2016 at 00:34 UTC | |
Wow! Your convergence criteria are a lot more stringent than mine ever have been, if you're trying to get below a 1bit shift for a 53-bit precision number. They aren't really my criteria; I'm trying to match the results produced by the code I am optimising, prior to my optimisations. I've got it to the point where over 25% of the runtime is now down to exactly 2 opcodes, both 64-bit double divides in deeply nested loops. Luckily, the divisor in both cases is invariant in the inner loop, so going the classical route of replacing the division by multiplication by the reciprocal of the divisor reduces the cost of both of those opcodes by just under 95%. (For my test case, from 1.17s to 0.06s.) The problem is that some 20% (~90,000 of 450,000) of the resultant values differ from the unoptimised code. The maximum individual difference is less than 2e-16; but cumulatively they could have an impact on the numbers derived from the dataset. And my simple testcase is 450,000 datapoints; the real ones that got me started on this quest have upwards of 10 million datapoints. But that is only half of the story. I'm just discovering that a big part of the reason for the dramatic effect, in this case, of replacing x /= n; with x *= 1/n (where 1/n has been pre-calculated outside of the inner loop) is that it avoids the generation of denormal numbers. And denormal numbers are known to have a huge performance affect on FPUs. I've only learnt this in the last 10 hrs or so. My OP was seeking to adjust the value produced by 1/n, so as to minimise the accumulated difference in the values produced by the pre- & post-optimised code. But, from a few samples of the 90,000 I've inspected so far, the differences (between x /= n and x *= 1/n) only rise above 0.5 ulp when x is a denormal value. I've never had to deal with denormals before; so this is all new ground for me; and I'm finding it particularly taxing; requiring lots of research in areas of math that go way over my head. At least the papers do. In many cases -- as so often -- when you cut through the jargon, notation and 'math-paper-ese' that seems to be obligatory, the actual code required -- which is *never* included -- is relatively simple. Eg. Pick a pdf; and then realise that it all comes down to something as simple as:
Why, oh why, do they insist on making everything so damn complicated? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
In the absence of evidence, opinion is indistinguishable from prejudice. Not understood.
| [reply] [d/l] [select] |
Re^3: Determining the minimum representable increment/decrement possible?
by pryrt (Abbot) on Jun 30, 2016 at 23:50 UTC | |
I'm sure you've moved beyond this... but for future searchers: While trying to implement some ULP-manipulating routines in my Data::IEEE754::Tools development (which I used to call Expand.pm), I was googling to fix a bug, and was led to Data::Float, which actually has most of the tools I was trying to implement in my module. Using that CPAN module, I was able to write a sub which found the ULP for any finite value (normal or denormal); it returns INF or NAN when one of those was passed.
| [reply] [d/l] |
by syphilis (Archbishop) on Jul 01, 2016 at 01:09 UTC | |
It also provides nextup, nextdown and nextafter functions. Be aware that the outputs you're getting provide insufficient precision - eg the approximation 4.44089209850063e-016 instead of the accurate 4.4408920985006262e-16. Cheers, Rob | [reply] |
by BrowserUk (Patriarch) on Jul 04, 2016 at 14:21 UTC | |
I was googling to fix a bug, and was led to Data::Float, which actually has most of the tools I was trying to implement in my module. You should not let that stop you. That module gets (mostly) the right answers, but boy does it ever go about it in a convoluted way; which makes it very slow even for pure perl code. For example, this compares his method of nextup() and nextdown() with a couple of trivial routines I threw together when exploring this earlier:
And this compares his float_hex() routine with my asHex():
His are more than a magnitude slower in both cases -- mostly because he uses convoluted and complicated numerical methods rather than simple and pragmatic bitwise methods -- and certainly for my OP problem of trying to tune some floating point optimisations, that would be a show stopper. Here is the code that produce the above timings -- is just a mish-mash of bits and pieces from other scripts thrown together to test and validate that module. If any of it is useful to you; feel free to use it:
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
In the absence of evidence, opinion is indistinguishable from prejudice. Not understood.
| [reply] [d/l] [select] |
by BrowserUk (Patriarch) on Jul 04, 2016 at 15:01 UTC | |
I was asked off-line to explain what I meant by: he uses convoluted and complicated numerical methods rather than simple and pragmatic bitwise methods Which would you rather maintain or debug? My routine for formating a double into a hexadecimal floating point constant:
Or same thing from Data::Float:
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
In the absence of evidence, opinion is indistinguishable from prejudice. Not understood.
| [reply] [d/l] [select] |