mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2012-08-06, 06:38   #78
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

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
Dubslow is offline   Reply With Quote
Old 2012-08-06, 20:36   #79
Mr. Odd
 
Mar 2010

5×11 Posts
Default

Any chance YAFU could take advantage of a GPU or is that further down the merge with MSIEVE?
Mr. Odd is offline   Reply With Quote
Old 2012-08-11, 02:14   #80
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

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).
Dubslow is offline   Reply With Quote
Old 2012-08-11, 04:31   #81
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by Mr. Odd View Post
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 is offline   Reply With Quote
Old 2012-08-11, 04:33   #82
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by Dubslow View Post
PLEASE make it `if (VFLAG > 1)`
Sounds reasonable.
bsquared is offline   Reply With Quote
Old 2012-08-13, 04:28   #83
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

Why does YAFU insist on searching for the last special-q if passed a -nc* option? Is it possible to skip that?
Dubslow is offline   Reply With Quote
Old 2012-08-14, 14:40   #84
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

64158 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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?
bsquared is offline   Reply With Quote
Old 2012-08-14, 16:07   #85
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

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

Last fiddled with by Dubslow on 2012-08-14 at 16:11
Dubslow is offline   Reply With Quote
Old 2012-08-14, 16:17   #86
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Ah. No, it is the version. The checks for "-nc*" were added in 1.32.
bsquared is offline   Reply With Quote
Old 2012-08-14, 16:20   #87
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by bsquared View Post
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

Last fiddled with by Dubslow on 2012-08-14 at 16:21 Reason: code
Dubslow is offline   Reply With Quote
Old 2012-08-15, 01:37   #88
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default About the PRP->P thing

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>
Dubslow is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:42.

Thu Nov 26 13:42:11 UTC 2020 up 77 days, 10:53, 3 users, load averages: 1.05, 1.37, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.