Git Product home page Git Product logo

rpolyplusplus's Issues

Incorrect roots found

I have been testing the library on some polynomials with integer coefficients. On many of them incorrect roots are found. One of the examples:

Coefficients: [1,0,-1,0,1,1,1,1,1,1,1,0,-1,0,1]

Roots found:

  1.1910 + 0.6054i
  1.1910 - 0.6054i
 -1.2766 + 0.3311i
 -1.2766 - 0.3311i
 -0.9114 + 0.8715i
 -0.9114 - 0.8715i
 -0.2781 + 1.1229i
 -0.2781 - 1.1229i
  0.4173 + 0.9860i
  0.4173 - 0.9860i
  0.6739 + 0.3241i
  0.6739 - 0.3241i
  0.1838 + 0.2115i
  0.1838 - 0.2115i

True roots:

  1.2051 + 0.5795i
  1.2051 - 0.5795i
 -0.5464 + 0.8375i
 -0.5464 - 0.8375i
 -0.9793 + 0.2023i
 -0.9793 - 0.2023i
 -0.8508 + 0.5254i
 -0.8508 - 0.5254i
  0.5333 + 0.8459i
  0.5333 - 0.8459i
 -0.0358 + 0.9994i
 -0.0358 - 0.9994i
  0.6739 + 0.3241i
  0.6739 - 0.3241i

Roots are sorted by magnitude.

Clang Reports Use of Uninitialized Variable

Clang complains that the uninitialized variable 'polynomial_at_root' at line 603 of find_polynomial_roots_jenkins_traub.cc is assigned to 'prev_polynomial_at_root' at line 618, which is subsequently used uninitialized.

Segfault for specific case

Creating the 6th degree polynomials with coefficients as given at the end
of this message ends with a segmentation fault error. I don't remember
which of the 4 cases given crashes, but I think it was number 2 or 3.
Running RPolyPlusPlus with the commit from Aug 11, 2015 will
not result in the crash. This means the error only happens with the
newest commit (on Mar 9, 2016).

Hilmar

coeffs =
1
-359951
3.78335e+10
-1.37262e+15
5.26491e+18
0
0

coeffs =
1
-611771
8.23017e+10
-5.62821e+14
-4.18369e+18
0
0

coeffs =
1
-691197
1.27678e+11
-6.9045e+15
8.80928e+19
0
0

coeffs =
1
-280525
2.53443e+10
-7.45354e+14
-7.27967e+17
0
0

Not correctly solving certain quartics

Under some situations, I have found that the solver is outputting all zeros, below are some coefficients that caused it for me. I have tried putting some of these into wolfram alpha, which gives non-zero solutions.

I was using the solver to render a torus in a ray-tracing application for an assignment.

I am currently working around this issue by detecting the all-zeros condition, and retrying with slightly different numbers. As this is relatively rare, it hasn't been causing a noticable performance impact.

          1
   -198.995
    15006.6
    -508127
6.52025e+06

          1
   -200.246
    15131.5
    -511320
6.52025e+06

          1
   -202.193
    15327.2
    -516281
6.52025e+06

          1
   -202.205
    15328.4
    -516313
6.52025e+06

          1
   -202.215
    15329.4
    -516336
6.52025e+06

          1
   -202.268
    15334.8
    -516476
6.52025e+06

          1
   -202.289
    15336.8
    -516525
6.52025e+06

          1
    -202.35
      15343
    -516680
6.52025e+06

          1
   -202.389
      15347
    -516781
6.52025e+06

          1
   -202.388
    15346.8
    -516775
6.52025e+06

          1
   -202.427
    15350.8
    -516876
6.52025e+06

          1
   -202.427
    15350.8
    -516876
6.52025e+06

code producing the unwanted behaviour:

//find closest intersection with a ray originating at posn, and traveling in unit direction d
float Torus::intersect(glm::vec3 posn, glm::vec3 d)
{

	glm::vec3 p = posn - this->center;

        //checking for intersection with bounding sphere for optimization reasons
	float len = glm::length(posn);
	glm::vec3 finalPos = posn + d*len;

	if (glm::length(finalPos) > (r1 + d1))
	{
		return -1.0;
	}


	float a = glm::dot(d, d);
	float b = 2 * glm::dot(p, d);
	float c = glm::dot(p, p) + powf(d1, 2) - powf(r1, 2);
	float alpha = powf(d.x, 2) + powf(d.z, 2);
	float beta = 2 * (p.x*d.x + p.z*d.z);
	float gamma = powf(p.x, 2) + powf(p.z, 2);
	Eigen::VectorXd polynomial(5);
	polynomial[0] = powf(a, 2);
	polynomial[1] = 2 * a*b;
	polynomial[2] = 2 * a*c + powf(b, 2) - 4 * powf(d1, 2) *alpha;
	polynomial[3] = 2 * b*c - 4 * powf(d1, 2) *beta;
	polynomial[4] = powf(c, 2) - 4 * powf(d1, 2) *gamma;

	Eigen::VectorXd *realRoots = new Eigen::VectorXd();
	Eigen::VectorXd *compRoots = new Eigen::VectorXd();
	rpoly_plus_plus::FindPolynomialRootsJenkinsTraub(polynomial, realRoots, compRoots);

	float closest = -1.0;
	bool nonzero = 0;
	for (int i = 0; (*realRoots).size() > i; i++)
	{
		double d = (*realRoots).data()[i];
		double c = (*compRoots).data()[i];
		nonzero = nonzero || (d != 0 || c != 0);
		if (fabs(c) < 1e-7 && d > 1e-7 && (d < closest || closest == -1.0))
		{
			closest = d;
		}
	}
	if (!nonzero)
	{
		std::cout << polynomial << "\n" << "\n";
		//return(this->intersect(glm::vec3(posn.x+0.0001, posn.y, posn.z), d));
	}
	//std::cout<<closest<<"\n";
	return closest;
}

program output(set to display surface normals for debugging purposes), the pixel sized holes represent the locations where the solver returned zeros:
image

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.