How programming has changed.
2 Boosts
0 Likes
@ygor Wow. [Claps.] Excellent. What an indulgence of Rust that is.
2/ I wanted to do this one for the AI idiot, but it was too long.
It's the same iterative matrix power fibonacci O(log n) algorithm just with the matrix power operation spelled out in a loop. One could complain, "It doesn't even have any + operation. It's obviously wrong."
![The iterative matrix power fibonacci O(log n) algorithm just with the matrix power operation spelled out in a loop. One could complain, "It doesn't even have any + operation. It's obviously wrong."
```rust
fn fib(mut n: u32) -> u32 {
let mut a = Mat2::identity();
let mut b = Mat2::new(
1u32, 1, 1, 0
);
while n > 0 {
if n & 1 != 0 {
a *= b;
}
b *= b;
n >>= 1;
}
a[(0, 1)]
}
```](https://cdn.masto.host/mastodongamedevplace/media_attachments/files/117/435/346/529/547/565/original/e67e9d356ea18c28.png)
The approximation Round[Exp[Log[GoldenRatio]*n - Log[5]/2] is O(1) in both space and time when using IEEE doubles and is exact when n is an integer between 0 and 78 with graceful degradation to n = 1476
@Arpie4Math A Mathematica user, I see, a man of taste. Yes, that is the most practical and seemingly least well known.
3/ If you need a big O refresher, here's how it's used on the street.
@shanecelis plz you will summon the Kool-Aid guy
@bms “Wait, do you want to be a wizard or a programmer?”
“Yes.”
* * *
“I write down linked list insertion.”
Party looks on dumbfounded. “What’s that supposed to do?!”
Player looks at the GM who sighs. “A red monstrosity breaks through the wall screaming, ‘OHHHH YEEEAAAAH!’”
4/ Ok, the joke is that the AI's algorithm is O(log n) but the human only accepts the O(2^n) algorithm because that's the one they recognize.
One of the comments on reddit sent me…
> I don’t get the meme. What does “programmer dismisses the unfamiliar matrix alg” mean? Why would the prompt engineer know to read code?
@shanecelis Thank your for this short programming primer for my kid :-)
We went through fast fibonacci algorithms, tail recursion, matrix multiplication and ended with the wikipedia article about asymptotic computational complexity.
@shanecelis How about this?
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=8b9878125f5725b4b271372be806a565
Rust Playground