Changeset 41ab421 in git


Ignore:
Timestamp:
Sep 13, 2010, 8:34:24 PM (14 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'd25190065115c859833252500a64cfb7b11e3a50')
Children:
2d10dab58ba1fb691c104a56640b19ca02cba241
Parents:
33593c798fdd0477d8edf4b31010084aafd9ce40
Message:
opti. primefactors

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

Legend:

Unmodified
Added
Removed
  • Singular/misc_ip.cc

    r33593c7 r41ab421  
    2424void number2mpz(number n, mpz_t m)
    2525{
    26   if (nlIsZero(n)) mpz_init_set_si(m, 0);
    27   else
    28   {
    29     int nAsInt = nlInt(n, NULL);
    30     if (nAsInt != 0) mpz_init_set_si(m, nAsInt);     /* n fits in an int */
    31     else             mpz_init_set(m, (mpz_ptr)n->z);
    32   }
     26  if (SR_HDL(n) & SR_INT) mpz_init_set_si(m, SR_TO_INT(n));     /* n fits in an int */
     27  else             mpz_init_set(m, (mpz_ptr)n->z);
    3328}
    3429
     
    5853}
    5954
     55void divTimes_ui(mpz_t n, long d, int* times)
     56{
     57  *times = 0;
     58  mpz_t r; mpz_init(r);
     59  mpz_t q; mpz_init(q);
     60  mpz_fdiv_qr_ui(q, r, n, d);
     61  while (mpz_cmp_ui(r, 0) == 0)
     62  {
     63    (*times)++;
     64    mpz_set(n, q);
     65    mpz_fdiv_qr_ui(q, r, n, d);
     66  }
     67  mpz_clear(r);
     68  mpz_clear(q);
     69}
     70
    6071/* returns an object of type lists which contains the entries
    6172   theInts[0..(length-1)] as INT_CMDs */
     
    7182void setListEntry(lists L, int index, mpz_t n)
    7283{ /* assumes n > 0 */
     84  /* try to fit nn into an int: */
     85  if (mpz_size1(n)<=1)
     86  {
     87    int ui=(int)mpz_get_si(n);
     88    if ((((ui<<3)>>3)==ui)
     89    && (mpz_cmp_si(n,(long)ui)==0))
     90    {
     91      L->m[index].rtyp = INT_CMD; L->m[index].data = (void*)ui;
     92      return;
     93    }
     94  }
    7395  number nn = mpz2number(n);
    7496  L->m[index].rtyp = BIGINT_CMD; L->m[index].data = (void*)nn;
     97}
     98
     99void setListEntry_ui(lists L, int index, long ui)
     100{ /* assumes n > 0 */
    75101  /* try to fit nn into an int: */
    76   int nnAsInt = nlInt(nn, NULL);
    77   if (nnAsInt != 0)
    78   {
    79     nlDelete(&nn, NULL);
    80     L->m[index].rtyp = INT_CMD; L->m[index].data = (void*)nnAsInt;
     102  if (((ui<<3)>>3)==ui)
     103  {
     104    L->m[index].rtyp = INT_CMD; L->m[index].data = (void*)ui;
     105  }
     106  else
     107  {
     108    number nn = nlInit(ui,NULL);
     109    L->m[index].rtyp = BIGINT_CMD; L->m[index].data = (void*)nn;
    81110  }
    82111}
     
    152181  int* multiplicities = new int[1000];
    153182
    154   mpz_set_ui(p, 2);
    155   if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(p, b) <= 0))
    156   {
    157     divTimes(nn, p, &tt);
     183  divTimes_ui(nn, 2, &tt);
     184  if (tt > 0)
     185  {
     186    setListEntry_ui(primes, index, 2);
     187    multiplicities[index++] = tt;
     188  }
     189
     190  divTimes_ui(nn, 3, &tt);
     191  if (tt > 0)
     192  {
     193    setListEntry_ui(primes, index, 3);
     194    multiplicities[index++] = tt;
     195  }
     196
     197  unsigned long p_ui=5; add = 2;
     198  mpz_sqrt(sr, nn);
     199  if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
     200  int limit=mpz_get_ui(pb);
     201  if ((limit==0)||(mpz_cmp_ui(pb,limit)!=0)) limit=1<<31;
     202  while (p_ui <=limit)
     203  {
     204    divTimes_ui(nn, p_ui, &tt);
    158205    if (tt > 0)
    159206    {
    160       setListEntry(primes, index, p);
     207      setListEntry_ui(primes, index, p_ui);
    161208      multiplicities[index++] = tt;
    162     }
    163   }
    164 
    165   mpz_set_ui(p, 3);
    166   if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(p, b) <= 0))
    167   {
    168     divTimes(nn, p, &tt);
    169     if (tt > 0)
    170     {
    171       setListEntry(primes, index, p);
    172       multiplicities[index++] = tt;
    173     }
    174   }
    175 
    176   mpz_set_ui(p, 5); add = 2;
     209      //mpz_sqrt(sr, nn);
     210      //if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
     211      if (mpz_size1(nn)<=2)
     212      {
     213        mpz_sqrt(sr, nn);
     214        if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
     215        unsigned long l=mpz_get_ui(sr);
     216        if (l<limit) limit=l;
     217      }
     218    }
     219    p_ui +=add;
     220    add += 2; if (add == 6) add = 2;
     221  }
     222  mpz_set_ui(p, p_ui);
    177223  mpz_sqrt(sr, nn);
    178224  if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
Note: See TracChangeset for help on using the changeset viewer.