0
$\begingroup$

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!

  • 0
    if sqrt{x} is irrational I don't really understand what this statement means.2011-02-07
  • 0
    @Qiaochu the floor of $\sqrt{x}$.2011-02-07
  • 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}$?2011-02-07
  • 0
    @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$.2011-02-07
  • 0
    @nkint: you need $\log (x^{\frac{1}{2}})$, not $log^{\frac{1}{2}}x$. That should help2011-02-07
  • 0
    mhmmm one moment.. no! $\sqrt x$ is long..$\sqrt x$! so the formula is $log_2 \sqrt x$ = $\frac{log x}{2}$2011-02-07
  • 0
    ohu yeah ross, i've got the point and i was writing last comment while you get me the solutions! thanks to all!2011-02-07

2 Answers 2

1

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}$?

2

$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