mersenneforum.org New Algorithm - Tester(s) required
 Register FAQ Search Today's Posts Mark Forums Read

2006-04-15, 19:42   #23
Jushi

Sep 2005
UGent

22×3×5 Posts

Quote:
 Originally Posted by bearnol Well you would say that, wouldn't you, Alex - since you're the competition (GMP-ECM)! :-)
Well, ecm finds the 12-digit factor of 2^607+1 in a matter of seconds, while you say your algorithm takes about an hour. I know which algorithm I prefer...

 2006-04-15, 20:29 #24 bearnol     Sep 2005 127 Posts Yes, I'm serious - I estimate (assuming all goes well - which is the point of the test) about 1 year to find the 20-digit factor of (M+2)607. Interested? About 8000 cpu years to find 40-digit factor of similar numbers, about 64000000 cpu years to find 80-digit factors, etc... [so I know which algorithm _I_ would prefer for big factors] This is using my (already-written) Java code - if I were to rewrite it in C might be faster?? J
 2006-04-15, 20:38 #25 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Run it yourself. I don't mind if you waste your own cpu time, but don't waste others' by luring them into pointless endeavours with baseless claims. Alex
 2006-04-15, 22:21 #26 bearnol     Sep 2005 127 Posts It's not a baseless claim (I've already had promising results). Lay off of my potential helpers! :-) J
2006-04-15, 23:50   #27
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa I can't write up a formal analysis until some time in may due to higher priority tasks (yes, including GMP-ECM), and quite possibly will have other things to do even then. I have analysed the idea of trying different bases for P-1 for my thesis, though, and found it utterly useless. IIRC, less than log(B1)/B1 of the possible bases lead to a end-of-stage-1 residue of smaller order than the worst case can have. Btw, providing an analysis of the algorithm would be up to you anyway, especially in the light of your grand claim of polynomial time complexity. Alex
Bearnol's claim to the contrary, I understand his proposal quite well.
It is strictly an exponential time algorithm and is actually worse than
trial division. It is pointless.

 2006-04-16, 02:24 #28 bearnol     Sep 2005 11111112 Posts Trial division requires testing values of the 'base' up to the size of the factor. The results I'm already getting show that only a small percentage of the size of the factor is needed from the 'base' to find the factor. What's more this beneficial effect increases with size of factor. Thinking theoretically, it is clear to me at least, that in the limit, the size of base needed for any size factor will tend to a constant (sic). How can this be worse than trial division!!!. Couple this fact with the polynomial/logarithmic time needed for each step (as I've already said, using Russian Peasant) and you get a polynomial/logarithmic algorithm. If you don't believe me - try it!! There's working programs there...
2006-04-16, 19:18   #29
ewmayer
2ω=0

Sep 2002
República de California

22·2,851 Posts

Quote:
 Originally Posted by bearnol Well you would say that, wouldn't you, Alex - since you're the competition (GMP-ECM)! :-)
I disagree - "competition" comes from the from the Latin competere, meaning to seek or strive together, and thus implies that the parties involved each have some nonvanishing chance of succeeding, which is most definitively not the case here. Not coincidentally, the word "competent" has the same root.
Quote:
 I was unaware that this algorithm was 'well-known' by anyone other than me...
Trust me, we'd have been more than happy to let you keep this one all to yourself, except that you insisted on fluttering to the top of your barnyard Misthaufen and crowing loudly about it to all the world.
Quote:
 If you don't believe me - try it!!
Wrong again - we don't believe you, so it's up to you to prove us wrong. Alas for you, this isn't the grade-school playground anymore, and your taunts of "I know something that the rest of you doooooooooon't" cut no ice here.

 2006-08-16, 04:57 #30 bearnol     Sep 2005 127 Posts You may already be aware of the Mersenneplustwo project - but if not I'd like to bring it to your attention, pls... http://bearnol.is-a-geek.com/Mersenn...neplustwo.html thanks, J Last fiddled with by akruppa on 2006-08-16 at 07:57 Reason: Post moved to "Tester(s) required" thread

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ Programming 19 2017-07-16 11:20 houding PrimeNet 14 2015-12-21 09:34 PageFault Software 2 2014-04-14 15:23 Ken_g6 Prime Sierpinski Project 10 2005-01-04 14:36 dave_0273 Hardware 2 2004-06-19 15:34

All times are UTC. The time now is 11:56.

Sun Aug 9 11:56:19 UTC 2020 up 23 days, 7:43, 3 users, load averages: 1.95, 1.93, 1.92