mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2009-03-22, 20:50   #45
mklasson
 
Feb 2004

2×3×43 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Yes joke, actually (I apologise about my deliberately poor English). I just forgot!
Regardless, here's a new aliqueit v1.04.

Btw, if you can compile the code it's an easy change to make it do less ecm if you really don't like the current situation. If more people feel the same way I can add some sort of config setting for it as well. If they could also explain why they feel it's too much then maybe I could make the defaults better for all. Given enough similar opinions I'll probably run with the herd even without an explanation.

Anyway:

+ also does P-1/P+1 in addition to ecm using the gmp-ecm recommended 10*B1 for P-1 and 3x 5*B1 for P+1.

+ only saves relevant parts of the ecm log, or nothing at all if no factor was found.

+ logs "*** c<digits> = <factor>" for found composite factors.

+ scans through the last 100KB of the log file when starting up and uses all relevant factors it finds. Makes restarting easier as you no longer need to manually specify factors with "-f" if you found them with the latest aliqueit run.
mklasson is offline   Reply With Quote
Old 2009-03-23, 22:49   #46
Phil MjX
 
Phil MjX's Avatar
 
Sep 2004

5×37 Posts
Default

Hello !

I have tried aliqueit with the sequence I am dealing with (5400 at index 3022) but I encountered a crash when verifying it :

at index 2924, the program does crash with Win XP !

I have been checking this problem with two machines : a Pentium M and a Core duo laptop.

I have checked the 2924th step and it is ok when processing alone

I have also tried with the 13200 sequence (that is the 5400 minus one step) and the program still crash at index 2924 (that is the 2925th of the 5400 sequence)...

Is this a bug ?

Kind regards !

Last fiddled with by Phil MjX on 2009-03-23 at 22:50
Phil MjX is offline   Reply With Quote
Old 2009-03-23, 23:30   #47
mklasson
 
Feb 2004

2·3·43 Posts
Default

Quote:
Originally Posted by Phil MjX View Post
Hello !

I have tried aliqueit with the sequence I am dealing with (5400 at index 3022) but I encountered a crash when verifying it :

at index 2924, the program does crash with Win XP !

I have been checking this problem with two machines : a Pentium M and a Core duo laptop.

I have checked the 2924th step and it is ok when processing alone

I have also tried with the 13200 sequence (that is the 5400 minus one step) and the program still crash at index 2924 (that is the 2925th of the 5400 sequence)...

Is this a bug ?

Kind regards !
Well, it sure isn't a feature.

Sounds very odd though. You're basically saying it always crashes at index 2924 for you regardless of sequence? Could you send me the elf file or attach it here? I just tried a sequence with 2931 lines (biggest I could find) without any problems.
mklasson is offline   Reply With Quote
Old 2009-03-24, 06:30   #48
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

186916 Posts
Default

I've been using aliqueit on Linux since version 1.01 and am, overall, quite happy with it. However, there are a couple of feature requests that I personally would find quite useful, if they aren't too hard to implement:

-I generally prefer to set aliqueit to do TF up to 1e8 instead of the default 1e4. However, the primary downside of this is that aliqueit takes quite some time to precalculate all the primes for TF when it first starts up. It's still only a couple of minutes, but nonetheless it got me thinking: would it possibly be faster to have aliqueit write its precalculated primes to disk after it calculates them, and then load them from that file upon all subsequent startups?

-When the program is first started, it prints to screen the full initial composite of the current line, and the number of digits it contains. Would it be possible to have it do this for all lines, not just the first one? That would make it a little easier to track how much a sequence has grown/shrunk since the program was started.

Thanks,
Max
mdettweiler is offline   Reply With Quote
Old 2009-03-24, 08:11   #49
axn
 
axn's Avatar
 
Jun 2003

13·192 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
I generally prefer to set aliqueit to do TF up to 1e8 instead of the default 1e4. However, the primary downside of this is that aliqueit takes quite some time to precalculate all the primes for TF when it first starts up. It's still only a couple of minutes
Calculating all primes up to 1e8 takes "couple of minutes"? That's just wrong!

Seriously... with an optimized implementation of SoE, it is faster to calculate the primes than reading them from disk.
axn is offline   Reply With Quote
Old 2009-03-24, 11:08   #50
mklasson
 
Feb 2004

2·3·43 Posts
Default

Quote:
Originally Posted by axn View Post
Calculating all primes up to 1e8 takes "couple of minutes"? That's just wrong!

Seriously... with an optimized implementation of SoE, it is faster to calculate the primes than reading them from disk.
I have put absolutely zero effort into the precalcing... It's just a loop with mpz_nextprime. With trial_cutoff = 1e4 it takes a couple of ms so it really hasn't seemed worth the bother. You've almost shamed me into doing something about it though.

There are several lazier options however. I could use gmp-ecm to do the trial factoring ("-t trial_cutoff"). Or, probably better, I could let yafu do a pollard rho right after the trial factoring. That would probably make a trial_cutoff of 1e8 really suboptimal and I could get away with not doing anything about the trial factoring. Yafu already does the rho, but after the ecm phase for bigger numbers which is presumably not optimal. Thoughts?

Quote:
Originally Posted by mdettweiler View Post
-When the program is first started, it prints to screen the full initial composite of the current line, and the number of digits it contains. Would it be possible to have it do this for all lines, not just the first one? That would make it a little easier to track how much a sequence has grown/shrunk since the program was started.
Something like
Code:
 1445 . c127 = 1684219780053232790182532264150037585657262227235724020539452224672674641583964846829593256612940760791424573187987177454181744 = 2^4 * ...
on the screen? I could certainly do that.
mklasson is offline   Reply With Quote
Old 2009-03-24, 13:18   #51
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·5·7·47 Posts
Default

Quote:
Originally Posted by mklasson View Post
I have put absolutely zero effort into the precalcing... It's just a loop with mpz_nextprime. With trial_cutoff = 1e4 it takes a couple of ms so it really hasn't seemed worth the bother. You've almost shamed me into doing something about it though.

There are several lazier options however. I could use gmp-ecm to do the trial factoring ("-t trial_cutoff"). Or, probably better, I could let yafu do a pollard rho right after the trial factoring. That would probably make a trial_cutoff of 1e8 really suboptimal and I could get away with not doing anything about the trial factoring. Yafu already does the rho, but after the ecm phase for bigger numbers which is presumably not optimal. Thoughts?

Yafu and gmp-ecm can both trial divide to user specified limits, but using those programs with high bounds would get expensive because the primes would need to be regenerated each time, even though it is fast. Yafu takes ~0.2 seconds to get all the primes up to 1e8.

That said, I definately don't think trial factoring to 1e8 is optimal. This is what Rho is for - it is supurb at pulling 6 to 9 digit factors in tens of milliseconds; much faster than you could do by trial division. I think Rho should be used right after trial division to low bounds (1e4).


- ben.

Last fiddled with by bsquared on 2009-03-24 at 13:23 Reason: checked soe speed... faster than I thought
bsquared is offline   Reply With Quote
Old 2009-03-24, 17:06   #52
Phil MjX
 
Phil MjX's Avatar
 
Sep 2004

5×37 Posts
Default

Quote:
Originally Posted by mklasson View Post
Well, it sure isn't a feature.

Sounds very odd though. You're basically saying it always crashes at index 2924 for you regardless of sequence? Could you send me the elf file or attach it here? I just tried a sequence with 2931 lines (biggest I could find) without any problems.
For sure !

Kind Regards !
Attached Files
File Type: zip alq_5400.zip (201.0 KB, 120 views)
Phil MjX is offline   Reply With Quote
Old 2009-03-24, 17:18   #53
mklasson
 
Feb 2004

2·3·43 Posts
Default

Ah, the problem is that the 2924 line has no space between "*" and the cofactor. Even so, it certainly isn't polite to crash...

Just add a space for now and it'll work ok.

Thanks!
mklasson is offline   Reply With Quote
Old 2009-03-24, 17:33   #54
mklasson
 
Feb 2004

1000000102 Posts
Default

Quote:
Originally Posted by bsquared View Post
That said, I definately don't think trial factoring to 1e8 is optimal. This is what Rho is for - it is supurb at pulling 6 to 9 digit factors in tens of milliseconds; much faster than you could do by trial division. I think Rho should be used right after trial division to low bounds (1e4).
This sounds good to me. I tried doing a "yafu rho(n)" separately before the ecm phase but the overhead with log parsing and whatnot resulted in a pretty dissatisfying performance. I've put together an internal rho now though which saves some time (and gives me some fun ).

Curiously, the original Floyd cycle finder yields better speed than the Brent version when I benchmark on real sequence data. "In the lab" Brent seems to perform significantly faster though... I've probably just overlooked something.
mklasson is offline   Reply With Quote
Old 2009-03-24, 17:49   #55
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by mklasson View Post
Something like
Code:
 1445 . c127 = 1684219780053232790182532264150037585657262227235724020539452224672674641583964846829593256612940760791424573187987177454181744 = 2^4 * ...
on the screen? I could certainly do that.
Perfect.
mdettweiler is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Resuming aliqueit johnadam74 Aliquot Sequences 4 2016-03-28 12:32
Apparent aliqueit issue with specifying factors pakaran Aliquot Sequences 2 2015-09-12 23:10
Using Several Instances of Aliqueit for a large gnfs job EdH Aliquot Sequences 6 2011-12-13 18:58
Setting up aliqueit science_man_88 Aliquot Sequences 185 2011-11-08 12:18
Tried out aliqueit.exe: ggnfs failing Greebley Aliquot Sequences 35 2010-02-13 15:23

All times are UTC. The time now is 00:25.

Sun Sep 20 00:25:33 UTC 2020 up 9 days, 21:36, 0 users, load averages: 1.41, 1.66, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.