I teach computer science to undergrads and write for The Renegade Coder. I'm most likely taking care of my daughter, watching the Penguins, or reading manga.
Location
Columbus, Ohio
Education
B.S. in CE from CWRU 2016; M.S. in CSE from OSU 2020; PhD in EED from OSU 2024
I graduated in 1990 in Electrical Engineering and since then I have been in university, doing research in the field of DSP. To me programming is more a tool than a job.
It turns out also in DSP, it is a classical example of use of z-trasform for beginners. Actually, the exact form has two terms: phi above and 1/phi and the n-th term is something like C*(phin +1/phin ) (more or less, I am going by memory and I am too lazy now to do the computation... ;-)). Of course, since 1/phi is smaller than one, 1/phin goes rapidly to zero and you get a wonderful approximation with only phin already for small n.
I only know it because my Theory of Computability professor used the “one trillionth Fibonacci number” as a limit to our newfound power understanding recursive solutions. (To find the Fn, you need to find Fn-1 + Fn-2. To find those two numbers, you need to find Fn-2 + 2*Fn-3+Fn-4. This gets towards heat death of the universe level amount of instructions fairly quickly. The loop with saved state gets you down to hours IIRC.)
Then he dropped that this equation existed and my mind kinda exploded.
It wasn’t until trying to get that Project Euler question 2 to complete in under 30 seconds that I ever implemented this. It’s simpler than I expected going in.
I teach computer science to undergrads and write for The Renegade Coder. I'm most likely taking care of my daughter, watching the Penguins, or reading manga.
Location
Columbus, Ohio
Education
B.S. in CE from CWRU 2016; M.S. in CSE from OSU 2020; PhD in EED from OSU 2024
Yeah, it’s not too hard to put together an inefficient solution using recursion (since that’s how the equation is written). If you’re clever, you might save computations in a list. Or, maybe you write an iterative solution which only needs two variables at any give time.
That said, an equation like this is next level. Haha
packagemainimport("fmt""os""strconv")funcfib(nint){a,b:=0,1fori:=0;i<n;i++{a,b=b,a+bfmt.Printf("%d: %d\n",i+1,a)}}constmsg="Usage: please input the count of fibonacci numbers to output"funcmain(){iflen(os.Args)==1{fmt.Println(msg)return}ifos.Args[1]==""{fmt.Println(msg)return}n,err:=strconv.Atoi(os.Args[1])iferr!= nil { fmt.Println(msg)return}fib(n)}
I graduated in 1990 in Electrical Engineering and since then I have been in university, doing research in the field of DSP. To me programming is more a tool than a job.
Ada (unfortunately seems that no syntax highlighting is available for Ada)
with Ada.Command_Line; with Ada.Text_IO; use Ada.Text_IO; use Ada; procedure Fib is Old : Natural := 1; Older : Natural := 0; Limit : Positive; Tmp : Positive; Bad_Command_Line : exception; begin if Command_Line.Argument_Count /= 1 Then raise Bad_Command_Line; end if; Limit := Positive'Value (Command_Line.Argument (1)); for K in 1..Limit Loop Put_Line (Standard_Error, Integer'Image (K) & ":" & Integer'Image(Old)); Tmp := Old + Older; Older := Old; Old := Tmp; end loop; exception when Bad_Command_Line | Constraint_Error => Put_Line(Standard_Error, "Usage : Please Input The Count of Fibonacci Numbers To Output"); Command_Line.Set_Exit_Status(Command_Line.Failure); end Fib;
This is my first post here. I am intrigued by such kinds of problems. this is a simple enough JS code, I hope, to achieve the goal. It is a recursive function, hence I am not expecting very match in terms of performance.
function fib(i){ if (i<=0) return -1; else if (i==1) return 1; else if (i==2) return 1; else return fib(i-1)+fib(i-2) } // some examples //fib(3) returns 2 //fib(5) returns 5
You may try this on chrome dev tools for quick tests.
Python: (constant time solution)
Edit: This is accurate until F4767 with the given precision.
Clever! I didn't realize there was an equation that could so closely approximate the series.
It turns out also in DSP, it is a classical example of use of z-trasform for beginners. Actually, the exact form has two terms: phi above and 1/phi and the n-th term is something like C*(phin +1/phin ) (more or less, I am going by memory and I am too lazy now to do the computation... ;-)). Of course, since 1/phi is smaller than one, 1/phin goes rapidly to zero and you get a wonderful approximation with only phin already for small n.
I only know it because my Theory of Computability professor used the “one trillionth Fibonacci number” as a limit to our newfound power understanding recursive solutions. (To find the Fn, you need to find Fn-1 + Fn-2. To find those two numbers, you need to find Fn-2 + 2*Fn-3+Fn-4. This gets towards heat death of the universe level amount of instructions fairly quickly. The loop with saved state gets you down to hours IIRC.)
Then he dropped that this equation existed and my mind kinda exploded.
It wasn’t until trying to get that Project Euler question 2 to complete in under 30 seconds that I ever implemented this. It’s simpler than I expected going in.
Yeah, it’s not too hard to put together an inefficient solution using recursion (since that’s how the equation is written). If you’re clever, you might save computations in a list. Or, maybe you write an iterative solution which only needs two variables at any give time.
That said, an equation like this is next level. Haha
Solution in Go language:
Ada (unfortunately seems that no syntax highlighting is available for Ada)
This is my first post here. I am intrigued by such kinds of problems. this is a simple enough JS code, I hope, to achieve the goal.
It is a recursive function, hence I am not expecting very match in terms of performance.
You may try this on chrome dev tools for quick tests.
Racket:
For anyone interested, this challenge is also available here in 257 languages : rosettacode.org/wiki/Fibonacci_seq...
Also related, Project Euler problem #2
haskell
Love that the example solution for this challenge was implemented in Haskell. Even being a beginner, I appreciate all that functional goodness.