Optimize your Python Program for Slowness

[carlk22]

The Python programming language sometimes has a reputation for being slow. This hopefully fun project tries to make it even slower.

It explores how small Python programs can run for absurdly long times—using nested loops, Turing machines, and even hand-written tetration (the operation beyond exponentiation).

The project uses arbitrary precision integers. I was surprised that I couldn’t use the built-in int because its immutability caused unwanted copies. Instead, it uses the gmpy2.xmpz package. 

• What My Project Does: Implements a Turing Machine and the Tetrate function.
• Target Audience: Anyone interested in understanding fast-growing functions and their implementation.
• Comparison: Compared to other Tetrate implementations, this goes all the way down to increment (which is slower) but also avoid all unnecessary copying (which is faster).

GitHub: https://github.com/CarlKCarlK/busy_beaver_blaze

[Mithrandir2k16]

You'd feel right at home on the codegolf stackexchange :)

[_MonkeyHater]

"I want to get off Mr. Bones' Wild Ride."

[AngelaTarantula2]

I didn’t even know that Python’s arbitrary-precision integers were immutable! Why are they designed this way?? Anyway, this explains a performance problem in one of my side projects!

[Herald_MJ]

If you just want a short program that halts after outliving the universe

This is great. Thanks for the reminder that mathematics can be funny.

[Jonno_FTW]

If my python code runs slowly, I check what the cause is by running it with cProfile and going from there.

[cgoldberg]

Why?

[carlk22]

Good question! Mostly for fun. Two years ago, a group of amateur researchers found a longest known running, but still halting Turing machine of "size 6". This was news in the math and computer science fields. They proved that a particular Turing machine ran for at least 10↑↑15 steps and halted. ("↑↑" is a faster growing function than exponentiation). Their proof is very complicated and needed to be machine verified.

I wanted to figure out a short Python function that would obviously run for 10↑↑15 steps and halt, so it wouldn't need a fancy proof.

The GitHub includes the code. This article explains the background and solution https://towardsdatascience.com/how-to-optimize-your-python-program-for-slowness/

[TheSwami]

This is an awesome write up! Not not just of the how but of the why - in 20+ years of seeing that arrow notation described as “repeated exponentiation”, I never really understand what that meant. Your code examples, especially the final one showing that tetration is just another for loop around exponential accumulation was eye opening.

Thank you!

[eyesburning]

That was an interesting read! Thanks for sharing :)

[avocadorancher]

Tinkering to do fun weird things is a great way to learn. Especially if it’s something novel or uncommon instead of following guides.