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 uint32 cl_trialdivision (const cl_I& n, uint32 d1, uint32 d2)
  19 {
  20         var uintL i = cl_small_prime_table_search(d1);
  21         var const uint16 * ptr = &cl_small_prime_table[i];
  22         var const uint16 * ptr_limit = &cl_small_prime_table[cl_small_prime_table_search(d2+1)];
  23         // Unpack n.
  24         CL_ALLOCA_STACK;
  25         var const uintD* n_MSDptr;
  26         var uintC n_len;
  27         I_to_NDS_nocopy(n, n_MSDptr=,n_len=,,cl_false,);
  28         if (mspref(n_MSDptr,0)==0) { msshrink(n_MSDptr); n_len--; }
  29         // Make room for a quotient.
  30         var uintD* q_MSDptr;
  31         num_stack_alloc(n_len,q_MSDptr=,);
  32         // Division loop.
  33         for ( ; ptr < ptr_limit; ptr++) {
  34                 var uint32 prime = *ptr;
  35                 var uintD r = divucopy_loop_msp(prime,n_MSDptr,q_MSDptr,n_len);
  36                 if (r == 0)
  37                         return prime;
  38         }
  39         return 0;
  40 }