Ways to do modulo multiplication with primitive types

by

You should use Russian Peasant multiplication. It uses repeated doubling to compute all the values (b*2^i)%m, and adds them in if the ith bit of a is set.

uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
    int64_t res = 0;
    while (a != 0) {
        if (a & 1) res = (res + b) % m;
        a >>= 1;
        b = (b << 1) % m;
    }
    return res;
}

It improves upon your algorithm because it takes O(log(a)) time, not O(a) time.

Caveats: unsigned, and works only if m is 63 bits or less.

More Related Contents:

  1. How to find number of words in a phrase with spaces removed by checking v. dictionary
  2. Create an algorithm that asks the user for two positive numbers, call them “first” and “last”, and prints the sum of all the numbers between first [closed]
  3. How to implement classic sorting algorithms in modern C++?
  4. Determine if two rectangles overlap each other?
  5. What is the efficient way to count set bits at a position or lower?
  6. Fast exact bigint factorial
  7. Generating combinations in c++
  8. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  9. Lock-free Progress Guarantees in a circular buffer queue
  10. Finding duplicates in O(n) time and O(1) space
  11. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  12. Emulate “double” using 2 “float”s
  13. How to get a random element from a C++ container?
  14. LRU cache design
  15. c++ sort keeping track of indices [duplicate]
  16. Need for predictable random generator
  17. Determining if a number is prime
  18. Reorder vector using a vector of indices [duplicate]
  19. Iterative DFS vs Recursive DFS and different elements order
  20. Converting epoch time to “real” date/time
  21. Searching in a sorted and rotated array
  22. `std::list::sort()` – why the sudden switch to top-down strategy?
  23. How can I sort an STL map by value?
  24. Easiest way of using min priority queue with key update in C++
  25. What is the safe way to fill multidimensional array using std::fill?
  26. Cut set of a graph, Boost Graph Library
  27. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  28. Why there is no std::copy_if algorithm?
  29. priority queue with limited space: looking for a good algorithm
  30. How can I test whether a number is a power of 2?

Leave a Comment