Featured request - Page 8

Dubslow · 2012-08-06, 06:38

This is a somewhat silly request, but in nfs.c, could you add some sort of description of how the state machine works at the beginning? It's not particularly hard to read from the code, but there's enough extra stuff/lines that by the time I've gotten through to case 6 I've already forgotten which one 2 was.

Alternately, use an enum NFS_STATE, but just adding a descriptive comment would probably be easier

(~~Btw, while I haven't put too much effort into it yet, I didn't see factor_obj_t or msieve_obj in any of the header files I looked in. Where can I find those defs?~~ Nvm, finally found them after following multiple levels of includes

)

Edit: An idea for way off in the future when there's nothing of priority to work on (yeah right): In order to facilitate multiple jobs in one dir, instead of using nfs.[various exts] as the files, you could use a different header for each job. A simple header would be cxxx.[ext] so e.g. a C130 job would be c130.dat.p, c130.job, etc. Of course, to provide even more flexibility, you could also use the first 3,4,5,6 digits of the number, e.g. c130_1462.nfs.dat.p and c130_1462.job or c150_9225.job, etc.

Code:

sprintf(nfs_obj_t->job_name, "c%d_%.4s", strlen(msieve_obj->input), msieve_obj->input);
sprintf(nfs_obj_t->logfile, "%s.log", nfs_obj_t->job_name);

Mr. Odd · 2012-08-06, 20:36

Any chance YAFU could take advantage of a GPU or is that further down the merge with MSIEVE?

Dubslow · 2012-08-11, 02:14

A pet-peeve request:
nfs_filemanip.c:631:

Code:

if (VFLAG > 0)
                                printf("found poly: %s",line);

PLEASE make it `if (VFLAG > 1)` (or even 2, 3... or delete it). That as well as the verbose poly select make it impossible to scroll up on my terminals to what happened before poly select (or even poly select itself, since that printf is called thousands and thousands of times).

bsquared · 2012-08-11, 04:31

Quote:

Originally Posted by Mr. Odd

Any chance YAFU could take advantage of a GPU or is that further down the merge with MSIEVE?

I've started toying with some things that I'm hopeful will pan out. Pretty slow progress so far tho.

bsquared · 2012-08-11, 04:33

Quote:

Originally Posted by Dubslow

PLEASE make it `if (VFLAG > 1)`

Sounds reasonable.

Dubslow · 2012-08-13, 04:28

Why does YAFU insist on searching for the last special-q if passed a -nc* option? Is it possible to skip that?

bsquared · 2012-08-14, 14:40

Quote:

Originally Posted by Dubslow

Why does YAFU insist on searching for the last special-q if passed a -nc* option? Is it possible to skip that?

For each of "-nc", "-nc2", "-nc3", "-ncr" I get the following output, and no special-q search:

Code:

nfs: checking for job file - number in job file matches input
nfs: checking for data file
nfs: commencing NFS restart
nfs: user specified post processing only, skipping search for last special-q

That's not the case for you? What command line exactly are you using?

Dubslow · 2012-08-14, 16:07

Code:

bill@Gravemind:~/yafu/rsals∰∂ taskset D nice -n 19 ./yafu "nfs($(cat num))" -threads 3 -ncr -R


08/13/12 06:58:15 v1.31.1 @ Gravemind, System/Build Info: 
Using GMP-ECM 6.3, Powered by GMP 5.0.1
detected        Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3392.309750
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> nfs: checking for job file - number in job file matches input
nfs: checking for data file
nfs: commencing NFS restart
nfs: previous data file found - commencing search for last special-q
line 0 = -26325291,50042659:4603,53FB,1FA39,6B809,988D3,342751,3A8A073,3,5,5,DF,347:63966941,24B5,4D33,404FF,2658127,8E9,5,D,17,1F7,6309FFB

line 1 = 21418767,175944275:834ea07,EC5B1,3B3C23,162257B,522BFBF,3,3,11,11,89,E3,6A3:40b07bd1,238C45,37D89D,5DD02B,351A31B,1499,11,6309FFB

line 2 = -8786805,125447437:1eb15509,2353,38B7,4451,234F5,3D0AF,C5011,106867,3,38F:1c7c74c9,ced9391,B1F13,1292161,3C5A3A1,D,1F,6309FFB

line 3 = -22063949,47404121:f50365f,966AF,BB0C69,BC23EB,15B5,118D,5,7,17,AD,137,5C9:24d2391d,b8faf5d,4CB955,8C4D0F,4151249,5,6309FFB

nfs: parsing special-q
parsing rat side spq from -22063949,47404121:f50365f,966AF,BB0C69,BC23EB,15B5,118D,5,7,17,AD,137,5C9:24d2391d,b8faf5d,4CB955,8C4D0F,4151249,5,6309FFB

found 5c9
parsing alg side spq from -22063949,47404121:f50365f,966AF,BB0C69,BC23EB,15B5,118D,5,7,17,AD,137,5C9:24d2391d,b8faf5d,4CB955,8C4D0F,4151249,5,6309FFB

found 6309ffb
parsing rat side spq from -26325291,50042659:4603,53FB,1FA39,6B809,988D3,342751,3A8A073,3,5,5,DF,347:63966941,24B5,4D33,404FF,2658127,8E9,5,D,17,1F7,6309FFB

found 347
parsing alg side spq from -26325291,50042659:4603,53FB,1FA39,6B809,988D3,342751,3A8A073,3,5,5,DF,347:63966941,24B5,4D33,404FF,2658127,8E9,5,D,17,1F7,6309FFB

found 6309ffb
parsing rat side spq from 21418767,175944275:834ea07,EC5B1,3B3C23,162257B,522BFBF,3,3,11,11,89,E3,6A3:40b07bd1,238C45,37D89D,5DD02B,351A31B,1499,11,6309FFB

found 6a3
parsing alg side spq from 21418767,175944275:834ea07,EC5B1,3B3C23,162257B,522BFBF,3,3,11,11,89,E3,6A3:40b07bd1,238C45,37D89D,5DD02B,351A31B,1499,11,6309FFB

found 6309ffb
nfs: commencing gnfs on c235: 5924803283046424380127702714410168927856963922073854385856048259658298530274495160311145216164689204483139094513462824443493417977121643921085458690640985251793305798081061369516712260880142935593529633572390949734336224813305984910083
nfs: found 214584929 relations, continuing job at specialq = 103849979
nfs: commencing msieve linear algebra

commencing linear algebra
matrix starts at (0, 0)
matrix is 8044900 x 8045076 (2404.6 MB) with weight 742704674 (92.32/col)
sparse part has weight 541868260 (67.35/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 8044852 x 8045076 (2327.3 MB) with weight 589558220 (73.28/col)
sparse part has weight 529625512 (65.83/col)
using block size 65536 for processor cache size 8192 kB
dump interval = 2000
commencing Lanczos iteration (3 threads)
memory use: 2018.8 MB
restarting at iteration 18633 (dim = 1178407)
linear algebra at 14.7%, ETA 85h15m 8045076 dimensions (14.7%, ETA 85h15m)    
checkpointing every 90000 dimensions
linear algebra completed 3620501 of 8045076 dimensions (45.0%, ETA 50h43m)

Could it be the -R?

Edit:

Code:

bill@Gravemind:~/yafu/rsals∰∂ cat yafu.ini
B1pm1=100000
B1pp1=20000
B1ecm=11000
rhomax=1000
threads=2
pretest_ratio=0.35 // btw, even with this, for aliquots i usually see ratio <0.33, typically ~0.30
v=1
ggnfs_dir=/home/bill/yafu/ggnfs/
ecm_path=/home/bill/yafu/ecm/ecm

bsquared · 2012-08-14, 16:17

Ah. No, it is the version. The checks for "-nc*" were added in 1.32.

Dubslow · 2012-08-14, 16:20

Quote:

Originally Posted by bsquared

Ah. No, it is the version. The checks for "-nc*" were added in 1.32.

I upgraded the exe in ~/yafu, but not the subfolders

Code:

^Cnear algebra completed 3640974 of 8045076 dimensions (45.3%, ETA 50h30m)    
Received signal 2... please wait
setting flag

Received signal 2... please wait
setting flag

Received signal 2... please wait
setting flag

lanczos halted after 57579 iterations (dim = 3641100)
BLanczosTime: 101792


***factors found***


***co-factor***
C235 = 5924803283046424380127702714410168927856963922073854385856048259658298530274495160311145216164689204483139094513462824443493417977121643921085458690640985251793305798081061369516712260880142935593529633572390949734336224813305984910083
bill@Gravemind:~/yafu/rsals∰∂ cp ../yafu .
bill@Gravemind:~/yafu/rsals∰∂ taskset D nice -n 19 ./yafu "nfs($(cat num))" -threads 3 -ncr -R


08/14/12 11:21:17 v1.32 @ Gravemind, System/Build Info: 
Using GMP-ECM 6.3, Powered by GMP 5.0.1
detected        Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3392.310470
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> nfs: checking for job file - number in job file matches input
nfs: checking for data file
nfs: commencing NFS restart
nfs: user specified post processing only, skipping search for last special-q
nfs: commencing gnfs on c235: 5924803283046424380127702714410168927856963922073854385856048259658298530274495160311145216164689204483139094513462824443493417977121643921085458690640985251793305798081061369516712260880142935593529633572390949734336224813305984910083
nfs: continuing with sieving - could not determine last special q; using default startq
nfs: commencing msieve linear algebra

commencing linear algebra

Dubslow · 2012-08-15, 01:37

The APRCL Wiki page says Alpertron uses it in his ECM/Java website, with downloadable source code. Another benefit is that since alpertron himself posts here, we can be absolutely sure no licenses are being violated

Code:

// Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
// Last updated September 10th, 2011. See http://www.alpertron.com.ar/ECM.HTM
//
// Based in Yuji Kida's implementation for UBASIC interpreter
//
// No part of this code can be used for commercial purposes without
// the written consent from the author. Otherwise it can be used freely
// except that you have to write somewhere in the code this header.

  // Prime checking routine
  // Return codes: 0 = Number is prime.
  //               1 = Number is composite.
  int AprtCle(BigInteger N)
  {
    int i, j, G, H, I, J, K, P, Q, T, U, W, X;
    int IV, InvX, LEVELnow, NP, PK, PL, PM, SW, VK, TestedQs, TestingQs;
    int QQ, T1, T3, U1, U3, V1, V3;
    int LengthN, LengthS;
    long Mask;
    double dS;
    String primalityString = "";

    lowerTextArea.setText("Starting Prime Check routine.");
    NumberLength = BigNbrToBigInt(N, TestNbr);
    GetYieldFrequency();
    GetMontgomeryParms();
    if (!Computing3Squares)
    {
      textAreaContents = "";
      StringToLabel = "Testing primality of ";
      insertBigNbr(N);
      addStringToLabel("(" + N.toString().length() + " digits)");
      primalityString =
        textAreaContents + StringToLabel + "\nAPRT-CLE progress: ";
    }
    j = PK = PL = PM = 0;
    for (I = 0; I < NumberLength; I++)
    {
      biS[I] = 0;
      for (J = 0; J < PWmax; J++)
      {
        aiJX[J][I] = 0;
      }
    }
    GetPrimes2Test : for (i = 0; i < LEVELmax; i++)
    {
      biS[0] = 2;
      for (I = 1; I < NumberLength; I++)
      {
        biS[I] = 0;
      }
      for (j = 0; j < aiNQ[i]; j++)
      {
        Q = aiQ[j];
        U = aiT[i] * Q;
        do
        {
          U /= Q;
          MultBigNbrByLong(biS, Q, biS, NumberLength);
        }
        while (U % Q == 0);

        // Exit loop if S^2 > N.

        if (CompareSquare(biS, TestNbr) > 0)
        {
          break GetPrimes2Test;
        }
      } /* End for j */
    } /* End for i */
    if (i == LEVELmax)
    { /* too big */
      return ProbabilisticPrimeTest(N);
    }
    LEVELnow = i;
    TestingQs = j;
    T = aiT[LEVELnow];
    NP = aiNP[LEVELnow];

    MainStart : for (;;)
    {
      for (i = 0; i < NP; i++)
      {
        P = aiP[i];
        SW = TestedQs = 0;
        Q = W = (int) BigNbrModLong(TestNbr, P * P);
        for (J = P - 2; J > 0; J--)
        {
          W = (W * Q) % (P * P);
        }
        if (P > 2 && W != 1)
        {
          SW = 1;
        }
        for (;;)
        {
          for (j = TestedQs; j <= TestingQs; j++)
          {
            Q = aiQ[j] - 1;
            G = aiG[j];
            K = 0;
            while (Q % P == 0)
            {
              K++;
              Q /= P;
            }
            Q = aiQ[j];
            if (K == 0)
            {
              continue;
            }
            if (!Computing3Squares)
            {
              lowerTextArea.setText(
                primalityString
                  + "P = "
                  + P
                  + ",  Q = "
                  + Q
                  + "  ("
                  + (i * (TestingQs + 1) + j) * 100 / (NP * (TestingQs + 1))
                  + "%)");
            }
            PM = 1;
            for (I = 1; I < K; I++)
            {
              PM = PM * P;
            }
            PL = (P - 1) * PM;
            PK = P * PM;
            J = 1;
            for (I = 1; I < Q; I++)
            {
              J = J * G % Q;
              aiIndx[J] = I;
            }
            J = 1;
            for (I = 1; I <= Q - 2; I++)
            {
              J = J * G % Q;
              aiF[I] = aiIndx[(Q + 1 - J) % Q];
            }
            for (I = 0; I < PK; I++)
            {
              for (J = 0; J < NumberLength; J++)
              {
                aiJ0[I][J] = aiJ1[I][J] = 0;
              }
            }
            if (P > 2)
            {
              JacobiSum(1, 1, P, PK, PL, PM, Q);
            }
            else
            {
              if (K != 1)
              {
                JacobiSum(1, 1, P, PK, PL, PM, Q);
                for (I = 0; I < PK; I++)
                {
                  for (J = 0; J < NumberLength; J++)
                  {
                    aiJW[I][J] = 0;
                  }
                }
                if (K != 2)
                {
                  for (I = 0; I < PM; I++)
                  {
                    for (J = 0; J < NumberLength; J++)
                    {
                      aiJW[I][J] = aiJ0[I][J];
                    }
                  }
                  JacobiSum(2, 1, P, PK, PL, PM, Q);
                  for (I = 0; I < PM; I++)
                  {
                    for (J = 0; J < NumberLength; J++)
                    {
                      aiJS[I][J] = aiJ0[I][J];
                    }
                  }
                  JS_JW(PK, PL, PM, P);
                  NormalizeJS(PK, PL, PM, P);
                  for (I = 0; I < PM; I++)
                  {
                    for (J = 0; J < NumberLength; J++)
                    {
                      aiJ1[I][J] = aiJS[I][J];
                    }
                  }
                  JacobiSum(3 << (K - 3), 1 << (K - 3), P, PK, PL, PM, Q);
                  for (J = 0; J < NumberLength; J++)
                  {
                    for (I = 0; I < PK; I++)
                    {
                      aiJW[I][J] = 0;
                    }
                    for (I = 0; I < PM; I++)
                    {
                      aiJS[I][J] = aiJ0[I][J];
                    }
                  }
                  JS_2(PK, PL, PM, P);
                  NormalizeJS(PK, PL, PM, P);
                  for (I = 0; I < PM; I++)
                  {
                    for (J = 0; J < NumberLength; J++)
                    {
                      aiJ2[I][J] = aiJS[I][J];
                    }
                  }
                }
              }
            }
            for (J = 0; J < NumberLength; J++)
            {
              aiJ00[0][J] = aiJ01[0][J] = MontgomeryMultR1[J];
              for (I = 1; I < PK; I++)
              {
                aiJ00[I][J] = aiJ01[I][J] = 0;
              }
            }
            VK = (int) BigNbrModLong(TestNbr, PK);
            for (I = 1; I < PK; I++)
            {
              if (I % P != 0)
              {
                U1 = 1;
                U3 = I;
                V1 = 0;
                V3 = PK;
                while (V3 != 0)
                {
                  QQ = U3 / V3;
                  T1 = U1 - V1 * QQ;
                  T3 = U3 - V3 * QQ;
                  U1 = V1;
                  U3 = V3;
                  V1 = T1;
                  V3 = T3;
                }
                aiInv[I] = (U1 + PK) % PK;
              }
              else
              {
                aiInv[I] = 0;
              }
            }
            if (P != 2)
            {
              for (IV = 0; IV <= 1; IV++)
              {
                for (X = 1; X < PK; X++)
                {
                  for (I = 0; I < PK; I++)
                  {
                    for (J = 0; J < NumberLength; J++)
                    {
                      aiJS[I][J] = aiJ0[I][J];
                    }
                  }
                  if (X % P == 0)
                  {
                    continue;
                  }
                  if (IV == 0)
                  {
                    LongToBigNbr(X, biExp, NumberLength);
                  }
                  else
                  {
                    LongToBigNbr(VK * X / PK, biExp, NumberLength);
                    if (VK * X / PK == 0)
                    {
                      continue;
                    }
                  }
                  JS_E(PK, PL, PM, P);
                  for (I = 0; I < PK; I++)
                  {
                    for (J = 0; J < NumberLength; J++)
                    {
                      aiJW[I][J] = 0;
                    }
                  }
                  InvX = aiInv[X];
                  for (I = 0; I < PK; I++)
                  {
                    J = I * InvX % PK;
                    AddBigNbrModN(aiJW[J], aiJS[I], aiJW[J], TestNbr,
                                  NumberLength);
                  }
                  NormalizeJW(PK, PL, PM, P);
...<char limit>

2012-08-06, 06:38	#78
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 7221₁₀ Posts	This is a somewhat silly request, but in nfs.c, could you add some sort of description of how the state machine works at the beginning? It's not particularly hard to read from the code, but there's enough extra stuff/lines that by the time I've gotten through to case 6 I've already forgotten which one 2 was. Alternately, use an enum NFS_STATE, but just adding a descriptive comment would probably be easier (~~Btw, while I haven't put too much effort into it yet, I didn't see factor_obj_t or msieve_obj in any of the header files I looked in. Where can I find those defs?~~ Nvm, finally found them after following multiple levels of includes ) Edit: An idea for way off in the future when there's nothing of priority to work on (yeah right): In order to facilitate multiple jobs in one dir, instead of using nfs.[various exts] as the files, you could use a different header for each job. A simple header would be cxxx.[ext] so e.g. a C130 job would be c130.dat.p, c130.job, etc. Of course, to provide even more flexibility, you could also use the first 3,4,5,6 digits of the number, e.g. c130_1462.nfs.dat.p and c130_1462.job or c150_9225.job, etc. Code: sprintf(nfs_obj_t->job_name, "c%d_%.4s", strlen(msieve_obj->input), msieve_obj->input); sprintf(nfs_obj_t->logfile, "%s.log", nfs_obj_t->job_name); Last fiddled with by Dubslow on 2012-08-06 at 06:59

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
ARM ASM request	ET_	Programming	0	2018-11-01 14:57
Bug/request	Dubslow	YAFU	4	2012-03-31 03:07
Odd request?	Xyzzy	Lounge	23	2011-03-08 17:50
Prime95 featured in Maximum PC!	ixfd64	Software	10	2010-05-31 15:21
GMP-ECM Request	rogue	GMP-ECM	4	2009-11-23 15:07

2012-08-06, 20:36	#79
Mr. Odd Mar 2010 5·11 Posts	Any chance YAFU could take advantage of a GPU or is that further down the merge with MSIEVE?

2012-08-11, 02:14	#80
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	A pet-peeve request: nfs_filemanip.c:631: Code: if (VFLAG > 0) printf("found poly: %s",line); PLEASE make it `if (VFLAG > 1)` (or even 2, 3... or delete it). That as well as the verbose poly select make it impossible to scroll up on my terminals to what happened before poly select (or even poly select itself, since that printf is called thousands and thousands of times).

2012-08-13, 04:28	#83
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1110000110101₂ Posts	Why does YAFU insist on searching for the last special-q if passed a -nc* option? Is it possible to skip that?

2012-08-14, 16:17	#86
bsquared "Ben" Feb 2007 D21₁₆ Posts	Ah. No, it is the version. The checks for "-nc*" were added in 1.32.