wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> the cube root 
        
(Message started by: kirru on Aug 30^th, 2013, 10:32am)

Title: the cube root
Post by kirru on Aug 30^th, 2013, 10:32am

The cube root of a natural number n is defined as the largest natural number m such that m power 3 <=n.(n is represented in binary notation).the complexity of finding cube root of n is?

Title: Re: the cube root
Post by towr on Aug 30^th, 2013, 12:12pm

I think the complexity is about the same as multiplication, like it is for square root (using Newton's method).

Title: Re: the cube root
Post by JohanC on Aug 31^st, 2013, 12:56pm

Wouldn't cube root (and square root) be quicker than multiplication?
For cube root you can divide your (binary or decimal) digits into groups of 3 and calculate every digit seperately. An example doing this by hand with decimal notation can be found at this (http://www.mathpath.org/Algor/cuberoot/algor.cube.root.htm) url.
An interesting overview of approaches for multiplication can be found at Wikipedia (http://en.wikipedia.org/wiki/Multiplication_algorithm).

Title: Re: the cube root
Post by towr on Sep 1^st, 2013, 7:56am

on 08/31/13 at 12:56:38, JohanC wrote:

For cube root you can divide your (binary or decimal) digits into groups of 3 and calculate every digit seperately. An example doing this by hand with decimal notation can be found at this (http://www.mathpath.org/Algor/cuberoot/algor.cube.root.htm) url.

It doesn't really look faster than multiplication to me; in fact it uses quite a few, and pretty large, multiplications (especially for the last digit, since it involves the result from all previous calculations.) Just look at the last step of finding the cuberoot of 12812904: it asks us to find the largest digit a_n-2 such that (30*23*(230+a_n-2) + a_n-2²)a_n-2 <= 645904

However, I did miss a part in the wikipedia article on Newton's method which discussed how it didn't work for the cube root.. :P So that avenue certainly doesn't work.