fork(2) download
copy 
  1. #include <stdint.h>
  2. #include <tuple>
  3. #include <iostream>
  4.  
  5. typedef std::tuple< uint32_t, uint32_t > split_t;
  6. split_t split( uint64_t a )
  7. {
  8.     static const uint32_t mask = -1;
  9.     auto retval = std::make_tuple( mask&a, ( a >> 32 ) );
  10.     // std::cout << "(" << std::get<0>(retval) << "," << std::get<1>(retval) << ")\n";
  11.     return retval;
  12. }
  13.  
  14. typedef std::tuple< uint64_t, uint64_t, uint64_t, uint64_t > cross_t;
  15. template<typename Lambda>
  16. cross_t cross( split_t lhs, split_t rhs, Lambda&& op )
  17. {
  18.     return std::make_tuple( 
  19.         op(std::get<0>(lhs), std::get<0>(rhs)),
  20.         op(std::get<1>(lhs), std::get<0>(rhs)),
  21.         op(std::get<0>(lhs), std::get<1>(rhs)),
  22.         op(std::get<1>(lhs), std::get<1>(rhs))
  23.     );
  24. }
  25.  
  26. // a and c must have high bit unset:
  27. uint64_t a_times_2_k_mod_c( uint64_t a, unsigned k, uint64_t c )
  28. {
  29.     a %= c;
  30.     for (unsigned i = 0; i < k; ++i)
  31.     {
  32.         a <<= 1;
  33.         a %= c;
  34.     }
  35.     return a;
  36. }
  37.  
  38. uint64_t a_times_b_mod_c( uint64_t a, uint64_t b, uint64_t c )
  39. {
  40.     // ensure a and b are < c:
  41.     a %= c;
  42.     b %= c;
  43.  
  44.     auto Z = cross( split(a), split(b), [](uint32_t lhs, uint32_t rhs)->uint64_t {
  45.         return (uint64_t)lhs * (uint64_t)rhs;
  46.     } );
  47.  
  48.     uint64_t to_the_0;
  49.     uint64_t to_the_32_a;
  50.     uint64_t to_the_32_b;
  51.     uint64_t to_the_64;
  52.     std::tie( to_the_0, to_the_32_a, to_the_32_b, to_the_64 ) = Z;
  53.  
  54.     // std::cout << to_the_0 << "+ 2^32 *(" << to_the_32_a << "+" << to_the_32_b << ") + 2^64 * " << to_the_64 << "\n";
  55.  
  56.     return
  57.         (to_the_0
  58.         + a_times_2_k_mod_c(to_the_32_a%c+to_the_32_b%c, 32, c)
  59.         + a_times_2_k_mod_c(to_the_64, 64, c) )
  60.     %c;
  61. }
  62.  
  63. int main()
  64. {
  65.     uint64_t retval = a_times_b_mod_c( 19010000000000000000, 1011000000000000, 1231231231231211 );
  66.     std::cout << retval << "\n";
  67. }
Success #stdin #stdout 0s 2896KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
946004848926081
https://ideone.com/0TFtz0
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!