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

math/big: Float.Sqrt does not set accuracy #37915

Open
mohanson opened this issue Mar 18, 2020 · 7 comments
Open

math/big: Float.Sqrt does not set accuracy #37915

mohanson opened this issue Mar 18, 2020 · 7 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@mohanson
Copy link

What version of Go are you using (go version)?

$ go version go1.13.8 linux/amd64

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/root/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/root/app/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/root/app/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build510748991=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I was researching ieee 754, and when using go, I found that the big.Float.Sqrt function always output exact results. I calculate sqrt(pi) with go and cpp on one enviroment:

Go

package main

import (
	"log"
	"math/big"
)

func main() {
	pi := big.NewFloat(3.14159265)
	r := big.NewFloat(0).Sqrt(pi)
	log.Println(r, r.Acc())
}

Cpp

#include <iostream>
#include <cfenv>
#include <cmath>

#pragma STDC FENV_ACCESS ON

double pi = 3.14159265;

int main()
{
    std::feclearexcept(FE_ALL_EXCEPT);
    std::cout << "sqrt(pi) = " << sqrt(pi) << '\n';
    if(std::fetestexcept(FE_INEXACT)) {
        std::cout << "inexact result reported\n";
    } else {
        std::cout << "inexact result not reported\n";
    }
}

What did you expect to see?

golang: 1.7724538498928541 "InExact"
cpp     : sqrt(pi) = 1.77245, inexact result reported

What did you see instead?

golang: 1.7724538498928541 "Exact"
cpp     :  sqrt(pi) = 1.77245, inexact result reported

I don't think this is an accurate value, for sqrt(pi) = 1.7724538498928541 in go

@ALTree
Copy link
Member

ALTree commented Mar 18, 2020

Yeah Sqrt never sets the acc field. It's true that the Acc( ) doc says

Acc returns the accuracy of x produced by the most recent operation.

but I'm not sure it applies to Sqrt. In general, I'm not sure we can report accuracy correctly at a small cost. It might require we run another Newton iteration in the worst case, which is pretty expensive (like it could double the time).

cc @griesemer

@ALTree ALTree changed the title big.Float.Sqrt does not give an Inexact error, which defined in ieee 754 math/big: Float.Sqrt does not set accuracy Mar 18, 2020
@ALTree ALTree added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 18, 2020
@ALTree
Copy link
Member

ALTree commented Mar 18, 2020

(small note: the Go equivalent of cmath's sqrt( ) is math.Sqrt( ), the big.Float type you are using is for arbitrary precision math).

@mohanson
Copy link
Author

Another point, 0.1 + 0.2 = 0.3 is "Inexact" in go.

r := big.NewFloat(0).Add(big.NewFloat(0.1), big.NewFloat(0.2))
log.Println(r.Acc())
// "Above"

@ALTree
Copy link
Member

ALTree commented Mar 18, 2020

@mohanson that is correct. 0.1 and 0.2 and 0.3 are not exactly representable in IEEE-754.

@griesemer
Copy link
Contributor

I see four ways this could be addressed:

  1. Do nothing.
  2. Document that Sqrt doesn't set the accuracy (and thus its value is invalid).
  3. Have Sqrt compute the square of the result in full precision and see if it is exactly the argument for Sqrt (in which case its result was accurate).
  4. Perhaps it's possible to track accuracy through the Newton iteration and report it that way.

Solution 1) is not a good idea. 4) might not be very expensive but I don't know if it is feasible. This leaves us with 2) or 3).

We should start with 2) (easy), and then follow up with 3) if if turns out that the extra multiplication is an acceptable cost. Since we always care about speed, it probably isn't.

For an application that needs to know whether the Sqrt was exact, it's always possible to do 3) separately. If this turns out to be important (which I doubt), one could even have a IsSqrtExact function that takes the original value and the sqrt of it and computes the accuracy.

@griesemer griesemer added the NeedsFix The path to resolution is known, but the work has not been done. label Mar 20, 2020
@gopherbot gopherbot removed the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 20, 2020
@griesemer griesemer added this to the Go1.15 milestone Mar 20, 2020
@gopherbot
Copy link

Change https://golang.org/cl/224497 mentions this issue: math/big: document that Sqrt doesn't set Accuracy

gopherbot pushed a commit that referenced this issue Mar 20, 2020
Document that the Float.Sqrt method does not set the receiver's
Accuracy field.

Updates #37915

Change-Id: Ief1dcac07eacc0ef02f86bfac9044501477bca1c
Reviewed-on: https://go-review.googlesource.com/c/go/+/224497
Reviewed-by: Robert Griesemer <gri@golang.org>
@griesemer griesemer added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed Documentation NeedsFix The path to resolution is known, but the work has not been done. labels Mar 20, 2020
@griesemer griesemer modified the milestones: Go1.15, Unplanned Mar 20, 2020
@griesemer
Copy link
Contributor

The original issue was fixed by updating the documentation.

Leaving this issue open as a reminder to investigate a better solution. No urgency. See also #37915 (comment).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

5 participants