Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
@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
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|cite|improve this answer

$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|cite|improve this answer

Your Answer


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.