Root cellar
 

[QUOTE=jasonp;172704]
v1.42 will have a much more sophisticated rootfinder.[/QUOTE]

Are you implementing Jenkins-Traub?

Brian Gladman has kindly produced his own complex- and real-valued Jenkins-Traub rootfinders by converting the original Fortran to C and applying heavy cleanup. I'm in the process of applying much more cleanup to the complex version, so that it can find roots to (at most) double precision. Then I'll switch to Laguerre's or Newton's method to get down to quad-precision accuracy. J-T is not fooled by multiple roots or multiple roots with the same magnitude, so hopefully these annoying crashes will go away.

is there a vague ETA for 1.42(when is version 2 coming along)?

Real life is intervening again, no idea. Sheesh, didn't I just pay bills [i]last[/i] month?

"Yes, but what have you done for us [I]lately[/I]!"
:popcorn:

[QUOTE=Batalov;172876]"Yes, but what have you done for us [I]lately[/I]!"
:popcorn:[/QUOTE]

That's not fair! :smile::smile:

Luigi

For the record, I was referring to the need to have a day job to pay bills that look familiar :)

SQRT failed
 

I just got a "Algebraic Square root failed" error in the first dependency of a c102 GNFS factorization. The second one succeeded:

[code]Sun May 17 14:35:25 2009 Msieve v. 1.41
Sun May 17 14:35:25 2009 random seeds: e7b39168 68c42838
Sun May 17 14:35:25 2009 factoring 853929635599422763695461633612823384788514896160663790367275722570272427322586836076040691299795492743 (102 digits)
Sun May 17 14:35:27 2009 searching for 15-digit factors
Sun May 17 14:35:29 2009 commencing number field sieve (102-digit input)
Sun May 17 14:35:29 2009 R0: -49477531833368853558
Sun May 17 14:35:29 2009 R1: 35633560421
Sun May 17 14:35:29 2009 A0: -225941343291346407191225
Sun May 17 14:35:29 2009 A1: -135008887690178691988
Sun May 17 14:35:29 2009 A2: 17514637356596807
Sun May 17 14:35:29 2009 A3: 2916207462008
Sun May 17 14:35:29 2009 A4: -97016682
Sun May 17 14:35:29 2009 A5: 2880
Sun May 17 14:35:29 2009 skew 11007.57, size 1.096739e-009, alpha -5.321200, combined = 2.784860e-009
Sun May 17 14:35:29 2009
Sun May 17 14:35:29 2009 commencing relation filtering
Sun May 17 14:35:29 2009 commencing duplicate removal, pass 1
Sun May 17 14:36:59 2009 found 292946 hash collisions in 4845545 relations
Sun May 17 14:37:36 2009 added 649 free relations
Sun May 17 14:37:36 2009 commencing duplicate removal, pass 2
Sun May 17 14:37:53 2009 found 263960 duplicates and 4582234 unique relations
Sun May 17 14:37:53 2009 memory use: 40.3 MB
Sun May 17 14:37:53 2009 reading rational ideals above 1769472
Sun May 17 14:37:53 2009 reading algebraic ideals above 1769472
Sun May 17 14:37:53 2009 commencing singleton removal, pass 1
Sun May 17 14:39:23 2009 relations with 0 large ideals: 68426
Sun May 17 14:39:23 2009 relations with 1 large ideals: 520708
Sun May 17 14:39:23 2009 relations with 2 large ideals: 1471072
Sun May 17 14:39:23 2009 relations with 3 large ideals: 1745334
Sun May 17 14:39:23 2009 relations with 4 large ideals: 722405
Sun May 17 14:39:23 2009 relations with 5 large ideals: 23413
Sun May 17 14:39:23 2009 relations with 6 large ideals: 30876
Sun May 17 14:39:23 2009 relations with 7+ large ideals: 0
Sun May 17 14:39:23 2009 4582234 relations and about 4482739 large ideals
Sun May 17 14:39:23 2009 commencing singleton removal, pass 2
Sun May 17 14:40:54 2009 found 1995969 singletons
Sun May 17 14:40:54 2009 current dataset: 2586265 relations and about 2098891 large ideals
Sun May 17 14:40:54 2009 commencing singleton removal, pass 3
Sun May 17 14:41:47 2009 found 436832 singletons
Sun May 17 14:41:47 2009 current dataset: 2149433 relations and about 1632475 large ideals
Sun May 17 14:41:47 2009 commencing singleton removal, final pass
Sun May 17 14:42:35 2009 memory use: 35.5 MB
Sun May 17 14:42:35 2009 commencing in-memory singleton removal
Sun May 17 14:42:35 2009 begin with 2149433 relations and 1678596

... <some of the filtering snipped>

Sun May 17 14:43:43 2009 reduce to 797782 relations and 649522 ideals in 6 passes
Sun May 17 14:43:43 2009 max relations containing the same ideal: 21
Sun May 17 14:43:43 2009 relations with 0 large ideals: 11842
Sun May 17 14:43:43 2009 relations with 1 large ideals: 80737
Sun May 17 14:43:43 2009 relations with 2 large ideals: 208309
Sun May 17 14:43:43 2009 relations with 3 large ideals: 263248
Sun May 17 14:43:43 2009 relations with 4 large ideals: 169083
Sun May 17 14:43:43 2009 relations with 5 large ideals: 54397
Sun May 17 14:43:43 2009 relations with 6 large ideals: 9509
Sun May 17 14:43:43 2009 relations with 7+ large ideals: 657
Sun May 17 14:43:43 2009 commencing 2-way merge
Sun May 17 14:43:44 2009 reduce to 493899 relation sets and 345639 unique ideals
Sun May 17 14:43:44 2009 commencing full merge
Sun May 17 14:43:52 2009 memory use: 25.2 MB
Sun May 17 14:43:52 2009 found 230803 cycles, need 211839
Sun May 17 14:43:52 2009 weight of 211839 cycles is about 14921060 (70.44/cycle)
Sun May 17 14:43:52 2009 distribution of cycle lengths:
Sun May 17 14:43:52 2009 1 relations: 20437
Sun May 17 14:43:52 2009 2 relations: 19168
Sun May 17 14:43:52 2009 3 relations: 19961
Sun May 17 14:43:52 2009 4 relations: 19394
Sun May 17 14:43:52 2009 5 relations: 18886
Sun May 17 14:43:52 2009 6 relations: 17704
Sun May 17 14:43:52 2009 7 relations: 16051
Sun May 17 14:43:52 2009 8 relations: 14779
Sun May 17 14:43:52 2009 9 relations: 12996
Sun May 17 14:43:52 2009 10+ relations: 52463
Sun May 17 14:43:52 2009 heaviest cycle: 18 relations
Sun May 17 14:43:52 2009 commencing cycle optimization
Sun May 17 14:43:53 2009 start with 1391589 relations
Sun May 17 14:43:59 2009 pruned 48328 relations
Sun May 17 14:43:59 2009 memory use: 34.9 MB
Sun May 17 14:43:59 2009 distribution of cycle lengths:
Sun May 17 14:43:59 2009 1 relations: 20437
Sun May 17 14:43:59 2009 2 relations: 19759
Sun May 17 14:43:59 2009 3 relations: 20794
Sun May 17 14:43:59 2009 4 relations: 20259
Sun May 17 14:43:59 2009 5 relations: 19717
Sun May 17 14:43:59 2009 6 relations: 18404
Sun May 17 14:43:59 2009 7 relations: 16553
Sun May 17 14:43:59 2009 8 relations: 15202
Sun May 17 14:43:59 2009 9 relations: 13248
Sun May 17 14:43:59 2009 10+ relations: 47466
Sun May 17 14:43:59 2009 heaviest cycle: 18 relations
Sun May 17 14:44:00 2009 RelProcTime: 514
Sun May 17 14:44:00 2009 elapsed time 00:08:35

Sun May 17 14:44:00 2009 Msieve v. 1.41
Sun May 17 14:44:00 2009 random seeds: 7feb18a8 0850d81a

<poly snipped>

Sun May 17 14:44:04 2009 commencing linear algebra
Sun May 17 14:44:05 2009 read 211839 cycles
Sun May 17 14:44:05 2009 cycles contain 706357 unique relations
Sun May 17 14:44:22 2009 read 706357 relations
Sun May 17 14:44:23 2009 using 20 quadratic characters above 67105692
Sun May 17 14:44:33 2009 building initial matrix
Sun May 17 14:44:49 2009 memory use: 77.0 MB
Sun May 17 14:44:49 2009 read 211839 cycles
Sun May 17 14:44:50 2009 matrix is 211645 x 211839 (59.3 MB) with weight 19909678 (93.98/col)
Sun May 17 14:44:50 2009 sparse part has weight 14066502 (66.40/col)
Sun May 17 14:44:56 2009 filtering completed in 2 passes
Sun May 17 14:44:56 2009 matrix is 210938 x 211132 (59.2 MB) with weight 19864437 (94.09/col)
Sun May 17 14:44:56 2009 sparse part has weight 14041674 (66.51/col)
Sun May 17 14:45:01 2009 read 211132 cycles
Sun May 17 14:45:12 2009 matrix is 210938 x 211132 (59.2 MB) with weight 19864437 (94.09/col)
Sun May 17 14:45:12 2009 sparse part has weight 14041674 (66.51/col)
Sun May 17 14:45:12 2009 saving the first 48 matrix rows for later
Sun May 17 14:45:13 2009 matrix is 210890 x 211132 (56.9 MB) with weight 15716425 (74.44/col)
Sun May 17 14:45:13 2009 sparse part has weight 13660065 (64.70/col)
Sun May 17 14:45:13 2009 matrix includes 64 packed rows
Sun May 17 14:45:13 2009 using block size 65536 for processor cache size 2048 kB
Sun May 17 14:45:16 2009 commencing Lanczos iteration (2 threads)
Sun May 17 14:45:16 2009 memory use: 56.6 MB
Sun May 17 14:55:59 2009 lanczos halted after 3336 iterations (dim = 210889)
Sun May 17 14:56:00 2009 recovered 29 nontrivial dependencies
Sun May 17 14:56:00 2009 BLanczosTime: 716
Sun May 17 14:56:00 2009 elapsed time 00:12:00
Sun May 17 14:56:00 2009
Sun May 17 14:56:00 2009
Sun May 17 14:56:00 2009 Msieve v. 1.41
Sun May 17 14:56:00 2009 random seeds: 3e0dbac8 fdda6c41

<poly snipped>

Sun May 17 14:56:04 2009 commencing square root phase
Sun May 17 14:56:04 2009 reading relations for dependency 1
Sun May 17 14:56:05 2009 read 105164 cycles
Sun May 17 14:56:05 2009 cycles contain 437700 unique relations
Sun May 17 14:56:18 2009 read 437700 relations
Sun May 17 14:56:22 2009 multiplying 351452 relations
Sun May 17 14:58:06 2009 multiply complete, coefficients have about 13.76 million bits
Sun May 17 14:58:08 2009 initial square root is modulo 80180141
[B][COLOR="Red"]Sun May 17 15:00:32 2009 Newton iteration failed to converge
Sun May 17 15:00:32 2009 algebraic square root failed[/COLOR][/B]
Sun May 17 15:00:32 2009 reading relations for dependency 2
Sun May 17 15:00:32 2009 read 105233 cycles
Sun May 17 15:00:33 2009 cycles contain 438941 unique relations
Sun May 17 15:00:45 2009 read 438941 relations
Sun May 17 15:00:49 2009 multiplying 352772 relations
Sun May 17 15:02:25 2009 multiply complete, coefficients have about 13.81 million bits
Sun May 17 15:02:26 2009 initial square root is modulo 86059027
Sun May 17 15:04:50 2009 sqrtTime: 526
Sun May 17 15:04:50 2009 prp42 factor: 197289354911829793712749335520867417551553
Sun May 17 15:04:50 2009 prp61 factor: 4328310749361265920008552701826983603115943218253862379228231
Sun May 17 15:04:50 2009 elapsed time 00:08:50[/code]

That's very unusual, and may be a bug somewhere in the multiple-precision math library used. I probably won't be able to reproduce it unless I have your relations, which may be too much data transfer for a C102.

[quote=jasonp;174563]That's very unusual, and may be a bug somewhere in the multiple-precision math library used. I probably won't be able to reproduce it unless I have your relations, which may be too much data transfer for a C102.[/quote]
i saw that as well recently with 1.41
it isnt ridiculously rare

[QUOTE=jasonp;174563]That's very unusual, and may be a bug somewhere in the multiple-precision math library used. I probably won't be able to reproduce it unless I have your relations, which may be too much data transfer for a C102.[/QUOTE]

Don't you have a possibility to chose fixed "random seeds" for bughunting? I don't have the relations anymore, as I have used aliqueit.exe for running an aliquot sequence and this program automatically deletes the relations for disk space reasons when it has finished the factorization.

I had used facmsieve.pl for this factorization, maybe you can reproduce the sieving with the parameters used by this script?