src/numtheory/cl_IF_trialdiv.cc

   1 // cl_trialdivision().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cl_IF.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cl_I.h"
  13
  14 #if !(intDsize >= 16)
  15 #error "intDsize too small for trialdivision!"
  16 #endif
  17
  18 namespace cln {
  19
  20 uint32 cl_trialdivision (const cl_I& n, uint32 d1, uint32 d2)
  21 {
  22         var uintL i = cl_small_prime_table_search(d1);
  23         var const uint16 * ptr = &cl_small_prime_table[i];
  24         var const uint16 * ptr_limit = &cl_small_prime_table[cl_small_prime_table_search(d2+1)];
  25         // Unpack n.
  26         CL_ALLOCA_STACK;
  27         var const uintD* n_MSDptr;
  28         var uintC n_len;
  29         I_to_NDS_nocopy(n, n_MSDptr=,n_len=,,cl_false,);
  30         if (mspref(n_MSDptr,0)==0) { msshrink(n_MSDptr); n_len--; }
  31         // Make room for a quotient.
  32         var uintD* q_MSDptr;
  33         num_stack_alloc(n_len,q_MSDptr=,);
  34         // Division loop.
  35         for ( ; ptr < ptr_limit; ptr++) {
  36                 var uint32 prime = *ptr;
  37                 var uintD r = divucopy_loop_msp(prime,n_MSDptr,q_MSDptr,n_len);
  38                 if (r == 0)
  39                         return prime;
  40         }
  41         return 0;
  42 }
  43
  44 }  // namespace cln