Man!!! I like that Hel,
what do you think of, or can do w/:
Posted on 2002-01-29 08:56:11 by BradB
I took a brief look at that post once. I don't really know what to make of it. It goes well over my head. I've always been good at math, but it never did anything more than bore me and / or give me a headache. I like applied math, such as in physics or other subjects that I like. Math for the sake of math is not something with which I agree. Look at Newton, he created calculus not for sake of math, but because those planets up in the sky prevented him from sleeping at night.
In any case, that article looks interesting; if only I could understand it.
I learned this method of computing the square root of a number in 5th grade or something like that. Even when I wrote that post last night, I did not consider the possibility of using other number bases. The fact that it works with any base is quite neat! Thanks bitRAKE for pointing it out.
Posted on 2002-01-29 13:03:22 by Hel
Hel: in youir method your must know alot of squared ( dont know how to say it

"Find the greatest number that squared is less " what if you cant do it .....?

here is way to calculate squar root :(code in visual basic but very easy to understand )

Const epsilon = 0.0000001

Private Function sqr2(ByVal x As Double) As Double
Dim a0 As Double, a1 As Double
a0 = 0
a1 = 1

Do While (fabs(a0 - a1) >= epsilon) ' // |ai - ai+1| < epsilon

a0 = a1
a1 = (x / a0 + a0) / 2 ' ' // ai+1= (x/ai+ai) /2

sqr2 = a1

End Function

Private Function fabs(ByVal n As Double) As Double
If n < 0 Then n = n * -1
fabs = n
End Function


Posted on 2002-01-29 13:31:41 by eko
Find the greatest number that squared is less " what if you cant do it .....?

I don't see what you can't do. This algorithm is absolute. There isn't anything that doesn't work. Certainly, you can find a one-digit number that when squared is less than a given two-digit number. Your choices are 0 - 9.
Hel: in your method your must know alot of squared ( dont know how to say it

My method requires that you can square a one-digit number, multiply, and subtract. That's all.
As for your method, I'm sure there are a lot of guessing methods out there. The point is not to blindly poke around until you find your number to the required number of decimal places. My algorithm finds you every digit without any guessing. And it can keep going for an infinite number of digits. Yours will overflow the double variable after a few decimal places. Not to mention that you're using floating point which in assembly isn't as easy as typing "double".

My explanation may be wordy and poorly worded; however, the picture is worth a thousand words. Just look at the picture and you'll see that it's quite easy. Especially if you do it in binary.

If everything in math/science would be about estimating instead of having an algorithm that gets you the needed result, then I don't know what our lives would be like.
Posted on 2002-01-29 13:50:11 by Hel
If anyone's interested, eko's method is called "Newton's Sqrt Method", however it was discovered long before Newton----
Posted on 2002-01-29 13:50:12 by BradB
eko, that division is costly.

Hel, in binary your algo requires much less - not even a look-up table for the sqares if you partition by two bits, but that requires 16 itterations for a DWORD - that is 16 multiplies. I think a byte lookup table and four loops (unrolled) would be pretty quick for a DWORD.

Having a variety of methods is good because you never know what will fit into your algo - integers, fixed-point, floating point, different bit depths, etc...
Posted on 2002-01-29 14:01:46 by bitRAKE
Hel, don't stop now----you might as well do a cube--:)
does base three make sense ???
Posted on 2002-01-29 14:08:11 by BradB
bitRAKE, I don't see how that would require 16 multiplications.
I don't think you need any multiplications at all.

For the first group where you need to square the first number, there is not problem because that group is 11b at most, which means that your first digit is always a 1. Then, you have to multiply that by 2 and that can be done with a shift_right by 1 bit. Then, because you can only append a 1 or a zero, you still don't have to multiply. A few comparisons will do.

On the other hand, if you group them by fours or more, you will have to do multiplications.
Posted on 2002-01-29 15:35:42 by Hel

bitRAKE, I don't see how that would require 16 multiplications.
I don't think you need any multiplications at all.
True, my mistake. :tongue:
Posted on 2002-01-29 15:52:56 by bitRAKE
BradB, base three is the base that makes the most sense. However, we pathetic human beings find it too hard to create a three state device.
One of my professors last semester briefly talked about why base 3 is the best base out there.
First, e is 2.7... ; therefore, base 3 is the closest you get to e. Don't ask me why e is so important. If you had enough math/science you'll believe in magical powers of the number e more than in God.
Second, the thing with binary is that it has very few states, although numbers are quite long. Hex has way too many states, but numbers are much shorter. It turns out that base e would be the optimal tradeoff between length and number of states. However, base e does not exist, so base 3 is the next best thing on this world.
Back in the 60s or so, people tried to create 3-state computers, but while base 3 is idealistic, base 2 is realistic and practical and it took over.
So ...
Posted on 2002-01-29 16:06:53 by Hel
Hel, havn't had time to dig in this yet----but I was just thinking that if we convert to base 3 for cubes that then we would only need shifts for our mult/div----B
Posted on 2002-01-29 16:13:23 by BradB
Here is a very small integer squareroot:

xor eax,eax
xor ecx,ecx
inc ecx
inc ecx
inc ecx
inc eax
sub edx,ecx
ja _loop

Result in EAX: floor(sqrt(EDX))

I guess nobody wants to use this because it is very slow.
Posted on 2002-01-30 01:07:39 by gliptic
Don't forget the Assembler Gems site, this page in paticular.
Posted on 2002-01-30 07:07:07 by Eóin
E?in, the problem with a look-up table is that it isn't in the cache most of the time.
Posted on 2002-01-30 09:26:16 by bitRAKE
Of course if you want the integer of the square root of an integer number you can use the fact that:

1 = 1*1
1+3 = 2*2
1+3+5 = 3*3
1+3+5+7= 4*4
1+3+5+7+9 = 5*5

Or in words, the square of an integer n is the sum of the first n odd numbers

To square root 26 you would do

26-1 = 25 #first subtraction
25-3 = 22 #2
22-5 = 17 #3
17-7 = 10 #4
10-9 = 1 #5
1-11 = -9 #6

We stop here (less than zero) and conclude that the square root is 5

EDIT: Lol, I've just noticed that this is the algorithm that gliptic posted code for above...

PS: Newton's method is actually very cool, and it's good to calculate other things beside square roots. It can calculate the zero of a real function. To calculate the square root of N with it the function you use is:

f(x) = x*x - N
Posted on 2002-08-31 20:15:41 by Knightmare

(x+1)*(x+1) = x^2+2x+1
If you know x^2 you can easily calculate (x+1)*(x+1).
Posted on 2002-09-02 01:16:12 by gliptic