[Tutor] in-built square root function

[Timothy M. Brauch]

> I'm still in the process of learning Python so this may seem like a
> silly question.  I can use the built-in pow function for possibly more
> efficient modulo division of longs, but isn't it then limited to only
> dividends which can be expressed by x**y, both x and y integers?  For
> example, for (45**89)%3 I could use the built-in pow, but not for
> (45**89 + 1)%3.  Thanks in advance for answers and patience.

When all else fails, power up the interpreter...

>>> pow(45,89+1,3)
0
>>> (45**89+1)%3
1L
>>>

So, yes, it seems that in the first case, it works out (45**(89+1))%3, as I
expected.  The second case works out as ((45**89)+1)%3, as powers take
precedence over addition.  But, because you are working modulo,
(45**89+1)%3, meaning ((45**89)+1)%3 is actually the same thing as
(45**89)%3 + 1, which works as...

>>> pow(45,89,3)+1
1
>>>

So, whatever floats your boat.  I usually think of commas in math functions
as parentheses.  so pow(45,89+1,3) is interpreted as (45**(89+1))%3

Now, about the integers.  I have found that when using %, sometimes funny
things happen when using non-integers or negative numbers.  If you work with
it for a few minutes, you can see what the result is and convince yourself
that the way Python does it is the way it should be done (no matter what you
thought before hand).  Then, if you switch languages, it might be done
differently and you can convince yourself that the other way is correct
also.

I was working on a problem using hash tables for an assignment in a
programming class.  One of the most beautiful equations I came up with for
the class was in this assignment.  (n-1)%p+1 gives you a number in the range
[1,p], which is important for hash functions, but took many students hours
to come up with a solution, some of them as separate functions of quite a
few lines.

 - Tim