How can I reduce time taken for Cardano Triplet Algorithm?-CodePudding

What is Cardano Triplet ?

If a set of any three positive integers, let's say a, b and c satisfies the condition

cbrt(a   b(sqrt(c))   cbrt(a - b(sqrt(c)) == 1

Explanation.

if sum of Cubic Root of a (b * square root of c) and Cubic root of a - (b * square root of c) equals 1 then (a, b, c) is said to be a Cardano triplet.

cbrt represents Cubic Root and sqrt means Square Root.

A integer n will be given, so the numbers a, b and c that we take when added should be lesser than or equal to n.

In short a b c <= n.

Constraint : n <= 2^31 -1.

Problem

I've already done something which finds out the correct triplets but when the value of n is greater than 1000 the program runs forever.

public static void cardanoTriplets(long n) {
        DecimalFormat decimalFormat = new DecimalFormat("#.###");

        long numberOfPairs = 0;

        for (long a = 0; a <= n; a  ) {
            for (long b = 0; b <= n; b  ) {
                for (long c = 0; c <= (n - a - b); c  ) {
                    if ((a   b   c) == n) {
                        double val = b * Math.sqrt(c);
                        double LHS = Double.parseDouble(decimalFormat.format(Math.cbrt(a   val)));
                        double RHS = Double.parseDouble(decimalFormat.format(Math.cbrt(a - val)));
                        double addedVal = LHS   RHS;
                        //System.out.println("RHS and LHS -: ( "   RHS   " , "   LHS   " )");

                        if (addedVal == 1.0d) {
                            numberOfPairs  ;
                            //System.out.println(a);
                            //System.out.println(b);
                            //System.out.println(c   "\n");
                        }
                    }
                }
            }
        }

        System.out.println(numberOfPairs);
    }

Results

When I pass the value of n as 8, on average the time taken to find the cardano triplet is 31ms and sometimes as low as 16ms. The result was accurate and the result is just one and the triplet is (2, 1, 5).
But when I pass the value of n as 1000, it increases to about 1015ms and the result are not as accurate. It misses out almost 19 triplets. Total number of triplets are 149 for n == 1000.
When the value of n > 1000, let's say 5000, it took 29271ms which is 29 seconds approx and the triplets found are 3364.

Is there any way to reduce time taken to a reasonable amount like less than 5 seconds ?

If so how ?

My Device Specs :

Processor : AMD Ryzen 5 3500U Quad Core

RAM : 8 GB

IDE used : IntelliJ IDEA v2021.2.3 (Community Edition)

Thank you :)

CodePudding user response：

This is a number-theoretical problem; using an imprecise floating point is obviously wrong.

The correct solution requires some math insight. Cardano's name is a great hint.

The expression

cbrt(a   b(sqrt(c))   cbrt(a - b(sqrt(c))

describes a root of a certain cubic equation. Specifically, the roots of an equation

x^3   px - q = 0

are

cbrt(q/2   sqrt((q/2)^2   (p/3)^3))   cbrt(q/2) - sqrt(q/2)^2   (p/3)^3))

Comparing with your problem statement, conclude that a = q/2, and c*b^2 = (q/2)^2 (p/3)^3

Since a is an integer, q must be even, and since b, c are also integers, p must be divisible by 3. Therefore we are interested in the equations

x^3   3ux - 2a = 0

having 1 as a root. That narrows the problem down to searching u, v such that 1 3u - 2a = 0. Here u^3 a^2 = b^2*c. Notice that u must be odd.

All these observations lead to a (pseudo)code:

   for u in range(1, n, 2)
       a = (1   3u)/2
       t = u^3   a^2
       find the largest b such that b^2 divides t
       c = t / b^2
       if a   b   c < n
           they are a Cardano triplet

CodePudding user response：

Your first problem, is the loop-in-loop-in-loop what will take 1.000.000.000 rounds for n=1000.

As you know already that n = a b c, you can take one loop out. the c-loop and rewrite as:

for (long a = 0; a <= n; a  ) {
            for (long b = 0; b <= (n - a); b  ) {
                long c = n - a - b;

so you go from n * n * n -> n * n

If the equation is n => a b c (as in your problem statement), you can use:

for (long a = 0; a <= n; a  ) {
        for (long b = 0; b <= (n - a); b  ) {
            for (long c = 0; c <= (n - a - b); c  ) {

Second, you are doing a format to a decimal and then convert back to double where as the Math.cbrt gives already a double. I would suggest not doing so.

The problem of "missing 19 triplets" is related to the point above. You only accept 1.0d as the correct answer, there in the previous step you did formatting on the doubles (most likely giving rounding issues). Even if you would take out the formatting, I believe it is better to allow for a bit more rounding error..

something like:

if (0.999 < addedVal && addedVal <  1.001)

However, I have no idea on the math of this equation as there must be a reason why you say there are 149 triplets.. Depending on the rounding for sure you have different answers... I believe there is something like mathemathical proof the triplets are 1.

Last what you can do: I believe the calculation of the Math.cbrt is not that fast. You are repeating this a lot. You can keep track of your calculation by placing the result of the Math,cbrt in a HashSet. The Key is the input and the Value the result of the Math.cbrt.

So first check if you have the Key already in the HashSet, if not calculate the cbrt and place it, if already available us it..