how to use bit operation to do \sqrt(n)

[Thomas Zhu]

hello all,
n is an 32bit-integer, how to calculate
sqrt(n)
I know high(n) is the the value, but how to use bit operation to
implement this function.

thanks in advance.

yours
Yin

[websnarf]

Thomas Zhu wrote:

n is an 32bit-integer, how to calculate
sqrt(n)
I know high(n) is the the value, but how to use bit operation to
implement this function.

http://www.pobox.com/~qed/sqroot.html

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[hurry]

Thomas Zhu wrote:

hello all,
n is an 32bit-integer, how to calculate
sqrt(n)
I know high(n) is the the value, but how to use bit operation to
implement this function.

thanks in advance.

yours
Yin

are you referring to fixed point implementation of sqrt(n)
what is high(n)?

bye,
hurry.

[Yin Zhu]

hurry wrote:

are you referring to fixed point implementation of sqrt(n)
what is high(n)?

if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

[Ico]

Thomas Zhu <zh********@gmail.comwrote:

hello all,
n is an 32bit-integer, how to calculate
sqrt(n)
I know high(n) is the the value, but how to use bit operation to
implement this function.

thanks in advance.

yours
Yin

Ah, the elusive square root,
It should be a cinch to compute.
But the best we can do
Is use powers of two
And iterate the method of Newt!

--
:wq
^X^Cy^K^X^C^C^C^C

[Richard Heathfield]

Yin Zhu said:

>
hurry wrote:

>are you referring to fixed point implementation of sqrt(n)
what is high(n)?

if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

If that were true, the square root of 9 (binary 1001) would be 2 (binary
10), whereas in fact it is 3, and the square root of 32 (binary 100000)
would be 8 (100) whereas in fact it lies between 5 and 6, either of which
would be a better approximation than 8.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Yin Zhu]

Richard Heathfield wrote:

Yin Zhu said:

hurry wrote:

are you referring to fixed point implementation of sqrt(n)
what is high(n)?

if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

If that were true, the square root of 9 (binary 1001) would be 2 (binary
10), whereas in fact it is 3, and the square root of 32 (binary 100000)
would be 8 (100) whereas in fact it lies between 5 and 6, either of which
would be a better approximation than 8.

What I need is not to get the exact sqrt, I just need a fast way to get
the
high half bits of a integer.
(I am trying to implemting van Emde Boas Tree, I want to use a fast
sqrt instead
the one in math.h)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Eric Sosman]

Yin Zhu wrote:

Richard Heathfield wrote:

>>Yin Zhu said:

>>>hurry wrote:
are you referring to fixed point implementation of sqrt(n)
what is high(n)?

if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

If that were true, the square root of 9 (binary 1001) would be 2 (binary
10), whereas in fact it is 3, and the square root of 32 (binary 100000)
would be 8 (100) whereas in fact it lies between 5 and 6, either of which
would be a better approximation than 8.

What I need is not to get the exact sqrt, I just need a fast way to get
the
high half bits of a integer.
(I am trying to implemting van Emde Boas Tree, I want to use a fast
sqrt instead
the one in math.h)

There are lots of square root implementations kicking around;
websnarf has already referred you to a web page that has several.
If what you care about is speed you should try *all* of them,
including sqrt() from <math.h>, to see which actually turns out
to be fastest in your application(s) on your machine(s).

Converting from integer to double and back sounds like -- and
may be -- a lot of work, but on some systems it could be faster
than purely-integer alternatives. Floating-point sqrt() is a
built-in hardware instruction on many machines, which may give it
enough of an advantage to compensate for the conversion overhead
(especially on machines where integer division is expensive).

Measure, measure, measure!

--
Eric Sosman
es*****@acm-dot-org.invalid

[Richard Harter]

On 29 Oct 2006 20:29:38 -0800, "Thomas Zhu" <zh********@gmail.com>
wrote:

>hello all,
n is an 32bit-integer, how to calculate
sqrt(n)
I know high(n) is the the value, but how to use bit operation to
implement this function.

thanks in advance.

What you need is to post in a more appropriate newsgroup
(comp.programming would be appropriate), to state your problem more
clearly, and to describe more clearly what the acceptable error is.

Judging from your further comments what you want is a fast, rough
approximation for an integer square root. One way to do this is to
find p, the position of the high order bit of n, and right shift n p/2
bits. If you know that n is large (greater than 2**16) and you are
willing to accept a really rough approximation just right shift n 16
bits (that gives you your "high") and add 1.

If you restate your request in comp.programming and state your
requirements more clearly, you should get a better answer than this.
In particular, you should characterize n more clearly than being a 32
bit integer, the level of accuracy that you desire (e.g., within a
factor of two), and whether there are storage constraints, i.e.,
whether it's okay to use lookup tables.

[Richard Bos]

"Yin Zhu" <zh********@gmail.comwrote:

Richard Heathfield wrote:

Yin Zhu said:

hurry wrote:
>
>are you referring to fixed point implementation of sqrt(n)
>what is high(n)?
>
if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

If that were true, the square root of 9 (binary 1001) would be 2 (binary
10), whereas in fact it is 3, and the square root of 32 (binary 100000)
would be 8 (100) whereas in fact it lies between 5 and 6, either of which
would be a better approximation than 8.

What I need is not to get the exact sqrt, I just need a fast way to get
the high half bits of a integer.

Just the high half bits? It really doesn't matter to you whether it's at
all an exact representation of any square root? If so, use & and >>,
combined with a judicious choice of sizeof (int) and CHAR_BIT.

Richard

[Fred Kleinschmidt]

"Eric Sosman" <es*****@acm-dot-org.invalidwrote in message
news:2-******************************@comcast.com...

Yin Zhu wrote:

>Richard Heathfield wrote:

>>>Yin Zhu said:
hurry wrote:
>are you referring to fixed point implementation of sqrt(n)
>what is high(n)?

if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

If that were true, the square root of 9 (binary 1001) would be 2 (binary
10), whereas in fact it is 3, and the square root of 32 (binary 100000)
would be 8 (100) whereas in fact it lies between 5 and 6, either of which
would be a better approximation than 8.

What I need is not to get the exact sqrt, I just need a fast way to get
the
high half bits of a integer.
(I am trying to implemting van Emde Boas Tree, I want to use a fast
sqrt instead
the one in math.h)

There are lots of square root implementations kicking around;
websnarf has already referred you to a web page that has several.
If what you care about is speed you should try *all* of them,
including sqrt() from <math.h>, to see which actually turns out
to be fastest in your application(s) on your machine(s).

A slight nit here. <math.hdoes not contain sqrt(). It merely provides
a prototype for the function that is included in some system library,
usually libm.a

>
Converting from integer to double and back sounds like -- and
may be -- a lot of work, but on some systems it could be faster
than purely-integer alternatives. Floating-point sqrt() is a
built-in hardware instruction on many machines, which may give it
enough of an advantage to compensate for the conversion overhead
(especially on machines where integer division is expensive).

Measure, measure, measure!

--
Eric Sosman
es*****@acm-dot-org.invalid

--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Software Reuse Project

[Martin Ambuhl]

Yin Zhu wrote:

hurry wrote:

>are you referring to fixed point implementation of sqrt(n)
what is high(n)?

if n is represented as a binary string, the first half is the sqrt(n),
which is high(n)

This is obviously inadequate. n must be represented as a binary string
with a first digit of 1. Consider a 16-bit representation of, for
example, 17 (0000 0000 0001 0001), the first half of which has a value
of 0, a not very useful result.

Further, 'the first half' has no meaning (without further specification)
for bitstrings of odd length. Consider the bit representation with a
leading 1 of, for example, 17 (10001). Is the first half 10 (2) or 100
(4). Either answer commits you to the first and second half having
different lengths, which is not an ordinary meaning of 'half'.

[pete]

Thomas Zhu wrote:

>
hello all,
n is an 32bit-integer, how to calculate
sqrt(n)
I know high(n) is the the value, but how to use bit operation to
implement this function.

unsigned isqrt(unsigned n, unsigned *remainder)
{
unsigned power_of_4, root, sum;

power_of_4 = ((unsigned)-1 >2 - (unsigned)-1 % 3) + 1;
root = 0;
do {
sum = root + power_of_4;
if (n >= sum) {
n -= sum;
root = sum + power_of_4;
}
root >>= 1;
power_of_4 >>= 2;
} while (power_of_4 != 0);
if (remainder != NULL) {
*remainder = n;
}
return root;
}

--
pete