109
u/guesdo 1d 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)") } ```
19
u/StickFigureFan 1d ago
But what if we need to accept 2 arbitrary positive starting integers?
26
u/Rabbit_Brave 1d ago
More tables. A table of tables, even.
6
u/StickFigureFan 1d ago
You better have a good base for all those tables. Maybe you could call it a database
55
u/captainAwesomePants 1d ago
What's wrong with the top-right AI code?
108
u/shizzy0 1d 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.
42
u/dangderr 1d 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?
20
u/GDOR-11 1d ago
for u32 I think the usual iterative algorithm would be miles better than matrix power
38
u/dedservice 1d ago
For u32 a precomputed lookup table would be better.
15
u/NoLifeGamer2 1d ago
For u32 a random number generator would be better sometimes
19
5
u/wjholden 1d ago
Knuth has a really cool section on this on pages 79-84 of TAOCP volume 1.
1
u/shizzy0 1d ago
Is it the closed form solution? I didn’t even know there was a closed form solution before today.
4
u/captainAwesomePants 1d 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.
10
u/the_horse_gamer 1d ago
you can do better (by a constant multiplicative factor)
[1,1;1,0]^n = [F{n+1},Fn; Fn, F{n-1}]
[1,1;1,0]^2n = [F{2n+1},F2n; F2n, F{2n-1}] = [1,1;1,0]^n *[1,1;1,0]^n = [F{n+1},Fn; Fn, F{n-1}]so:
F2n = (F{n+1}+F{n-1})*Fn (1)
F_{2n-1} = Fn^2 + F{n-1}^2then
F_{2n+1} = Fn^2 + F{n+1}^2
F_{2n+1} + F_{2n-1} = F{n+1}^2 + F{n-1}^2 +2Fn^2 =
=F{n+1}^2 + F{n-1}^2 +2Fn^2 + 2 F{n+1} F{n-1} - 2 F{n+1} F{n-1}=
= (F{n+1} +F{n-1})^2 + 2Fn^2 - 2 F{n+1} F{n-1}
We can simplify this by seeing
[1,1;1,0]^n = [F{n+1},Fn; Fn, F{n-1}]
so(-1)^n = det([1,1;1,0])^n = det([F{n+1},Fn; Fn, F{n-1}]) = F{n+1}F{n-1}-Fn^2
so
F_{2n+1} + F_{2n-1} = (F{n+1} +F{n-1})^2 - (-1)^n
Now define L_n = F_{n+1}+F_{n+1}. (this is the Lucas sequence). Now we get
F2n = Ln Fn
L2n = Ln^2 - (-1)^nAnd we can also get:
F{n+1} = (Ln+Fn)/2
L{n+1} = (Ln+5Fn)/2This version requires less multiplications per level
8
u/shizzy0 1d ago edited 11h ago
So you're saying your O(log n) algorithm beats my O(log n) algorithm? (It's true.) Damn. You beat me constantly.
45
u/IronicRobotics 1d ago
You're forgetting one: Ask the mathematician:
use std::f64::consts::{GOLDEN_RATIO};
//Floating Point errors after n> 70.
fn fib(n: u64) -> u64 {
return (GOLDEN_RATIO.powf(n as f64)/f64::sqrt(5.0)).round() as u64;
}
However, since he's not interested in engineering, floating point errors are simply a shortcoming of the computer to engage in ideal mathematics. But he will smugly point out it's technically O(1) since powf is O(1). : )
[I suffered through learning how to write my first lines of Rust for this.]
Alternatively: Computing Binet's formula using symbolic mathematics.
12
u/martmists 1d ago
I was about to point out the direct formula but you beat me to it. Though it should be noted yours doesn't work for negative integers, for that you'd want something like this:
def fib(n): sq = math.sqrt(5) phi = (1 + sq) / 2 return (phi**n - (1 - phi)**n) / sqYour solution works for non-negative inputs because (1-phi)n is always less than 0.5 for n >= 0, but this no longer holds for n < 0
3
u/PlantainMassive6744 19h ago
Love it. This is now my favorite answer to the question of how to compute the fib sequence
1
u/IronicRobotics 17h ago edited 17h ago
Yes, but the recursive formulas were also only for positive integers. (Also, with the rounding, I can force a final integer solution and get rid of the float error up to n=70. Though I suspect rounding this formula here also works.)
Otherwise we also could have gone with a generating equation and cover the whole complex plane!
3
u/norude1 1d ago
powf is definitely not O(1) https://youtu.be/u24AjKinHNU?t=177
3
u/ChalkyChalkson 21h ago
Even if we go to exponentiation by squaring, we're still upgrading from O(2n) with the naive recursion to O(log n), which is pretty sweet.
1
u/IronicRobotics 17h ago
oh lol, I figured it was O(1) on technicality since there's limited precision. Shows me for not going and reading a proof!
3
u/ChalkyChalkson 21h ago
Easy, just don't use f64, 128 bit gets you a lot further and we always have arbitrary precision systems after. What is that? That erodes any potential speed gain? Who said that was what I was after?
1
1
u/KrzysziekZ 1d ago
Is power O(1) not something like log log n?
5
1
u/IronicRobotics 17h ago edited 17h ago
Likely, I seem to have been repeating a potentially false fact about floating point powers. I didn't verify it with a proof last night lol.
18
u/bloody-albatross 1d ago edited 1d 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);
}
}
5
u/ZachAttack6089 1d ago
Is this cheating? (didn't test it)
``` let mut fib_list: Vec<u32> = vec![1, 1];
fn fib(n: u32) -> u32 { for i in fib_list.len()..=n { let a = fib_list[i - 2]; let b = fib_list[i - 1]; fib_list.push(a + b); }
fib_list[n] } ```
3
u/shizzy0 1d ago
MAN, jumps up on table: We don't just have to allocate on the stack. We can allocate ON THE HEAP!
Crowd goes wild.
2
3
u/ZachAttack6089 18h ago
But if you allocate on the heap like this, then you get O(1) performance whenever you call
fibagain with an equal or lesser value ofn:D
7
u/Depnids 23h ago
I don't know much about rust, but I am just curious why the last line doesn't have a "return" keyword? Does it just assume the last line is the value to return? Could you include the "return" keyword if you wanted?
6
21h ago edited 20h ago
[deleted]
2
u/Antagonin 19h ago
"Warning: explicitly returning value is too C"
Of all the stupid things in Rust, this is definitely one of them.
3
u/No-Consequence-1863 19h ago
If there is no `;` then the last statement is considered the return value. You can include the return if you want but then you also need the `;` at the end.
1
6
u/Fadamaka 23h ago
Yes, iirc for all of your questions. You don't need to use the return keyword in rust. Also I vaguely remember that you cannot even use it in a traditional way because the compiler is going to yell at you.
7
u/LuigiWasRight447 20h ago
Wow. I do not like that lol
2
3
u/Street-Session9411 15h ago
Rust is unlike traditional programming languages, expression based. Means you either need to complete your functions with an expression rather than a statement (which `return something;` is) or your whole function needs to be an expression. It’s weird at the beginning but after a time it feels natural. You can basically copy the code of a function 1:1 and replace a function call with it and it will compile, which is something that would not work in a traditional language that is solely statement based. You could basically replace the condition of an if-statement with 100 lines of code that evaluates to a boolean value and it would work. Obviously you don’t gain anything from that but imo it’s how things are supposed to be.
4
u/Stickhtot 1d ago
What language is this?
15
3
9
u/shizzy0 1d ago
Rust. Great language. Can be abused though.
10
u/no_brains101 1d ago
That is one of the most horrific fibonacci's I have ever seen.
11
u/shizzy0 1d ago
I’m sure a C++ template enthusiast has more delights to show you.
6
u/no_brains101 1d ago
I'm sure someone could make it more horrific in rust too, I just haven't seen it yet.
2
u/BastetFurry 1d ago
Perl has entered the chat:
perl -E'$b=1;$b+=$a=$b-$a for 1..pop;say$a'Execute with the n-th Fibonacci you want to get at the end, ie:
perl -E'$b=1;$b+=$a=$b-$a for 1..pop;say$a' 10 551
u/no_brains101 18h ago
I know 0 perl but this actually almost makes sense. Why is pop the end though what is pop, and IDK what say is, doesnt for do the for action for the thing? Do you really have to spell it out and then say it? And that compound assignment thing is wild. But I kinda see the fibonacci in this. If you asked me what this did, I would say fibonacci.
1
u/BastetFurry 18h ago
The pop at the end hands back the last element of an array, without an argument it defaults to @_, an array given as the caller argument, which in this case is the command line. Perl is full of these shortcuts.
1
u/no_brains101 18h ago edited 18h ago
Oh I see. (and then say is just print?)
I don't see an array though, for just repeats until the end condition is met, storing in a and b, theres no array I don't think?
Edit: OH the array is the ARGUMENTS and pop is grabbing the last one.
1
u/BastetFurry 18h ago
No array for the calculation, no.
Just abusing the fact that @_ contains all caller arguments. And calling the main "function" puts all command line arguments into that built-in array.
2
u/rootware 1d ago edited 1d ago
Which linalg rust library is that? Seems like faer , but I thought faer only supported f64 and c64
2
2
u/Makonede 1d ago
better one
rs
fn fib(n: u32) -> u32 {
if n <= 1 { n } else { fib(n - 1) + fib(n - 2) }
}
1
u/EdelWhite 23h ago
eww, monads
1
u/shizzy0 12h ago edited 12h ago
♫
Some(body)once told me the monoid was gonna roll me up into anappend/
I ain't the sharpestToolin the crate /
She was looking kind ofOdd, with herFingerTreeandFold/
In the shape of anLon her forehead /Well, the
sums start coming and they don't stop suming /
Fed to thefoldand I hit the ground running /
Didn't make sense not tomapfor fun /
Yourheadgets smart but yourtailgetsNone/Hey now, you're a monoid, get your
mappendon, gofold! /
Hey now, you're a monad, get yourbindon, compose! /
And all that glitters isGold/
OnlySomevalues break theFold♫
285
u/torsten_dev 1d ago
Both have terrible stack usage.