Author |
Topic: the cube root (Read 6701 times) |
|
kirru
Newbie
Posts: 34
|
 |
the cube root
« on: Aug 30th, 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 30th, 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 31st, 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 1st, 2013, 7:56am » |
Quote Modify
|
on Aug 31st, 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 an-2 such that (30*23*(230+an-2) + an-22)an-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..  So that avenue certainly doesn't work.
|
| « Last Edit: Sep 1st, 2013, 7:56am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print