Hi All, I got a reply at another forum; here is the link for that http://stackoverflow.com/questions/5581040/i-have-a-new-algorithm-to-find-factors-or-primes-in-linear-time-need-verificati
.. Don i believe you are correct. Thanks Harish On Apr 7, 4:56 pm, harish <[email protected]> wrote: > 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-o... > > (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 -- 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.
