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 functionfindNb
will be an integerm
and you have to return the integern
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:
public static long findNb(long m) {
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:
public static long findNb(long m) {
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:
System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// 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:
public static long findNb(long m) {
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
?
(1646842954019151681L == 1646842954019151682D)
(1646842954019151681L == (long) 1646842954019151682D)
Top comments (0)