| Bytes | Lang | Time | Link |
|---|---|---|---|
| 049 | AWK | 170228T150113Z | Robert B |
| 046 | APLNARS | 250325T164315Z | Rosario |
| 4411 | MMIX | 210429T193625Z | NoLonger |
| nan | 180326T153032Z | Ramanath | |
| nan | 180326T152559Z | Ramanath | |
| nan | Stax | 180302T172706Z | Weijun Z |
| 7372 | Javascript 73/72 characters | 140222T154645Z | Victor S |
| 057 | Js | 180302T144231Z | Luis fel |
| 069 | C | 170518T235817Z | ceilingc |
| 024 | TIBasic | 140222T181428Z | Timtech |
| 051 | GameMaker Language | 140222T183401Z | Timtech |
| 028 | J | 140227T164006Z | jpjacobs |
| 037 | Smalltalk | 140224T225200Z | blabla99 |
| nan | 140225T204107Z | danmcard | |
| nan | 140225T201940Z | Justin | |
| 181 | Java | 140222T175522Z | md_rasle |
| 031 | APL | 140223T140115Z | mniip |
| 016 | J | 140223T123213Z | mudri |
| 6962 | SageMath | 140222T125801Z | yo' |
| 055 | Javascript | 140222T155453Z | Michael |
| 092 | Perl | 140222T193518Z | Heiko Ob |
| 061 | PHP | 140222T182021Z | Amal |
| 157 | Javascript | 140222T130107Z | Victor S |
| 081 | PHP | 140222T125817Z | Razvan |
| 035 | Haskell | 140222T125808Z | mniip |
| 062 | Python | 140222T130133Z | primo |
AWK, 49 bytes
{for(n=x=$1;x-(x=(2*x+n/x/x)/3););printf"%.4f",x}
Thanks go to @Mig for the JavaScript solution which this is derived from. It runs surprisingly quickly given that the for loop requires the iteration to stop changing.
Note: This solution has trailing 0s for all results with fewer than 4 digits to the right of the decimal, including integer results.
Also, subsequent results are not separated.
Changing the %.4f to %.5g removes trailing 0s, but will lose digits to the right of the decimal for results >= 10.
An alternative solution adds 4 bytes, but it also makes the output prettier:
{for(n=x=$1;x-(x=(2*x+n/x/x)/3););CONVFMT="%.4f"}$0=x
APL(NARS), 46 chars
r←q w;t
t←1
→3×⍳1e¯9>∣t-r←t-3÷⍨t-w÷t×t⋄t←r⋄→2
//8+4+34=46
I followed the formula written in the post: https://codegolf.stackexchange.com/a/21793/120560. It seems is ok with test
aaa←27 64 1 18.609625 3652264 0.001 7 2E¯13 0
q¨aaa
3 4 1 2.65 154 0.1 1.912931183 0.00005848035476 1.568328545E¯9
q¨-aaa
¯3 ¯4 ¯1 ¯2.65 ¯154 ¯0.1 ¯1.912931183 ¯0.00005848035476 1.568328545E¯9
It seems work for input big float v but not work for rationals...It could be ok with
the restriction of question so ok.
The problem would be find in this case cube root function, the min number e
that can find all digits possibles of one float when the sys has float
XXXbits=⎕FPC (without generate one never ending loop for some number of input w due
the number e is too small)....
I propose this function that would break convension of return the same type
of the input, it would return a v number a float according ⎕FPC variable
r←q3 w;t;e
t←1v⋄e←÷10*⌊(⎕FPC-{1>∣w:0⋄3÷⍨1+2⍟∣w})÷3.323v
→3×⍳e>∣t-r←t-3÷⍨t-w÷t×t⋄t←r⋄→2
The error in this case would be less than e←÷10*⌊(⎕FPC-{1>∣w:0⋄3÷⍨1+2⍟∣w})÷3.323v
where w is the input number, ⎕FPC is the lenght in bit of the float point
1+2⍟w would be the lenght in bit of integer part of w, but I have to
consider the 1/3 of that number because the resul will have 1/3 of these
digits...log_2(10)=3.32192809 here approximated as 3.323 (I don't know if
it is the right number, 3.322 is not right because I remember generate one never ending
loop with the input 18.609625v). Test
q3¨aaa
3 4 1 2.65 154 0.1 1.912931183 0.00005848035476 1.381590388E¯38
q3¨-aaa
¯3 ¯4 ¯1 ¯2.65 ¯154 ¯0.1 ¯1.912931183 ¯0.00005848035476 1.381590388E¯38
q3¨aaa×1v
3 4 1 2.65 154 0.1 1.912931183 0.00005848035476 1.872107764E¯154
q3¨aaa×1x
3 4 1 2.65 154 0.1 1.912931183 0.00005848035476 1.872107764E¯154
note that it seems ok even with rationals...
q3 2
1.25992105
q3 2v
1.25992105
q3 2x
1.25992105
q3 18.609625x
2.65
for big numbers it is possible too
⎕fpc←512
512÷3.322
154.1240217
150⍕q 2v
1.259921049894873164779198323884500528076109625698508732184198175469013575303302345933958149409424814616937169595159013873478464862408338554282464069753
150⍕q3 2v
1.259921049894873164767210607278228350570251464701507980081975112155299676513959483729396562436255094154310256035615665259399024040613737228459110304269
note how q3 wuould be the right result, but q is right until 19th digit.
It is possible that I make some error and there is a number of input that
generate one infinite loop because e variable in code is too little
(for example I wrong the number 3.323 or if variable t or r have
integer part > of input w even if t-r decrease)
I have not consider the case the number of input w is too big for
variable ⎕FPC, for example when digits of number are > ⎕FPC÷3.322 (float for me has to be fixed point float because
this is too tricly)
MMIX, 44 bytes (11 instrs)
E0013FF0 48000002 E8018000 C1FF0100
1001FFFF 14010001 040101FF E401FFF0
11FF01FF 53FFFFFA F8020000
Disassembly
cbrt SETH $1,#3FF0 // y = 1.
BNN $0,0F // if(x >= 0) goto loop (ensuring sign is correct)
ORH $1,#8000 // y = fnabs(y) (bit tricks!)
0H SET $255,$1 // loop: prev = y
FMUL $1,$255,$255 // y = prev *. prev
FDIV $1,$0,$1 // y = x /. y
FADD $1,$1,$255 // y = y +. prev
INCH $1,#FFF0 // y = y /. 2. (bit tricks again)
FCMPE $255,$1,$255 // prev = comp_eps(y, prev)
PBNZ $255,0B // if(prev) goto loop
POP 2,0 // return {y,x}
It is up to the caller to set a suitable value of rE. Much faster convergence may be arranged by essentially setting y up by dividing the exponent by 3, but that costs another four instructions (though in time it pays really quickly, since three FDIVs cost about the same amount as two DIVs):
cbrt SLU $1,$0,1 // 3B010001 shift left to erase sign
INCH $1,#8020 // E4018020 unbias exponent
DIV $1,$1,3 // 1D010103 divide by 3 as integer; approximate cube root
INCH $1,#7FE0 // E4017FE8 rebias exponent
SRU $1,$1,1 // 3F010101 shift right again
and then continue from the second line in the original.
If mispredicted branches are particularly expensive, I would also replace the second and third lines of the original with:
ZSN $255,$0,1 // 71020001 $255 = ($0 neg? 1 : 0)
SLU $255,$255,63 // 3B02023F $255 <<= 63
OR $1,$1,$255 // C0010102 $1 |= $255
This costs one more instruction, but is branchless.
Python Solution
def cube_root(num):
if num == 0:
return 0
t = 0
absNum = abs(num)
root = absNum/3
while (t - root) != 0:
t = root
root = (1/3) * ((2 * root) + absNum/(root * root))
return root * (num / absNum)
JAVA Solution
public BigDecimal cubeRoot(BigDecimal number) {
if(number == null || number.intValue() == 0) return BigDecimal.ZERO;
BigDecimal absNum = number.abs();
BigDecimal t;
BigDecimal root = absNum.divide(BigDecimal.valueOf(3), MathContext.DECIMAL128);
do {
t = root;
root = root.multiply(BigDecimal.valueOf(2))
.add(absNum.divide(root.multiply(root), MathContext.DECIMAL128))
.divide(BigDecimal.valueOf(3), MathContext.DECIMAL128);
} while (t.toBigInteger().subtract(root.toBigInteger()).intValue() != 0);
return root.multiply(number.divide(absNum), MathContext.DECIMAL128);
}
Stax, 10 bytesCP437
╘♀┘A╕äO¶∩'
Explanation
Uses the unpacked version to explain.
gpJux*_+h4je
gp Iterate until a fixed point is found, output the fix point
Ju Inverse of square
x* Multiplied by input
_+h Average of the value computed by last command and the value at current iteration
4je Round to 4 decimal digits
Javascript: 73/72 characters
This algorithm is lame, and exploits the fact that this question is limited to 4 digits after the decimal point. It is a modified version of the algorithm that I suggested in the sandbox for the purpose of reworking the question. It counts from zero to the infinite while h*h*h<a, just with a multiplication and division trick to handle the 4 decimal digits pecision.
function g(a){if(a<0)return-g(-a);for(h=0;h*h*h<1e12*a;h++);return h/1e4}
Edit, 4 years later: As suggested by Luis felipe De jesus Munoz, by using ** the code is shorter, but that feature was not available back in 2014 when I wrote this answer. Anyway, by using it, we shave an extra character:
function g(a){if(a<0)return-g(-a);for(h=0;h**3<1e12*a;h++);return h/1e4}
Js 57 bytes
f=(x)=>eval('for(w=0;w**3<1e12*x;w++);x<0?-f(-x):w/1e4')
f=(x)=>eval('for(w=0;w**3<1e12*x;w++);x<0?-f(-x):w/1e4')
document.getElementById('div').innerHTML += f(-27) + '<br>'
document.getElementById('div').innerHTML += f(-64) + '<br>'
document.getElementById('div').innerHTML += f(-1) + '<br>'
document.getElementById('div').innerHTML += f(-18.609625) + '<br>'
document.getElementById('div').innerHTML += f(-3652264) + '<br>'
document.getElementById('div').innerHTML += f(-0.001) + '<br>'
document.getElementById('div').innerHTML += f(-7) + '<br><hr>'
document.getElementById('div').innerHTML += f(27) + '<br>'
document.getElementById('div').innerHTML += f(64) + '<br>'
document.getElementById('div').innerHTML += f(1) + '<br>'
document.getElementById('div').innerHTML += f(18.609625) + '<br>'
document.getElementById('div').innerHTML += f(3652264) + '<br>'
document.getElementById('div').innerHTML += f(0.001) + '<br>'
document.getElementById('div').innerHTML += f(7) + '<br>'
<div id="div"></div>
C, 69 bytes
i;float g(float x){for(float y=x;++i%999;x=x*2/3+y/3/x/x);return x;}
Just another implementation of Newton's method. Try it online!
TI-Basic, 26 24 bytes
Input :1:For(I,1,9:2Ans/3+X/(3AnsAns:End
GameMaker Language, 51 bytes
for(i=x=1;i++<99;1)x=(2*x+argument0/x/x)/3;return x
J 28
*@[*(3%~+:@]+(%*~@]))^:_&|&1
Using Newtons method, finding the root of x^3 - X the update step is x - (x^3 - C)/(3*x^2), where x is the current guess, and C the input. Doing the maths on this one yields the ridiculously simple expression of (2*x+C/x^2) /3 . Care has to be taken for negative numbers.
Implemented in J, from right to left:
|Take abs of both arguments, pass them on^:_Do until convergence(%*~@])isC / x^2(*~ yis equivalent toy * y)+:@]is2 x3%~divide by three. This yields the positive root*@[ * positive_rootmultiplies positive root with the signum of C.
Test run:
NB. give it a name:
c=: *@[*(3%~+:@]+(%*~@]))^:_&|&1
c 27 64 1 18.609625 3652264 0.001 7
3 4 1 2.65 154 0.1 1.91293
Smalltalk, 37
credit goes to mniip for the algorithm; Smalltalk version of his code:
input in n; output in x:
1to:(x:=99)do:[:i|x:=2*x+(n/x/x)/3.0]
or, as a block
[:n|1to:(x:=99)do:[:i|x:=2*x+(n/x/x)/3.0].x]
Haskell: 99C
Can't beat @mniip in cleverness. I just went with a binary search.
c x=d 0 x x
d l h x
|abs(x-c)<=t=m
|c < x=d m h x
|True=d l m x
where m=(l+h)/2;c=m*m*m;t=1e-4
Ungolfed:
-- just calls the helper function below
cubeRoot x = cubeRoot' 0 x x
cubeRoot' lo hi x
| abs(x-c) <= tol = mid -- if our guess is within the tolerance, accept it
| c < x = cubeRoot' mid hi x -- shot too low, narrow our search space to upper end
| otherwise = cubeRoot' lo mid x -- shot too high, narrow search space to lower end
where
mid = (lo+hi)/2
cubed = mid*mid*mid
tol = 0.0001
Befunge 98 - Work in progress
This language does not support floating point numbers; this attempts to emulate them. It currently works for positive numbers that do not start with 0 after the decimal point (mostly). However, it only outputs to 2 decimal places.
&5ka5k*&+00pv
:::**00g`!jv>1+
/.'.,aa*%.@>1-:aa*
It works by inputting the part before the decimal point, multiplying that by 100000, then inputting the part after the point and adding the two numbers together. The second line does a counter until the cube is greater than the inputted number. Then the third line extracts the decimal number from the integer.
If anyone can tell me why the third line only divides by 100 to get the correct values, please tell me.
IOs:
27.0 3 .0
64.0 4 .0
1.0 1 .0
18.609625 2 .65
0.001 0 .1
7.0 1 .91
0.1 0 .1
Java, 207 182 181
Sometimes when I play golf I have two many beers and play really really bad
class n{public static void main(String[]a){double d=Double.valueOf(a[0]);double i=d;for(int j=0;j<99;j++)i=(d/(i*i)+(2.0*i))/3.0;System.out.println((double)Math.round(i*1e4)/1e4);}}
Iterative Newton's Method of Approximation, runs 99 iterations.
Here is the unGolfed:
class n{
public static void main(String a[]){
//assuming the input value is the first parameter of the input
//arguments as a String, get the Double value of it
double d=Double.valueOf(a[0]);
//Newton's method needs a guess at a starting point for the
//iterative approximation, there are much better ways at
//going about this, but this is by far the simplest. Given
//the nature of the problem, it should suffice fine with 99 iterations
double i=d;
//make successive better approximations, do it 99 times
for(int j=0;j<99;j++){
i=( (d/(i*i)) + (2.0*i) ) / 3.0;
}
//print out the answer to standard out
//also need to round off the double to meet the requirements
//of the problem. Short and sweet method of rounding:
System.out.println( (double)Math.round(i*10000.0) / 10000.0 );
}
}
APL - 31
(×X)×+/1,(×\99⍴(⍟|X←⎕)÷3)÷×\⍳99
Uses the fact that cbrt(x)=e^(ln(x)/3), but instead of doing naive ⋆ exponentiation, it computes e^x using Taylor/Maclaurin series.
Sample runs:
⎕: 27
3
⎕: 64
4
⎕: 1
1
⎕: 18.609625
2.65
⎕: 3652264
154
⎕: 0.001
0.1
⎕: 7
1.912931183
⎕: ¯27
¯3
⎕: ¯7
¯1.912931183
Seeing as there's a J answer in 16 characters, I must be really terrible at APL...
J: 16 characters
Loose translation of the Haskell answer:
-:@((%*~)+])^:_~
Test cases:
-:@((%*~)+])^:_~27
3
-:@((%*~)+])^:_~64
4
-:@((%*~)+])^:_~1
1
-:@((%*~)+])^:_~18.609625
2.65
-:@((%*~)+])^:_~3652264
154
-:@((%*~)+])^:_~0.001
0.1
-:@((%*~)+])^:_~7
1.91293
It works like this:
(-:@((% *~) + ])^:_)~ 27
↔ 27 (-:@((% *~) + ])^:_) 27
↔ 27 (-:@((% *~) + ])^:_) 27 (-:@((% *~) + ])) 27
↔ 27 (-:@((% *~) + ])^:_) -: ((27 % 27 * 27) + 27)
↔ 27 (-:@((% *~) + ])^:_) 13.5185
↔ 27 (-:@((% *~) + ])^:_) 27 (-:@((% *~) + ])) 13.5185
↔ 27 (-:@((% *~) + ])^:_) -: ((27 % 13.5185 * 13.5185) + 13.5185)
↔ 27 (-:@((% *~) + ])^:_) 6.83313
...
In words:
half =. -:
of =. @
divideBy =. %
times =. *
add =. +
right =. ]
iterate =. ^:
infinite =. _
fixpoint =. iterate infinite
by_self =. ~
-:@((%*~)+])^:_~ ↔ half of ((divideBy times by_self) add right) fixpoint by_self
Not one of the best wordy translations, since there's a dyadic fork and a ~ right at the end.
SageMath, (69) 62 bytes
However, don't ever believe it will give you the result, it's very difficult to go randomly through all the numbers:
def r(x):
y=0
while y*y*y-x:y=RR.random_element()
return "%.4f"%y
if you didn't insist on truncating:
def r(x):
y=0
while y*y*y-x:y=RR.random_element()
return y
SageMath, 12 bytes, if exp is allowed
Works for all stuff: positive, negative, zero, complex, ...
exp(ln(x)/3)
Javascript (55)
function f(n){for(i=x=99;i--;)x=(2*x+n/x/x)/3;return x}
BONUS, General formulation for all roots
function f(n,p){for(i=x=99;i--;)x=x-(x-n/Math.pow(x,p-1))/p;return x}
For cube root, just use f(n,3), square root f(n,2), etc...
Example : f(1024,10) returns 2.
Explanation
Based on Newton method :
Find : f(x) = x^3 - n = 0, the solution is n = x^3
The derivation : f'(x) = 3*x^2
Iterate :
x(i+1) = x(i) - f(x(i))/f'(x(i)) = x(i) + (2/3)*x + (1/3)*n/x^2
Tests
[27,64,1,18.609625,3652264,0.001,7].forEach(function(n){console.log(n + ' (' + -n + ') => ' + f(n) + ' ('+ f(-n) +')')})
27 (-27) => 3 (-3)
64 (-64) => 4 (-4)
1 (-1) => 1 (-1)
18.609625 (-18.609625) => 2.65 (-2.65)
3652264 (-3652264) => 154 (-154)
0.001 (-0.001) => 0.09999999999999999 (-0.09999999999999999)
7 (-7) => 1.912931182772389 (-1.912931182772389)
Perl, 92 bytes
sub a{$x=1;while($d=($x-$_[0]/$x/$x)/3,abs$d>1e-9){$x-=$d}$_=sprintf'%.4f',$x;s/\.?0*$//;$_}
- The function
areturns a string with the number without an unnecessary fraction part or insignificant zeroes at the right end.
Result:
27 --> 3
-27 --> -3
64 --> 4
-64 --> -4
1 --> 1
-1 --> -1
18.609625 --> 2.65
-18.609625 --> -2.65
3652264 --> 154
-3652264 --> -154
0.001 --> 0.1
-0.001 --> -0.1
7 --> 1.9129
-7 --> -1.9129
0.0000000000002 --> 0.0001
-0.0000000000002 --> -0.0001
0 --> 0
-0 --> 0
Generated by
sub test{
my $a = shift;
printf "%16s --> %s\n", $a, a($a);
printf "%16s --> %s\n", "-$a", a(-$a);
}
test 27;
test 64;
test 1;
test 18.609625;
test 3652264;
test 0.001;
test 7;
test "0.0000000000002";
test 0;
The calculation is based on Newton's method:

PHP, 61
Based on Newton's method. Slightly modified version of Michael's answer:
for($i=$x=1;$i++<99;)$x=(2*$x+$n/$x/$x)/3;echo round($x,14);
It works with negative numbers, can handle floating point numbers, and rounds the result to 4 numbers after the decimal point if the result is a floating point number.
Javascript - 157 characters
This function:
- Handle negative numbers.
- Handle floating-pointing numbers.
- Execute quickly for any input number.
- Has the maximum precision allowed for javascript floating-point numbers.
function f(a){if(p=q=a<=1)return a<0?-f(-a):a==0|a==1?a:1/f(1/a);for(v=u=1;v*v*v<a;v*=2);while(u!=p|v!=q){p=u;q=v;k=(u+v)/2;if(k*k*k>a)v=k;else u=k}return u}
Ungolfed explained version:
function f(a) {
if (p = q = a <= 1) return a < 0 ? -f(-a) // if a < 0, it is the negative of the positive cube root.
: a == 0 | a == 1 ? a // if a is 0 or 1, its cube root is too.
: 1 / f (1 / a); // if a < 1 (and a > 0) invert the number and return the inverse of the result.
// Now, we only need to handle positive numbers > 1.
// Start u and v with 1, and double v until it becomes a power of 2 greater than the given number.
for (v = u = 1; v * v * v < a; v *= 2);
// Bisects the u-v interval iteratively while u or v are changing, which means that we still did not reached the precision limit.
// Use p and q to keep track of the last values of u and v so we are able to detect the change.
while (u != p | v != q) {
p = u;
q = v;
k = (u + v) / 2;
if (k * k * k > a)
v=k;
else
u=k
}
// At this point u <= cbrt(a) and v >= cbrt(a) and they are the closest that is possible to the true result that is possible using javascript-floating point precision.
// If u == v then we have an exact cube root.
// Return u because if u != v, u < cbrt(a), i.e. it is rounded towards zero.
return u
}
PHP - 81 bytes
Iterative solution:
$i=0;while(($y=abs($x=$argv[1]))-$i*$i*$i>1e-4)$i+=1e-5;@print $y/$x*round($i,4);
Haskell - 35
c n=(iterate(\x->(x+n/x/x)/2)n)!!99
Example runs:
c 27 => 3.0
c 64 => 4.0
c 1 => 1.0
c 18.609625 => 2.6500000000000004 # only first 4 digits are important, right?
c 3652264 => 154.0
c 0.001 => 0.1
c 7 => 1.9129311827723892
c (-27) => -3.0
c (-64) => -4.0
Moreover, if you import Data.Complex, it even works on complex numbers, it returns one of the roots of the number (there are 3):
c (18:+26) => 3.0 :+ 1.0
The :+ operator should be read as 'plus i times'
Python - 62 bytes
x=v=input()
exec"x*=(2.*v+x*x*x)/(v+2*x*x*x or 1);"*99;print x
Evaluates to full floating point precision. The method used is Halley's method. As each iteration produces 3 times as many correct digits as the last, 99 iterations is a bit of overkill.
Input/output:
27 -> 3.0
64 -> 4.0
1 -> 1.0
18.609625 -> 2.65
3652264 -> 154.0
0.001 -> 0.1
7 -> 1.91293118277
0 -> 1.57772181044e-30
-2 -> -1.25992104989