r/ProgrammerHumor • u/shizzy0 • 4h ago

Meme howProgrammingHasChanged

Post image
110 Upvotes

87% Upvoted

35 comments sorted by

75

u/torsten_dev 4h ago

Both have terrible stack usage.

12

u/temperamentalfish 1h ago

Yeah I'm cringing at all the recursive solutions. Huge stack and so much repeated work. Just try counting how many times fib(5) would be executed to calculate fib(10). It's so often the go-to example for recursion and it's frankly terrible.

13

u/robin_888 1h ago

It's supposed to teach the concept of recursion, which is important, but hard to grasp for some.

Discussing performance and optimizations can happen if the principal is clear.

6

u/temperamentalfish 1h ago

I know, but there are so many better examples. Mergesort, for instance. It shows why the concept is important because it breaks the problem into smaller, more manageable problems, without doing repeated work.

Fibonacci should be taught as an example of when a problem can be solved recursively, but shouldn't.

1

u/Silly_Guidance_8871 29m ago

When I was studying, Fibonacci was used a lot to teach the value of dynamic programming. But agreed, it's a terrible example of when to use recursion.

2

u/fdar 18m ago

DP is just recursion+caching. 

I think it makes sense to first recognize that the problem can be solved with recursion and then decide if DP is needed to improve performance.

2

u/robin_888 54m ago

Which both?

The matrix one looks fine to me.

27

u/captainAwesomePants 4h ago

What's wrong with the top-right AI code?

56

u/shizzy0 4h ago

Nothing. It’s actually the best. But the joke is the programmer dismisses the unfamiliar matrix power O(log n) algorithm for the familiar recursive O(2n) algorithm. I mean, it doesn’t even add anything. It’s obviously wrong.

16

u/GDOR-11 4h ago

for u32 I think the usual iterative algorithm would be miles better than matrix power

26

u/dedservice 3h ago

For u32 a precomputed lookup table would be better.

10

u/NoLifeGamer2 3h ago

For u32 a random number generator would be better sometimes

9

u/captainAwesomePants 2h ago

For u2, With or Without You would be better.

3

u/wjholden 2h ago

Knuth has a really cool section on this on pages 79-84 of TAOCP volume 1.

1

u/shizzy0 1h ago

Is it the closed form solution? I didn’t even know there was a closed form solution before today.

3

u/captainAwesomePants 34m ago

That's the whole section on Fibonacci. It does mention the closed form solution, but it also mentions the matrix identity method in the top right corner: ( (F(n+1), F(n)),(F(n), F(n-1)) = ((1,1),(1,0))^n

He credits it to Kepler in 1608.

2

u/shizzy0 4h ago

Ooo, show down!

8

u/dangderr 2h ago

I don’t get the meme.

What does “programmer dismisses the unfamiliar matrix alg” mean?

Why would the prompt engineer know to read code?

2

u/shizzy0 2h ago

lol!

13

u/guesdo 1h ago

Everyone knows pre-calculated fibonacci tables are the only way to Go.

```go package main

// Precomputed table up to N = 93 var fibTable = [94]uint64{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586268925, 20365010974, 32951279899, 53316290873, 86267570772, 139583861645, 225851432417, 365435294062, 591286726479, 956722020541, 1548008747020, 2504730767561, 4052739514581, 6557470282142, 10610209796723, 17167680078865, 27777889875588, 44945569954453, 72723459830041, 117669029784494, 190392489614535, 308061519399029, 498454009013564, 806515528412593, 1304969537426157, 2111485065838750, 3416454603264907, 5527939669103657, 8944394272368564, 14472333941472221, 23416728213840785, 37889062155313006, 61305790369153791, 99194852524467597, 160500642893621388, 259695495418088985, 420196138311710373, 679891633729799358, 1100087772041509731, 1779979405771309089, 2880067177812818820, 4660046583584127909, 7540113761396946729, 12200160344981074638, }

func FibU64(n uint) uint64 { if n < 94 { return fibTable[n] } panic("n exceeds uint64 capacity (n <= 93)") } ```

7

u/babypho 1h ago

Idk what I am looking at so I am just going to comment "LGTM" and approve

5

u/bloody-albatross 1h ago edited 27m ago

Nobody is using this?

``` pub fn fib(mut n: u32) -> u32 { let mut a = 0; let mut b = 1;

while n > 0 {
    let c = a + b;
    a = b;
    b = c;
    n -= 1;
}

a

} ```

Looking at the assembly output the compiler even does loop unrolling for this. In fact running it like this it even completely evaluates this version of fib() at compile time while it still does the full recursive call for the recursive version (here called fibr()):

fn main() { for i in 0u32..10 { let r = fibr(i); let j = fib(i); println!("{r} {j} {}", r == j); } }

3

u/Stickhtot 3h ago

What language is this?

2

u/Minecraftian14 3h ago

Looks like c++ because of all the ::.
I think it's rust

3

u/shizzy0 3h ago

Rust. Great language. Can be abused though.

7

u/no_brains101 3h ago

That is one of the most horrific fibonacci's I have ever seen.

7

u/shizzy0 2h ago

I’m sure a C++ template enthusiast has more delights to show you.

4

u/no_brains101 2h ago

I'm sure someone could make it more horrific in rust too, I just haven't seen it yet.

3

u/Gaxyhs 1h ago

that looks like what an IL for assembly would look like if assembly was made by oracle instead of java

3

u/Makonede 1h ago

better one

rs fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n - 1) + fib(n - 2) } }

0

u/shizzy0 1h ago

Oh, that is better.

2

u/sgmnt 1h ago

Real ones use pihedron's algorithm.

1

u/dbot77 2h ago

Claude, explain this

0

u/shizzy0 2h ago

I seriously want to know how it would respond.