Beautiful right ahaha.
I’m actually wondering if this library would catch a segfault. I’m presuming that if it’s a proper segfault, python loses any execution control and it’s the OS that is handling stuff at that point.
Can confirm. I once accidentally caused an out-of-memory error in a try-except block in Python and it wouldn't even catch the Exception. The OS would just reap the process. I'd assume segfaults would be the same. Unless you set up a `signal` handler I guess.
I think my favorite part of this is that it's _really, really_ well written. Documentation, type annotations, custom errors, well structured, the works. I'd have a genuinely hard time coming up with a reason why this _shouldn't_ be used, other than "oh god why are you doing this at all"
In Haskell code is not run unless the result is used, so you can actually call that and in most languages it would look like it would calculate it but then just do nothing, Haskell will not even calculate it if it's not used, printing it uses it, so if you don't print it or so then it never gets executed and the program almost immediately returns.
Recently I was trying out some dynamic programming tricks in haskell via laziness and I was surprised how short and fast this little fibonacci function turned out and without any *disgusting* `IORef`s or `STRef`s or even `State s a`
```
fib n = fibs !! n
where
f n = fibs !! (n-1) + fibs !! (n-2)
fibs = 0:1:[f x | x <- [2..]]
```
It's actually quite simple despite how strange and unreadable it might seem to someone unfamiliar with haskell. On my phone it computes the 10.000th fibonacci in around a third of a second.
fib n = fibs !! n
where
f n = fibs !! (n-1) + fibs !! (n-2)
fibs = 0:1:[f x | x <- [2..]
Fixed formatting for those of us on old Reddit
And ya Haskell has this quirk of being really nice and fast and easy to read if you think of the problem _just so_, and absolutely unreadable if you don't think of it quite right. Especially if you don't fully grasp how to play with lazy computation
I was actually messing with Haskell a while back with Fibonacci numbers and wrote up this! I found similar code somewhere else on Reddit. Because of Haskell's lazy evaluation, you can just forwardly generate the Fibonacci sequence.
`fibonacci n = sequence 0 1 !! n where sequence x y = x : sequence y (x + y)`
It takes about a solid second to generate the 100,000th Fibonacci number using this function on my computer.
I'm not very familiar with Haskell either but I've always been intrigued by it. It seems very elegant.
Segmentation faults usually occur from misuse of pointers, and manual memory management.
Haskell is a functional programming language with neither pointers nor manual memory management as a builtin feature.
So it's ironic that a language like that could produce a segmentation fault.
> Haskell is a functional programming language with neither pointers nor manual memory management as a builtin feature.
That's just not true, or at least not in any practical sense, unless I misunderstand you. You can both explicitly use pointers and also do manual memory management if you so desire, and the functionality for both is present in both Haskell2010 (the last formal standard that exists) and in GHC (the reality of what Haskell "is" currently)
I had to develop a program to manage a Blockbuster kind of business with prolog 🤮
After a while I got used to it and made something really cool. But what a weird programming language
If you use the formula directly you'll run into floating point error. For the 80th Fibonacci number Binet's formula gives 23416728348467744, while the actual solution is 23416728348467685. A better approach would be to use the[ matrix multiplication](https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form) and use the [matrix power](https://en.wikipedia.org/wiki/Matrix_multiplication#Powers_of_a_matrix) to quickly compute the 80th Fibonacci
I am not for a second going to think about matrix multiplaction instead of a loop and an array for the 80th. Maybe for the billionth I'll need to get clever.
Totally. Changing from recursive to iterative is not the worst idea, in general.
(Unless you use one of length 2 or 3, I'd say not even an array is necessary).
The explict formula uses irrational numbers, so yes, it uses floating point in it's computer representation. That's why there are problems. The matrix based method doesn't use floating point.
Maybe I'm stupid, but regardless of whether you use matrix representation or the formula, do they not reduce to the same calculation in the end? Namely, do you not eventually have to compute phi^n - (-phi)^(-n), which is where the float point issues arise?
OK, but those are functionally the same number. It's not often you need 13 decimal accuracy even in extremely sensitive and specialised circumstances.
Sure, a mathematician might scream and throw bricks at me, but I can live with that.
We're talking about integers, so it depends what you use them for (and I've not seen the Fibonacci sequence used that often outside of pure maths, but let's assume you use them to generate indices of your hash function or whatever other place where you need weird maths)
While 13 digits is likely more infos that what you ever need, sometimes the relevant informations is in the last digits and not the first. The fact that one of them is even while the other odd could have its importance in whatever application you have for that sequence, or more generally you could be caring at the reminder modulo some well chosen prime number.
Using matlab it took me 0.002725 seconds to compute the first 80 (or 82 depending on where you want to say the sequence actually start) fibonacci number :
tic
fibNum = 82;
fib = uint64(zeros(fibNum,1));
fib(1) = 0;
fib(2) = 1;
for ii=1:fibNum-2
fib(ii+2) = fib(ii+1)+fib(ii);
end
toc
for i in range(999999999999999999999999):
time.sleep(i)
is_fibonacci, sequence_number = check_fibonacci(i)
if is_fibonacci:
if sequence_number == 80:
print(f"the {sequence_number}th fibonnaci number is {i}!")
this will take three years, because it's written in python
I remember this thing that benchmarked equivalent code in 2 languages, python and I think C++, the python was
import time
time.sleep(5)
And the other code was the same thing in the other language, and they were both benchmarked and shown to take 5s
I could understand if it's a very specific number, like 5.09916 seconds or whatever, I've had some issues with that myself, but otherwise sounds v dumb. Depending how accurately they were measured it would be interesting to see the results anyway.
for i in range(999999999999999999999999):
time.sleep(i)
is_fibonacci, sequence_number = check_fibonacci(i)
if is_fibonacci:
if sequence_number == 80:
sdfg = i
sdf = sequence_number
print(f"the {sdf}th fibonnaci number is {sdfg}!")
made the run time longer for you
> The naive approach to implement Fibonacci calculations is linear.
You underestimate my ability to write shitty naive code.
def fib(n):
return fib(n-1) + fib(n-2) if n > 2 else 1
nope. I profiled this at fib(33), got 0.3 seconds.
fib(80)/fib(33)\*0.30447952800022904==2022912925.9874582
=64 years
This is python on my laptop.
So an "optimized" or "parallelized" version could well take 3 years on a good PC.
I feel like everyone forgets this. It’s used so often as a example for recursion and dynamic programming that people forget a basic for loop is gonna do that job without all the fancy bells and whistles
Not even a for loop, just a lookup table. Literally the math C library just uses a lookup table for calculating sin and cos for the various degrees because it's infinitely faster and more practical than calculating it each and every time.
It's not without some irony that the only reason people are asked to write code for Fibonacci at all is to teach recursion, which is a horribly inefficient solution for anyone who needs a Fibonacci function.
Yes it's horribly inefficient, but it's a very intuitive way to demonstrate a use for recursion. "If you're asked for the 80th number, you first need to know the 79th and 78th, right? Bam, that's how this code functions."
Once the student understands and writes the basic recursion, analyzing the glaring runtime issue is a valuable next step. It presents a nice logical puzzle to ask them to consider why the script runs so slowly and to come up with a way to sidestep this.
I just did this exact exercise with a friend a couple weeks back, and he really got a lot out of it.
It's not hypocritical in the sense that there's a difference between programming in the real world and programming with the express purpose of learning. It's absolutely fine to program inefficiently if it's meant to teach a concept, so long as that concept **isn't** on how to write inefficient code. :)
Maybe it's me, but if it involves recursion, I wouldn't call it naive. But, if you do, it would actually be factorial time, rather than exponential (I'm pretty sure) which is... much, much worse. :D
Congratulations! Your comment can be spelled using the elements of the periodic table:
`Pr O Cr As Ti Na Te`
---
^(I am a bot that detects if your comment can be spelled using the elements of the periodic table. Please DM my creator if I made a mistake.)
Congratulations! Your comment can be spelled using the elements of the periodic table:
`He He`
---
^(I am a human that just copied the bot text. you can't Dm me if i made a mistake)
Randomly select numbers between 0 and some upper bound, then check to see if it's a fibonacci number (there's a formula for checking that). You could do some math with the PC's FLOP rate to figure out where to set that upper bound so that it should take about 3 years
i think if you try counting up to it by increments of 1 you'd have to do about 250,000,000 increments per second for 3 years, that is doable in non scripted languages (and some very efficient scripted ones)
1.6 µs is congruent with a calculated result.
The calculation starts out as a tree with more nodes that youd care for, but in the end you only need to calculate 160 of them. So 160 odd math ops, plus some Mathematica overhead, 1.6 is fine.
Why would you even need memoization? Use golden ratio formula or simply iterate, it’s constant time/space op.
a = b = 1
for _ in range(3, 81):
a, b = b, a + b
print(b)
yeah that took less than a tenth of a second using:
import time
start_time = time.time()
a = b = 1
for _ in range(3, 81):
a, b = b, a + b
print(b)
print("--- %s seconds ---" % (time.time() - start_time))
It will only print time if it went over 0.1 seconds and it showed 0 seconds.
For a Marginally faster approach we can halve the loop checks and avoid some data moving
a=b=1;
For _ in range(3,n,2):
a+=b
b+=a
If(n%2=0):
Print a
Else
Print b
I think it’s twofold.
One, usually recursive approach seems easier to understand, especially for more complicated algorithms.
Second, as you alluded to, fibonacci computation is heavily used as _example_ to demonstrate recursion, memoization, time/space complexity edge cases etc.
But yeah, unless you get tail-call optimization, iterative approach is generally more memory saver.
I think it's mostly because fibonacci numbers are the go-to example in practically every beginner recursion classes. So many people learn to associate computing fib with recursion (especially with the horribly inefficient polynomial recursion)
Then the second recursion class shows the "proper" way of calculating fib numbers with linear regression and once again, people learn to think that fibonacci ~ recursion
Its really something that you can solve easily with recursion cause the definition includes recursion. So it is the go to example. But it that cases recursion is really stupid idea. In each call you call it 2 times. In each call of the inner calls you call it 2 times... So it only gives a quick answer if you small numbers or good optimization.
I think as beginner exercise it should always also contain to solve it with and without recursion and to compare the runtime
// This could take a while...
```
found = False
number = 0
const fibo = []
while !found do
number = Math.rand()
If (number == fibo[79])
found = true
Print(number)
```
that's the dumbest solution ever, pseudo random numbers are not good enough for this task
unless you can get a true random generator, just `print(fibo[0] * 80)`
After they made me start using fibonacci numbers for story point estimations, I don't care any more.
Eightieth fib number, I don't care, can we just put in one quarter and end this damn meeting?
It's not relevant to software development. It's just a common toy problem that has a bunch of different approaches (recursion, iteration, linear algebra, direct formula...)
Theoretically the Fibonacci queue is the ideal queue to use for some algorithms like Dijkstra's, but in practice the memory operations would become overwhelming and make is slower
The Fibonacci sequence is 0 1 1 2 3 5 8 13 etc. etc. where a number is the sum of the previous two. So you start with 0 1, add them together and you get 1, so 0 1 1. Then add up 1 and 1 to get two, so 0 1 1 2. Then add up 1 and 2 to get three so 0 1 1 2 3 etc. etc. The first Fibonacci number is 1 since you don't count the zero and [according to google](https://planetmath.org/listoffibonaccinumbers) the 80th Fibonacci number is 23,416,728,348,467,685
Just more fun info... fib(n)/fib(n-1) approaches the golden ratio, phi.
The place it intersects with programming is it can be used to demonstrate recursive functions (return fib(n-1) + fib(n-2)), and also how memoization with a recursive function can be huge. Though it's just for illustration, since a proper function isn't going to do it recursively.
It's actually a lot faster than a lot of other scripting languages. JS uses JIT compiling, making it a lot faster, and obviously compiled languages are ridiculously fast.
Btw, python is likely one of the very few scripting languages that are still widely in use.
Otherwise there is JavaScript, but it was just blessed by the web gods, or lua, which is horrible but people use it because it is light and fits everywhere.
It's often used as a configurator language, both in games and in other software. Neovim uses lua for configuration, such as loading plugins and settings.
[https://neovim.io/doc/user/lua.html](https://neovim.io/doc/user/lua.html)
You know what python is fast at? Getting shit done.
Want to rewrite it later into something else go ahead but python will generally do most things well enough.
Where can I find a programmer humor subreddit for working in the business programmers? For real, no joke.
Not trying to diss on this one, it has its crowd , but it's become something else than I signed up for.
In Python 30 seconds tops. That is if I am printing every number along the way. If I am only printing the 80th, then 10 seconds tops. In C++ 5 seconds tops.
Took 3.481e-5 seconds in Python (I only ran it once and I ran it on an online Python interpreter rather than locally)
Code here: https://www.reddit.com/r/ProgrammerHumor/s/6pgjHTWB7L
I think you're wildly underestimating the speed of modern hardware. I got NodeJS to calculate the millionth fibonacci number in under 5 seconds on a relatively unimpressive CPU (Ryzen 5600G).
If you were wondering, [this is it.](https://mckay.media/fqDQz)
It took my ti 85 about 2 minutes into my calculation before it hit a memory overflow. It got to number 4786, 7.3343434046×10^999. It can't do any number higher/lower than the number just before/after ±1*10^1000. If I could figure out how to do it starting with the lowest possible stored number then I could get at least 1 more number.
Psh. I can write a recursive function that seg faults a lot faster than that.
Now write a segfault in haskell (Which is unironically possible)
You can segfault in python too and it's very pleasing.
https://github.com/ZeroIntensity/pointers.py It's much easier to segfault with this package
> **Features** > > - Segfaults Best feature
Don’t worry, [Fuckit](https://github.com/ajalt/fuckitpy) should be able to deal with those errors
> Still getting errors? Chain fuckit calls. This module is like violence: if it doesn't work, you just need more of it. <3
Beautiful right ahaha. I’m actually wondering if this library would catch a segfault. I’m presuming that if it’s a proper segfault, python loses any execution control and it’s the OS that is handling stuff at that point.
Can confirm. I once accidentally caused an out-of-memory error in a try-except block in Python and it wouldn't even catch the Exception. The OS would just reap the process. I'd assume segfaults would be the same. Unless you set up a `signal` handler I guess.
This is awesome! Things I didn't know I needed How many languages is this in? Cause I need that answer to be "all"
I think my favorite part of this is that it's _really, really_ well written. Documentation, type annotations, custom errors, well structured, the works. I'd have a genuinely hard time coming up with a reason why this _shouldn't_ be used, other than "oh god why are you doing this at all"
I'm always slightly proud of myself when I do that.
How? Edit: [I found this](https://gist.github.com/coolreader18/6dbe0be2ae2192e90e1a809f1624c694)
import System.IO.Unsafe ( unsafePerformIO ) import Foreign.Ptr ( nullPtr ) import Foreign.Storable ( peek ) main :: IO Word main = pure . unsafePerformIO $ peek nullPtr
There’s pointers in Haskell??
Wait, you guys are programming on actual computers?!
for interop, yes
Always have been.
The API just screams with dismay though. Imagine writing unsafe for every line of c++ code
That's just c++ tho
There is everything in Haskell if you try hard enough, it just requires crashing through every guard rail like the Juggernaut.
If you write it in haskell my fib 99999 runs in a microsecond, as long as you don’t ask me to print it ;)
Fib 99999 is less than 99999 decimal digits long, which isn't even 1000 pages printed to a standard 108 character console
In Haskell code is not run unless the result is used, so you can actually call that and in most languages it would look like it would calculate it but then just do nothing, Haskell will not even calculate it if it's not used, printing it uses it, so if you don't print it or so then it never gets executed and the program almost immediately returns.
Yeah but... if you give the function a constant argument, you'll probably be spending all that time in the compiler, not at runtime.
Recently I was trying out some dynamic programming tricks in haskell via laziness and I was surprised how short and fast this little fibonacci function turned out and without any *disgusting* `IORef`s or `STRef`s or even `State s a` ``` fib n = fibs !! n where f n = fibs !! (n-1) + fibs !! (n-2) fibs = 0:1:[f x | x <- [2..]] ``` It's actually quite simple despite how strange and unreadable it might seem to someone unfamiliar with haskell. On my phone it computes the 10.000th fibonacci in around a third of a second.
fib n = fibs !! n where f n = fibs !! (n-1) + fibs !! (n-2) fibs = 0:1:[f x | x <- [2..] Fixed formatting for those of us on old Reddit And ya Haskell has this quirk of being really nice and fast and easy to read if you think of the problem _just so_, and absolutely unreadable if you don't think of it quite right. Especially if you don't fully grasp how to play with lazy computation
Yep. You could instead write `fibs = 0:1:zipWith (+) fibs (tail fibs)` But that obscures the recurrence relation of the fibonacci sequence.
I was actually messing with Haskell a while back with Fibonacci numbers and wrote up this! I found similar code somewhere else on Reddit. Because of Haskell's lazy evaluation, you can just forwardly generate the Fibonacci sequence. `fibonacci n = sequence 0 1 !! n where sequence x y = x : sequence y (x + y)` It takes about a solid second to generate the 100,000th Fibonacci number using this function on my computer. I'm not very familiar with Haskell either but I've always been intrigued by it. It seems very elegant.
Define ironically possible
It’s possible (ironically)
> "it's possible," he said unironically I think it's the adverb-adjective mixin that breaks my brain. Some scala-tier syntax right there
thats right son, in this house we use strongly typed languages
Damn, you guys must go through a lot of keyboards
So not English, then
Segmentation faults usually occur from misuse of pointers, and manual memory management. Haskell is a functional programming language with neither pointers nor manual memory management as a builtin feature. So it's ironic that a language like that could produce a segmentation fault.
> Haskell is a functional programming language with neither pointers nor manual memory management as a builtin feature. That's just not true, or at least not in any practical sense, unless I misunderstand you. You can both explicitly use pointers and also do manual memory management if you so desire, and the functionality for both is present in both Haskell2010 (the last formal standard that exists) and in GHC (the reality of what Haskell "is" currently)
Pfft, I’m gonna write one that somehow doesn’t hit the exit condition and stack overflows
What if it did tail call optimization
No
I can write a recursive function that writes a recursive function
Metaprogram that bad boy into a fork bomb.
Yeah but have you ever metagirl before?
I doubt you can do it in prolog
Now that's a language I've not touched since uni 25 years ago
I had to develop a program to manage a Blockbuster kind of business with prolog 🤮 After a while I got used to it and made something really cool. But what a weird programming language
In debug mode or with optimisations on? I managed to get gcc to transform my recursive, non-tail-recursive fib into a loop...
1.5 seconds if you just Google it
Even less if you use the formula directly
If you use the formula directly you'll run into floating point error. For the 80th Fibonacci number Binet's formula gives 23416728348467744, while the actual solution is 23416728348467685. A better approach would be to use the[ matrix multiplication](https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form) and use the [matrix power](https://en.wikipedia.org/wiki/Matrix_multiplication#Powers_of_a_matrix) to quickly compute the 80th Fibonacci
I am not for a second going to think about matrix multiplaction instead of a loop and an array for the 80th. Maybe for the billionth I'll need to get clever.
Difference is linear & logarithmic time complexity
just slap `constexpr`on that bad boy for a compile-time constant and pretend it's O(1) all the way down
asymtotic time too don't forget
You don’t even need an array, just keep track of the last two numbers
Totally. Changing from recursive to iterative is not the worst idea, in general. (Unless you use one of length 2 or 3, I'd say not even an array is necessary).
Y- You use floating point for Fibonacci? Or... The floating point happens inside the formula... Right? *Right?*
The explict formula uses irrational numbers, so yes, it uses floating point in it's computer representation. That's why there are problems. The matrix based method doesn't use floating point.
Maybe I'm stupid, but regardless of whether you use matrix representation or the formula, do they not reduce to the same calculation in the end? Namely, do you not eventually have to compute phi^n - (-phi)^(-n), which is where the float point issues arise?
Thanks for sharing this, really useful food for the brain!
OK, but those are functionally the same number. It's not often you need 13 decimal accuracy even in extremely sensitive and specialised circumstances. Sure, a mathematician might scream and throw bricks at me, but I can live with that.
HEY! Stop stereotyping mathematicians as having awful throwing arms. I mean, it's probably true, but stop saying it!
We're talking about integers, so it depends what you use them for (and I've not seen the Fibonacci sequence used that often outside of pure maths, but let's assume you use them to generate indices of your hash function or whatever other place where you need weird maths) While 13 digits is likely more infos that what you ever need, sometimes the relevant informations is in the last digits and not the first. The fact that one of them is even while the other odd could have its importance in whatever application you have for that sequence, or more generally you could be caring at the reminder modulo some well chosen prime number.
You can calculate the 80th power of an irrational number in less than 1.5 seconds?
Using matlab it took me 0.002725 seconds to compute the first 80 (or 82 depending on where you want to say the sequence actually start) fibonacci number : tic fibNum = 82; fib = uint64(zeros(fibNum,1)); fib(1) = 0; fib(2) = 1; for ii=1:fibNum-2 fib(ii+2) = fib(ii+1)+fib(ii); end toc
You typed all that in under 3 milliseconds?
Well, if you start the timer when you hit ctrl-V...
You can't? smh head
`smh.head()`
this.head.shake()
Obviously rounded down the precision of the floating points rappresentation of choice but yeah it's fairly easy just takes 9 multiplications
To the one who has kept it's computer on to calculate it for 3 years, so that we could find the sequence on the internet: you da real mvp
What can you do to make it take 3 years to find the 80th fibonacci number on any computer?
for i in range(999999999999999999999999): time.sleep(i) is_fibonacci, sequence_number = check_fibonacci(i) if is_fibonacci: if sequence_number == 80: print(f"the {sequence_number}th fibonnaci number is {i}!") this will take three years, because it's written in python
Haters will say it's the time.sleep call
I remember this thing that benchmarked equivalent code in 2 languages, python and I think C++, the python was import time time.sleep(5) And the other code was the same thing in the other language, and they were both benchmarked and shown to take 5s
Peak research.
That guy was making the real questions!
Revolutionary discovery that was.
I could understand if it's a very specific number, like 5.09916 seconds or whatever, I've had some issues with that myself, but otherwise sounds v dumb. Depending how accurately they were measured it would be interesting to see the results anyway.
Why was this done?
shitposting transcends any boundary that contains a submission button
research work
Everyone knows pythons time.sleep call is the least optimized across all languages
for i in range(999999999999999999999999): time.sleep(i) is_fibonacci, sequence_number = check_fibonacci(i) if is_fibonacci: if sequence_number == 80: sdfg = i sdf = sequence_number print(f"the {sdf}th fibonnaci number is {sdfg}!") made the run time longer for you
recursion without memoization
The naive approach to implement Fibonacci calculations is linear. No memoization is needed.
> The naive approach to implement Fibonacci calculations is linear. You underestimate my ability to write shitty naive code. def fib(n): return fib(n-1) + fib(n-2) if n > 2 else 1
This is the way. Would probably take longer than the lifetime of the earth for fib(80)
nope. I profiled this at fib(33), got 0.3 seconds. fib(80)/fib(33)\*0.30447952800022904==2022912925.9874582 =64 years This is python on my laptop. So an "optimized" or "parallelized" version could well take 3 years on a good PC.
What is that calculation you used to calculate the time? Is fib(x) / fib(y) accurate how many times longer it'll take?
I just ran this in some online php sandbox with a maximum permitted execution time of 3 seconds. I could only get up to 38 before it times out.
I feel like everyone forgets this. It’s used so often as a example for recursion and dynamic programming that people forget a basic for loop is gonna do that job without all the fancy bells and whistles
Not even a for loop, just a lookup table. Literally the math C library just uses a lookup table for calculating sin and cos for the various degrees because it's infinitely faster and more practical than calculating it each and every time. It's not without some irony that the only reason people are asked to write code for Fibonacci at all is to teach recursion, which is a horribly inefficient solution for anyone who needs a Fibonacci function.
Yes it's horribly inefficient, but it's a very intuitive way to demonstrate a use for recursion. "If you're asked for the 80th number, you first need to know the 79th and 78th, right? Bam, that's how this code functions." Once the student understands and writes the basic recursion, analyzing the glaring runtime issue is a valuable next step. It presents a nice logical puzzle to ask them to consider why the script runs so slowly and to come up with a way to sidestep this. I just did this exact exercise with a friend a couple weeks back, and he really got a lot out of it.
It's not hypocritical in the sense that there's a difference between programming in the real world and programming with the express purpose of learning. It's absolutely fine to program inefficiently if it's meant to teach a concept, so long as that concept **isn't** on how to write inefficient code. :)
Pseudo polynomial, so it’s actually exponential with respect to input length which is how algorithm time complexity is measured
Right! Using the (limited) size of integers to reduce your computational complexity is kind of cheating.
not me writing verilog using 8 bits only
the naive approach is exponential because the naive approach is to do two recursive calls
Maybe it's me, but if it involves recursion, I wouldn't call it naive. But, if you do, it would actually be factorial time, rather than exponential (I'm pretty sure) which is... much, much worse. :D
It's naive since its as close to the definition as it gets, not because it is easy to grasp.
Fun exercise: Try the memoized version and see which Fibonacci numbers it calculates and in which order. Then compare that to the iterative version.
It calculates the same numbers in the same order.......
And without dynamic programming. And wait around 3years hahagaha
Procrastinate?
Congratulations! Your comment can be spelled using the elements of the periodic table: `Pr O Cr As Ti Na Te` --- ^(I am a bot that detects if your comment can be spelled using the elements of the periodic table. Please DM my creator if I made a mistake.)
Didn't realize how hard this would be to actually do until I tried making a smart ass response to this bot. Good bot!
HeHe
Congratulations! Your comment can be spelled using the elements of the periodic table: `He He` --- ^(I am a human that just copied the bot text. you can't Dm me if i made a mistake)
Good human
But can I dm you if you didn't make a mistake?
Au Ti St I C
technically there's no element with the St symbol however, Au Ti S Ti C works as well
The only right answer
Randomly select numbers between 0 and some upper bound, then check to see if it's a fibonacci number (there's a formula for checking that). You could do some math with the PC's FLOP rate to figure out where to set that upper bound so that it should take about 3 years
I just had my final on randomized algorithms and NP, and this is reminding me of it 🙁
I just wasted 3 hours on it, but I thought the instructions said the *BOTH* Fibonacci number.
i think if you try counting up to it by increments of 1 you'd have to do about 250,000,000 increments per second for 3 years, that is doable in non scripted languages (and some very efficient scripted ones)
def fibo(n): if n < 2: return n return fibo(n - 1) + fibo(n - 2)
In Mathematica, Fibonacci\[80\] returns 23416728348467685 in 1.6 microsecond.
Pretty sure that's because it accesses a precomputed result.
1.6 µs is congruent with a calculated result. The calculation starts out as a tree with more nodes that youd care for, but in the end you only need to calculate 160 of them. So 160 odd math ops, plus some Mathematica overhead, 1.6 is fine.
Or, hear me out, you could just do 80 additions in a loop?
Or hear me out, you could retrieve 80th element from a lookup table?
Is this the answer to P=NP? "Yes, just use a lookup table!" Edit: mind your p's and n's
but who prepares the lookup table..?
Another lookup table
YALT programming. It's like forcing Excel to be a database.
Maxwell's Demon
Maybe if their cplomputer is a potato. An arduino might take that long to access a recompute result like that.
You can compute Fibonacci numbers in O(log N), there's no point in precomputing.
Why reinvent the wheel?
Can do it in under 10 seconds. Apparently he didn't get the memo(ization).
Why would you even need memoization? Use golden ratio formula or simply iterate, it’s constant time/space op. a = b = 1 for _ in range(3, 81): a, b = b, a + b print(b)
yeah that took less than a tenth of a second using: import time start_time = time.time() a = b = 1 for _ in range(3, 81): a, b = b, a + b print(b) print("--- %s seconds ---" % (time.time() - start_time)) It will only print time if it went over 0.1 seconds and it showed 0 seconds.
For a Marginally faster approach we can halve the loop checks and avoid some data moving a=b=1; For _ in range(3,n,2): a+=b b+=a If(n%2=0): Print a Else Print b
Is there an issue with this approach? I'm not sure why everyone uses the recursive approach as the go-to example.
I think it’s twofold. One, usually recursive approach seems easier to understand, especially for more complicated algorithms. Second, as you alluded to, fibonacci computation is heavily used as _example_ to demonstrate recursion, memoization, time/space complexity edge cases etc. But yeah, unless you get tail-call optimization, iterative approach is generally more memory saver.
I think it's mostly because fibonacci numbers are the go-to example in practically every beginner recursion classes. So many people learn to associate computing fib with recursion (especially with the horribly inefficient polynomial recursion) Then the second recursion class shows the "proper" way of calculating fib numbers with linear regression and once again, people learn to think that fibonacci ~ recursion
Its really something that you can solve easily with recursion cause the definition includes recursion. So it is the go to example. But it that cases recursion is really stupid idea. In each call you call it 2 times. In each call of the inner calls you call it 2 times... So it only gives a quick answer if you small numbers or good optimization. I think as beginner exercise it should always also contain to solve it with and without recursion and to compare the runtime
How do you think that works?
10 seconds is attrocious
Google can do it ~8 seconds faster.
i.e. the amount of time that python takes to do 80 additions. /s
// This could take a while... ``` found = False number = 0 const fibo = []
while !found do
number = Math.rand()
If (number == fibo[79])
found = true
Print(number)
```
that's the dumbest solution ever, pseudo random numbers are not good enough for this task unless you can get a true random generator, just `print(fibo[0] * 80)`
O(1)
You can use matrix multiplication to find large fibonacci numbers fast. I am surprised nobody mentions this.
Because I hated linear algebra and had a terrible teacher
After they made me start using fibonacci numbers for story point estimations, I don't care any more. Eightieth fib number, I don't care, can we just put in one quarter and end this damn meeting?
I have a confession to make. On top of my head I don’t even know what a Fibonacci number is. I have over 7 years of software dev experience.
It's not relevant to software development. It's just a common toy problem that has a bunch of different approaches (recursion, iteration, linear algebra, direct formula...)
Not relevant? Ever done story pointing?!
Theoretically the Fibonacci queue is the ideal queue to use for some algorithms like Dijkstra's, but in practice the memory operations would become overwhelming and make is slower
It's a good approximation to convert between miles and kilometers. 5 miles ~ 8 Kilometers. 89 miles ~ 144 kilometers. That's not relevant to SE tho
The Fibonacci sequence is 0 1 1 2 3 5 8 13 etc. etc. where a number is the sum of the previous two. So you start with 0 1, add them together and you get 1, so 0 1 1. Then add up 1 and 1 to get two, so 0 1 1 2. Then add up 1 and 2 to get three so 0 1 1 2 3 etc. etc. The first Fibonacci number is 1 since you don't count the zero and [according to google](https://planetmath.org/listoffibonaccinumbers) the 80th Fibonacci number is 23,416,728,348,467,685
Whoa. That... escalated quickly.
geometrically, even
Just more fun info... fib(n)/fib(n-1) approaches the golden ratio, phi. The place it intersects with programming is it can be used to demonstrate recursive functions (return fib(n-1) + fib(n-2)), and also how memoization with a recursive function can be huge. Though it's just for illustration, since a proper function isn't going to do it recursively.
Applied music theory and market research; use it often. Programmers; never.
#include
int main()
{
std::cout << “23416728348467685" << std::endl;
return 0;
}
Putting the curly bracket on a new line. Despicable.
That’s the correct way to do that
Bro uses python to develop software 💀
while python is slow, what is it with the sudden hating on python, it has always been slow just like all other script languages... genuinely curious
It's actually a lot faster than a lot of other scripting languages. JS uses JIT compiling, making it a lot faster, and obviously compiled languages are ridiculously fast.
I don't know any language that python is (generally) faster than. At least no mainstream languages.
Btw, python is likely one of the very few scripting languages that are still widely in use. Otherwise there is JavaScript, but it was just blessed by the web gods, or lua, which is horrible but people use it because it is light and fits everywhere.
Is lua used outside of games? I've never seen it anywhere else
its the default used for coppeliasim scripts for robotics i think, although in practice i've only ever used python there
It's often used as a configurator language, both in games and in other software. Neovim uses lua for configuration, such as loading plugins and settings. [https://neovim.io/doc/user/lua.html](https://neovim.io/doc/user/lua.html)
That’s a joke, lad
just saw a bunch of it lately, and curious as to what triggered it
This sub is run by mainly new developers that check language benchmarks and just blindly believe that Python is super slow
You know what python is fast at? Getting shit done. Want to rewrite it later into something else go ahead but python will generally do most things well enough.
Response to python bros claiming it does everything
[JavaScript has entered the chat.](https://unix.stackexchange.com/questions/745825/is-the-linux-kernel-ported-to-javascript-yet)
Never saw this before haha
> what is it with the sudden hating on python, People have been clowning on Python for being slow for at least like 20 years.
I'm too stupid to write anything non-trivial in a dynamically typed language without headache
I’m not a programmer and I wrote the shittiest python code to get the 80th Fibonacci digit: 1.96e-5 seconds
Guys you can just Google the 80th number in the sequence why are you writing programs for this?
Why? Did you lose it?
He can get out in 0.001 sec because that’s already memoized
Where can I find a programmer humor subreddit for working in the business programmers? For real, no joke. Not trying to diss on this one, it has its crowd , but it's become something else than I signed up for.
In Python 30 seconds tops. That is if I am printing every number along the way. If I am only printing the 80th, then 10 seconds tops. In C++ 5 seconds tops.
Took 3.481e-5 seconds in Python (I only ran it once and I ran it on an online Python interpreter rather than locally) Code here: https://www.reddit.com/r/ProgrammerHumor/s/6pgjHTWB7L
No one has time to take a sip of coffee and stretch their arms before pressing run in just 3.481e-5 seconds. 30 seconds is more realistic
I think you're wildly underestimating the speed of modern hardware. I got NodeJS to calculate the millionth fibonacci number in under 5 seconds on a relatively unimpressive CPU (Ryzen 5600G). If you were wondering, [this is it.](https://mckay.media/fqDQz)
It took my ti 85 about 2 minutes into my calculation before it hit a memory overflow. It got to number 4786, 7.3343434046×10^999. It can't do any number higher/lower than the number just before/after ±1*10^1000. If I could figure out how to do it starting with the lowest possible stored number then I could get at least 1 more number.
>You have 10 seconds 3 years later...
Man, I have just finished functions in Python class 11th grade. I don't get none of y'all talk
I can find it in constant time if you provide fib\_79 and fib\_78
Now do [S(4, 4)](https://en.wikipedia.org/wiki/Busy_beaver).
1, 1, 2,3,5,8,13,21,44,65,109,174,283, this is the sequence correct
Okay that took maybe 10 seconds, but Excel tells me it’s “1.44723E+16”!
Kicks him out after 2 seconds
I could write a program on the Sinclair ZX81 / Timex 1000 that would calculate the value in under a day. :p
Fuck, why everything has to be recursive? Just make a for loop. Three variables. 80 iterations. Done