need for speed

I had my first recitations for the new session's physics class today. It went pretty rough. The class is non-calc E&M. I think I like the calc-based classes better. I was supposed to go through three problems, but I got through one in the first recitation and two in the second. On top of that, I got the late afternoon sessions, everybody's already spaced out by then. Fortunately I only have six more work days for this session. One is tomorrow. Hopefully in the fall I can snag a calc-based physics TA spot.

I killed the time between recitations by going over the new modular exponentiation algorithm I found a couple days ago. It's really not so much the math that's the clever bit as the implementation in the code. I put it into my program and ran it side by side with the old method. I was expecting maybe Corvette vs. Model T results. It's more like the speed of light vs. a Model T. Probably worse. The new method is so fast that its processing time doesn't even register, even when I max out the new unsigned long long variables. Here is why the new method is faster:

Problem: 4353^(10^18) mod 13562
Number of operations required for old method: 10^18.
Number of operations required for new method: 60.

So I'm using the new method from now on.

I'm somewhat tempted to get bigger numbers, but I estimate that even the mythical thousand digit data type would take 3325 operations at most. Working that out proved that the algorithm goes as the log of the exponent. Somebody somewhere was very clever indeed.

I might poke at the RSA stuff a little more tonight, but more likely playing the pirate game and going to bed early.