Phil Carmody on Tue, 13 May 2008 18:34:25 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

bnfinit perhaps getting stuck?


I can't say I know what is going on in the internals of bnfinit, but after having a calculation need a brutal ^C-ing after running for over a week, I decided to re-run it  with debugging on.

"""
? \g4
   debug = 4
? fx=x^48-4480*x^46+6446166*x^44-4264459596*x^42+1478886437833*x^40-285105080513874*x^38+31889235205373758*x^36-21214\
39237229539886*x^34+85402904661020604132*x^32-2135353095967932952670*x^30+33598928331347094937681*x^28-32917885141426\
7453674068*x^26+1921830083990594248605887*x^24-6073485443598792677635446*x^22+8678003479406190695431500*x^20-50408809\
45156845853405236*x^18+1107548264142923903525751*x^16-86732115508150902475470*x^14+2990032812785352896663*x^12-456658\
82622132841454*x^10+253846170912137901*x^8-442257995520456*x^6+153587989616*x^4-13500288*x^2+256
%1 = x^48 - 4480*x^46 + 6446166*x^44 - 4264459596*x^42 + 1478886437833*x^40 - 285105080513874*x^38 + 3188923520537375\
8*x^36 - 2121439237229539886*x^34 + 85402904661020604132*x^32 - 2135353095967932952670*x^30 + 33598928331347094937681\
*x^28 - 329178851414267453674068*x^26 + 1921830083990594248605887*x^24 - 6073485443598792677635446*x^22 + 86780034794\
06190695431500*x^20 - 5040880945156845853405236*x^18 + 1107548264142923903525751*x^16 - 86732115508150902475470*x^14 \
+ 2990032812785352896663*x^12 - 45665882622132841454*x^10 + 253846170912137901*x^8 - 442257995520456*x^6 + 1535879896\
16*x^4 - 13500288*x^2 + 256
? allocatemem(450000000)
? k3=bnfinit(fx);
Time setup: 0


... a short while later ...


cglob = 60.
rel = 2475^1 2476^1 2477^1 2478^1 2479^1 2480^1 2481^1 2482^1 2483^1 2484^1 2485^1 2486^1 2487^1 2488^1 2489^1 2490^1\
 2491^1 2492^1 2493^1 2494^1 2495^1 2496^1 2497^1 2498^1 2499^1 2500^1 2501^1 2502^1 2503^1 2504^1 2505^1 2506^1 2507\
^1 2508^1 2509^1 2510^1 2511^1 2512^1 2513^1 2514^1 2515^1 2516^1 2517^1 2518^1 2519^1 2520^1 2521^1 2522^1
cglob = 61.
rel = 2523^1 2524^1 2525^1 2526^1 2527^1 2528^1 2529^1 2530^1 2531^1 2532^1 2533^1 2534^1 2535^1 2536^1 2537^1 2538^1\
 2539^1 2540^1 2541^1 2542^1 2543^1 2544^1 2545^1 2546^1 2547^1 2548^1 2549^1 2550^1 2551^1 2552^1 2553^1 2554^1 2555\
^1 2556^1 2557^1 2558^1 2559^1 2560^1 2561^1 2562^1 2563^1 2564^1 2565^1 2566^1 2567^1 2568^1 2569^1 2570^1

#### Looking for 2622 relations (small norms)

*** Ideal no 2570: [19267, [9264, 1, -2, -3, 1, -2, 0, 6, 7, -5, -3, -3, -8, -1, 2, 4, 0, -2, -3, -5, -2, -3, 1, -1, \
2, 4, 2, -4, 0, 0, -2, 0, 0, 2, 0, 1, 2, -2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0]~, 1, 1]
K2  (28) (23) (14) (1)K3  (14) (8) (4) (1)K4  (10) (3)K5  (7) (5) (1)K6  (6)K7  (5)K8  (4)K9  (4) (1)K10  (3)K11  (3)\
K12  (3) (0)K13  (2)K14  (2)K15  (2)K16  (2)K17  (1)K18  (0)K19  (0)K20  (0)K21  (0)K22 K23 K24 K25 K26 K27 K28 K29 K\
30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2 K3  (0)K4  (0)K5  (0)K6  (1)K7  (0)K8 K9  (0)K10  (2) (1)K11  (1)K12  (1)K13  (1)K14  (1)K15  (0)K16  (1)K17  (0)K\
18  (2)K19  (1)K20  (1)K21  (2)K22  (1)K23  (0) (1)K24  (0) (0)K25 K26 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K3\
8 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
Checking LLL basis...in precision 3
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48


... a long while later (about a day) ...


BOUND = 800
**.**....*..*..**.*.*.*...*....*.**...**.**..**Time for this ideal: 1621

*** Ideal no 1: [2, [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \
0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]~, 1, 8]
K2 K3 K4 K5  (1)K6  (0)K7  (0)K8  (0)K9 K10 K11 K12 K13 K14 K15 K16 K17  (1) (0)K18  (1)K19  (0)K20  (0)K21 K22 K23 K\
24 K25 K26 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2 K3  (0)K4 K5  (0)K6 K7  (0)K8  (1)K9 K10 K11 K12 K13 K14  (1)K15 K16  (1) (0)K17  (1)K18  (0)K19  (2) (1)K20 K21  \
(2)K22  (1) (0)K23  (1) (0)K24  (1) (0)K25 K26 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K4\
4 K45 K46 K47 K48
Checking LLL basis...in precision 3
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
v[1]=192 v[2]=388 v[3]=304.5 v[4]=263.7 v[5]=403.2 v[6]=348.9 v[7]=348.9 v[8]=364.6 v[9]=340.7 v[10]=300.3 v[11]=290.\
1 v[12]=217.6 v[13]=553 v[14]=553 v[15]=458.5 v[16]=458.5 v[17]=454.4 v[18]=434 v[19]=402.4 v[20]=378.9 v[21]=310.8 v\
[22]=366.1 v[23]=308.6 v[24]=294.1 v[25]=324.5 v[26]=243.4 v[27]=264.9 v[28]=198.7 v[29]=229.7 v[30]=180.7 v[31]=185.\
4 v[32]=148 v[33]=138.3 v[34]=193.3 v[35]=193.3 v[36]=174.1 v[37]=168.2 v[38]=174.1 v[39]=168.2 v[40]=151.5 v[41]=151\
.5 v[42]=328 v[43]=246 v[44]=218.7 v[45]=427.4 v[46]=320.6 v[47]=285 v[48]=1051
BOUND = 800
*..**.*.*....**.*..*...*.**...*.**...**.**...**Time for this ideal: 1612

Time small norm relations: 0
  small norms gave 2451 relations.
  nb. fact./nb. small norm = 2390/1164205 = 0.002

#### Looking for random relations
Computing powers for subFB: Vecsmall([147, 148, 149])
K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2  (24) (16) (11) (2)K3  (13) (6)K4  (11) (1)K5  (7) (3) (1)K6  (5) (1)K7  (4) (1)K8  (2) (0) (0)K9  (2)K10  (2)K11 \
 (1) (0) (0)K12  (2) (0)K13  (1) (1) (0)K14  (1) (0)K15  (0) (1)K16  (0)K17  (0)K18  (0)K19  (1)K20  (1)K21  (1)K22  \
(0) (0)K23  (0) (0)K24  (0)K25 K26 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K4\
7 K48
Checking LLL basis...in precision 3
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
IFAC: cracking composite
        217790123
IFAC: checking for pure square
IFAC: checking for odd power
  *** bnfinit: Warning: IFAC: untested integer declared prime.
IFAC: prime 217790123
        appears with exponent = 1
IFAC: main loop: this was the last factor
IFAC: found 1 large prime (power) factor.
 2K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2  (11) (4)K3  (8)K4  (7) (1)K5  (3)K6  (3)K7  (3)K8  (1)K9  (1)K10  (1)K11  (1)K12  (1)K13  (0)K14  (0)K15 K16 K17 \
K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K\
47  (29) (0)K48  (53) (48) (44) (42) (37) (20)
Checking LLL basis...in precision 3
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
IFAC: cracking composite
        225520585627


... etc. etc. for a short while ...


K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
IFAC: cracking composite
        560742642625307459112461
IFAC: checking for pure square
IFAC: checking for odd power
  *** bnfinit: Warning: IFAC: untested integer declared prime.
IFAC: prime 560742642625307459112461
        appears with exponent = 1
IFAC: main loop: this was the last factor
IFAC: found 1 large prime (power) factor.
 15K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2  (11) (6) (1)K3  (5)K4  (5) (2)K5  (3)K6  (3)K7  (3)K8  (1)K9  (0)K10  (0)K11  (1)K12  (1)K13  (0)K14  (0)K15 K16 \
K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K\
46 K47 K48
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 6
count_max = 16
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48  (155) (149) (147) (145) (141) (132) (129) (126) (122)\
 (116) (113) (107) (103) (98) (95) (93) (91) (88) (86) (83) (81) (77) (74) (71) (67) (64) (60) (56) (54) (52) (34) (3\
3) (29) (22) (17) (11) (9) (4) (0)
Checking LLL basis...in precision 4
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
IFAC: cracking composite
        9955455930650259994021
IFAC: checking for pure square
IFAC: checking for odd power
  *** bnfinit: Warning: IFAC: untested integer declared prime.
IFAC: prime 9955455930650259994021
        appears with exponent = 1
IFAC: main loop: this was the last factor
IFAC: found 1 large prime (power) factor.
 16
Time powFBgen: 214554

(more relations needed: 171)
(1)K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2  (13) (3) (0)K3  (4) (1)K4  (6) (3)K5  (6)K6  (4) (2)K7  (5)K8  (3)K9  (2)K10  (1)K11  (2) (1)K12  (3)K13 K14 K15 \
K16 K17  (2) (0)K18  (2) (0)K19  (2)K20  (2)K21  (2)K22  (2) (1)K23  (1) (0)K24  (1) (0)K25 K26 K27 K28 K29 K30  (0)K\
31 K32 K33 K34 K35  (0)K36 K37 K38 K39 K40 K41 K42 K43  (0)K44  (0)K45  (5) (2)K46  (6)K47  (6) (2) (0)K48
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 6
count_max = 16
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48  (288) (282) (277) (273) (267) (262) (247) (238) (234)\
 (229) (222) (218) (211) (206) (203) (197) (194) (190) (188) (182) (180) (172) (166) (159) (155) (152) (147) (142) (1\
31) (128) (123) (118) (113) (110) (103) (96) (94) (88) (85) (83) (80) (72) (69) (51) (48) (39) (32) (19) (11) (9) (4)
Checking LLL basis...in precision 5
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
.K2
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 4
count_max = 16
K2 K3  (13) (9) (2)K4  (11)K5  (12) (6)K6  (7) (5) (1)K7  (6) (1)K8  (5) (2)K9  (3) (1) (0)K10  (3) (1) (0)K11  (3)K1\
2  (4) (1) (1) (0)K13  (1)K14 K15 K16  (1)K17  (3)K18  (2)K19  (2)K20  (2) (0)K21  (2)K22  (3)K23  (3)K24  (2)K25  (0\
) (0)K26  (0)K27  (0)K28  (0)K29  (0)K30  (1)K31  (1)K32  (1)K33  (0) (1) (0)K34  (1) (0)K35 K36  (0) (0)K37  (0)K38 \
K39 K40 K41  (0)K42 K43 K44  (0)K45  (6)K46  (7)K47  (6) (2) (0) (0)K48
  *** bnfinit: Warning: increasing prec in lllfp (exact); new prec = 6
count_max = 16
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48  (288) (285) (282) (278) (274) (263) (257) (253) (249)\
 (245) (238) (226) (220) (214) (211) (201) (198) (195) (192) (189) (187) (183) (178) (171) (166) (161) (157) (152) (1\
49) (141) (139) (132) (131) (126) (120) (114) (110) (108) (104) (100) (95) (90) (89) (83) (75) (68) (63) (57) (51) (4\
9) (45) (41) (39) (34) (30) (22) (18) (11) (6) (1)
Checking LLL basis...in precision 5
K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 K13 K14 K15 K16 K17 K18 K19 K20 K21 K22 K23 K24 K25 K26 K27 K28 K29 K30 K31 K32 K\
33 K34 K35 K36 K37 K38 K39 K40 K41 K42 K43 K44 K45 K46 K47 K48
.K2


... and apparently it just sits there doing variations on those last few dozen or so lines ...
"""

It's still running, just on the offchance that it kicks into a different phase. (Logs are available on request, they'll be 10MB quite soon, and growing quickly.)

Is the algorithm guaranteed to terminate that phase, do you know, or it it worrying that bnfinit has apparently got stuck in a loop of endless variations that it apparently can't break out of?

Phil
-- 
()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]