Skip to content
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

RFC for std.math.hypot: "An Improved Algorithm for hypot(a,b)" #17915

Closed
expikr opened this issue Nov 7, 2023 · 0 comments · Fixed by #19472
Closed

RFC for std.math.hypot: "An Improved Algorithm for hypot(a,b)" #17915

expikr opened this issue Nov 7, 2023 · 0 comments · Fixed by #19472
Labels
enhancement Solving this issue will likely involve adding new logic or components to the codebase. optimization standard library This issue involves writing Zig code for the standard library.
Milestone

Comments

@expikr
Copy link
Contributor

expikr commented Nov 7, 2023

I've transcribed the proposed algorithm described in this paper (published https://dl.acm.org/doi/10.1145/3428446) as follows:

// The "Corrected (fused)" algorithm described in https://dl.acm.org/doi/10.1145/3428446
fn hypot_corrected_fused(comptime T: type, x: T, y: T) T {
    const r = @sqrt(@mulAdd(T, x, x, y * y));
    const rr = r * r;
    const xx = x * x;
    const z = @mulAdd(T, -y, y, rr - xx) + @mulAdd(T, r, r, -rr) - @mulAdd(T, x, x, -xx);
    return r - z / (2 * r);
}

The key idea seems to be summarized in this paragraph:

The second existing approach is the code that has been delivered with the stan-
dard C math library since at least 1991. The code appears in appendix B and
we shall refer to it as clib hypot(). It deals with widely varying operands and
prevents intermediate overflow/underflow using methods similar to those we will
use in ours.[footnote 1] It works by using a variety of tricks to artificially extend the precision
of the computed a2 + b2 so that they get a correctly rounded value (or very nearly
so). This is then passed to the sqrt() function. What we will observe in the test-
ing is that all this additional work can be effectively superseded by a single fused
multiply-add.

[footnote 1] There is a clear flaw in the threshold used for widely varying operands and it is much broader
than necessary.

I haven't personally benchmarked the accuracy claims of the paper yet, wondering if folks here might share some thoughts on its veracity and whether it's worth integrating into the stdlib?

@expikr expikr changed the title RFC for std.math: "An Improved Algorithm for hypot(a,b)" RFC for std.math.hypot: "An Improved Algorithm for hypot(a,b)" Nov 7, 2023
@Vexu Vexu added standard library This issue involves writing Zig code for the standard library. enhancement Solving this issue will likely involve adding new logic or components to the codebase. optimization labels Mar 26, 2024
@Vexu Vexu added this to the 1.0.0 milestone Mar 26, 2024
@andrewrk andrewrk modified the milestones: 1.0.0, 0.13.0 Jun 4, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement Solving this issue will likely involve adding new logic or components to the codebase. optimization standard library This issue involves writing Zig code for the standard library.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants