Re: polredabs() suggestion

[Igor Schein <igor@txc.com>]

On Mon, Apr 28, 2003 at 04:26:01PM +0200, Karim BELABAS wrote:
> On Mon, 28 Apr 2003, Igor Schein wrote:
> > I was thinking, maybe it's a good idea to restart smallvectors() with
> > a lower bound once a better generator is found, to shorten the sorting
> > stage.
> 
> The current algorithm does this. Anytime a better generator is found, the bound
> is updated, pruning the search tree.

Then I don't understand the following behavior ( snapshot of a
polredabs() running I happen to be running right now, at \g5 ):

[snip]
sorting...
  generator: x^72 - 584*x^70 + 159180*x^68 - 26966352*x^66 + 5280*x^65 + 3189879422*x^64 - 1740864*x^63 - 280623705760*x^62 + 250721856*x^61 + 19093602177160*x^60 - 19990295328*x^59 - 1031609831824768*x^58 + 849521263520*x^57 + 45092358862867350*x^56 - 3222480247936*x^55 - 1616410863779765552*x^54 - 2133312049218432*x^53 + 47999559997060678976*x^52 + 163965317972004320*x^51 - 1189654185400390906016*x^50 - 7418311578584297760*x^49 + 24746685586836557455808*x^48 + 241248303190536627136*x^47 - 433785852780082474413664*x^46 - 6019063464003165611456*x^45 + 6425471238341988305952568*x^44 + 118811656491585385935904*x^43 - 80568172219702408319488640*x^42 - 1887734746778936505415328*x^41 + 855891958952542840784496841*x^40 + 24400966737352621678517248*x^39 - 7703551679987665016068010376*x^38 - 258437336522034988891026432*x^37 + 58705061255744272131376885364*x^36 + 2254519720364219639502725664*x^35 - 378227994069993409771019886352*x^34 - 16269709328815475411717755264*x^33 + 2055822777880105212009902127434*x^32 + 97522135472078083378101465600*x^31 - 9399164929902768041614024205632*x^30 - 487566570016682498580031479296*x^29 + 36008100951466483107464939423200*x^28 + 2041576297160724487330176971264*x^27 - 115030321174460095558641912027520*x^26 - 7183465261485506215451426090240*x^25 + 304573241997617367757170650780296*x^24 + 21259704283125372052536524474368*x^23 - 663371124016173404299467804910016*x^22 - 52746956244133108935636234276864*x^21 + 1177352455014408329513943323895264*x^20 + 108707501669527805238060748510464*x^19 - 1682578877269181011714546711270784*x^18 - 183192441088583714128192219273728*x^17 + 1907039149573880801507997111607504*x^16 + 246922011273477927019128986151936*x^15 - 1680495570565998784912158895220480*x^14 - 258807485341525254851133499251712*x^13 + 1121055926222777339130952176574464*x^12 + 203623285439920130174710074496512*x^11 - 545491260970993822181189849331200*x^10 - 114867052228179705809415255529984*x^9 + 183371995516272194222784690699216*x^8 + 43564477500014593636687552806912*x^7 - 39138492284417678016657885462656*x^6 - 10038783094614324405268945330176*x^5 + 4602497843036743161287111954240*x^4 + 1161404403112777896096694387200*x^3 - 234163125180634706701086673152*x^2 - 39726828431429449637184043008*x + 5979359146064140159932558368
sorting...
  generator: x^72 - 584*x^70 + 159180*x^68 - 26966352*x^66 + 5280*x^65 + 3189879422*x^64 - 1740864*x^63 - 280623705760*x^62 + 250721856*x^61 + 19093602177160*x^60 - 19990295328*x^59 - 1031609831824768*x^58 + 849521263520*x^57 + 45092358862867350*x^56 - 3222480247936*x^55 - 1616410863779765552*x^54 - 2133312049218432*x^53 + 47999559997060678976*x^52 + 163965317972004320*x^51 - 1189654185400390906016*x^50 - 7418311578584297760*x^49 + 24746685586836557455808*x^48 + 241248303190536627136*x^47 - 433785852780082474413664*x^46 - 6019063464003165611456*x^45 + 6425471238341988305952568*x^44 + 118811656491585385935904*x^43 - 80568172219702408319488640*x^42 - 1887734746778936505415328*x^41 + 855891958952542840784496841*x^40 + 24400966737352621678517248*x^39 - 7703551679987665016068010376*x^38 - 258437336522034988891026432*x^37 + 58705061255744272131376885364*x^36 + 2254519720364219639502725664*x^35 - 378227994069993409771019886352*x^34 - 16269709328815475411717755264*x^33 + 2055822777880105212009902127434*x^32 + 97522135472078083378101465600*x^31 - 9399164929902768041614024205632*x^30 - 487566570016682498580031479296*x^29 + 36008100951466483107464939423200*x^28 + 2041576297160724487330176971264*x^27 - 115030321174460095558641912027520*x^26 - 7183465261485506215451426090240*x^25 + 304573241997617367757170650780296*x^24 + 21259704283125372052536524474368*x^23 - 663371124016173404299467804910016*x^22 - 52746956244133108935636234276864*x^21 + 1177352455014408329513943323895264*x^20 + 108707501669527805238060748510464*x^19 - 1682578877269181011714546711270784*x^18 - 183192441088583714128192219273728*x^17 + 1907039149573880801507997111607504*x^16 + 246922011273477927019128986151936*x^15 - 1680495570565998784912158895220480*x^14 - 258807485341525254851133499251712*x^13 + 1121055926222777339130952176574464*x^12 + 203623285439920130174710074496512*x^11 - 545491260970993822181189849331200*x^10 - 114867052228179705809415255529984*x^9 + 183371995516272194222784690699216*x^8 + 43564477500014593636687552806912*x^7 - 39138492284417678016657885462656*x^6 - 10038783094614324405268945330176*x^5 + 4602497843036743161287111954240*x^4 + 1161404403112777896096694387200*x^3 - 234163125180634706701086673152*x^2 - 39726828431429449637184043008*x + 5979359146064140159932558368
final sort & check...
  generator: x^72 - 584*x^70 + 159180*x^68 - 26966352*x^66 - 5280*x^65 + 3189879422*x^64 + 1740864*x^63 - 280623705760*x^62 - 250721856*x^61 + 19093602177160*x^60 + 19990295328*x^59 - 1031609831824768*x^58 - 849521263520*x^57 + 45092358862867350*x^56 + 3222480247936*x^55 - 1616410863779765552*x^54 + 2133312049218432*x^53 + 47999559997060678976*x^52 - 163965317972004320*x^51 - 1189654185400390906016*x^50 + 7418311578584297760*x^49 + 24746685586836557455808*x^48 - 241248303190536627136*x^47 - 433785852780082474413664*x^46 + 6019063464003165611456*x^45 + 6425471238341988305952568*x^44 - 118811656491585385935904*x^43 - 80568172219702408319488640*x^42 + 1887734746778936505415328*x^41 + 855891958952542840784496841*x^40 - 24400966737352621678517248*x^39 - 7703551679987665016068010376*x^38 + 258437336522034988891026432*x^37 + 58705061255744272131376885364*x^36 - 2254519720364219639502725664*x^35 - 378227994069993409771019886352*x^34 + 16269709328815475411717755264*x^33 + 2055822777880105212009902127434*x^32 - 97522135472078083378101465600*x^31 - 9399164929902768041614024205632*x^30 + 487566570016682498580031479296*x^29 + 36008100951466483107464939423200*x^28 - 2041576297160724487330176971264*x^27 - 115030321174460095558641912027520*x^26 + 7183465261485506215451426090240*x^25 + 304573241997617367757170650780296*x^24 - 21259704283125372052536524474368*x^23 - 663371124016173404299467804910016*x^22 + 52746956244133108935636234276864*x^21 + 1177352455014408329513943323895264*x^20 - 108707501669527805238060748510464*x^19 - 1682578877269181011714546711270784*x^18 + 183192441088583714128192219273728*x^17 + 1907039149573880801507997111607504*x^16 - 246922011273477927019128986151936*x^15 - 1680495570565998784912158895220480*x^14 + 258807485341525254851133499251712*x^13 + 1121055926222777339130952176574464*x^12 - 203623285439920130174710074496512*x^11 - 545491260970993822181189849331200*x^10 + 114867052228179705809415255529984*x^9 + 183371995516272194222784690699216*x^8 - 43564477500014593636687552806912*x^7 - 39138492284417678016657885462656*x^6 + 10038783094614324405268945330176*x^5 + 4602497843036743161287111954240*x^4 - 1161404403112777896096694387200*x^3 - 234163125180634706701086673152*x^2 + 39726828431429449637184043008*x + 5979359146064140159932558368
  generator: x^72 - 584*x^70 + 159180*x^68 - 26966352*x^66 - 5280*x^65 + 3189879422*x^64 + 1740864*x^63 - 280623705760*x^62 - 250721856*x^61 + 19093602177160*x^60 + 19990295328*x^59 - 1031609831824768*x^58 - 849521263520*x^57 + 45092358862867350*x^56 + 3222480247936*x^55 - 1616410863779765552*x^54 + 2133312049218432*x^53 + 47999559997060678976*x^52 - 163965317972004320*x^51 - 1189654185400390906016*x^50 + 7418311578584297760*x^49 + 24746685586836557455808*x^48 - 241248303190536627136*x^47 - 433785852780082474413664*x^46 + 6019063464003165611456*x^45 + 6425471238341988305952568*x^44 - 118811656491585385935904*x^43 - 80568172219702408319488640*x^42 + 1887734746778936505415328*x^41 + 855891958952542840784496841*x^40 - 24400966737352621678517248*x^39 - 7703551679987665016068010376*x^38 + 258437336522034988891026432*x^37 + 58705061255744272131376885364*x^36 - 2254519720364219639502725664*x^35 - 378227994069993409771019886352*x^34 + 16269709328815475411717755264*x^33 + 2055822777880105212009902127434*x^32 - 97522135472078083378101465600*x^31 - 9399164929902768041614024205632*x^30 + 487566570016682498580031479296*x^29 + 36008100951466483107464939423200*x^28 - 2041576297160724487330176971264*x^27 - 115030321174460095558641912027520*x^26 + 7183465261485506215451426090240*x^25 + 304573241997617367757170650780296*x^24 - 21259704283125372052536524474368*x^23 - 663371124016173404299467804910016*x^22 + 52746956244133108935636234276864*x^21 + 1177352455014408329513943323895264*x^20 - 108707501669527805238060748510464*x^19 - 1682578877269181011714546711270784*x^18 + 183192441088583714128192219273728*x^17 + 1907039149573880801507997111607504*x^16 - 246922011273477927019128986151936*x^15 - 1680495570565998784912158895220480*x^14 + 258807485341525254851133499251712*x^13 + 1121055926222777339130952176574464*x^12 - 203623285439920130174710074496512*x^11 - 545491260970993822181189849331200*x^10 + 114867052228179705809415255529984*x^9 + 183371995516272194222784690699216*x^8 - 43564477500014593636687552806912*x^7 - 39138492284417678016657885462656*x^6 + 10038783094614324405268945330176*x^5 + 4602497843036743161287111954240*x^4 - 1161404403112777896096694387200*x^3 - 234163125180634706701086673152*x^2 + 39726828431429449637184043008*x + 5979359146064140159932558368
[snip]

The same generator is output over and over again.  

In other recent examples, I saw cases where several different
generators are output during this stage.   It doesn't make sense if
pruning is done, because the non-optimal ones shouldn't be seen more
than once.

Thanks

Igor