Forum unknown
· Programming
#Three-Dee graphics
9 messages in this thread
The classic way is the Newton iteration approach. Given a number A and an
estimate R of its root, the next estimate is given by
R' = 1/2 (R + A / R).
You can use some kind of test on the difference, to decide when to quit,
but it's usually easier to just loop a fixed number of times. Depending on
the initial guess, the method converges in about 5-10 iterations.
The initial guess is the trick. The worst you can do is to use some fixed
value like 1. Next best is to use some kind of table lookup, based upon the
value of the input. Of course, that takes time too. Someone else suggested
a table lookup for the whole thing, if you only need an 8-bit answer.
Taking this a little farther, you could do a lookup on only the first few
bits in the input value, and then do one or two Newton iterations to
finish.
If you're doing it in floating point (doubtful, since you're doing it in
assember), I've had good look by just halving the exponent. In other words,
the starting value is always 1.0E to the something. Crude but it works.
There is also a closed-form algorithm for the square root, which works a
lot like an integer divide. If you go back to your old grade school math
books, you'll find the decimal version of it. But usually that can take
longer than the iterative approach.
Jack
Jack, thank you for your reply. I've pretty much decided that the best way
to do this is with Newton's method. The problem with this has been coming
up with a good initial guess. With large numbers, it can take up to 13
iterations for a evaluation correct to 4 decimal places
The problem with lookup tables or interpolation is that the square root
function is not linear and you get greater errors as you look for the
square roots of larger numbers. The only solution to this is to create a
table of increasing density. This is my solution to the problem. Using a
table of known square roots, interpolating to a close answer is easy. I
then use this number as my initial guess in solving for the square root by
Newton's method. This produces accurate values in only 2 – 4 iterations.
Another method for anyone who already was a natural log function and a
EXPonent function is the equation:
x^2 – (value) = 0
ln(x^2) = ln(value) ( x = sqr(value) )
2ln(x) = constant – look up in table
x = exp(constant/2)…outa room..thanks….kirk
Kirk, approximating the initial square root: assume that the input value is
a binary integer of some size, or can be looked at as one (e.g. the
mantissa of a floating point number). There are a certain number of
leading zeros, followed by a 1, and then some digits that are either 0 or
1:
000…0001xxx…xxx
a crude approximation of the square root of this number is:
000…0001xxx…xxx
where the new string of xxx….xxx is half as many bits long as the old
one. This will be correct within a factor of 2. My first impulse was to
use all zeros for the new xxx, but then I realized it would make more sense
to use the next few bits of the original value. E.g., if you're taking the
square root of
00001abcdefghij
then use an initial value of
00001abcde
I don't have any proof, but it seems to me that will always be closer than
straight zeros.
How do you create that value? Something like this:
Assume Value contains the number to be square-rooted
ApproxSqrt=Value
Temp=Value
While Temp isn't 0
Shift Temp right by two bits
Shift ApproxSqrt right by one bit
End while
I believe a slight improvement is:
Assume Value contains the number to be square-rooted
ApproxSqrt=Value
Temp=Value
While Temp isn't 0 or 1
Shift Temp right by two bits
Shift ApproxSqrt right by one bit
End while
If Temp is 1, multiply ApproxSqrt by the square root of 2
(for approximation purposes, multiply by 1.5 —
ApproxSqrt=ApproxSqrt + ApproxSqrt shift-right by 1)
I might have some of the logic slightly wrong, but I'm sure the idea is
valid. However: how close does the approximate square root have to be? Is
a factor of 2 unacceptably far off (needs too many iterations to fix up)?
– Bela PS: an article in this month's Computer Language examines the
assembly language of the IBM RT PC. It mentions an instruction to count
the number of leading 0 bits in a register. Boy, that would be handy in
this operation…
Kirk, approximating the initial square root: assume that the input value is
a binary integer of some size, or can be looked at as one (e.g. the
mantissa of a floating point number). There are a certain number of
leading zeros, followed by a 1, and then some digits that are either 0 or
1:
000…0001xxx…xxx
a crude approximation of the square root of this number is:
000…0001xxx…xxx
where the new string of xxx….xxx is half as many bits long as the old
one. This will be correct within a factor of 2. My first impulse was to
use all zeros for the new xxx, but then I realized it would make more sense
to use the next few bits of the original value. E.g., if you're taking the
square root of
00001abcdefghij
then use an initial value of
00001abcde
I don't have any proof, but it seems to me that will always be closer than
straight zeros.
How do you create that value? Something like this:
Assume Value contains the number to be square-rooted
ApproxSqrt=Value
Temp=Value
While Temp isn't 0
Shift Temp right by two bits
Shift ApproxSqrt right by one bit
End while
I believe a slight improvement is:
Assume Value contains the number to be square-rooted
ApproxSqrt=Value
Temp=Value
While Temp isn't 0 or 1
Shift Temp right by two bits
Shift ApproxSqrt right by one bit
End while
If Temp is 1, multiply ApproxSqrt by the square root of 2
(for approximation purposes, multiply by 1.5 —
ApproxSqrt=ApproxSqrt + ApproxSqrt shift-right by 1)
I might have some of the logic slightly wrong, but I'm sure the idea is
valid. However: how close does the approximate square root have to be? Is
a factor of 2 unacceptably far off (needs too many iterations to fix up)?
– Bela PS: an article in this month's Computer Language examines the
assembly language of the IBM RT PC. It mentions an instruction to count
the number of leading 0 bits in a register. Boy, that would be handy in
this operation…
If you have an exp and ln function (and don't mind the time it takes to use
them) then the problem is much easier than you say:
sqrt(x) = exp( ln(x) / 2.0).
But then, if you have a language that has exp and ln, it also has sqrt!
You still haven't told us if you're doing this in integer or floating point
math. Since we were on a chain discussing 3-D graphics, I think we all kind
of assumed you were needing something small & fast. Now I'm not so sure.
If you have an exp and ln function (and don't mind the time it takes to use
them) then the problem is much easier than you say:
sqrt(x) = exp( ln(x) / 2.0).
But then, if you have a language that has exp and ln, it also has sqrt!
You still haven't told us if you're doing this in integer or floating point
math. Since we were on a chain discussing 3-D graphics, I think we all kind of
assumed you were needing something small & fast. Now I'm not so sure.
Jack
If you have an exp and ln function (and don't mind the time it takes to use
them) then the problem is much easier than you say:
sqrt(x) = exp( ln(x) / 2.0).
But then, if you have a language that has exp and ln, it also has sqrt!
You still haven't told us if you're doing this in integer or floating point
math. Since we were on a chain discussing 3-D graphics, I think we all kind of
assumed you were needing something small & fast. Now I'm not so sure.
Jack
If you have an exp and ln function (and don't mind the time it takes to use
them) then the problem is much easier than you say:
sqrt(x) = exp( ln(x) / 2.0).
But then, if you have a language that has exp and ln, it also has sqrt!
You still haven't told us if you're doing this in integer or floating point
math. Since we were on a chain discussing 3-D graphics, I think we all kind
of assumed you were needing something small & fast. Now I'm not so sure.
Jack, thank you for your reply. I've pretty much decided that the best way
to do this is with Newton's method. The problem with this has been coming
up with a good initial guess. With large numbers, it can take up to 13
iterations for a evaluation correct to 4 decimal places
The problem with lookup tables or interpolation is that the square root
function is not linear and you get greater errors as you look for the
square roots of larger numbers. The only solution to this is to create a
table of increasing density. This is my solution to the problem. Using a
table of known square roots, interpolating to a close answer is easy. I
then use this number as my initial guess in solving for the square root by
Newton's method. This produces accurate values in only 2 – 4 iterations.
Another method for anyone who already was a natural log function and a
EXPonent function is the equation:
x^2 – (value) = 0
ln(x^2) = ln(value) ( x = sqr(value) )
2ln(x) = constant – look up in table
x = exp(constant/2)…outa room..thanks….kirk