Calculate the cube root of a number

Question

The goal of this code golf is to create a program or function that calculates and outputs the cube root of a number that's given as input.
The rules:

No external resources
No use of built-in cube root functions.
No use of methods/operators that can raise a number to a power.
Your function/program must be able to accept floating-point numbers and negative numbers as input.
If the cube root is a floating-point number, then round it to 4 numbers after the decimal point.
This is a code golf, the shortest code in bytes wins.

Test cases:

27 --> 3
64 --> 4
1  --> 1
18.609625 --> 2.65
3652264 --> 154
0.001 --> 0.1
7  --> 1.9129

You can use all test cases above to test negative numbers (-27 --> -3, -64 --> -4 ...)

damn, if you allowed only numbers with precise cube, I would have a nice golf — tohecz, 2 days ago
Judging from your test cases I assume the program only needs to deal with real numbers? — ace, 2 days ago

mniip · Answer 1 · 2014-02-22 13:26:44Z

up vote 12 down vote

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'

edited 2 days ago

answered 2 days ago

mniip
1,758322

1

This deserves a +1. I've been refactoring generalized nth root algs for the last hour, and I just now arrived at the same result. Bravo. – primo 2 days ago

@primo I instantly recalled all n'th root approximation algorithms, and after giving up on Taylor/Maclaurin series in APL I used this. – mniip 2 days ago

Using Newton method I got x=(2*x+n/x/x)/3, can you explain why you can use x=(x+n/x/x)/2 ? It converges slower but I can't explain why it converges... – Michael 2 days ago

@Michael because if you take x=cbrt(n), then x=(x+n/x/x)/2 is true. So is it true for your expression – mniip 2 days ago

@Michael I got there this way: codepad.org/gwMWniZB – primo 2 days ago

show 3 more comments

tohecz · Answer 2 · 2014-02-22 22:02:47Z

up vote 6 down vote

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)

edited 2 days ago

answered 2 days ago

tohecz
2015

I believe you are using an operator that can raise a number to a power. – ace 2 days ago

ah ok, right, edited – tohecz 2 days ago

2

+1 for a monumentally stupid algorithm that still satisfies the requirements. – Mechanical snail 2 days ago

@Mechanicalsnail Thanks. I hope it's obvious that what I do is a sort of recession :D However, if exp is allowed, I'm down to 12 and not being stupid at all :) – tohecz 2 days ago

add comment

primo · Answer 3 · 2014-02-22 13:17:03Z

up vote 4 down vote

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

edited 2 days ago

answered 2 days ago

primo
7,1381955

How does this work? – justhalf 2 days ago

1

@justhalf I think this is the Newton's method of approximation basically. – tohecz 2 days ago

Btw, fails on 0 – tohecz 2 days ago

Fails on -2, sorry for that. – tohecz 2 days ago

@tohecz fixed for all cases. – primo 2 days ago

add comment

Razvan · Answer 4 · 2014-02-22 14:20:20Z

up vote 2 down vote

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);

edited 2 days ago

answered 2 days ago

Razvan
2112

What happens if it tries to calculate the cube root of zero? – Victor 2 days ago

It will just output "0" (thanks to the error suppression operator - "@"). – Razvan 2 days ago

1

0.0001 can be replaced by 1e-4 and 0.00001 by 1e.5. – ComFreek 2 days ago

Thanks! I updated the script. – Razvan 2 days ago

add comment

Michael · Answer 5 · 2014-02-22 20:07:40Z

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)

James Wood · Answer 6 · 2014-02-23 12:32:13Z

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.

Timtech · Answer 7 · 2014-02-22 18:14:28Z

up vote 1 down vote

TI-BASIC

Input X:round((X>0)*e^ln(|X|)/3),4

answered 2 days ago

Timtech
3,276527

That directly uses the ^ operator, doesn't it. It is forbidden by the rules – mniip 2 days ago

@mniip: Is e^ is a single operator on the TI-83 series? I don't remember. Either way, it's violating the spirit of the rules. – Mechanical snail 2 days ago

@Mechanicalsnail It doesn't matter I would say. In most languages you could just do exp(ln(x)/3) or e^(ln(x/3)) if you allowed any of these two. But somehow I understand to exp(ln(x)/a) as too much equivalent to x^(1/a) to be allowed by the rules :-/ – tohecz 2 days ago

add comment

Amal Murali · Answer 8 · 2014-02-22 18:27:14Z

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.

Working demo

Timtech · Answer 9 · 2014-02-22 18:34:01Z

up vote 1 down vote

Game Maker Language, 54

for(i=x=1;i++<99;i=i)x=(2*x+argument0/x/x)/3;return x}

Yes, i=i is required.

answered 2 days ago

Timtech
3,276527

add comment

Victor · Answer 10 · 2014-02-22 22:02:03Z

up vote 1 down vote

Java, 207

Sometimes when I play golf I have two many beers and play really really bad

public class n{public static void main(String args[]){double d=Double.valueOf(args[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*10000.0)/10000.0);}}

edited 2 days ago

Victor
4,01241238

answered 2 days ago

md_rasler
111

1

You may rename the args variable to something like z, reducing 6 chars. You may remove the space and the curly braces in the body of the for-loop, reducing 3 chars. You may replace 10000.0 by 1e4, reducing 6 chars. The class does not needs to be public, so you can reduce more 7 chars. This way it will be reduced to 185 characters. – Victor 2 days ago

Is the cast at the end really necessary? It does not for me. – Victor 2 days ago

@Victor Thanks for the good eye, the use of E notation for the 10000.0 double was a spectacularly good idea. By the design of the question, I think it is legit to make this a method instead of a functioning cli class, which would reduce the size considerably. With Java, I didn't think I had a chance, so I erred on the side of functional. – md_rasler 3 hours ago

Welcome to CodeGolf! Don't forget to add an in-answer explanation of how this works! – Quincunx 1 hour ago

add comment

steve verrill · Answer 11 · 2014-02-22 14:58:44Z

up vote 0 down vote

Polyglot, 24 chars (cheeky)

Depends if you consider EXP to be raising a number to a power. Anyway, EXP is a function, not a "method/operator", so I guess it falls within the spec.

Fails for X=0, but the question says "negative numbers" but doesn't mention zero. Complies with all test cases, positive and negative.

Hey, I could save quite a few chars by making it work ONLY for negative numbers and not positive ones..

SGN(X)*EXP(LN(ABS(X))/3)

edited 2 days ago

answered 2 days ago

steve verrill
58617

3

"funcation" and "method" are used synonymously. – primo 2 days ago

@primo According to wikipedia a method is a function associated with an object. What object is EXP associated with? Terminology could vary with language, sure. – steve verrill 2 days ago

1

Interesting approach, but I believe exp is against the rules – mniip 2 days ago

@mniip hence the word "cheeky" in the title. I could have gone for pow(x,1/3) as that's technically not a cube root function, but that would just be trolling. – steve verrill 2 days ago

add comment

Victor · Answer 12 · 2014-02-22 15:18:51Z

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
}

Victor · Answer 13 · 2014-02-22 15:46:45Z

Javascript: 73 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}

Heiko Oberdiek · Answer 14 · 2014-02-22 19:35:18Z

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 a returns 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:

Calculation

mniip · Answer 15 · 2014-02-23 14:01:15Z

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...

blabla999 · Answer 16 · 2014-02-24 22:52:00Z

Smalltalk

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]

asked	2 days ago
viewed	925 times
active	today

current community

more stack exchange communities

Calculate the cube root of a number

16 Answers

Haskell - 35

SageMath, (69) 62 bytes

SageMath, 12 bytes, if `exp` is allowed

Python - 62 bytes

PHP - 81 bytes

Javascript (55)

J: 16 characters

TI-BASIC

PHP, 61

Game Maker Language, 54

Java, 207

Polyglot, 24 chars (cheeky)

Javascript - 157 characters

Javascript: 73 characters

Perl, 92 bytes

APL - 31

Smalltalk

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Community Bulletin

Hot Network Questions

current community

more stack exchange communities

Calculate the cube root of a number

16 Answers

Haskell - 35

SageMath, (69) 62 bytes

SageMath, 12 bytes, if exp is allowed

Python - 62 bytes

PHP - 81 bytes

Javascript (55)

J: 16 characters

TI-BASIC

PHP, 61

Game Maker Language, 54

Java, 207

Polyglot, 24 chars (cheeky)

Javascript - 157 characters

Javascript: 73 characters

Perl, 92 bytes

APL - 31

Smalltalk

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Community Bulletin

Related

Hot Network Questions

SageMath, 12 bytes, if `exp` is allowed