Page 1 of 1

Some Basic Math Functions

#1 archistrage  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 1
  • Joined: 18-August 10

Posted 18 August 2010 - 11:37 PM

Recently, I decided to get back to the basics. While doing some reading about some of the basic Math functions, I discovered that many functions actually use lookup tables rather than actually calculating out the answer. As a bit of a perfectionist, this disturbed me, mainly because I didn't know if libraries such as Math we use in .Net does this.

So, I set out to discover what I could about these functions, and attempt to put these into usable code if I could.


The first function I looked into was the square root function. The obvious first solution is the Babylonian Method, where you divide and average the answer until you reach a determined accuracy. So now that I knew the method, I need to determine how accurate I wanted it. As I said, I'm a bit of a perfectionist, so I would prefer it to be as accurate as possible. After some trial and error, I came up with a solution, which is actually very useful for other scenarios.

do
{
   PreviousAnswer = Answer;

   //Do whatever here to get an answer

}while(PreviousAnswer != Answer);



I've yet to see anyone else use this, so I don't know if it has an official name, but I just call it a solution loop. It will stop when the answer it just calculated matches the answer it calculated beforehand. Essentially, it's a more efficient version of a recursion function, but you don't need to return anything: all needed information is still within the loop.

So, by using the Babylonian Method, I came up with this:

        static double Sqrt(double Num)
        {
            double Ans = 1.0;
            double Recip = 0.0;
            double Prev;

            do
            {
                Prev = Ans;
                Recip = Num / Ans;
                Ans = (Ans + Recip) / 2.0;
            } while (Prev != Ans);
            return Ans;
        }



The function starts with the Answer as Positive One: This is a pretty good point for any number, and in my experience, there's not really any need to change it. However, should you feel the need to make it somewhat faster, you can start it as
Ans = Num / 2.0;



Provided that

Num > 1.0



Otherwise you'll make calculating the Square Root of a decimal slower.

Anyways, to explain how it works, let's take a deeper look at the logic. You know that the square root of a number lies somewhere between 1 and Num. Divide Num by 1, and you'll get, Num. Divide that by Two. Then, divide Num / (Num/2) and you get another number. Average that number with (Num/2), then repeat. The idea is that you are slowly lowering the domain of numbers that the Root could possibly be. You know that Root lies somewhere between 1 and ((Num + 1) / 2 and you know that the Root lies somewhere between those numbers as well. With each iteration you increase the accuracy of the Root.

This sounds like a slow process, but it's actually very quick. For instance, it takes 9 iterations to get the Square Root of 100, 11 iterations to get the root of 1000;
12 for 10,000
14 for 100,000
16 for 1,000,000
17 for 10,000,000
19 for 100,000,000
and
21 for 1,000,000,000

So all in all, it's a very fast algorithm to get an accurate answer out of.


Next I took a look into the Trig functions. These were a bit more complicated, and I ended up having to use Taylor series, which actually adapted quite well into code. FYI, these answers will Radians, NOT Degrees. For those of you who have forgotten,
Radians = (Degrees * PI) / 180.0;
&
Degrees = (Radians * 180.0) / PI;

The first two will be Sine and Cosine. The Taylor Series themselves are over my head, so I'm not going to explain why or how they work, because I'm not sure myself. Look here if you really want to know about the series and the Trig functions. If you don't understand how I adapted the series into the code, please post below, or feel free to PM or email me.

        static double Sin(double X)
        {
            double I = -1.0;
            double Prev;
            double Ans = X;
            double N = 3.0;
            double Fact = 1.0;
            double Exp = X * X * X;

            do
            {
                Prev = Ans;
                Fact *= N * (N - 1);
                Ans += (I * (Exp / Fact));
                I *= -1.0;
                N += 2.0;
                Exp *= X * X;
            } while (Prev.ToString() != Ans.ToString());

            return Ans;            
        }



        static double Cos(double X)
        {
            double I = -1.0;
            double N = 2.0;
            double Prev;
            double Ans = 1.0;
            double Fact = 1.0;
            double Exp = X * X;
            do
            {
                Prev = Ans;
                Fact *= N * (N - 1);
                Ans += (I * (Exp / Fact));
                I *= -1.0;
                N += 2.0;
                Exp *= X * X;
            } while (Prev.ToString() != Ans.ToString());

            return Ans;
        }



Now for the Tangent function, I did something a little different. The actual Tangent function of the Taylor series is amazingly long and complicated, and I wasn't able to successfully peel through it. As hopefully you all know, the Tan(X) is equal to Sin(x) / Cos(x), so you could just do

static double Tan (double X)
{
   return Sin(X)/Cos(X);
}



However I figured that would be a waste of resources, so I integrated the Sin and Cos into one function, and divided the answers at the end.

static double Tan(double X)
        {
            double Ans = 0.0;
            double Sine = X;
            double Cosine = 1.0;
            double I = -1.0;
            double N = 2.0;
            double Prev = 0.0;
            double Fact = 1.0;
            double Exp = X * X;

            do
            {

                Prev = Ans;
                Fact *= N;
                Cosine += (I * (Exp / Fact));
                N += 1.0;

                Exp *= X;
                Fact *= N;
                Sine += (I * (Exp / Fact));

                Ans = Sine / Cosine;
                I *= -1.0;
                N += 1.0;
                Exp *= X;
            } while (Prev != Ans);
            return Ans;
        }



Amazingly enough, my tests indicate that this is actually faster than either sin or cos individually??? Weird, but cool.


Now for my last one, I would like to give you the pinnacle of these achievements; the ATan2(). I don't know who else has done it this way, but I'm very proud of figuring it out and having it work so well. If you're curious about what I did, you should look into vectors and circles. This article was the one that finally gave me the way I needed to find an angle without having to use arcsin() or arccos(). For those of you who don't remember, ATan2 is used primarily for converting X,Y coordinates into an angle or polar coordinates.

        static double NewArcTan(double OX, double OY)
        {
            double Sub = 1.0;
            double X = Math.Abs(OX);
            double Y = Math.Abs(OY);
            double Radius = Sqrt((X * X) + (Y * Y));
            double Distance = Sqrt(Math.Pow(Radius - X, 2.0) + (Y * Y));
            double Rad = (((2 * (Radius * Radius)) - (Distance * Distance)) / (2 * Radius * Radius));
            double N = 3.0;
            double Prev = 0.0;
            double Exp = Rad * Rad * Rad;
            double Ans = (Math.PI / 2) - Rad;
            double Frac = 1.0;
            double T = 2.0;

            do
            {
                Prev = Ans;
                Frac *= (T - 1.0) / T;

                Ans -= (Frac * Exp) / N;

                Exp *= Rad * Rad;
                T += 2.0;
                N += 2.0;
            } while (Prev != Ans);

            if (X < 0)
            {
                Ans = Math.PI - Ans;
            }
            if (Y < 0)
            {
                Ans *= -1;
            }

            return Ans;
        }




Well, I hope you've all learned about how these functions came to be. As some of the most integral parts of our calculations, you may find it very useful to know how they work, especially should you ever need to calculate them out past the most commonly used digits. Also, maybe now I can stop hearing people say, "Why are you trying to figure out how to build one when the Math library has a perfectly usable function." Shut up you unhelpful morons! We want to know!

Enjoy,
Archistrage

Is This A Good Question/Topic? 1
  • +

Page 1 of 1