<commit_before>package spire
package math

import spire.algebra.Sign
import spire.tests.SpireProperties

import org.scalacheck.{ Arbitrary, Gen }
import org.scalacheck.Arbitrary.arbitrary

import java.math.{ MathContext, RoundingMode }
import MathContext.{DECIMAL64, DECIMAL128}

class AlgebraicTest extends SpireProperties {

  def approximation(approx0: Algebraic, scale: Int, actual: BigDecimal): Unit = {
    val error = BigDecimal(10).pow(-scale)
    val approx = approx0.toBigDecimal(scale, RoundingMode.HALF_EVEN)
    (approx - error) should be <= actual
    actual should be <= (approx + error)
  }

  property("root isolation failure") {
    val poly = Polynomial("4x^3 + 2x^2 - 3x - 1")
    val roots = Algebraic.roots(poly) 
    // should be -1, (1 - sqrt(5))/4, (1 + sqrt(5))/4
    (roots(0) - roots(1)).isZero shouldBe false 
  }

  property("absolute approximation of addition is correct") {
    val sqrt2x100 = Iterator.fill(100)(Algebraic(2).sqrt).reduce(_ + _)
    val dblSqrt2x100 = math.sqrt(2) * 100
    approximation(sqrt2x100, 4, BigDecimal(dblSqrt2x100))
  }

  property("relative approximation of addition is correct") {
    val sum = Iterator.fill(29)(Algebraic(1) / 29) reduce (_ + _)
    sum.toDouble shouldBe 1.0
    sum.toBigDecimal(DECIMAL128) shouldBe BigDecimal(1)
  }

  property("absolute approximation of subtraction is correct") {
    val negSqrt2x98 = Iterator.fill(100)(Algebraic(2).sqrt) reduce (_ - _)
    val dblNegSqrt2x98 = -math.sqrt(2) * 98
    approximation(negSqrt2x98, 4, BigDecimal(dblNegSqrt2x98))
  }

  property("absolute approximation of multiplication is correct") {
    val p = Iterator.fill(32)(Algebraic(2).sqrt).reduce(_ * _)
    approximation(p, 4, BigDecimal(1 << 16))
  }

  property("relative approximation of multiplication is correct") {
    val p = Iterator.fill(32)(Algebraic(2).sqrt).reduce(_ * _)
    p.toBigDecimal(DECIMAL64) shouldBe BigDecimal(1 << 16)
  }

  property("absolute approximation of division is correct") {
    val q = Algebraic(2).sqrt / 2
    approximation(q, 4, BigDecimal(0.7071067811865476))
  }

  property("relative approximation of division is correct") {
    val q = Iterator.fill(16)(Algebraic(2)).foldLeft(Algebraic(1 << 16))(_ / _)
    q.toDouble shouldBe 1.0

    val oneThird = BigDecimal(-1, DECIMAL128) / 3
    (Algebraic(-1) / 3).toBigDecimal(DECIMAL128) shouldBe oneThird
    (Algebraic(1) / -3).toBigDecimal(DECIMAL128) shouldBe oneThird
  }

  property("absolute approximation of roots is correct") {
    approximation(Algebraic(2).sqrt, 5, BigDecimal(1.4142135623730951))

    // give or take
    approximation(Algebraic(-4) nroot 3, 5, BigDecimal(-1.5874010519681994))
  }

  property("associativity with large and small numbers") {
    val x = Algebraic(1e308)
    val y = Algebraic(-1e308)
    val z = Algebraic(1)
    ((x + (y + z)) shouldBe (x + y + z))
  }

  // This generates rational Algebraic expressions along with their Rational
  // value, then tests that the 2 are equal.
  property("equality test of rational algebraic is correct") {
    forAll("rational") { (qa: RationalAlgebraic) =>
      val RationalAlgebraic(a, q) = qa
      a == Algebraic(q)
    }
  }

  // This generates a Algebraic expression that we know if rational, along with
  // its actual Rational value. We then verify that the computed square root
  // using Algebraic is actually a good approximation to the real square root.
  property("approximation of sqrt of rational is correct") {
    forAll("rational") { (qa: RationalAlgebraic) =>
      val RationalAlgebraic(a, q) = qa
      val x = a.sqrt.toBigDecimal(DECIMAL64)
      val error = x.ulp * 4
      val xSq = x * x
      Rational(xSq - error) < q && Rational(xSq + error) > q
    }
  }

  // This generates a class of sums of square-roots that evaluate to 0. We
  // simply verify that Algebraic agrees they are 0. Many of the terms
  // generated will be irrational.
  property("simple zero sum of sqrt") {
    forAll("rational") { (z0: RationalAlgebraic) =>
      val RationalAlgebraic(a, z) = z0
      val y = z.pow(3)
      val x = y + 2 * z.pow(2) + z
      val zero = Algebraic(x).sqrt - Algebraic(y).sqrt - a.sqrt
      zero.isZero
    }
  }

  def trickyZero = Algebraic(18).sqrt - Algebraic(8).sqrt - Algebraic(2).sqrt

  // This is just a simpler special case of the property test above.
  property("sign of tricky zero is Zero") {
    (trickyZero.sign shouldBe Sign.Zero)
  }

  property("relative approximation of zero is zero") {
    ((Algebraic(0).toBigDecimal(DECIMAL128)) shouldBe BigDecimal(0))
    (trickyZero.toDouble shouldBe 0.0)
  }

/*
  // this causes frequent test failures. Todo: fix this
  // Generate a bunch of rational roots for a polynomial, then construct a
  // rational polynomial with these roots, and then verify that Algebraic.roots
  // finds all the roots exactly.
  property("find all rational roots of rational polynomial") {
    import spire.implicits._
    val genRootSelection: Gen[(List[Rational], Int)] = for {
      roots <- Gen.nonEmptyListOf(genRational)
      i <- Gen.choose(0, roots.size)
    } yield (roots, i)

    // These tests can be a bit slow, so we bump down the # and size.
    forAll(Gen.nonEmptyListOf(genRational), minSuccessful(20), maxSize(8)) { roots =>
      val poly = roots.map(x => Polynomial.linear(Rational.one, -x)).qproduct
      val algebraicRoots = Algebraic.roots(poly)
      (roots.sorted zip algebraicRoots).forall { case (qRoot, aRoot) =>
        aRoot == Algebraic(qRoot)
      }
    }
  }
  */

  // This was a failing test case found using the property tests above.
  property("root isolation uses inverse transform to map upper-bound") {
    import spire.implicits._
    val roots = List(
      Rational("16279/50267"),
      Rational("223/175")
    )<commit_msg>Re-enable broken test.<commit_after>package spire
package math

import spire.algebra.Sign
import spire.tests.SpireProperties

import org.scalacheck.{ Arbitrary, Gen }
import org.scalacheck.Arbitrary.arbitrary

import java.math.{ MathContext, RoundingMode }
import MathContext.{DECIMAL64, DECIMAL128}

class AlgebraicTest extends SpireProperties {

  def approximation(approx0: Algebraic, scale: Int, actual: BigDecimal): Unit = {
    val error = BigDecimal(10).pow(-scale)
    val approx = approx0.toBigDecimal(scale, RoundingMode.HALF_EVEN)
    (approx - error) should be <= actual
    actual should be <= (approx + error)
  }

  property("root isolation failure") {
    val poly = Polynomial("4x^3 + 2x^2 - 3x - 1")
    val roots = Algebraic.roots(poly) 
    // should be -1, (1 - sqrt(5))/4, (1 + sqrt(5))/4
    (roots(0) - roots(1)).isZero shouldBe false 
  }

  property("absolute approximation of addition is correct") {
    val sqrt2x100 = Iterator.fill(100)(Algebraic(2).sqrt).reduce(_ + _)
    val dblSqrt2x100 = math.sqrt(2) * 100
    approximation(sqrt2x100, 4, BigDecimal(dblSqrt2x100))
  }

  property("relative approximation of addition is correct") {
    val sum = Iterator.fill(29)(Algebraic(1) / 29) reduce (_ + _)
    sum.toDouble shouldBe 1.0
    sum.toBigDecimal(DECIMAL128) shouldBe BigDecimal(1)
  }

  property("absolute approximation of subtraction is correct") {
    val negSqrt2x98 = Iterator.fill(100)(Algebraic(2).sqrt) reduce (_ - _)
    val dblNegSqrt2x98 = -math.sqrt(2) * 98
    approximation(negSqrt2x98, 4, BigDecimal(dblNegSqrt2x98))
  }

  property("absolute approximation of multiplication is correct") {
    val p = Iterator.fill(32)(Algebraic(2).sqrt).reduce(_ * _)
    approximation(p, 4, BigDecimal(1 << 16))
  }

  property("relative approximation of multiplication is correct") {
    val p = Iterator.fill(32)(Algebraic(2).sqrt).reduce(_ * _)
    p.toBigDecimal(DECIMAL64) shouldBe BigDecimal(1 << 16)
  }

  property("absolute approximation of division is correct") {
    val q = Algebraic(2).sqrt / 2
    approximation(q, 4, BigDecimal(0.7071067811865476))
  }

  property("relative approximation of division is correct") {
    val q = Iterator.fill(16)(Algebraic(2)).foldLeft(Algebraic(1 << 16))(_ / _)
    q.toDouble shouldBe 1.0

    val oneThird = BigDecimal(-1, DECIMAL128) / 3
    (Algebraic(-1) / 3).toBigDecimal(DECIMAL128) shouldBe oneThird
    (Algebraic(1) / -3).toBigDecimal(DECIMAL128) shouldBe oneThird
  }

  property("absolute approximation of roots is correct") {
    approximation(Algebraic(2).sqrt, 5, BigDecimal(1.4142135623730951))

    // give or take
    approximation(Algebraic(-4) nroot 3, 5, BigDecimal(-1.5874010519681994))
  }

  property("associativity with large and small numbers") {
    val x = Algebraic(1e308)
    val y = Algebraic(-1e308)
    val z = Algebraic(1)
    ((x + (y + z)) shouldBe (x + y + z))
  }

  // This generates rational Algebraic expressions along with their Rational
  // value, then tests that the 2 are equal.
  property("equality test of rational algebraic is correct") {
    forAll("rational") { (qa: RationalAlgebraic) =>
      val RationalAlgebraic(a, q) = qa
      a == Algebraic(q)
    }
  }

  // This generates a Algebraic expression that we know if rational, along with
  // its actual Rational value. We then verify that the computed square root
  // using Algebraic is actually a good approximation to the real square root.
  property("approximation of sqrt of rational is correct") {
    forAll("rational") { (qa: RationalAlgebraic) =>
      val RationalAlgebraic(a, q) = qa
      val x = a.sqrt.toBigDecimal(DECIMAL64)
      val error = x.ulp * 4
      val xSq = x * x
      Rational(xSq - error) < q && Rational(xSq + error) > q
    }
  }

  // This generates a class of sums of square-roots that evaluate to 0. We
  // simply verify that Algebraic agrees they are 0. Many of the terms
  // generated will be irrational.
  property("simple zero sum of sqrt") {
    forAll("rational") { (z0: RationalAlgebraic) =>
      val RationalAlgebraic(a, z) = z0
      val y = z.pow(3)
      val x = y + 2 * z.pow(2) + z
      val zero = Algebraic(x).sqrt - Algebraic(y).sqrt - a.sqrt
      zero.isZero
    }
  }

  def trickyZero = Algebraic(18).sqrt - Algebraic(8).sqrt - Algebraic(2).sqrt

  // This is just a simpler special case of the property test above.
  property("sign of tricky zero is Zero") {
    (trickyZero.sign shouldBe Sign.Zero)
  }

  property("relative approximation of zero is zero") {
    ((Algebraic(0).toBigDecimal(DECIMAL128)) shouldBe BigDecimal(0))
    (trickyZero.toDouble shouldBe 0.0)
  }

  // Generate a bunch of rational roots for a polynomial, then construct a
  // rational polynomial with these roots, and then verify that Algebraic.roots
  // finds all the roots exactly.
  property("find all rational roots of rational polynomial") {
    import spire.implicits._
    val genRootSelection: Gen[(List[Rational], Int)] = for {
      roots <- Gen.nonEmptyListOf(genRational)
      i <- Gen.choose(0, roots.size)
    } yield (roots, i)

    // These tests can be a bit slow, so we bump down the # and size.
    forAll(Gen.nonEmptyListOf(genRational), minSuccessful(20), maxSize(8)) { roots =>
      val poly = roots.map(x => Polynomial.linear(Rational.one, -x)).qproduct
      val algebraicRoots = Algebraic.roots(poly)
      (roots.sorted zip algebraicRoots).forall { case (qRoot, aRoot) =>
        aRoot == Algebraic(qRoot)
      }
    }
  }

  // This was a failing test case found using the property tests above.
  property("root isolation uses inverse transform to map upper-bound") {
    import spire.implicits._
    val roots = List(
      Rational("16279/50267"),
      Rational("223/175")
    )
{'fraction_non_alphanumeric': 0.11666811129409725, 'fraction_numerical': 0.03952500650082344, 'mean_word_length': 3.349038823972861, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4734849', 'n_tokens_mistral': 4092, 'n_tokens_neox': 3713, 'n_words': 1072}