3
$\begingroup$

My code needs to check whether a lot of low-degree equations (usually quadratic and cubic) are solvable in integers. There are many equations, so the speed is crucial. Let us start with quadratic equations and, for test, consider 10,000 equations in the form $ax^2+bx+c=0$ where $a,b,c$ are random integers up to $10^{10}$. If I use standard command

Reduce[a x^2 + b x + c == 0, {x}, Integers]

then these equations are solved in total time 1.34. Alternatively, we can check whether the determinant $d=b^2-4ac$ is a perfect square. If for this I use

If[IntegerQ[Sqrt[d]]

command, then the total time becomes 0.53. However, I then searched online for the best way to check whether an integer is a perfect square and found the command

If[FractionalPart@Sqrt[d + 0``1] == 0,

With it help, all the equations are checked in just 0.047 second!

My question is whether a method with similar speed up comparing to Reduce exists for checking integer solvability for cubic equations $ax^3+bx^2+cx+d=0$, where $a,b,c,d$ are integer coefficients with about $10-30$ digits.

$\endgroup$
7
  • $\begingroup$ Have you tried Solve? For example, with d = {-824150223890338609745847277134931678957, 648037579, 685402538, 1436522590} I find that Or @@ IntegerQ /@ SolveValues[d . {1, y, y^2, y^3} == 0, y] takes less than 4 milliseconds. $\endgroup$
    – Roman
    May 2, 2022 at 16:06
  • $\begingroup$ I have just tried Solve for the 10,000 equations with random coefficients in the same range, and the total time for all equations is over 9 seconds, which is much slower than 1.34 seconds for Reduce. $\endgroup$ May 2, 2022 at 16:31
  • $\begingroup$ Maybe the math stackexchange could give some neat insight into condition on the coefficients that can be derived from Vieta's formulas or other tricks. $\endgroup$
    – Roman
    May 2, 2022 at 17:36
  • $\begingroup$ There are formulas for cubic equations, I can just apply them to find solutions and use IntegerQ to check if any solution is integer. But, as you can see from the question, for quadratic equations IntegerQ reduces to checking whether an integer is a perfect square and can be replaced by a 10 times faster FractionalPart@Sqrt trick. I am looking for similar Mathematica-specific trick for cubic equations, and I do not think people from math stackexchange know such tricks better than here. $\endgroup$ May 2, 2022 at 17:50
  • $\begingroup$ I guess that most equations won't have solutions in the integers, so a fast technique that eliminates a lot of obviously impossible equations might be useful. For example, reducing the equations modulo a small integer would allow many equations to be eliminated using a practical look up table (e.g. n^4 for mod n). You would still need to do full checks for any cases with solutions modulo n. $\endgroup$
    – mikado
    May 2, 2022 at 19:44

1 Answer 1

3
$\begingroup$

My fastest version of extending the trick, FractionalPart[expr]==0 to roots of a cubic is below.

integerRootTest[a_.*z_^3+b_.*z_^2+c_.*z_+d_.,z_Symbol]/;
  And[NumericQ[a],NumericQ[b],NumericQ[c],NumericQ[d]]:=
  Module[{p,q,r,s},
    p= 3 a c - b^2;
    q= -2 b^3 + 3a(3b c - 9 a d);
    r= q + Sqrt[4 p^3 + q^2 + 0.``1];
    s= -b/(3a);
    Or[
      FractionalPart[s+(r^(1/3)/2^(1/3)-((2^(1/3)*p)/r^(1/3)))/(3 a)]==0,
      FractionalPart[s+(((1+I*Sqrt[3])*p)/(2^(1/3)*r^(1/3))-((1-I*Sqrt[3])*r^(1/3))/2)/(3 a 2^(1/3))]==0,
      FractionalPart[s+(((1-I*Sqrt[3])*p)/(2^(1/3)*r^(1/3))-((1+I*Sqrt[3])*r^(1/3))/2)/(3 a 2^(1/3))]==0
    ]]

Examples:

integerRootTest[ -15 + 14 x - 6 x^2 + x^3, x]
(* True *)

integerRootTest[ -17 + 14 x - 6 x^2 + x^3, x]
(* False *)

If you know (a,b,c,d) are all machine integers, you can make the above Compile which will run much faster. I leave it to others to see how fast that is compared with using built-in functions.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer! However, I just did the same experiment with 10,000 equations with random coefficients, but now cubic, and discovered that Reduce works in 1.76 seconds for all equations in total, while the suggested test works in 2.42 seconds. So, it looks like Reduce is implemented quite inefficiently for quadratic equations but is quite difficult to beat for higher degree equations starting from the cubic ones. $\endgroup$ May 2, 2022 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.