4 ms·
Yes I see. So, I assume there must be a quicker way to work out x ^ n that incorporates wrapping than just doing x = x * x % y repetitively. Darn it, my maths
by weavie 13y ago
Yes I see.
So, I assume there must be a quicker way to work out x ^ n that incorporates wrapping than just doing x = x * x % y repetitively. Darn it, my maths is getting rusty in my old age.
- ColinWright 13y agoThere is a fast exponentiation that is effectively Russian Peasant Multiplication, and it works in time proportional to number of bits in the exponent. Look up "fast exponentiation" or similar.
- weavie 13y agoGot it. This has been very enlightening. Thanks.
- sluukkonen 13y agoThere is. x^n = (x^(n/2))^2 if n is even, (x^(n-1/2))^2 if n is odd, so it's possible to exponentiation in logarithmic time.