t-perfsqr.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:3k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. /* Test mpn_perfect_square_p data.
  2. Copyright 2002 Free Software Foundation, Inc.
  3. This file is part of the GNU MP Library.
  4. The GNU MP Library is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU Lesser General Public License as published by
  6. the Free Software Foundation; either version 3 of the License, or (at your
  7. option) any later version.
  8. The GNU MP Library is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  11. License for more details.
  12. You should have received a copy of the GNU Lesser General Public License
  13. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include "gmp.h"
  17. #include "gmp-impl.h"
  18. #include "tests.h"
  19. #include "mpn/perfsqr.h"
  20. #define PERFSQR_MOD_MASK   ((CNST_LIMB(1) << PERFSQR_MOD_BITS) - 1)
  21. void
  22. check_mod_2 (mp_limb_t d, mp_limb_t inv, mp_limb_t got_hi, mp_limb_t got_lo)
  23. {
  24.   int        want[2*GMP_LIMB_BITS], got;
  25.   unsigned   r, idx;
  26.   mp_limb_t  q;
  27.   ASSERT_ALWAYS (d <= numberof (want));
  28.   ASSERT_ALWAYS (((inv * d) & PERFSQR_MOD_MASK) == 1);
  29.   ASSERT_ALWAYS (MP_LIMB_T_MAX / d >= PERFSQR_MOD_MASK);
  30.   /* the squares mod d */
  31.   for (r = 0; r < d; r++)
  32.     want[r] = 0;
  33.   for (r = 0; r < d; r++)
  34.     want[(r*r)%d] = 1;
  35.   /* for each remainder mod d, expect the table data to correctly identify
  36.      it as a residue or non-residue */
  37.   for (r = 0; r < d; r++)
  38.     {
  39.       /* as per PERFSQR_MOD_IDX */
  40.       q = ((r) * (inv)) & PERFSQR_MOD_MASK;
  41.       idx = (q * (d)) >> PERFSQR_MOD_BITS;
  42.       if (idx >= GMP_LIMB_BITS)
  43.         got = (got_hi >> (idx - GMP_LIMB_BITS)) & 1;
  44.       else
  45.         got = (got_lo >> idx) & 1;
  46.       if (got != want[r])
  47.         {
  48.           printf ("Wrong generated datan");
  49.           printf ("  d=%un", (unsigned) d);
  50.           printf ("  r=%un", r);
  51.           printf ("  idx=%un", idx);
  52.           printf ("  got  %dn", got);
  53.           printf ("  want %dn", want[r]);
  54.           abort ();
  55.         }
  56.     }
  57. }
  58. /* Check the generated data in perfsqr.h. */
  59. void
  60. check_mod (void)
  61. {
  62. #define PERFSQR_MOD_34(r, up, usize)       { r = 0; } /* so r isn't unused */
  63. #define PERFSQR_MOD_PP(r, up, usize)       { r = 0; }
  64. #define PERFSQR_MOD_1(r, d, inv, mask)     check_mod_2 (d, inv, CNST_LIMB(0), mask)
  65. #define PERFSQR_MOD_2(r, d, inv, mhi, mlo) check_mod_2 (d, inv, mhi, mlo)
  66.   PERFSQR_MOD_TEST (dummy, dummy);
  67. }
  68. /* Check PERFSQR_PP, if in use. */
  69. void
  70. check_pp (void)
  71. {
  72. #ifdef PERFSQR_PP
  73.   ASSERT_ALWAYS_LIMB (PERFSQR_PP);
  74.   ASSERT_ALWAYS_LIMB (PERFSQR_PP_NORM);
  75.   ASSERT_ALWAYS_LIMB (PERFSQR_PP_INVERTED);
  76.   /* preinv stuff only for nails==0 */
  77.   if (GMP_NAIL_BITS == 0)
  78.     {
  79.       ASSERT_ALWAYS (PERFSQR_PP_NORM
  80.                      == PERFSQR_PP << refmpn_count_leading_zeros (PERFSQR_PP));
  81.       ASSERT_ALWAYS (PERFSQR_PP_INVERTED
  82.                      == refmpn_invert_limb (PERFSQR_PP_NORM));
  83.     }
  84. #endif
  85. }
  86. int
  87. main (void)
  88. {
  89.   tests_start ();
  90.   check_mod ();
  91.   check_pp ();
  92.   tests_end ();
  93.   exit (0);
  94. }