Welcome!

Join our community of MMO enthusiasts and game developers! By registering, you'll gain access to discussions on the latest developments in MMO server files and collaborate with like-minded individuals. Join us today and unlock the potential of MMO server development!

Join Today!

Evaluating functions on comupters

JavaScript Is Best Script
Joined
Dec 13, 2010
Messages
631
Reaction score
131
Every computer has these four predefined arithmetic operations : Addition, Subtraction, Multiplication, Division. Today, we're gonna look at how they can be used to evaluate functions not commonly found as hardware instructions, functions such as the square root of x and the sine of x.

Newton's method:
Introduction to Newton's Method:
Let f(x) be a differentiable function.
Let (x of n + 1) = (x of n) - f(x of n) / f'(x of n)
Set a suitable value of (x of 0).
Sub x of 0 into the iterative procedure to get x of 1
Sub x of 1 into the iterative procedure to get x of 2
Keep repeating until you get a value whose precision of accuracy is satisfactory.
This value will be a root of f(x) = 0

Example : solving cos(x) = x by Newton's method:
For example, we want to solve cos(x) = x
We rearrange the terms to get : cos(x) - x = 0
Then, we let f(x) = cos(x) - x
It follows that f'(x) = -sin(x) - 1
So we set (x of n + 1) = (x of n) - (cos(x of n) - (x of n)) / (-sin(x of n) - 1)
We set x of 0 to a suitable value (say, 0.1).
Then, x of 1 = 0.913763386
x of 2 = 0.744664242
x of 3 = 0.739091966
x of 4 = 0.739085133
x of 5 = 0.739085133
x of 6 = 0.739085133
Therefore, x = 0.739085133 is an approximate root of cos(x) = x

Computing square roots using Newton's method:
Now we'll look at square roots, and how to use Newton's method to compute them using only the four basic operators : addition, subtraction, multiplication and division.
Let x^2 = 17
Then, x^2 - 17 = 0
We hence set f(x) = x^2 - 17
Differentiating : f'(x) = 2x
Now, we let (x of n + 1) = (x of n) - f(x of n) / f'(x of n)
(x of n + 1) = (x of n) - (x^2 - 17) / (2x)
We choose x of 0 = 0.1
Then evaluating we get,
x of 1 = 85.05
x of 2 = 42.62494121
x of 3 = 21.51188437
x of 4 = 11.15107261
x of 5 = 6.337794815
x of 6 = 4.510057898
x of 7 = 4.139705419
x of 8 = 4.123138907
x of 9 = 4.123105626
x of 10 = 4.123105626
Hence, x = 4.123105626 is an approximate root of x^2 = 17
Which means, square root of 17 = x = 4.123105626

Well you may be asking "where's the coding part?" Sorry if i'm turning this into mathematics rather than keeping it as coding. But if you looked closely, you can easily write a function that computes square root as follows in pseudocode:
Code:
k = 123
cur = 0.1
for (i = 0; i < 100; i++)
{
   cur = cur - (cur * cur - k) / (2 * cur)
}
output(cur) // this outputs 11.09053651
Which i believe is what some computers use (except for the number of iterations)

Taylor series-es:
If you looked at Newton's method, it you to know how to compute the initial function (x^2 - k back in that example) as well as it's derivative (which was 2x). But what if the initial function and it's derivative requires evaluating of functions the computer doesn't know how to do? For example i wanna compute sin(1.23):
sin(1.23) = x
1.23 = asin(x)
asin(x) -1.23 = 0
We set f(x) = asin(x) - 123
But how are we ever gonna evaluate asin(x)? We can't using only a finite number of addition, subtraction ,multiplication and division. This is where Taylor series-es comes in:

First, we express sin(x) as it's Taylor series (if you're interested how, Im gonna skip the how part cause its rather long) to get:
sin(x) = x - (x^3)/(3!) + (x^5)/(5!) - (x^7)/(7!) + ...
Then, we just evaluate term by term until we reach a precision of accuracy we're satisfied with to get the value of sin(x) for some x.

Well, that's all for now! I hope that you can comprehend my English and sorry if this thread has been more mathematical than programming-ical
 
Newbie Spellweaver
Joined
Oct 23, 2012
Messages
5
Reaction score
1
Hey bro, Taylor Series when you're only 16? Don't be nuts. You're missing out a lot of things. And 1.23 = asin(x) isn't the only way to solve via Newton's Method.
 
Back
Top