Changeset 3dabc0 in git


Ignore:
Timestamp:
Oct 4, 2010, 6:49:44 PM (14 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '8a337797cc4177aa8747d661d5c4214ea2095dac')
Children:
4326e5b680361011d38f1ddc9d4295b9176cb475
Parents:
03ac3b21311266c39cf26cbbbb862ec708b1cd92
Message:
primefactors: limits

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

Legend:

Unmodified
Added
Removed
  • Singular/misc_ip.cc

    r03ac3b r3dabc0  
    186186
    187187/* n and pBound are assumed to be bigint numbers */
    188 lists primeFactorisation(const number n, number pBound)
     188lists primeFactorisation(const number n, const number pBound)
    189189{
    190190  mpz_t nn; number2mpz(n, nn);
     
    220220    unsigned long p_ui=5; add = 2;
    221221    mpz_sqrt(sr, nn);
    222     unsigned long  limit=nlInt(pBound,NULL);
    223     if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0))
     222    // there are 3 possible limits, we take the minimum:
     223    // - argument pBound (if >0)
     224    // - sr = sqrt(nn)
     225    // - 1<<31
     226    unsigned long  limit=1<<31;
     227    if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0))
    224228    {
    225229      mpz_set(pb, sr);
    226       mpz_set(b, sr);
    227       limit=mpz_get_ui(sr);
    228     }
    229     else if (limit==0)
    230     {
    231       limit=1<<31;
     230    }
     231    if (mpz_cmp_ui(b, limit)<0)
     232    {
     233     limit=mpz_get_ui(pb);
     234    }
     235    else
     236    {
    232237      mpz_set_ui(pb,limit);
    233       mpz_set_ui(b,limit);
    234238    }
    235239    while (p_ui <=limit)
     
    242246        //mpz_sqrt(sr, nn);
    243247        //if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
    244         if (mpz_size1(nn)<=1)
     248        if (mpz_size1(nn)<=2)
    245249        {
    246250          mpz_sqrt(sr, nn);
     
    251255          {
    252256            unsigned long nn_ui=mpz_get_ui(nn);
    253             while ((p_ui <=limit)&&(nn_ui>1))
     257            while (p_ui <=limit)
    254258            {
    255259              divTimes_ui_ui(&nn_ui, p_ui, &tt);
     
    258262                setListEntry_ui(primes, index, p_ui);
    259263                multiplicities[index++] = tt;
     264                if (nn_ui==1) break;
    260265                if (nn_ui<(limit/6)) { limit=nn_ui/6;}
    261266              }
     
    283288        mpz_sqrt(sr, nn);
    284289        if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
     290        if (mpz_cmp_ui(nn,1)==0) break;
    285291      }
    286292      mpz_add_ui(p, p, add);
     
    288294    }
    289295    if ((mpz_cmp_ui(nn, 1) > 0) &&
    290         ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(nn, b) <= 0)))
     296        ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(nn, pb) <= 0)))
    291297    {
    292298      setListEntry(primes, index, nn);
Note: See TracChangeset for help on using the changeset viewer.