Tell me more ×
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.
up vote 0 down vote favorite

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

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
up vote 2 down vote

$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

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.