Changeset ea9f7aa in git


Ignore:
Timestamp:
Dec 12, 2006, 4:46:40 PM (17 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
Children:
49c8210a22155cb41cda3570f5ead66a6e09464c
Parents:
0dec467b51a7c120adea4424f2e499a2ec47f618
Message:
*hannes: format


git-svn-id: file:///usr/local/Singular/svn/trunk@9584 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/AtkinsTest.lib

    r0dec46 rea9f7aa  
    11///////////////////////////////////////////////////////////////////////////////
    2 version="$Id: AtkinsTest.lib,v 1.3 2006-12-11 18:51:12 Singular Exp $";
     2version="$Id: AtkinsTest.lib,v 1.4 2006-12-12 15:46:40 Singular Exp $";
    33category="Teaching";
    44info="
    … …  
    1414
    1515PROCEDURES:
    16   new(L,D)                     checks if number D already exists in list L
    17   bubblesort(L)                sorts elements (out of Z) of the list L in decreasing order
    18   disc(N,k)                    generates a sequence of negative discriminants D with |D|<4N, sort in decreasing order
    19   Cornacchia(d,p)              computes solution (x,y) for the Diophantine equation x^2+d*y^2=p with p prime and 0<d<p
     16  new(L,D)        checks if number D already exists in list L
     17  bubblesort(L)   sorts elements (out of Z) of the list L in decreasing order
     18  disc(N,k)       generates a sequence of negative discriminants D with |D|<4N, sort in decreasing order
     19  Cornacchia(d,p) computes solution (x,y) for the Diophantine equation x^2+d*y^2=p with p prime and 0<d<p
    2020  CornacchiaModified(D,p)      computes solution (x,y) for the Diophantine equation x^2+|D|*y^2=4p with p prime
    21   pFactor1(n,B,P)              Pollard's p-factorization
    22   maximum(L)                   computes the maximal number contained in list L
    23   cmod(x,y)                    computes x mod y while working in the complex numbers, e.g. ring C=(complex,30,i),x,dp;
    24   sqr(w,k)                     computes the square root of w
    25   e(z,k)                       computes e^z, i.e. the exponential function of z to the order k
    26   jot(t,k)                     computes the j-invariant of the complex number t
    27   round(r)                     rounds r to the nearest number out of Z
     21  pFactor1(n,B,P) Pollard's p-factorization
     22  maximum(L)      computes the maximal number contained in list L
     23  cmod(x,y)       computes x mod y while working in the complex numbers, e.g. ring C=(complex,30,i),x,dp;
     24  sqr(w,k)        computes the square root of w
     25  e(z,k)          computes e^z, i.e. the exponential function of z to the order k
     26  jot(t,k)        computes the j-invariant of the complex number t
     27  round(r)        rounds r to the nearest number out of Z
    2828  HilbertClassPolynomial(D,k)  computes the monic polynomial of degree h(D) in Z[X] of which jot((D+sqr(D))/2) is a root
    29   RootsModp(p,P)               computes roots of the polynomial P modulo p with p prime and p>=3
    30   w(D)                         computes the number of roots of unity in the quadratic order of discriminant D
    31   Atkin(N,K,B)                 tries to prove that N is prime
     29  RootsModp(p,P)  computes roots of the polynomial P modulo p with p prime and p>=3
     30  w(D)            computes the number of roots of unity in the quadratic order of discriminant D
     31  Atkin(N,K,B)    tries to prove that N is prime
    3232";
    3333
    … …  
    4646"
    4747{
    48       number a=1;                // a=1 bedeutet: D noch nicht in L vorhanden
    49       int i;
    50       for(i=1;i<=size(L);i++)
    51          {
    52            if(D==L[i])
    53               {
    54                 a=-1;            // a=-1 bedeutet: D bereits in L vorhanden
    55                 break;
    56               }
    57          }
    58 
    59       return(a);
     48  number a=1;                // a=1 bedeutet: D noch nicht in L vorhanden
     49  int i;
     50  for(i=1;i<=size(L);i++)
     51  {
     52    if(D==L[i])
     53    {
     54      a=-1;            // a=-1 bedeutet: D bereits in L vorhanden
     55      break;
     56    }
     57  }
     58 return(a);
    6059}
    6160example
    … …  
    6766}
    6867
    69 
    70 
    7168proc bubblesort(list L)
    7269"USAGE: bubblesort(L);
    … …  
    7572"
    7673{
    77       number b;
    78       int n,i,j;
    79       while(j==0)
    80          {
    81            i=i+1;
    82            j=1;
    83            for(n=1;n<=size(L)-i;n++)
    84               {
    85                 if(L[n]<L[n+1])
    86                    {
    87                      b=L[n];
    88                      L[n]=L[n+1];
    89                      L[n+1]=b;
    90                      j=0;
    91                    }
    92               }
    93          }
    94 
    95       return(L);
     74  number b;
     75  int n,i,j;
     76  while(j==0)
     77  {
     78    i=i+1;
     79    j=1;
     80    for(n=1;n<=size(L)-i;n++)
     81    {
     82      if(L[n]<L[n+1])
     83      {
     84        b=L[n];
     85        L[n]=L[n+1];
     86        L[n+1]=b;
     87        j=0;
     88      }
     89    }
     90  }
     91  return(L);
    9692}
    9793example
    … …  
    112108"
    113109{
    114       list L=-3,-4,-7;
    115       number D;
    116       number B;
    117       int a,b;
    118       for(b=0;b<=k;b++)
    119          {
    120            B=b^2;
    121            for(a=int(intPart(B/4))+1;a<=k;a++)
    122               {
    123                 D=-4*a+B;
    124                 if((D<0)&&((D mod 4)!=2)&&((D mod 4)!=3)&&(absValue(D)<4*N)&&(new(L,D)==1))
    125                    {
    126                      L[size(L)+1]=D;
    127                    }
    128               }
    129          }
    130 
    131       L=bubblesort(L);
    132       return(L);
     110  list L=-3,-4,-7;
     111  number D;
     112  number B;
     113  int a,b;
     114  for(b=0;b<=k;b++)
     115  {
     116    B=b^2;
     117    for(a=int(intPart(B/4))+1;a<=k;a++)
     118    {
     119      D=-4*a+B;
     120      if((D<0)&&((D mod 4)!=2)&&((D mod 4)!=3)&&(absValue(D)<4*N)&&(new(L,D)==1))
     121      {
     122        L[size(L)+1]=D;
     123      }
     124    }
     125  }
     126  L=bubblesort(L);
     127  return(L);
    133128}
    134129example
    … …  
    149144"
    150145{
    151 
    152       if((d<0)||(p<d))                                                   // (0)[Test if assumptions well-defined]
    153          {
    154            return(0);
    155            // ERROR("Parameters wrong selected! It has to be 0<d<p!");
    156          }
    157 
    158       else
    159          {
    160            number k,x(0),x(1),a,b,l,r,c,i;
    161            int j;
    162 
    163            k=Jacobi(-d,p);                                               // (1)[Test if residue]
    164            if(k==-1)
    165               {
    166                 return(-1);
    167                 // ERROR("The Diophantine equation has no solution!");
    168               }
    169 
    170            else
    171               {
    172                 x(0)=squareRoot(-d,p);                                   // (2)[Compute square root]
    173                 x(1)=-x(0) mod p;
    174                 while(1)
    175                    {
    176                      while((p/2>=x(0))||(p<=x(0)))
    177                         {
    178                           x(0)=x(0)+p;
    179                           if(p<=x(0))
    180                              {
    181                                x(0)=-x(0)+p;
    182                              }
    183                         }
    184 
    185                      a=p;
    186                      b=x(0);
    187                      l=intRoot(p);
    188 
    189                      while(b>l)                                          // (3)[Euclidean algorithm]
    190                         {
    191                           r=a mod b;
    192                           a=b;
    193                           b=r;
    194                         }
    195 
    196                      c=(p-b^2)/d;                                        // (4)[Test solution]
    197                      i=intRoot(c);
    198                      if((((p-b^2) mod d)!=0)||(c!=i^2))
    199                         {
    200                           if(j==1)
    201                              {
    202                                return(-1);
    203                                // ERROR("The Diophantine equation has no solution!");
    204                              }
    205 
    206                           else
    207                              {
    208                                j=j+1;
    209                                x(0)=x(1);
    210                              }
    211                         }
    212 
    213                      else
    214                         {
    215                           list L=b,i;
    216                           return(L);
    217                         }
    218                    }
    219               }
    220          }
     146  if((d<0)||(p<d))                                                   // (0)[Test if assumptions well-defined]
     147  {
     148    return(0);
     149    // ERROR("Parameters wrong selected! It has to be 0<d<p!");
     150  }
     151  else
     152  {
     153    number k,x(0),x(1),a,b,l,r,c,i;
     154    int j;
     155
     156    k=Jacobi(-d,p);                                               // (1)[Test if residue]
     157    if(k==-1)
     158    {
     159      return(-1);
     160      // ERROR("The Diophantine equation has no solution!");
     161    }
     162    else
     163    {
     164      x(0)=squareRoot(-d,p);                                   // (2)[Compute square root]
     165      x(1)=-x(0) mod p;
     166      while(1)
     167      {
     168        while((p/2>=x(0))||(p<=x(0)))
     169        {
     170          x(0)=x(0)+p;
     171          if(p<=x(0))
     172          {
     173            x(0)=-x(0)+p;
     174          }
     175        }
     176
     177        a=p;
     178        b=x(0);
     179        l=intRoot(p);
     180
     181        while(b>l)                                          // (3)[Euclidean algorithm]
     182        {
     183          r=a mod b;
     184          a=b;
     185          b=r;
     186        }
     187
     188        c=(p-b^2)/d;                                        // (4)[Test solution]
     189        i=intRoot(c);
     190        if((((p-b^2) mod d)!=0)||(c!=i^2))
     191        {
     192          if(j==1)
     193          {
     194            return(-1);
     195            // ERROR("The Diophantine equation has no solution!");
     196          }
     197          else
     198          {
     199            j=j+1;
     200            x(0)=x(1);
     201          }
     202        }
     203        else
     204        {
     205          list L=b,i;
     206          return(L);
     207        }
     208      }
     209    }
     210  }
    221211}
    222212example
    … …  
    237227"
    238228{
    239 
    240229      if((D>=0)||((D mod 4)==2)||((D mod 4)==3)||(absValue(D)>=4*p))            // (0)[Test if assumptions well-defined]
    241230         {
Note: See TracChangeset for help on using the changeset viewer.