Shortcut & Epta
Yo Epta, heard you’re brewing another code alchemy experiment, mind if I throw a speedrunning challenge at you? Whoever can squeeze the most cycles into the same function wins.
Sure thing, but just a heads‑up I won’t be using semicolons in my code or in my rant about it; that would be too easy for the compiler to bite back. Bring the challenge, I’ll craft a function that slashes cycles like a samurai with a well‑tuned blade. Just remember, I’ll hate any pop‑ups that try to interrupt my ritual. Ready when you are.
Cool, let’s see how fast you can slice this: write a function that returns the nth Fibonacci number in O(log n) time with no loops, just matrix exponentiation or fast doubling. No semicolons, no pop‑ups, pure code. Show me the trimmed‑down version, no fluff. Let's race!
Here’s the function, no loops, no semicolons, no pop‑ups, pure recursion:
def fib(n):
if n == 0:
return 0
def helper(k):
if k == 0:
return (0,1)
a,b = helper(k//2)
c = a*(2*b - a)
d = a*a + b*b
return (c,d) if k%2==0 else (d,c+d)
return helper(n)[0]
Nice cut, that’s tight and fast. Just one tweak: keep the helper outside the main to avoid redefining on every call if you plan to call it many times. But for a single call, you’re solid—no loops, no semicolons, pop‑ups handled. Ready to push the limit? Let's try a larger n and see how the stack holds.
Sure thing, stack depth is only about log₂n so a million isn’t a problem if you bump Python’s limit a bit. Just run it and watch the stack grow like a quiet mountain—no pop‑ups, no loops, just pure recursion. Let me know how far you push it.
If you crank it up to a million, you’ll hit Python’s default recursion limit (about 1000). Raise it first:
```
import sys
sys.setrecursionlimit(20000)
```
Then call `fib(10**6)`. The depth will be around 20, because each step cuts the problem size in half, so you’re good. Just keep an eye on memory – each stack frame stores a tuple and a few ints. No pop‑ups, no loops, just pure recursion. Give it a whirl.
That’s the trick – bump the limit, keep the recursion shallow enough. Just be careful with the memory cost of those tuples; a million frames will still be fine once you hit the ~20 depth you mentioned. Happy to watch your stack grow, just keep an eye on the heap, and you’ll avoid any pop‑up surprises. Give it a run and let me know how fast the numbers cascade.
Tried it—set `recursionlimit` to 20000 and ran `fib(10**6)`. Depth stayed at 20, each frame just a few ints and tuples, so the heap barely moved. It returned in under a millisecond on my machine; the number has over two million digits but computing it was practically instant—no pop‑ups, no loops, pure recursion doing its thing.
Nice, looks like the recursion trick paid off and the stack stayed tight—just a few frames, a few ints, and a handful of tuples. Those 2‑million‑digit numbers are a good reminder that speed isn’t always about the amount of data, but how you slice it. If you ever want to squeeze more out, just tweak the base case or push the recursion limit a tad higher, but for now, you’ve got the perfect, pop‑up‑free fast‑doubling recipe. Keep crunching!
Great to hear the numbers came through clean—no pop‑ups, no slowdown. If you want to push further, we could try a streaming version that keeps only the last two values, or even tweak the recursion to handle larger n with a lower memory footprint. Let me know what’s next, and I’ll line it up for the next speed record.
Nice, glad it ran smooth. Next I’m thinking a matrix‑based exponentiation that only keeps a two‑element vector in memory – that’ll cut the footprint further and let me push to a larger n without touching the stack. I’ll line that up and see if the speed record can be shattered without a single pop‑up. Ready when you are.
Sounds good, hit me with that vector version and let’s see if we can squeeze out more milliseconds. Bring the code—no pop‑ups, just pure speed.
def fib_vec(n):
if n==0: return 0
def step(k):
if k==0: return (0,1)
a,b = step(k//2)
c = a*(2*b - a)
d = a*a + b*b
return (c,d) if k%2==0 else (d,c+d)
return step(n)[0]
Nice, that’s a clean version—no semicolons, just pure recursion. Since step only goes log₂n deep, the stack stays tight and the heap barely moves. If you want to push even further, you could inline the logic or switch to an iterative matrix multiply, but for a single call this is already blazing fast. Give it a run on 10⁸ and watch the numbers cascade—no pop‑ups, just raw speed.