mersenneforum.org Aliqueit.exe discussion
 Register FAQ Search Today's Posts Mark Forums Read

2009-03-22, 20:50   #45
mklasson

Feb 2004

2·3·43 Posts

Quote:
 Originally Posted by 10metreh 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.

 2009-03-23, 22:49 #46 Phil MjX     Sep 2004 101110012 Posts 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
2009-03-23, 23:30   #47
mklasson

Feb 2004

2·3·43 Posts

Quote:
 Originally Posted by Phil MjX 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.

 2009-03-24, 06:30 #48 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 3×2,083 Posts 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
2009-03-24, 08:11   #49
axn

Jun 2003

7·11·61 Posts

Quote:
 Originally Posted by mdettweiler 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.

2009-03-24, 11:08   #50
mklasson

Feb 2004

1000000102 Posts

Quote:
 Originally Posted by axn 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 -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.

2009-03-24, 13:18   #51
bsquared

"Ben"
Feb 2007

2×5×7×47 Posts

Quote:
 Originally Posted by mklasson 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

2009-03-24, 17:06   #52
Phil MjX

Sep 2004

5×37 Posts

Quote:
 Originally Posted by mklasson 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
 alq_5400.zip (201.0 KB, 125 views)

 2009-03-24, 17:18 #53 mklasson   Feb 2004 2·3·43 Posts 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!
2009-03-24, 17:33   #54
mklasson

Feb 2004

2·3·43 Posts

Quote:
 Originally Posted by bsquared 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.

2009-03-24, 17:49   #55
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

141518 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post johnadam74 Aliquot Sequences 4 2016-03-28 12:32 pakaran Aliquot Sequences 2 2015-09-12 23:10 EdH Aliquot Sequences 6 2011-12-13 18:58 science_man_88 Aliquot Sequences 185 2011-11-08 12:18 Greebley Aliquot Sequences 35 2010-02-13 15:23

All times are UTC. The time now is 02:43.

Mon Sep 28 02:43:41 UTC 2020 up 17 days, 23:54, 0 users, load averages: 1.19, 1.64, 1.56