×

# Fast exponentiaion and multiplication

 0 Hi, I am unable to understand the iterative version of fast modular exponentiation code. long long prod(long long a, long long b, long long mod = MOD) { long long res = 0; while(b) { if(b & 1) res = (res + a) % mod; a = (a + a) % mod; b >>= 1; } return res; } long long bpow(long long a, long long b, long long mod = MOD) { long long res = 1; while(b) { if(b & 1) res = prod(res, a, mod); a = prod(a, a, mod); b >>= 1; } return res; }  The prod function does overflow safe multiplication, again similar to fast exponentiation code, but hard to get. asked 25 Aug '18, 14:16 1 accept rate: 0%

 0 Recursive version of fast modular exponentiation is easy to understand, so first you should try the recursive version function power (a,b,m): if b == 0: return 1 else if b == 1: return a % m t = power (a,b/2) if b % 2 == 0: return (t * t) % m else : return (t * t * a) % m  It is the recursive algorithm for fast exponentiation, try to get it first. answered 25 Aug '18, 15:14 5★admin5 226●9 accept rate: 18%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×153
×90
×24
×4

question asked: 25 Aug '18, 14:16

question was seen: 99 times

last updated: 25 Aug '18, 14:16