Author 
Topic: the cube root (Read 6701 times) 

kirru
Newbie
Posts: 34


the cube root
« on: Aug 30^{th}, 2013, 10:32am » 
Quote Modify

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?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: the cube root
« Reply #1 on: Aug 30^{th}, 2013, 12:12pm » 
Quote Modify

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


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



JohanC
Senior Riddler
Posts: 460


Re: the cube root
« Reply #2 on: Aug 31^{st}, 2013, 12:56pm » 
Quote Modify

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 url. An interesting overview of approaches for multiplication can be found at Wikipedia.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: the cube root
« Reply #3 on: Sep 1^{st}, 2013, 7:56am » 
Quote Modify

on Aug 31^{st}, 2013, 12:56pm, 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 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_{n2} such that (30*23*(230+a_{n2}) + a_{n2}^{2})a_{n2} <= 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.. So that avenue certainly doesn't work.

« Last Edit: Sep 1^{st}, 2013, 7:56am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



