0

this question is different from [Exponentials in python x.**y vs math.pow(x, y) because a snippet using math.pow() cannot compute result, while the ** operator can.

I am experimenting with a little snippet to compute first N doubly prime numbers with Fermat's Little theorem:

per 1<= a < n,

if a^n mod(n) = a mod(n) then n is a Prime

http://en.wikipedia.org/wiki/Fermat%27s_little_theorem http://en.wikipedia.org/wiki/Fermat_pseudoprime

I found that:

math.pow(a,n) % n == a % n

yields to overflow error:

math range error

for: a = 2, n == 1508950

instead with ** operator works fine: 2**1508950 yields ... a very, very, very long number :)

2**1508950 = 1629135338929954... #with 450K+ and counting digits.

Python documentation states that The two-argument form pow(x, y) is equivalent to using the power operator: x**y.

Why this difference ?

Community
  • 1
  • 1
user305883
  • 1,635
  • 2
  • 24
  • 48
  • 1
    math.pow works with floats and two "*" works with the type of operand: ie: `math.pow(2, 3)` give 8.0 and `2* *3` give 8. Instead, `pow` (built-in) works the same two "*". – Clodion Apr 18 '16 at 11:55
  • Clodion your comment should be marked as answer, I was just now reading about it here [http://stackoverflow.com/a/10283032/305883] : @Martijn Pieters I think this would be the appropriate reference to mark this question as duplicate. – user305883 Apr 18 '16 at 12:08
  • @user305883: done. – Martijn Pieters Apr 18 '16 at 12:10
  • You should use the optional third argument to the `pow` function: `pow(x,y,m)` is equivalent to `pow(x,y)%m`, but all the calculations are done mod _m_ and will not involve the large intermediate numbers. – user448810 Apr 18 '16 at 14:03
  • @user448810 yes I tried that, I would like to better understand which is the difference in time complexity (big O notation) between the two implementation: how does python handle the two operations without "involving the large intermediate numbers"? I also tried `pow(a,n, n) == a % n` which is different then `b = pow(a,n, n) if b == (a % n) : // do something` : it looks like the first is computed "on the fly" with "no need to store in memory". – user305883 Apr 18 '16 at 19:31
  • 1
    See my answer [here](http://stackoverflow.com/a/28140940/448810). That answer uses a method called [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring), except that all multiplications are done using modular arithmetic. – user448810 Apr 18 '16 at 20:21

0 Answers0