Suppose we have a number N which we wish to resolve into its prime factors. To see if the number P is a factor of N, we find the quotient Q = N/P. If Q is an integer, then P is a factor of N.
In the search for prime factors, only prime divisors P need to be tried because if a divisor is composite, then any prime factor of such a divisor also divides the number N.
The largest divisor that has to be tried is the square root of N because if there is a divisor P larger than the square root of N, then the resulting quotient Q would be a smaller divisor than the square root.
Each time a prime factor P of N is found, the quotient Q becomes the new N to be factored, providing a new, smaller, square root limit. Furthermore, the search does not have to start again at the prime factor 2, but at the latest prime factor P found.
Addition, subtraction, multiplication and division
If we have two complex numbers X and Y: X = A + B*i ; Y = C + D*i, then:
X ą Y = (A ą C) + (B ą D)*i
X * Y = (A*C - B*D) + (A*D + B*C)*i
X (A*B - C*D)
(B*C - A*D)
Powers and roots
Here we use De Moivre's theorem: If Z is a complex number, then
zn = rncos(nq) + i*rnsin(nq)
where r is the MODULUS (or LENGTH) and q the argument of the polar form of z.
If x=a+b*i and we wish to find ex, then
ex = ea + b*i = ea e b*i
Using Euler's formula on e b*i , we have
ex = ea [ cos(b) + i*sin(b) ]
The polar form of a complex number z is: z = r [cos(q) + i*sin(q)]
Using Euler's formula: z = r * e i q
Taking logarithms on both sides: log(z) = log(r) + i*q
The following formulas are used to solve a triangle with sides a, b and c and corresponding opposite angles A, B and C:
A + B + C = 180°
cē = aē + bē - 2 a b cos(C) (law of cosines)
a b c
The following formulas are used in the program to find the solution:
s = r*q
c = 2 r sin(q/2)
r = radius
s = arc length
c = chord length
q = central angle in radians
A = sector area
a = segment area
First, consider the way we write numbers in base 10. For clarity, let's look at a specific number, say 2745 (BASE 10). This is a short way of writing
2745 (BASE 10) = 5 + 4*10 + 7*102 + 2*103
If 2745 were in base 8, for instance, then it would be
2745 (BASE 8) = 5 + 4*8 + 7*82 + 2*83
which has the value 1509 (BASE 10).
In base 10 we use the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 to represent the values of the first ten nonnegative integers. If the base we are considering is less than 10, then we may use the same symbols, up to the BASE-1, for convenience. But we always need a number of symbols equal to the base, so if the base is >10 then we need to adopt additional symbols. The usual practice is to use the letters of the alphabet for this purpose.
If the N digit integral part of a number in base B is to be converted to base 10, we evaluate:
DIGIT1 + DIGIT2*B + DIGIT3*B2 +...+ DIGITN*BN-1
where DIGIT1 is the rightmost digit and DIGITN the leftmost of the integral part. If the number also has a decimal part with M digits, we also evaluate
DIGIT1/B + DIGIT2/B2 + DIGIT3/B3 +...+ DIGITM/BM
where DIGIT1 is the first digit after the decimal point and DIGITM is the rightmost digit after the decimal point, then add the two results.
To convert a number N.M in base 10 to base B, we also do the integral part N and the decimal part M separately. First, the integral part:
DIGIT1 = N MODULO B
where DIGIT1 is the rightmost digit of the integral part of the number expressed in base B. We then compute
N1 = INT(N/B)
which is the integral part of the quotient N/B.
In a similar way, we continue to compute DIGITX and NX:
DIGIT2=N1 MODULO B
DIGIT3=N2 MODULO B
DIGIT4=N3 MODULO B
until we get a zero NX.
Next the decimal part. The computations in this case are:
until we get a zero MX.
The program uses a method based on merging two already ordered lists. Suppose we have the two ordered lists A and B:
A1, A2, A3, ... An
B1, B2, B3, ... Bm
We can easily create a third ordered list C consisting of all the elements of both lists by always comparing one element of list A with one element of list B. We start by comparing A1 with B1. If A1 <= B1 then we can select A1 as the first element of list C, and delete one element from list A. The status of the three lists would at this stage be:
A2, A3, ... An (list A)
B1, B2, B3, ... Bm (list B)
C1 (list C)
where C1 = A1. We next compare A2 and B1, and so on until all the elements of one of the lists A or B are exhausted. The remaining elements of the unexhausted list are added at the end of list C.
Since at the beginning what we really have is a long list of randomly ordered elements, what we do is to consider each element as an ordered one-element list. We then start by merging pairs of elements into two-element ordered lists. We then proceed to merge two-element lists into four-element lists, and so on, until we are left with a single ordered list.
Another method used is called the QUICK SORT. In this method, a pivotal element is chosen near the center of the list. The items on either side of the pivot are then moved in such a way that all of those smaller than the pivot are on one side, and all of those larger are on the other. The method is then applied to each one of the two parts of the list, and so on, until the entire list is ordered.
Copyright Đ 2001-2010 Numerical Mathematics. All rights reserved.