Number Theory

[Robert Maxwell]

When you write your Python program, try switching between the my_exp and my_exp2 algorithms. I wouldn't be surprised if you actually notice the speed difference, at least outside of really tiny n. (Please report whether you can?)

Will do!

Interesting that it takes more work to calculate the inverse than to check it

This is extremely common, and is in fact a very important principle.

http://en.wikipedia.org/wiki/P_versus_NP_problem

Yup, I know about P vs. NP. Fascinating stuff. Although only CC's my_exp2 is actually polynomial. my_exp is O(log(n)) which is pretty efficient, just not nearly as efficient as checking the inverse!

 

[YellowSubmarine]

Well, it's not like inverting x^y (mod n) is any faster.

 

[Crewman Commander]

Actually, my_exp2 has an exponential runtime.

That is to say, its runtime is exponential in the number of significant bits in the input (on a hypothetical ideal machine that can take arbitrary precision input). my_exp2 loops over every positive value that does not exceed one of the input parameters, namely y. That's exponentially many iterations in the number of significant bits in y.

That's why it's so bad.

 

[Lindley]

my_exp is O(log(n)) which is pretty efficient, just not nearly as efficient as checking the inverse!

In my experience, you have to have some absolutely massive inputs before the difference between O(log n) and O(1) really matters.

 

[YellowSubmarine]

In my experience, you have to have some absolutely massive inputs before the difference between O(log n) and O(1) really matters.

Yeah. The O(log n) algorithm would work on a dataset the size of the Internet (circa 2008) a mere 50 times slower than the O(1) one. That's probably less than the overhead of arithmetic in Python. If the dataset was made up of all the particles in the known universe, it will still be only about 300 times slower. Right about the speed of INTERCAL?! It also might be the difference between your phone and a supercomputer from a decade or two ago. If the supercomputer couldn't process the universe, now your phone can!

I had teacher who got lazy and labelled O(log n) as O(1). Very sloppy, I did not approve, but he was right as far as any practical purposes were concerned.

 

[Lindley]

Then there's the disjoint set algorithm with union by rank and path compression, in which the time complexity is the inverse Ackermann function, which grows so slowly it makes log n look exponential by comparison....