Re: the minimal polynomial over the composite field

[macsyma <macsyma@yahoo.co.jp>]

----- Original Message -----
> From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
> To: pari-users@pari.math.u-bordeaux.fr
> Cc: 
> Date: 2019/10/3, Thu 18:01
> Subject: Re: the minimal polynomial over the composite field
> 
> On Wed, Oct 02, 2019 at 09:57:24PM +0200, Bill Allombert wrote:
>> On Mon, Sep 02, 2019 at 07:04:50PM +0900, macsyma wrote:
>> > Thank you for the new function.
>> > I've tried it with some examples,
>> > unfortunately, it doesn't seem to speed up my code at the moment
>> > so I look forward to future progress.
>> 
>> I have just made a new version which is faster.
>> Now
>> ? G=galoissplittinginit(x^17-2);
>> ? ##
>>   ***  last result computed in 7,913 ms.
>> and
>> ? P=x^17-2;Q=nfsplitting(P,17*16);nfisincl(P,Q);
>> ? ##
>>   ***  last result computed in 4,769 ms.
> 
> This version was lackig one improvement, so I updated again.
> For the new version:
> 
> ? G=galoissplittinginit(x^17-2);
> ? ##
>   ***  last result computed in 7,552 ms.
> ? P=x^17-2;Q=nfsplitting(P,17*16);nfisincl(P,Q);
> ? ##
>   ***  last result computed in 4,433 ms.

Thank you so much for the high-speed new version.

/* example.1 */
for(n=2,25,t=getwalltime();nfsplitting(f=x^n-2,,1);printf([n,getwalltime()-t]));

/* using previous version (pari-bill-nfsplitting-3d153e5) */
[2,1][3,3][4,10][5,15][6,14][7,25][8,10][9,42]
[10,49][11,419][12,99][13,1304][14,415][15,770][16,188]
[17,21814][18,1336][19,45510][20,5567][21,15341][22,15270]
[23,253108][24,775][25,237403]
time = 9min, 58,627 ms.

/* using new version (pari-bill-nfsplitting-dcd5add) */
[2,1][3,4][4,10][5,11][6,11][7,27][8,10][9,39]
[10,44][11,225][12,80][13,448][14,270][15,407][16,178]
[17,3061][18,745][19,4821][20,2113][21,3202][22,3930]
[23,14542][24,423][25,17174]
time = 51,676 ms.

/* example.2 */
for(n=2,25,t=getwalltime();galoissplittinginit(x^n-2);printf([n,getwalltime()-t]));

/* using previous version (pari-bill-nfsplitting-3d153e5) */
[2,1][3,7][4,15][5,19][6,12][7,51][8,13][9,69]
[10,61][11,604][12,123][13,1747][14,516][15,951][16,232]
[17,24853][18,1543][19,51651][20,6207][21,17008][22,16886]
[23,289139][24,876][25,261634]
time = 11min, 13,605 ms.

/* using new version (pari-bill-nfsplitting-dcd5add) */
[2,1][3,5][4,11][5,20][6,7][7,45][8,14][9,74]
[10,61][11,411][12,105][13,963][14,388][15,601][16,224]
[17,5597][18,960][19,10062][20,2725][21,4772][22,5474]
[23,44817][24,525][25,36173]
time = 1min, 53,714 ms.

/* example.3 */
/* my code of the representation of the roots of x^n-2 by radicals, for n=2,...,25 */

/* using previous version (pari-bill-nfsplitting-3d153e5) */
Evaluation took 3.9150 seconds (103.1630 elapsed) using 1641.008 MB.

/* using new version (pari-bill-nfsplitting-dcd5add) */
Evaluation took 3.9280 seconds (92.6980 elapsed) using 1640.936 MB.

macsyma