Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]

by

In the line

result = mymod((result * x),d);

in result * x your both result and x can be as large as d (more precisely, d-1), so you need a data type that can hold integers as big as d*d. For your cases, this may be long long int.

Another approach will be not to use library operator* for ints, but implement a manual multiplication function with a similar divide and conquer approach using only additions. This way you will need a data type that can hold integers as big as 2d only.

Also note that you do not need to call mymod each time in the main loop. You can call it only once before the loop to make x positive (x=mymod(x,d)), and then use just the operator%.

More Related Contents:

  1. Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraint
  2. Where can I find source or algorithm of Python’s hash() function?
  3. Removing duplicates in lists
  4. How to generate all permutations of a list?
  5. How to split text without spaces into list of words
  6. Python string ‘in’ operator implementation algorithm and time complexity
  7. Algorithm to find which number in a list sum up to a certain number
  8. Checking if all elements in a list are unique
  9. Py_initialize / Py_Finalize not working twice with numpy
  10. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  11. Extending setuptools extension to use CMake in setup.py?
  12. How do I convert a Python list into a C array by using ctypes?
  13. Weighted random sample in python
  14. Run a python script with arguments
  15. What’s the algorithm of ‘set.intersection()’ in python?
  16. How to incrementally sample without replacement?
  17. Replace list of list with “condensed” list of list while maintaining order
  18. Python Weighted Random [duplicate]
  19. How can I interleave or create unique permutations of two strings (without recursion)
  20. How to pass a 2d array from Python to C?
  21. Calling Python script from C++ and using its output
  22. Building Mesa for windows 7. Mesa 9.1
  23. Python: powerset of a given set with generators [duplicate]
  24. Embedding Python in C, linking fails with undefined reference to `Py_Initialize’
  25. Writing code translator from Python to C? [closed]
  26. Installing lxml for Python 3.4 on Windows x 86 (32 bit) with Visual Studio C++ 2010 Express
  27. What is this odd sorting algorithm?
  28. counting combinations and permutations efficiently
  29. Extending python – to swig, not to swig or Cython
  30. Call python code from c via cython

Leave a Comment