Loading ...
Sorry, an error occurred while loading the content.

3053Re: [PrimeNumbers] Re: gmp-ecm-4c-r3

Expand Messages
  • Phil Carmody
    Sep 30, 2001
    • 0 Attachment
      On Sun, 30 September 2001, jfoug@... wrote:
      > --- In primenumbers@y..., Phil Carmody <fatphil@a...> wrote:
      > > On Sat, 29 September 2001, Jim Fougeron wrote:
      > > > I will be uploading a newer version of GMPECM shortly. This
      > version contains these new things:
      > > >
      > > > 1. reads the entire file and converts all to GMP numbers. This
      > is done so that the file only needs to be read one time, so that -i
      > file and < file can behave the same, and so that other tracking can
      > be done.
      > > >
      > > > 1.a If GMPECM detects that stdin is NOT redirected and that -i
      > was not used, it does NOT try to read all numbers before operating.
      > This still allows the user to type numbers into GMPECM.
      > >
      > > What if the input is redirected output from another program?
      > > For example
      >
      > Does not matter. The program automatically detects this, and it is
      > treated the same as ecm < compositesall

      My cat below was a bad example, as that closes the pipe.

      However,
      cat | ecm 10000
      just sits there doing nothing. The program can no longer be used in a pipe. Try that with the old code, and your new code - you'll see that the old code behaves as you'd expect it, but the new one just hangs there.

      | really _isn't_ the same as < at all. One is a pipe which will block until closed or given more data, the other is a file which will return EOF.

      > > cat composites1 composites2 composites3 | ecm ...
      > >
      > > Apart from that query, it looks fantastic.
      > >
      > > (Though I think there are some simplifications that can be made in
      > non-critical places, at least e.g. if a found factor takes 24 miller-
      > rabins to prove composite...)
      >
      > No, to test for "primeness" requires 25 RM tests, some trial
      > factoring, and 1 Fermat test. As soon as GMP knows the number is
      > composite, it returns from that test. Even though it is listed as
      > mpz_probable_prime(n,25) do not exect 25 loops of RM to be needed
      > to know something is composite, usually the Fermat test will suffice,
      > but if not, the first or second MR will probably find out it is
      > composite.

      I was just thinking of the code not far after line 700
      (I've had to change a few things to get it to compile, as the code has K&R signitures, and C++ comments, so was strictly neither valid C nor valid C++)

      if (mpz_probab_prime_p(p,25))
      Printf("Found probable prime factor");
      else
      Printf("Found COMPOSITE factor");
      Printf(" of %u digits: ",nb_digits(p));
      Printf_mpz_out_str(p);
      Printf("\n");
      if (mpz_probab_prime_p(p,25) && nb_digits(p)>=48)
      {
      Printf("Report your potential champion to Richard Brent <rpb@...>\n");
      Printf("(see ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.txt)\n");
      }

      The second call to mpz_probab_prime_p is unnecessary, and the if could be moved inside the case it's a subset of.
      Sure, 24 M-R's before finding it's a composite is unlikely, but it's just a neatness thing, that's all.


      Actually, while I'm here, I had other problems compiling other bits too

      Near line 550:
      #ifdef __DJGPP__
      srandom(time(NULL) + getpid()); /* thanks to Conrad Curry */
      #else
      # ifdef ANSIONLY
      time_t timer;
      struct tm tp;
      time(&timer);
      tp = *localtime(&timer);
      srand(tp.tm_hour * 3600 + tp.tm_min * 60 + tp.tm_sec);
      #else
      struct timeval tp;
      gettimeofday(&tp, NULL);
      srand48(65536 * tp.tv_sec + tp.tv_usec + getpid());
      #endif
      #endif


      The
      #else
      #ifdef ANSIONLY
      used to be
      #elif ANSIONLY
      but ANSIONLY was defined as
      #define ANSIONLY
      which meant that the line translated to
      #elif
      which shouldn't work in any conforming compiler.

      The other solution was to change the #define to provide a real value, but that was no longer a peephole solution.

      > Yes, there are certainly simplifications which can be made. That is
      > why I build an array of GMP numbers and pre-read the file.

      Do that to files, sure, but not to pipes. Pipes are more like interactive behaviour, kind-of semi-infinite. Files are finite.

      struct stat statstruct;
      fstat(0, &statstruct);
      if(S_ISREG(statstruct->st_mode))
      {
      /* is a regular file,
      and can be read in a finite amount of time
      */
      }
      else
      {
      /* is a fifo or a socket, (maybe a terminal)
      potentially infinite
      */
      }


      Phil

      Mathematics should not have to involve martyrdom;
      Support Eric Weisstein, see http://mathworld.wolfram.com
      Find the best deals on the web at AltaVista Shopping!
      http://www.shopping.altavista.com
    • Show all 4 messages in this topic