tests/mpz/t-nextprime.c

   1 /* Test mpz_nextprime.
   2
   3 Copyright 2009 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  19
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23
  24 #include "gmp.h"
  25 #include "gmp-impl.h"
  26 #include "tests.h"
  27
  28 void
  29 refmpz_nextprime (mpz_ptr p, mpz_srcptr t)
  30 {
  31   mpz_add_ui (p, t, 1L);
  32   while (! mpz_probab_prime_p (p, 10))
  33     mpz_add_ui (p, p, 1L);
  34 }
  35
  36 void
  37 run (char *start, int reps, char *end, short diffs[])
  38 {
  39   mpz_t x, y;
  40   int i;
  41
  42   mpz_init_set_str (x, start, 0);
  43   mpz_init (y);
  44
  45   for (i = 0; i < reps; i++)
  46     {
  47       mpz_nextprime (y, x);
  48       mpz_sub (x, y, x);
  49       if (diffs != NULL && diffs[i] != mpz_get_ui (x))
  50         {
  51           gmp_printf ("diff list discrepancy\n");
  52           abort ();
  53         }
  54       mpz_set (x, y);
  55     }
  56
  57   mpz_set_str (y, end, 0);
  58
  59   if (mpz_cmp (x, y) != 0)
  60     {
  61       gmp_printf ("got  %Zx\n", x);
  62       gmp_printf ("want %Zx\n", y);
  63       abort ();
  64     }
  65
  66   mpz_clear (y);
  67   mpz_clear (x);
  68 }
  69
  70 extern short diff1[];
  71 extern short diff3[];
  72 extern short diff4[];
  73 extern short diff5[];
  74
  75 int
  76 main (int argc, char **argv)
  77 {
  78   int i;
  79   int reps = 20;
  80   gmp_randstate_ptr rands;
  81   mpz_t bs, x, nxtp, ref_nxtp;
  82   unsigned long size_range;
  83
  84   tests_start();
  85   rands = RANDS;
  86
  87   run ("2", 1000, "0x1ef7", diff1);
  88
  89   run ("3", 1000 - 1, "0x1ef7", NULL);
  90
  91   run ("0x8a43866f5776ccd5b02186e90d28946aeb0ed914", 50,
  92        "0x8a43866f5776ccd5b02186e90d28946aeb0eeec5", diff3);
  93
  94   run ("0x10000000000000000000000000000000000000", 50,
  95        "0x100000000000000000000000000000000010ab", diff4);
  96
  97   run ("0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898d8b1b", 50,
  98        "0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898da957", diff5);
  99
 100   mpz_init (bs);
 101   mpz_init (x);
 102   mpz_init (nxtp);
 103   mpz_init (ref_nxtp);
 104
 105   if (argc == 2)
 106      reps = atoi (argv[1]);
 107
 108   for (i = 0; i < reps; i++)
 109     {
 110       mpz_urandomb (bs, rands, 32);
 111       size_range = mpz_get_ui (bs) % 8 + 2; /* 0..1024 bit operands */
 112
 113       mpz_urandomb (bs, rands, size_range);
 114       mpz_rrandomb (x, rands, mpz_get_ui (bs));
 115
 116 /*      gmp_printf ("%ld: %Zd\n", mpz_sizeinbase (x, 2), x); */
 117
 118       mpz_nextprime (nxtp, x);
 119       refmpz_nextprime (ref_nxtp, x);
 120       if (mpz_cmp (nxtp, ref_nxtp) != 0)
 121         abort ();
 122     }
 123
 124   mpz_clear (bs);
 125   mpz_clear (x);
 126   mpz_clear (nxtp);
 127   mpz_clear (ref_nxtp);
 128
 129   tests_end ();
 130   return 0;
 131 }
 132
 133 short diff1[] =
 134 {
 135   1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,
 136   2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,
 137   2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,
 138   2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,
 139   4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,
 140   2,10,2,6,4,6,8,4,2,4,12,8,4,8,4,6,
 141   12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,
 142   2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,
 143   6,6,4,8,6,4,8,4,14,10,12,2,10,2,4,2,
 144   10,14,4,2,4,14,4,2,4,20,4,8,10,8,4,6,
 145   6,14,4,6,6,8,6,12,4,6,2,10,2,6,10,2,
 146   10,2,6,18,4,2,4,6,6,8,6,6,22,2,10,8,
 147   10,6,6,8,12,4,6,6,2,6,12,10,18,2,4,6,
 148   2,6,4,2,4,12,2,6,34,6,6,8,18,10,14,4,
 149   2,4,6,8,4,2,6,12,10,2,4,2,4,6,12,12,
 150   8,12,6,4,6,8,4,8,4,14,4,6,2,4,6,2,
 151   6,10,20,6,4,2,24,4,2,10,12,2,10,8,6,6,
 152   6,18,6,4,2,12,10,12,8,16,14,6,4,2,4,2,
 153   10,12,6,6,18,2,16,2,22,6,8,6,4,2,4,8,
 154   6,10,2,10,14,10,6,12,2,4,2,10,12,2,16,2,
 155   6,4,2,10,8,18,24,4,6,8,16,2,4,8,16,2,
 156   4,8,6,6,4,12,2,22,6,2,6,4,6,14,6,4,
 157   2,6,4,6,12,6,6,14,4,6,12,8,6,4,26,18,
 158   10,8,4,6,2,6,22,12,2,16,8,4,12,14,10,2,
 159   4,8,6,6,4,2,4,6,8,4,2,6,10,2,10,8,
 160   4,14,10,12,2,6,4,2,16,14,4,6,8,6,4,18,
 161   8,10,6,6,8,10,12,14,4,6,6,2,28,2,10,8,
 162   4,14,4,8,12,6,12,4,6,20,10,2,16,26,4,2,
 163   12,6,4,12,6,8,4,8,22,2,4,2,12,28,2,6,
 164   6,6,4,6,2,12,4,12,2,10,2,16,2,16,6,20,
 165   16,8,4,2,4,2,22,8,12,6,10,2,4,6,2,6,
 166   10,2,12,10,2,10,14,6,4,6,8,6,6,16,12,2,
 167   4,14,6,4,8,10,8,6,6,22,6,2,10,14,4,6,
 168   18,2,10,14,4,2,10,14,4,8,18,4,6,2,4,6,
 169   2,12,4,20,22,12,2,4,6,6,2,6,22,2,6,16,
 170   6,12,2,6,12,16,2,4,6,14,4,2,18,24,10,6,
 171   2,10,2,10,2,10,6,2,10,2,10,6,8,30,10,2,
 172   10,8,6,10,18,6,12,12,2,18,6,4,6,6,18,2,
 173   10,14,6,4,2,4,24,2,12,6,16,8,6,6,18,16,
 174   2,4,6,2,6,6,10,6,12,12,18,2,6,4,18,8,
 175   24,4,2,4,6,2,12,4,14,30,10,6,12,14,6,10,
 176   12,2,4,6,8,6,10,2,4,14,6,6,4,6,2,10,
 177   2,16,12,8,18,4,6,12,2,6,6,6,28,6,14,4,
 178   8,10,8,12,18,4,2,4,24,12,6,2,16,6,6,14,
 179   10,14,4,30,6,6,6,8,6,4,2,12,6,4,2,6,
 180   22,6,2,4,18,2,4,12,2,6,4,26,6,6,4,8,
 181   10,32,16,2,6,4,2,4,2,10,14,6,4,8,10,6,
 182   20,4,2,6,30,4,8,10,6,6,8,6,12,4,6,2,
 183   6,4,6,2,10,2,16,6,20,4,12,14,28,6,20,4,
 184   18,8,6,4,6,14,6,6,10,2,10,12,8,10,2,10,
 185   8,12,10,24,2,4,8,6,4,8,18,10,6,6,2,6,
 186   10,12,2,10,6,6,6,8,6,10,6,2,6,6,6,10,
 187   8,24,6,22,2,18,4,8,10,30,8,18,4,2,10,6,
 188   2,6,4,18,8,12,18,16,6,2,12,6,10,2,10,2,
 189   6,10,14,4,24,2,16,2,10,2,10,20,4,2,4,8,
 190   16,6,6,2,12,16,8,4,6,30,2,10,2,6,4,6,
 191   6,8,6,4,12,6,8,12,4,14,12,10,24,6,12,6,
 192   2,22,8,18,10,6,14,4,2,6,10,8,6,4,6,30,
 193   14,10,2,12,10,2,16,2,18,24,18,6,16,18,6,2,
 194   18,4,6,2,10,8,10,6,6,8,4,6,2,10,2,12,
 195   4,6,6,2,12,4,14,18,4,6,20,4,8,6,4,8,
 196   4,14,6,4,14,12,4,2,30,4,24,6,6,12,12,14,
 197   6,4,2,4,18,6,12,8
 198 };
 199
 200 short diff3[] =
 201 {
 202   33,32,136,116,24,22,104,114,76,278,238,162,36,44,388,134,
 203   130,26,312,42,138,28,24,80,138,108,270,12,330,130,98,102,
 204   162,34,36,170,90,34,14,6,24,66,154,218,70,132,188,88,
 205   80,82
 206 };
 207
 208 short diff4[] =
 209 {
 210   91,92,64,6,104,24,46,258,68,18,54,100,68,154,26,4,
 211   38,142,168,42,18,26,286,104,136,116,40,2,28,110,52,78,
 212   104,24,54,96,4,626,196,24,56,36,52,102,48,156,26,18,
 213   42,40
 214 };
 215
 216 short diff5[] =
 217 {
 218   268,120,320,184,396,2,94,108,20,318,274,14,64,122,220,108,
 219   18,174,6,24,348,32,64,116,268,162,20,156,28,110,52,428,
 220   196,14,262,30,194,120,300,66,268,12,428,370,212,198,192,130,
 221   30,80
 222 };