Searching \ for 'Another math problem!' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/method/math.htm?key=math
Search entire site for: 'Another math problem!'.

Truncated match.
PICList Thread
'Another math problem!'
1996\06\12@201715 by Xaq

flavicon
face
I while back I posted a question about a simple math problem, that everyone
was very helpful in solving.  I hope you guys can help me with this one, it
is a little harder.

I need to solve this equation:

       sqrt(x^2+y^2)/(x*y)

    Both x, y, and the answer are all byte(0-255) values.

I have compiled a number routines for various math problems (the latest is
the sqrt, thanks guys), but not enough to solve this equation.

In the equation above, the problem is in the fact that you must add x^2 and
y^2, right there you might have a number larger than 16 bits (I am not sure
how to handle double word mult and sqrt). I even tried manipulating the
equation first to see if I could make it any easier.  This is what I came up
with:

       sqrt( (x/y)^2 )/y

This is equivalent to the first equation and it does not have the problem
with large numbers, instead x/y could be a very small fraction.  We don't
like floating point :^( .

I am not sure what to do. I tried the old lookup table approach, but it
would have to be real big (255 by 255) to get any real accuracy.  On top of
all that I need to keep the whole routine down to bellow 600 cycles.  Any
suggestions would be a great help.


Thanks

Zach

1996\06\13@001007 by Steve Hardy

flavicon
face
> From: Xaq <spam_OUTxaqTakeThisOuTspamINDIRECT.COM>
>
> I while back I posted a question about a simple math problem, that everyone
> was very helpful in solving.  I hope you guys can help me with this one, it
> is a little harder.
>
> I need to solve this equation:
>
>         sqrt(x^2+y^2)/(x*y)
>
>      Both x, y, and the answer are all byte(0-255) values.
>
> [cut]

That's easy:

if x or y are zero, return 255 (nearest thing to infinity).
if x == 1 or y == 1, return 1 (nearest thing to sqrt(x^2+1)/x).
else return 0 (nearest thing to any other case).

But seriously! I presume you want to scale the result to a meaningful
precision?

Regards,
SJH

1996\06\13@003946 by Martin J. Maney

flavicon
face
On Wed, 12 Jun 1996, Xaq wrote:

> I need to solve this equation:
>
>         sqrt(x^2+y^2)/(x*y)

In order to check that I've read this right, that's the ratio of the
length of the diagonal to the area of the rectangle where one side is x
and the other is y, yes?

> In the equation above, the problem is in the fact that you must add x^2 and
> y^2, right there you might have a number larger than 16 bits (I am not sure
> how to handle double word mult and sqrt). I even tried manipulating the

If you can make any guarantees about the values that can come up you
might not need a full double-word intermediate.  In any event,
multi-precision multiplication and division are more tedious - and slow!
- than we might wish.

> equation first to see if I could make it any easier.  This is what I came up
> with:
>
>         sqrt( (x/y)^2 )/y

This is why I want to make sure I understand the original.  The
rearrangement I get that's close to this is

       sqrt( (y/x)^2 + 1 )
      ---------------------
                y

Not that this gets us any further in finding an efficent solution, but it
does raise some doubt whether I've read the same problem you started out
with!

> I am not sure what to do. I tried the old lookup table approach, but it
> would have to be real big (255 by 255) to get any real accuracy.  On top of
> all that I need to keep the whole routine down to bellow 600 cycles.  Any
> suggestions would be a great help.

No floating point, then the trigonometric form won't be of any use, will
it?  What was the original problem, if it's not too shy of publicity?
Just possibly you've analyzed it into a form that disguises the key to a
solution.

1996\06\14@170246 by Scott Dattalo

face
flavicon
face
Xaq wrote:
>
> I need to solve this equation:
>
>         sqrt(x^2+y^2)/(x*y)
>


and ....

Donald F. Wright Jr. wrote:
>
> I need to find the result of adding two vectors together.
>
> Result= SQRT(X^2 + Y^2)
>

These are very similar problems, so killing two stones with one bird...

You guys might wish to consider the binomial expansion of the square root
function:

          1            u       u^2       u^3       u^4
(1 + u)^(---) =  1 +  ---  -  -----  +  ----- - 5*----- + ...
          2            2        8        16        128

In either case, u is the ratio of x and y squared. For example, Xaq's problem
may be rewritten (contrary to how Xaq rewrote it):

 sqrt(x^2 + y^2)        sqrt(1 + (y/x)^2)
----------------- =   ----------------------
       x*y                      y

And for Donald's problem:

 sqrt(x^2 + y^2) = x * sqrt(1 + (y/x)^2)

Using the binomial expansion on Donald's problem:
                               (y/x)^2   (y/x)^4
 x*sqrt(1 + (y/x)^2) = x*(1  + ------- - ------- + ...)
                                  2         8

I've assumed that y is greater than x. If it isn't, then you will want to form
the
ratio of x/y instead. The number of terms that you need evaluating depend upon
the
ratio of x and y and also on how much accuracy you desire.

There are a couple of exceptions worth noting. Obviously, if x or y is zero then
the sqrt computation is not necessary. (In Xaq's case, it's even detrimental).
Similarly, if x and y are equal then the square root reduces to simply a
sqrt(2),
i.e. a constant. If x and y are about the same size, then you need to make a
simple
modification to the series approximation.

If u = (y/x)^2 ~ 1 then let v = 1 - u and substitute this into the series:


          1                     1
(1 + u)^(---) =   (1 + 1 - v)^(---)
          2                     2
                            1
              =   (2 - v)^(---)
                            2

                                v     1
              =   sqrt(2)*(1 - ---)^(---)
                                2     2


                                v       v^2       v^3       v^4
              =  sqrt(2)*(1 -  ---  -  -----  -  ----- - 5*----- + ...
                                4       32        128       2048

The question still remains whether or not these series approximations are any
more
efficient then the square root of the sum of squares. Considering that we now
have
a fairly efficient way of computing square roots, it may not be.


Speaking of efficient square roots... I initially considered this series
approximation
to compute the square root of a 16 bit unsigned integer. The way it would work
is:

Given a 16 bit unsigned integer N:

1) Let M = 2^m where m is the most significant bit position of N. For example,
if
N = 0001 0001 1101 1111 then
M = 0001 0000 0000 0000  and  m = 12.

2) If m is odd, then
      a) M = M * 2
      b) m = m + 1
      c) N = N * 2
      d) let K = sqrt(2)
  else
      a) let K = 1

let P = N ^ M , this clears the most significant bit of N

At this point, N can be expressed as
 N = (M + P) / K^2

3) Introduce the binomial expansion of the square root function:

 sqrt(N) = sqrt(M + P)/K
         = sqrt(M) * sqrt(1 + P/M) / K

Note, that M is a perfect square. So,
 sqrt(M) = sqrt(2^m) = 2^(m/2)


                              P/M     (P/M)^2     (P/M)^3      (P/M)^4
 sqrt(N) = 2^(m/2)/K * ( 1 +  ---  -  -------  +  -------- - 5*------- + ...
                               2        8            16           128

 sqrt(N) = 2^(m/2)/K * ( 1 + P>>(m+1) - (P*P)>>(2*m+3) + (P*P*P)>>(3*m+4) -
...)

This will give you at least seven bits of resolution. This is because P/M is
less
than 1/2. The fourth term cubes P/M and divides it by 2^4. In effect, dividing P
by
2^7. The next term divides P by ~2^9. At any rate, the square root computation
has
been converted into a multiplication computation. It's not exactly efficient,
but
I thought it was interesting.


Scott

1996\06\18@050027 by fastfwd

face
flavicon
face
Xaq <.....PICLISTKILLspamspam@spam@MITVMA.MIT.EDU> wrote:

> I need to solve this equation:
>
>         sqrt(x^2+y^2)/(x*y)
>
>      Both x, y, and the answer are all byte(0-255) values.
>
> ....
>
> In the equation above, the problem is in the fact that you must add
> x^2 and y^2, right there you might have a number larger than 16 bits
> (I am not sure how to handle double word mult and sqrt).

Zach:

Scott Dattalo and others have given you a lot of good information
already... Have you solved your problem?

If not, and if you want to do it by simply translating your equation
directly into code, you can get over the hurdle you mentioned (x^2 +
y^2 > 16 bits) by noting that sqrt(a*b) = sqrt(a) * sqrt(b).

Therefore, you can simply divide the result of your "x^2 + y^2"
calculation by 4, perform the square-root operation on this new
number (now guaranteed to fit within 16 bits), then multiply the
result of the square-root operation by 2.

My apologies if anyone else has already pointed this out... I've been
away from the list for a while.

-Andy

Andrew Warren - fastfwdspamKILLspamix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

More... (looser matching)
- Last day of these posts
- In 1996 , 1997 only
- Today
- New search...