Hi Don, I reposting my reply to you to all now.. The GNFS mentioned here is polynomial time as I got to understand from wikipedia. I claim that the above algorithm is linear time.
I putting the proof here for correctness and linear time (warning its big and messy). Also this one applies to the algorithm given in the blog: http://randomoneness.blogspot.com/2011/04/algorithm-to-find-factors-or-primes-in.html (The above given is a faster version of the one given in my blog) Analysis of algorithms: In below proof used: Operation A is: While r is smaller than mL then, mL can be decremented by one and the new r can be computed as r + mR. As taking out one mL, means one mR is send to remainder. (first inner while loop) Operation B is: While r is bigger than mL, then mL can be taken out from r and this basically increases mR by one. (2nd inner while loop) Operation C is: Operations A and B can be repeated till, r not equals mL. When we arrive at the results, Operation C is exited. (main while loop) 1. Proof of correctness: If the number is a perfect square root then, the answer is found when square root is found. For more reading on Square root refer: http://en.wikipedia.org/wiki/Square_root Else if the number is not a perfect square, then r is not equal to 0. Hence it enters the while loop. Operation A: While mL is greater than r, then mL is decremented by 1, and r is incremented by mR. The step is correct because, mL * mR means mR added mL times. If one is taken from mL, then mR is added (mL-1) times. So, one mR is added less, when taking one out of mL. This mR is added to r. – (1) Operation B: While mL is less than r, then mR is incremented by 1 and r is decremented by mL. This step is correct because, mL * mR means mL added mR times. If one is added to mR, then mL is added (mR + 1) times in mL*mR. So if mR is incremented by 1, then to equate to N, mL can be taken away from r the remainder. – (2) Operation C: Operation A and B are repeated till mL is equal to r. This leads to the answer because: We start from the approximate square root of the number. As operation A and B, calculates the remainder r, when the factors are mL and mR. Operation A never leads to the answer as, r + mR is always greater than mL, as mL is smaller than mR. Operation B, leads to the answer. If for any case mL is a factor, then, when r is reduced by mL in operation B to mL (r becomes a factor of mL). As Operation A and B are correct (refer 1 and 2), if there is a factor then this leads to r to be zero. And before r becomes zero, r should be equal to mL. At this point the answer is found. 2. Proof that the number of Operations required is linear: Let’s take only the case of numbers which are not perfect squares. The algorithm consists of basic operations, of addition, subtraction and comparison. Let’s see how many times a different while loops are invoked. We take mL as nearest square root. And take mR > mL. There for Operation A is invoked only once during one iteration of the Operation C. This is because, by incrementing r by mR, increases r to be greater than mL (mR > mL) and hence invalidates the loop condition. The basic number of steps in Operation A is 3: 1. While loop evaluation, 2. decrement mL by 1 and 3. Increment r by mR. Operation B is repeated to find a r which is greater than mL. As mR varies as algorithm progress, its hard to calculate number of time r Operation B is repeated. The basic number of steps in Operation B is 3: 1. while loop evaluation, 2. Increment mR by 1 and 3. Decrement r by mL. However two things are certain, for worst case scenario i.e. N is prime number, mL is reduced to 1 and mR is incremented to N. From this we can conlude that, Operation B is repeated N-sqrt(N) times i.e. Increment mR to N from sqrt(N) and Operation A is repeated till mL becomes 1 i.e from sqrt(N) to 1. Based on this the number of steps required is: Operation B : N – sqrt(N) Operation A : sqrt(N) And the Operation C, which apart from the steps we calculate from Operation A and Operation B, will have 2 basic steps; 1. the main while evaluation, 2. the exit evaluation of one of the while either of Operation A or B; during each loop execution. Operation C is called maximum of N times in worst case, as its sum of number of times Operation A and B = (N- sqrt(N) + sqrt(N) = N. The total number of steps is: => Operation B + Operation A + Operation C => (N – sqrt(N))* 3 + sqrt(N) * 3 + 2*N => 3*N+ 2*N => 5*N Hence the total number of steps is 5*N in worst case and lesser in all other cases. However, in normal computers as the input size increases the time taken to do addition, subtraction and comparison varies. As the input size increases above the size of computers word size, the number of operations required for the computing basic steps are higher. But for a given arbitrarily large number (higher than computer word size), the time taken for each basic operation would be fixed, even though is larger than in case of smaller number. Hence time taken would increase by the hidden factor times 5*N. On Apr 7, 1:14 am, Don <[email protected]> wrote: > The General Number Field Sieve is the fastest known method of > factoring large numbers, but the elliptic curve method may be faster > in some cases. Either one is much faster than your method. > Don > > On Apr 6, 12:58 pm, harish <[email protected]> wrote: > > > > > Hi all, > > > I have developed an algorithm to find factors of a given number. Thus > > it also helps in finding if the given number is a prime number. I feel > > this is the fastest algorithm for finding factors or prime numbers. > > > I have put the algorithm > > here:http://randomoneness.blogspot.com/2011/04/algorithm-to-find-factors-o... > > This one finds if a give number is prime in say time frame of 5*N > > (where N is the input number). So I hope I can call this a linear time > > algorithm. > > > Can anybody verify the above for me? > > > A faster version of algorithm i put here: > > > Input: A Number (whose factors is to be found) > > Output: The two factor of the Number. If the one of the factor found > > is 1 then it can be concluded that the > > Number is prime. > > > Integer N, mL, mR, r; > > Integer temp1; // used for temporary data storage > > mR = mL = square root of (N); > > /*Check if perfect square*/ > > temp1 = mL * mR; > > if temp1 equals N then > > { > > r = 0; //answer is found > > End;} > > > mR = N/mL; (have the value of mL less than mR) > > r = N%mL; > > while r not equals 0 do > > { > > mL = mL-1; > > r = r+ mR; > > > temp1 = r/mL; > > mR = mR + temp1; > > r = r%mL;} > > > End; //mR and mL has answer- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
