tests/mpz/t-powm_ui.c

   1 /* Test mpz_powm_ui, mpz_mul, mpz_mod.
   2
   3 Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software
   4 Foundation, Inc.
   5
   6 This file is part of the GNU MP Library.
   7
   8 The GNU MP Library is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU Lesser General Public License as published by
  10 the Free Software Foundation; either version 3 of the License, or (at your
  11 option) any later version.
  12
  13 The GNU MP Library is distributed in the hope that it will be useful, but
  14 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  15 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  16 License for more details.
  17
  18 You should have received a copy of the GNU Lesser General Public License
  19 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  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 dump_abort __GMP_PROTO ((mpz_t, mpz_t));
  29 void debug_mp __GMP_PROTO ((mpz_t, int));
  30
  31 int
  32 main (int argc, char **argv)
  33 {
  34   mpz_t base, exp, mod;
  35   mpz_t r1, r2, base2;
  36   mp_size_t base_size, exp_size, mod_size;
  37   unsigned long int exp2;
  38   int i;
  39   int reps = 1000;
  40   gmp_randstate_ptr rands;
  41   mpz_t bs;
  42   unsigned long bsi, size_range;
  43
  44   tests_start ();
  45   rands = RANDS;
  46
  47   mpz_init (bs);
  48
  49   if (argc == 2)
  50      reps = atoi (argv[1]);
  51
  52   mpz_init (base);
  53   mpz_init (exp);
  54   mpz_init (mod);
  55   mpz_init (r1);
  56   mpz_init (r2);
  57   mpz_init (base2);
  58
  59   for (i = 0; i < reps; i++)
  60     {
  61       mpz_urandomb (bs, rands, 32);
  62       size_range = mpz_get_ui (bs) % 13 + 2;
  63
  64       do  /* Loop until mathematically well-defined.  */
  65         {
  66           mpz_urandomb (bs, rands, size_range);
  67           base_size = mpz_get_ui (bs);
  68           mpz_rrandomb (base, rands, base_size);
  69
  70           mpz_urandomb (bs, rands, 6L);
  71           exp_size = mpz_get_ui (bs);
  72           mpz_rrandomb (exp, rands, exp_size);
  73           exp2 = mpz_getlimbn (exp, (mp_size_t) 0);
  74         }
  75       while (mpz_cmp_ui (base, 0) == 0 && exp2 == 0);
  76
  77       do
  78         {
  79           mpz_urandomb (bs, rands, size_range);
  80           mod_size = mpz_get_ui (bs);
  81           mpz_rrandomb (mod, rands, mod_size);
  82         }
  83       while (mpz_cmp_ui (mod, 0) == 0);
  84
  85       mpz_urandomb (bs, rands, 2);
  86       bsi = mpz_get_ui (bs);
  87       if ((bsi & 1) != 0)
  88         mpz_neg (base, base);
  89
  90       /* printf ("%ld %ld\n", SIZ (base), SIZ (mod)); */
  91
  92 #if 0
  93       putc ('\n', stderr);
  94       debug_mp (base, -16);
  95       debug_mp (mod, -16);
  96 #endif
  97
  98       mpz_powm_ui (r1, base, exp2, mod);
  99       MPZ_CHECK_FORMAT (r1);
 100
 101       mpz_set_ui (r2, 1);
 102       mpz_set (base2, base);
 103
 104       mpz_mod (r2, r2, mod);    /* needed when exp==0 and mod==1 */
 105       while (exp2 != 0)
 106         {
 107           if (exp2 % 2 != 0)
 108             {
 109               mpz_mul (r2, r2, base2);
 110               mpz_mod (r2, r2, mod);
 111             }
 112           mpz_mul (base2, base2, base2);
 113           mpz_mod (base2, base2, mod);
 114           exp2 = exp2 / 2;
 115         }
 116
 117 #if 0
 118       debug_mp (r1, -16);
 119       debug_mp (r2, -16);
 120 #endif
 121
 122       if (mpz_cmp (r1, r2) != 0)
 123         {
 124           fprintf (stderr, "\ntest %d: Incorrect results for operands:\n", i);
 125           debug_mp (base, -16);
 126           debug_mp (exp, -16);
 127           debug_mp (mod, -16);
 128           fprintf (stderr, "mpz_powm_ui result:\n");
 129           debug_mp (r1, -16);
 130           fprintf (stderr, "reference result:\n");
 131           debug_mp (r2, -16);
 132           abort ();
 133         }
 134     }
 135
 136   mpz_clear (bs);
 137   mpz_clear (base);
 138   mpz_clear (exp);
 139   mpz_clear (mod);
 140   mpz_clear (r1);
 141   mpz_clear (r2);
 142   mpz_clear (base2);
 143
 144   tests_end ();
 145   exit (0);
 146 }
 147
 148 void
 149 dump_abort (mpz_t dividend, mpz_t divisor)
 150 {
 151   fprintf (stderr, "ERROR\n");
 152   fprintf (stderr, "dividend = "); debug_mp (dividend, -16);
 153   fprintf (stderr, "divisor  = "); debug_mp (divisor, -16);
 154   abort();
 155 }
 156
 157 void
 158 debug_mp (mpz_t x, int base)
 159 {
 160   mpz_out_str (stderr, base, x); fputc ('\n', stderr);
 161 }