Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

x is an integer, and i can write it with $\log_2 x$ bit, and, viceversa, with $n$ bit i can write a number till $2^n$.. but.. how many bits to write $\sqrt x$ ?

EDIT: the integer part!

share|improve this question
    
if sqrt{x} is irrational I don't really understand what this statement means. –  Qiaochu Yuan Feb 7 '11 at 20:23
    
@Qiaochu the floor of $\sqrt{x}$. –  Yuval Filmus Feb 7 '11 at 20:26
1  
@nkint Suppose $x$ is an $n$-bit number. How big can $\sqrt{x}$ be? How many bits do you need to store all possible values of $\sqrt{x}$? –  Yuval Filmus Feb 7 '11 at 20:26
    
@Yuval: "how big can $\sqrt x$ be" is the point :-) sure more less that $\frac{x}{2}$.. i can't see a link with exponential.. the problem is that i don't manage to solve $log^{\frac{1}{2}}x$. –  nkint Feb 7 '11 at 21:24
    
@nkint: you need $\log (x^{\frac{1}{2}})$, not $log^{\frac{1}{2}}x$. That should help –  Ross Millikan Feb 7 '11 at 21:28
show 2 more comments

2 Answers 2

up vote 1 down vote accepted

If $\sqrt{x}$ is not an integer, it will take a lot of bits.

Hint: If it is an integer (or you are just writing the integer part) you should have a rule of logarithms that will help. Do you know another way to express $\sqrt{x}$?

share|improve this answer
add comment

$log_2 \sqrt n = log_2 n^{\frac{1}{2}} = \frac{1}{2} log_2 x$

thanks to Yuval Filmus and Ross Millikan for comments

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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