util/X86LINUX64/cuda-6.5/include/thrust/random/detail/linear_congruential_engine_discard.h

   1 /*
   2  *  Copyright 2008-2013 NVIDIA Corporation
   3  *
   4  *  Licensed under the Apache License, Version 2.0 (the "License");
   5  *  you may not use this file except in compliance with the License.
   6  *  You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  *  Unless required by applicable law or agreed to in writing, software
  11  *  distributed under the License is distributed on an "AS IS" BASIS,
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  *  See the License for the specific language governing permissions and
  14  *  limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <thrust/detail/cstdint.h>
  20 #include <thrust/random/detail/mod.h>
  21
  22 namespace thrust
  23 {
  24
  25 namespace random
  26 {
  27
  28 namespace detail
  29 {
  30
  31
  32 template<typename UIntType, UIntType a, unsigned long long c, UIntType m>
  33   struct linear_congruential_engine_discard_implementation
  34 {
  35   __host__ __device__
  36   static void discard(UIntType &state, unsigned long long z)
  37   {
  38     for(; z > 0; --z)
  39     {
  40       state = detail::mod<UIntType,a,c,m>(state);
  41     }
  42   }
  43 }; // end linear_congruential_engine_discard
  44
  45
  46 // specialize for small integers and c == 0
  47 // XXX figure out a robust implemenation of this for any unsigned integer type later
  48 template<thrust::detail::uint32_t a, thrust::detail::uint32_t m>
  49   struct linear_congruential_engine_discard_implementation<thrust::detail::uint32_t,a,0,m>
  50 {
  51   __host__ __device__
  52   static void discard(thrust::detail::uint32_t &state, unsigned long long z)
  53   {
  54     const thrust::detail::uint32_t modulus = m;
  55
  56     // XXX we need to use unsigned long long here or we will encounter overflow in the
  57     //     multiplies below
  58     //     figure out a robust implementation of this later
  59     unsigned long long multiplier = a;
  60     unsigned long long multiplier_to_z = 1;
  61
  62     // see http://en.wikipedia.org/wiki/Modular_exponentiation
  63     while(z > 0)
  64     {
  65       if(z & 1)
  66       {
  67         // multiply in this bit's contribution while using modulus to keep result small
  68         multiplier_to_z = (multiplier_to_z * multiplier) % modulus;
  69       }
  70
  71       // move to the next bit of the exponent, square (and mod) the base accordingly
  72       z >>= 1;
  73       multiplier = (multiplier * multiplier) % modulus;
  74     }
  75
  76     state = static_cast<thrust::detail::uint32_t>((multiplier_to_z * state) % modulus);
  77   }
  78 }; // end linear_congruential_engine_discard
  79
  80
  81 struct linear_congruential_engine_discard
  82 {
  83   template<typename LinearCongruentialEngine>
  84   __host__ __device__
  85   static void discard(LinearCongruentialEngine &lcg, unsigned long long z)
  86   {
  87     typedef typename LinearCongruentialEngine::result_type result_type;
  88     const result_type c = LinearCongruentialEngine::increment;
  89     const result_type a = LinearCongruentialEngine::multiplier;
  90     const result_type m = LinearCongruentialEngine::modulus;
  91
  92     // XXX WAR unused variable warnings
  93     (void) c;
  94     (void) a;
  95     (void) m;
  96
  97     linear_congruential_engine_discard_implementation<result_type,a,c,m>::discard(lcg.m_x, z);
  98   }
  99 }; // end linear_congruential_engine_discard
 100
 101
 102 } // end detail
 103
 104 } // end random
 105
 106 } // end thrust
 107