# how many bits to write $\sqrt x$?

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!

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

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}$?
$log_2 \sqrt n = log_2 n^{\frac{1}{2}} = \frac{1}{2} log_2 x$