square root

S

snehashis

Guest
Hii,
Can anybody suggest some good algorithms to find square root of an
integer(e.g 8bit) to its nearest integer(4bit)
(e.g root(65<=n<=80)=8)?Is it possible to have square root(of 8bit
integer)in fully combinational manner?I need any sloution other than
lookup table or ROM or Karnaugh map based solution.I appreciate any help
,
Thanks,
snehashis
 
"snehashis" <snehashis_iitkgp@yahoo.co.in> wrote in message
news:0b72b78c38d90ce65410ce941394039b@localhost.talkaboutprogramming.com...
Hii,
Can anybody suggest some good algorithms to find square root of an
integer(e.g 8bit) to its nearest integer(4bit)
(e.g root(65<=n<=80)=8)?Is it possible to have square root(of 8bit
integer)in fully combinational manner?I need any sloution other than
lookup table or ROM or Karnaugh map based solution.I appreciate any help
,
Thanks,
snehashis
Click to expand...
Though another poster may declare it "impossible" it's pretty easy; a
binary extension from the base-10 manual method makes it work great.

The manual-10 method for sqrt(16129) would take the number in 2-bit chunks
(relative to the decimal) and works similar to long division with a couple
major differences. Rather than long division bringing in one digit and
working with the fixed divisor, the sqaure root brings down 2 digits and has
a divisor that has a digit in the result; when you're part way through the
equation, your divisor is 20 times the result so far (2x shifted a digit)
plus the result digit your looking for. In the example below, the three
stages look for x, y, and z for the result digits working with the 2x/20x
"front end" for the divisor. For the middle stage, the "2y into 61" wants
the largest y where 20*y+y^2<=61. Work the method below for several numbers
yourself or put together an excel example to show you that it works.

Please view the following in a fixed-space font.

1 61 29
_x_____
x )1

_1_____
1 )1

_1y___
2y )61

_12___
22 )61
44
-----
17 29

__12z
24z )1729

__127
247 )1729
1729
----
0

Once you realize how the system goes together, you can extend it to any base
in a similar manner. You want base 2, so you want to use 4x rather than 20x
(still 2x shifted a digit) plus the digit you're solving for as the divisor
in the middle stages. In binary, "solving" for your digit comes down to a
compare. Is 4 times the result digits so far plus one greater than or equal
to the digits brought down? If so, the 1 is used; if not, the 0 brings down
2 more digits with no initial subtract. Again, the fixed-space font is
needed to make sense:

10 01
__x___
x)10
__1___
1)10
1
-----
1 01

__1y
10y)101
__11
101)101
101
___
0

I hope you have fun with this. It's a lot like a divide.
 
Thanx John for the wonderful method.I think by 2y u meant 2 concatenated
with y i.e 2*10+y so that (2y)*y<=61.Would u plz explain the logic for
which the method works?
Snehashis
 
In article <EK8gd.13$2R1.2909@news-west.eli.net>,
John_H <johnhandwork@mail.com> wrote:
"snehashis" <snehashis_iitkgp@yahoo.co.in> wrote in message
news:0b72b78c38d90ce65410ce941394039b@localhost.talkaboutprogramming.com...
Hii,
Can anybody suggest some good algorithms to find square root of an
integer(e.g 8bit) to its nearest integer(4bit)
(e.g root(65<=n<=80)=8)?Is it possible to have square root(of 8bit
integer)in fully combinational manner?I need any sloution other than
lookup table or ROM or Karnaugh map based solution.I appreciate any help
,
Thanks,
snehashis

Though another poster may declare it "impossible" it's pretty easy; a
binary extension from the base-10 manual method makes it work great.
Click to expand...
I'm sorry about the rash claim of impossibility for division; I was
thinking about wider dividers, and my intuition is that clock-cycle
time is only enough for two or three levels of logic.

For an eight-bit square root, it's not going to be _that_ ridiculous
in area to have comparators with the 16 squares and a thermometer
decoder, and it'll definitely be quick.

Or the top bit of the square root of b[7:0] is just b[7] | b[6], and
you can do the rest of the binary search using three 'layers' with a
multiplier and a comparator in each.

(the floor of the square root of binary ABCD is

[A|B, (A&B) | (C|D & (~B | A))]

which is really very quick, so that gets the top two bits; but I don't
have Boolean-equation-optimising software to throw at the 8->4 problem)

Something like (I haven't compiled this, so it may be nonsense, but it's
ought to be easy-to-follow nonsense)

function [3:0] Sqrt8(in);
input [7:0] in;
output [3:0] out;

wire [3:0] out, stage2A,stage1A,stage0A;
wire [7:0] stage2B, stage1B, stage0B;

out[3] = in[7] | in[6];
stage2A = {out[3], 1, 0, 0};
stage2B = stage2A * stage2A;
out[2] = (stage2B >= in);
stage1A = {out[3], out[2], 1, 0};
stage1B = stage1A * stage1A;
out[1] = (stage1B >= in);
stage0A = {out[3], out[2], out[1], 0};
stage0B = stage0A * stage0A;
out[0] = (stage0B >= in);
out;
endmodule

Tom
 
"Thomas Womack" <twomack@chiark.greenend.org.uk> wrote in message
news:BDC*eCfyq@news.chiark.greenend.org.uk...
[snip]
, and
you can do the rest of the binary search using three 'layers' with a
multiplier and a comparator in each.
Click to expand...
Why use a multiplier in each of the three layers when a compare/subtract
would work just as well?
If you follow the manual method for doing a square root, it comes across as
VERY simple.

out[3] = in[7] | in[6];
stage2A = {in[7:6]-(out[3] ? 1 : 0),in[5:4]};
stage2B = {out[3], 2'b1};
out[2] = Stage2A >= Stage2B;
stage1A = {Stage2A-(out[2] ? Stage2B : 0), in[3:2]};
stage1B = {out[3:2], 2'b1};
out[1] = Stage1A >= Stage1B;
stage0A = {Stage1A-(out[2] ? Stage1B : 0), in[1:0]};
stage0B = {out[3:1],2'b1};
out[0] = (stage0A >= stage0B);
 
I tried it with both binary and decimal and it works fine and I also coded
that for 4bit(to simplify of course),but now I am wondering on "why"
rather than "how" becuase I didnt understand the hidden logic behind the
"taking 2 digits" at a time,plz help..
Snehashis
 
Twomack,
I think u r trying to have some Karnaugh Map type simplification and
sequential linear search combined.But the number of clock pulses will be
different for different numbers,isnt it?At any stage if comparator gives
high(to say),then next stage will not be calculated.So throughput will not
be fixed
snehashis
 
"snehashis" <snehashis_iitkgp@yahoo.co.in> wrote in message
news:3d0a5000c84d15704ae0bb5e37b0889b@localhost.talkaboutprogramming.com...
I tried it with both binary and decimal and it works fine and I also coded
that for 4bit(to simplify of course),but now I am wondering on "why"
rather than "how" becuase I didnt understand the hidden logic behind the
"taking 2 digits" at a time,plz help..
Snehashis
Click to expand...
I'll talk base 10 but the method goes to other bases easily.

The "two digits at a time" is because (x*10^n)^2 is x^2*10^2n. Every digit
we solve for needs two digits from the original number.

The first digit of a sqrt is pretty simple. A value from 1*10^2n to
99*10^2n (limited because 100*10^2n is 1*10^2(n+1)) will have a square root
= 1*10^n but <10*10^n. The first digit is easily found from the sqrt of
the first pair.
Click to expand...

For the following digits consider the equation (a*10+b)^2.
Expanding it, we have 100*a^2 +20ab +b^2.
If the a and b values are the first and second digits, we want to solve for
b knowing a and our original value.
When we took the first sqrt to find a, we subtracted a^2 from the digits to
get a remainder. When shifted by 2 digits, this was the same as subtracting
100*a^2 from the new value we want to work with (remainder plus 2 digits).

We want to find from this new value the solution for the largest b where
20ab + b^2 is less than the value. The equation can be rewritten as b(20*a
+ b) which is what you were asked to work with for the intermediate values.
You were to double the value so far and add a digit (20*a) and find the
largest b where (20*a+b)*b is less than the remainder. This solves for the
largest (10*a+b) portion of the square root.

You can conceptually increase a to 2, 3, and more digits as you move through
the following stages. The a*10+b solution is solved for in the same manner.

With base 2, there's no need to determine the "largest b" as with the base
10 solution because there are only 2 choices: 1 or 0. If the 1 fails, use
0.

Working backwards, 1234^2 = 1 52 27 56

To determine the sqrt(1522756) we go through the following.

sqrt(1) >= 1.

sqrt(152) >= 12
because (152-1^2*100)=52 >= (20+2)*2
giving a "remainder" of 8

sqrt(15227) >= 123
because (15227-12^2*100)=827=(8*10+27)) >= (240+3)*3
giving a "remainder" of 98

sqrt(1522756) = 1234
because (1522756-123^2*100)=9856=(98*10+56) == (2460+4)*4
leaving no remainder.

Neat, huh?
You can see the 2ab+b^2 decomposition at each stage.
 
Thanx John for the wonderful method.I think by 2y u meant 2 concatenated
with y i.e 2*10+y so that (2y)*y<=61.Would u plz explain the logic more
clearly how the method works?
Snehashis
 
"snehashis" <snehashis_iitkgp@yahoo.co.in> wrote in message
news:6d6198e6888dccb4b424648adf9468f8@localhost.talkaboutprogramming.com...
Thanx John for the wonderful method.I think by 2y u meant 2 concatenated
with y i.e 2*10+y so that (2y)*y<=61.Would u plz explain the logic more
clearly how the method works?
Snehashis
Click to expand...
You are correct with the "2y" notation - concatenation is intended.
In what way am I unclear? Did you try to do the base-10 example by hand?
The base 2?

Take digits 2*n+1 and 2*n, look for the largest number where (using the
concatenation concept) you get {2*partial_result, y}*y is less than the
value you're dividing.
Subtract to get the remainder and bring down the next two digits.
Use the new value for the next iteration.

Referencing "the logic" are you not looking for the algorithm but instead
the Verilog?

Are you wondering more "why" it works rather than "how" it works?
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top