This text is a translation of the original article by my friend, Maksim Pelevin. If you are comfortable with reading Russian, you might find more interesting articles in his blog.
You already know this:
The double data type is not very precise
Let’s reinforce this understanding by solving a problem on CodeWars.
Problem statement
The task as described on CodeWars is as follows:
Your task is to construct a building, which will be a pile of n cubes.
The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.
You are given the total volume m of the building. Being given m, can you find the number n of cubes you will have to build?
The parameter of the function findNb will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + … + 1^3 = m* if such a n exists or -1 if there is no such n.
Naive solution
The most straightforward solution using loops would be something like:
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : –1;
}
Mathematical solution
Back in university, I learned about mathematical series and the methods to calculate their sums, so here is my take on a mathematical solution.
I no longer recall the formulas, but thankfully, Wolfram Alpha is here to help. To get the formula, let’s run the following query: n^3, n = 1 to k.
The results tell us that:
Let’s substitute m for the left side of the equation, then apply the square root property and multiply both sides of the equation by two.
After simplifying, we get:
Write the code
Here is a solution for the equation above, written in Java:
double res = Math.sqrt(m);
double d = 1 + 8 * res;
double n = (Math.sqrt(d) – 1) / 2;
return n – Math.floor(n) == 0 ? (long) n : –1;
}
Results
It turns out that this code returns an incorrect result for a subset of test data. This inconcistency is visible, for example, when you pass 1646842954019151682L as the input.
While calculating a square root in Java, you may get a result that isn’t wholly accurate. Let’s take a look:
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912…
Obviously, the output and the correct answer are different. Fin!
Conclusion
The most technically correct and potentially fastest solution is not always the best one to choose. This may be no surprise to a skilled developer, but those new to programming might puzzle over the cause of the error for quite a while.
If you’re wondering how to fix the problem with the mathematical solution, one approach is to use BigDecimal. This code passes all the tests:
MathContext mc = new MathContext(64);
BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : –1;
}
… and a little bonus: can you guess which of the following true, and which is false?
