-
Notifications
You must be signed in to change notification settings - Fork 0
cbrt
cbrt is short for "cube root".
Similar to how every number has 2 square roots (except 0, it just has 0), every number also has 3 cube roots (except 0, it just has 0).
∛(1) = 1, (-1+√(3)i)/2, (-1-√(3)i)/2
∛(-8) = 1+√(3)i, -2, 1-√(3)i
∛(27i) = (3√(3)+3i)/2, -3i, (-3√(3)+3i)/2
∛(2+11i) = 2+i, (-2-√(3)+(2√(3)-1)i)/2, (-2+√(3)-(2√(3)+1)i)/2
Unlike with the square root (where both roots were arithmetic opposites), the pattern here isn't as obvious. However, there is a pattern, and it's more visible if we show them in polar notation (with the angles in degrees between 0 and 360 just to make it more clear):
∛(1∠0) = 1∠0°, 1∠120°, 1∠240°
∛(8∠180) = 2∠60°, 2∠180°, 2∠300°
∛(27∠90) = 3∠30°, 3∠270°, 3∠350°
∛(√(125)∠79.70°) = √(5)∠26.57°, √(5)∠146.57°, √(5)∠266.57°
All 3 cube roots are 120° from each other.
Likewise, every number also has 4 fourth roots (each 90° from each other), 5 fifth roots (each 360/5=72° from each other), 6 sixth roots (each 60° from each other), and so on. And, looking in the opposite direction, each number has 2 square roots (each 180° from each other) and 1 1st-root (360° from itself).
The way an n-th root is calculated is by n-th rooting the magnitude, then dividing the angle by n. However, since we can keep adding 360° to the angle over and over and still have the same number, we can also keep adding 360/n to the n-th root and have a valid n-th root. Alternatively, this is also the same as repeatedly multiplying by one of the complex n-th roots of +1 (also known as "roots of unity").
Just like with the square root, we've also defined a principal cube root. It's whichever of the 3 cube roots has the largest real part (which is the same as having the angle closest to 0). If it's a tie between two numbers, we pick whichever has a positive imaginary part. Unfortunately, this has a somewhat sad consequence:
When working with real numbers, we found that, unlike the square root, the cube root was defined for all real numbers, not just the positive ones. The cube root of a positive was a positive, and the cube root of a negative was a negative. Sadly, when we introduce complex numbers into the mix, this is no longer the case. The cube root of a positive number is positive, but the cube root of a negative number is a complex number with an angle of 60° from the positive real axis.
That's kind of how it has to be. If you make a special case for negative numbers, then that only makes things more complicated. The magnitude has to be the cube root of the magnitude of the input, and the argument has to be 1/3 of the argument of the input. We've defined the argument of the input to be the angle when measured counterclockwise, and for it to be over the range (-π,π] in radians. Now, we could make the cube root of -1 be -1 if we changed it so the argument is instead from (π,3π]. However, that would mean the cube root of +1 is now 1∠120° (as well as create several other consequences). We could define the cube root to be different than other power functions, forcing it to be odd by defining it as the normal cube root when the real part is positive, but as -∛(-z) when the real part is negative. This would work, but it would cause us to have 2 branch cuts along the imaginary axis instead of just one along the negative real axis (a branch cut is a jump discontinuity on a function when evaluated over the complex plane. Long story short, it's usually not a good thing).
However, just to give you the option, I've implemented a public, static, boolean variable within the Complex class:
cbrt_Option
When this field is false, the cube root will continue to return the principal cube root. However, when this field is true, the cube root will make a special case and evaluate the cube root of a negative real as a negative real, but evaluate the cube root of all other numbers as the principal value. This field is toggleable since both modes have their pros and cons. False is easier to work with if you actually end up needing to use the cube root. True, however, provides more consistency with definitions for real numbers.
If you've read the article on the square root, you saw there was an interesting formula, obtained by converting to polar, square rooting, converting to rectangular, then using some clever rules and tricks to remove all trigonometry and turn the formula into an arithmetic problem with 2 square roots shoved into the mix.
So, with that, you might be expecting some sort of clever trick for cube roots as well, right? Well, as it so happens, the formula for the cube root is:
∛(x+yi) = ∛(|x+yi|)*(cos(arg(x+yi)/3) + sin(arg(x+yi)/3)i)
Yup! That's right! There's no way to simplify it! We convert to polar, cube root it, then convert back to rectangular. There's literally no way to simplify any further.
This is what is known as "Casus Irreducilibis", which the astute among you might infer means "irreducible case". It's been known since antiquity that, while you can split an angle in half using a compass and straightedge, the only way to split an angle in thirds is to measure the angle, then measure a third the angle. In a similar sense, there's no special trick to compute the cosine and sine of 1/3 an angle like there is 1/2. You literally just compute the angle with the arc tangent, divide by 3, then compute the cosine and sine. There's no square roots or cube roots or division or any other trick you can use to arrive at that result.
In fact, here's the kicker, the most computationally efficient way to calculate cos(θ/3) and sin(θ/3), assuming you already know cos(θ) and sin(θ), is to use Newton's method (or a similar approximation) to find ∛(cos(θ)+sin(θ)i), then take the real and imaginary parts. That's it. So the best way of computing the cube root is to compute the cube root. Hence why it's an irreducible case.
"So, wait", you might be wondering, "why don't we use Newton's method to compute the cube root, then?" Well, that's a good question. It's also for the same reason we don't save one Math.sqrt and compute the square root with Newton's method: Java isn't low level enough. Floating point arithmetic operations are built into the ALU (Arithmetic Logic Unit) of most computers by default. In order to implement Newton's method in such a way that the computed result is both faster (or even as fast) and just as accurate as anything you could get with the built-in trigonometric functions in the ALU, you'd have to do some very low-level programming stuff. Java isn't low-level, so we're better off using trigonometry.
It should also be noted that the third root isn't unique in this feature. The fifth root, sixth root, seventh root, ninth root, tenth root, eleventh root, and so on are all like this. None of them can just be rewritten as an arithmetic expression with radicals thrown in, like we could with the square root. In fact, the only time the n-th roots of complex numbers do have a fancy expression, are when n is a power of 2. That's because the 4th root is the square root of the square root, the 8th root is the square root of the 4th root, the 16th root is the square root of the 8th root, and so on. All other n-th roots can really only be written by converting to polar, splitting the angle, then converting back to rectangular (or, again, with something like Newton's method). But keep in mind, this isn't necessarily a bad thing. This isn't a terribly inefficient way of calculating roots. In fact, by the time you hit the 16th root, it's actually computationally easier to do it this way than it is to repeatedly take square roots. It might even be more efficient for 8th roots, I have yet to rigorously test it.
So, with that disappointing algorithm explained, it's time to move on to the special cases. First and foremost, it is possible for the absolute value to overflow, but the input to not overflow. Since the cube root works with the absolute value, this case must be accounted for. And we do so by dividing by 8, cube rooting, then multiplying by 2. Another special case happens when the input is infinite. This is treated as 2 special cases: one where the real part is -∞, the other where it isn't. If the real part is -∞, the result will be ∞±∞i, with the ± depending on the sign of the imaginary part. If the real part isn't -∞, but the input is still infinite, that's another case. We either return ∞+0i if the input has a finite imaginary part, or we return ∞+im*i if the input has an infinite imaginary part.
And with that, we have everything covered.