Bug #1719
FactorINT has got worse
Description
The following test case now works definitely worse: it does not find all factors even with a time limit of 500s
/**/ N := 733570152518245585572373250756625559113448134660198602303761161115768747640039790717209417626237639378612023600490998560722366656257767282271308180638747136088764270749773654824484097677309351264928310667618996967019071560568831505591299639667359324551823276389297210040085671683356842319268396798510128707839918660731651742944976182635483631384847979486107394446898018107511016560910005596514601338985074510750215438930245087413050220796147701159726256814712012430345949169082884990882874530827566925946130804418075993039636875871360592392749067729886377741458157850134121950567909549916726565397848350058686540214069105764188760584468853383349892739951103124613301580381750725368069448730717900262503172080923537952743527354828006932763006833830058133849992482291591524548614013950525960214987678697268976937102229896196592235700018104635466880427783347121785745984684523358075173076499827180279652949273573698343711529875229825990875365483702750885670859290649584291883576700534135208017967703488280321905547261081835293870066770359958302581979227942835018238328109584924539289677754705385683050233697765599283208166228744877599997885044727054894989397250197864060072413943048908893072281613818181255952564156500184276607648975880782796071856116659; /**/ facs := FactorINT_TimeOut(N,150); /**/ len(facs.factors); --> 164 or 146?? /**/ TimeFrom(0); --> 203.014 /**/ indent(facs);
Fix it!
Related issues
History
#1
Updated by John Abbott over 1 year ago
Updated by With the current impl on 127 factors are found, and they are all small enough to be split easily.
So why weren't they split?
I guess there should be a priority of composites still to factorize, and the remaining time should
"shared" among them (somehow). The current recursive approach could soak up all the time just
trying to spit one factor [which has supposedly been checked to be non prime]
Too late/tired to investigate now.
#2
Updated by John Abbott over 1 year ago
- Related to Feature #1718: FactorINT with time-out added
#3
Updated by John Abbott over 1 year ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
I now have a simpler case:
N:=247791785944581739801301490935121039934579377242586087632913196488565691086949771704341604678953965644848613255206002904696132271823245244297341106055140426571436941804751621633237213366590207876556514469529961738642003205240903166519898987791573464612160928820311447243577699504315279381041379805020577653410356076373452127317542712872617850416789935682534600486610638479668107575729740859589136302820960943572348440781583273904876520605461745834958204698846679168105326967615596337173883897725500982366670904945336447236139484335909224625975210006424970052329750496284041467999849356023268907689315561144393069893490828305045902428170300866707044870638391726523593031045407984564584577896295982661600067137457974854069039430186771628107;
It seems that FactorINT is unable to factorize it, but FactorINT_PollardRho(N,1000000) finds a factor instantly.
I wonder what is going on.
#4
Updated by John Abbott over 1 year ago
- Assignee set to John Abbott
- % Done changed from 10 to 50
It'd be nice to blame someone else for the "poorly organized" code...
Now it seems to work better. But the revised code still need tidying!
Maybe I'll check in soon what I have... and tidy it later (hah!)
#5
Updated by John Abbott over 1 year ago
On some inputs which have many small factors, the code spends much more time inside IsProbPrime than actually computing factors.
Need a strategy to test for primality not too often...
#6
Updated by John Abbott about 1 year ago
- Status changed from In Progress to Feedback
- Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880
- % Done changed from 50 to 90
The current code works a lot better.
I suppose I should find time sooner or later to implement the idea in comment 5 (but that is low priority for CoCoALib).
#7
Updated by John Abbott 5 days ago
- Status changed from Feedback to Closed
- % Done changed from 90 to 100
- Estimated time set to 4.25 h
The current impl is good enough. It behaves well enough on the two "big" test examples listed above. If we really want to offer good integer factorization, we should use an external library. But we should do that only if there is genuine demand... there are other more pressing issues!
Closing!