fibonacci,apl , Generate a fibonacci series with no loops or flow control in APL

## Question:

Tag: fibonacci,apl

Is there a way to create a fibonacci sequence in APL with a one-liner that doesn't require loops or flow control?

I've done it with a function using `→` and a conditional test, but I feel there must be a more elegant, declarative way. An example that I've found that claims to do it on one line doesn't work on gnu-apl - it seems it's on the right track, using matrix math, but I'm having a hard time following along, and can't tweak it to work correctly.

I'm pursuing APL as my first real programming language (I love the symbols. I just do.) I'm now using Project Euler as a way to become better acquainted.

I love APL's symbols too, as well as its array programming power. Other array languages may be more powerful, such as J, but they lack the beauty of APL's symbols and explicit syntax.

I just tried the example you link to in GNU APL and it works all right:

``````      ↑0 1↓↑+.×/5/⊂2 2⍴1 1 1 0
5
↑0 1↓↑+.×/6/⊂2 2⍴1 1 1 0
8
↑0 1↓↑+.×/7/⊂2 2⍴1 1 1 0
13
``````

If you can't get it to work, make sure to:

• type (or copy and paste) the exact symbols shown in the example: in particular `×` is U+00D7 MULTIPLICATION SIGN, not an X; `⍴` is U+2374 APL FUNCTIONAL SYMBOL RHO, not any other Greek Rho, and definitely not a P; `⊂` is U+2282 SUBSET OF; and so on;
• test some numbers other that 1 or 5, because they are the only numbers that are equal to their Fibonacci number;
• if you are not putting an actual number in place of N, make sure you define N in a proper way, such as `N←7` by itself in a previous line.

If you still can't get it to work, type the formula one step at a time, starting from the right:

``````      2 2⍴1 1 1 0
1 1
1 0
⊂2 2⍴1 1 1 0
1 1
1 0
7/⊂2 2⍴1 1 1 0
1 1   1 1   1 1   1 1   1 1   1 1   1 1
1 0   1 0   1 0   1 0   1 0   1 0   1 0
+.×/7/⊂2 2⍴1 1 1 0
21 13
13  8
↑+.×/7/⊂2 2⍴1 1 1 0
21 13
13  8
0 1↓↑+.×/7/⊂2 2⍴1 1 1 0
13
8
↑0 1↓↑+.×/7/⊂2 2⍴1 1 1 0
13
``````

As for the question title, I think this matrix formula nails it (bravo @mappo!)

If I were golfing, I'd probably use a shorter variation, but that's all:

``````      2⌷∊+.×/7/⊂∘.∨⍨1 0
13
``````

There, from 24 to 17 chars. See if you can figure it out :-)

GNU APL is ok, although it lacks some modern features, but keep a copy of Dyalog APL Programmer's Guide & Language Reference handy, because it's one of the most comprehensive references about the language.

# Related:

## Fibonacci with huge numbers in c#

c#,.net,stack-overflow,biginteger,fibonacci
I`m trying to find the first fib number to contain 1000 digits. Because i have no data-type capeable of holding such a number, i created a class called hugeNumber which holds the digits in a list, with a decimal base. I get a stack overflow at the generation of the...

## how to write generate Fibonacci in python

python,generator,fibonacci,yield,def
def fib(a, b, f): fib must generate (using yield) the generalized Fibonacci sequence, a and b is first and second element. f is function to get the third element instead of a+b as normal Fibonacci sequence. Use take function(which show below) to test it. my code is below def fib(a,...

## Why do we discard 2 fibonacci numbers in fibnacci search, if value at current index is less than what we're trying to find?

arrays,algorithm,search,binary-search,fibonacci
I have code that does Fibonacci search and I was wondering why we discard 2 Fibonacci numbers if our key is greater than the value at current index in the array? public class FibSearch{ static int fibSearch(int[] a, int x){ int f1 = 1, f2 = 0, mid = 2;...

## Formal proof for what algorithm return

algorithm,fibonacci,proof
I need to formal proof that below algorithm return 1 for n = 1 and 0 in other cases. function K( n: word): word; begin if (n < 2) then K := n else K := K(n − 1) * K(n − 2); end; Anyone could help? Thank you...

## Fibonacci Recursive function takes forever

recursion,fortran,fibonacci
I want to get the 48th element of the Fibonacci sequence which I can store in a 64 bit integer. I am using a recursive subroutine, but it is taking forever to finish. If anyone can find a problem with my recursive subroutine, I would be very grateful. Integer (Int8)...

## Most efficient way to calculate Fibonacci sequence in Javascript

javascript,algorithm,big-o,fibonacci
I'm attempting to get better with optimizing algorithms and understanding big-o, etc. I threw together the below function to calculate the n-th Fibonacci number. This works (for a reasonably high input). My question is, how can I improve this function? What are the drawbacks of calculating the Fibonacci sequence this...

## Need help- basic Java code.(Fibonacci Series)

java,fibonacci
Very new Java programmer and I'm trying to get myself around this Fibonacci problem. (Leaving out the import/class defines Scanner sc = new Scanner(System.in); System.out.print("Put in how many you want to input"); numToPrint = sc.nextInt(); sc.close(); int current = 1; int last = 0; System.out.println(last); System.out.println(current); // This is the...

## On declaring variables as global gives different answers

c++,variables,global-variables,fibonacci
I have two similar codes Code1: #include <bits/stdc++.h> using namespace std; long long int MOD = 1000000007; long long int fib(long long int n) { if(n <= 2) return 1; long long int k = n/2; long long int a = fib(k+1); long long int b = fib(k); if(n%2 ==...

## maxi and min times to calculate the Fibonacci numbers for six seperate runs at n [closed]

c++,recursion,iteration,fibonacci,timing
The wording for this problem has me completely confused. I know how to get "timing" using GetTickCount() but I have to repeat the calculation 6 times for each N and I have to have 6 different N and the results have to be reported in one table as max an...

## I cannot )SAVE in GNU apl

save,apl
I named my file (WSID nameOfFile), but when I typed )SAVE this comes out: Unable to )SAVE workspace 'nameOfFile'. No such file or directory My workspaces are stored in /apl-1.4...

## Memoizing fibonacci function in php

php,recursion,fibonacci,memoization
I've created a memoized function of the recursive version of fibonacci. I use this as an example for other kinds of functions that would use memoization. My implementation is bad since if I include it in a library, that means that the global variable is still seen.. This is the...

## Fibonacci in Go using channels

go,fibonacci
I am following the examples on tour.golang.org. I understand the example mostly, the only issue I have is why does it stop when we pass 0 to quit channel? Regardless of whether 0 was passed to quit, there is always a value for x. So shouldn't select always fall on...

## Adding Fibonacci odd sequence in java

java,arrays,fibonacci
I would like to add all the odd numbers in: System.out.print(store + " "); If you got any suggestion please help me. import java.util.stream.IntStream; public class Fibonacci { public static void main(String a[]) { int Fibcnt = 25; int[] feb = new int[Fibcnt]; feb[0] = 0; feb[1] = 1; for...

## How does Haskell evaluate the Fibonacci function?

I am currently looking at this function in Haskell which returns the Fibonacci number at position n fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) Now, it compiles, returns the correct result and everything... but I don't...

## “n.” Fibonacci Number [closed]

python,python-3.x,fibonacci
How can I find "n." Fibonacci number in Fibonacci Sequence, in Python By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous...

## Fast doubling Fibonacci Python generator sequence

python,fibonacci
I'm having troubles try to create a Fast doubling Fibonacci python generator, using the following. Given F(k) and F(k+1), we can calculate these: F(2k) = F(k)[2F(k + 1) − F(k)] F(2k+1) = F(k+1)^2 + F(k)^2 I've got the following for the simplest (slow) Fibonacci generator: def fib_generator(): n = 1...

## Generate a fibonacci series with no loops or flow control in APL

fibonacci,apl
Is there a way to create a fibonacci sequence in APL with a one-liner that doesn't require loops or flow control? I've done it with a function using → and a conditional test, but I feel there must be a more elegant, declarative way. An example that I've found that...

## Local variable returned in recursive function

c,recursion,fibonacci
i have written a code for a fibonacci series returning the sum of the complete series, can the local "static int" variable be returned to the main function where the code is trying to print the sum. Below is my code #include<stdio.h> int fiborecur(int n) { static int first=0,second=1,sum=0,total=0; if(...

## Space leak with recursive list zipWith

My space leak happens in one of my personal project. But I don't want someone to solve it in my project. I want to understand it. I reproduced my space leak by making up this algorithm: u is a sequence defined by: u(0) = 1 u(1) = 2 u(2) =...

## Why Wont Python Wont Do a Lot of Recursion?

python,recursion,fibonacci
I'm doing the Project Euler problems, and I'm on number two. The question is: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55,...

## awk skipping records. getline command

bash,ubuntu,awk,fibonacci
this is a task related to data compression using fibonacci binary representation. what i have is this text file: result.txt a 20 b 18 c 18 d 15 e 7 this file is a result of scanning a text file and counting the appearances of each char on the file...

## Fast Dobuling to find Fibonacci number, function not working in C++

c++,fibonacci,modulus
I am learning this algorithm to calculate nth number in fibonacci series. This is my code, #include <bits/stdc++.h> using namespace std; #define MOD 1000000007 long long int fib(long long int n) { if(n < 2) return n; if(n == 2) return 1; long long int k = n/2; long long...

## Improve C++ Fibonacci series

c++,dynamic-programming,fibonacci
I know that: int fib(int n) { if (n == 0 || n == 1) return 1; return fib(n − 1)+ fib(n − 2); } when n=5，fib(5) evaluates as: fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + (fib(2) + fib(1)) ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) +...

## Fibonacci sequence animation

javascript,html5,fibonacci
I am currently attempting to program the Fibonacci Sequence animation on a HTML5 canvas using JavaScript. I have calculated the Fibonacci numbers and am able to add the squares to a grid layout. The trouble I am having is being able to calculate the offset so they will automatically fit...

## What is wrong with my fibonacci sequence program that uses “for loop”

python,loops,for-loop,fibonacci
def fibonacci(n): terms = [0,1] i = 2 for i in terms[2:n+1]: terms.append(terms[i-1] + terms[i-2]) return terms[n] user_input= input ('Write the number order by which you want to know its corresponding value in the fibonacci sequence') fibonacci_user_input = fibonacci(user_input) print fibonacci_user_input The semantic error cited in the Pyscripter Python 2.7.9...

## What is the right way to compute Fibonacci using cilk?

c++,fibonacci,cilk
While I'm learning cilk, I countered with 2 opposite examples: From intel from wiki (or other examples in the net): The oppposite lies on those 2 lines: x = spawn fib (n-1); y = spawn fib (n-2); The first site says: You do not need to add a cilk_spawn attribute...

## Number of ways to reach N from 0 using only 2 or 3?

algorithm,fibonacci
I am solving this problem where we need to reach from X=0 to X=N.We can only take a step of 2 or 3 at a time. For each step of 2 we have a probability of 0.2 and for each step of 3 we have a probability of 0.8.How can...

## Is this working properly - Sum of Fibonacci in Python 3

python,numbers,sum,fibonacci
I have a task to make a program that will sum the first 100 Fibonacci numbers. I checked my output in Python, and my output in QBasic 64 and they aren't same. I checked with different inputs also. Input: 10 Output: 89 ----------- Input: 100 Output: 573147844013817084101 Is it correct...

## How many calls will be stored in stack?

java,recursion,stack,fibonacci
Could someone please explain how many calls will be stored in stack for the recursive method below and why? When is something stored in stack exactly? Apparently it is 49 calls, but I don't understand why. Thanks. public static long fib( int n ){ // n = 50 if( n...

## I don't know why this Ruby Fibonacci sequence works

ruby,fibonacci
I'm writing a program that pushes Fibonacci numbers into an array, using Ruby. The code works, but I can't wrap my head around why it works. This part I understand, it's the Fibonacci equation: fib_array = [] def fib (n) return n if n <= 1 fib(n - 1) +...

## Get each fibbonacci value in haskell

I'm learning haskell and I have the following code: fib a b = a : fib b (a + b) findFibSum = sum [x | x <- fib 1 2, mod x 2 == 0 && x < 100] If I run findFibSum nothing happens, it just sits there. Shouldn't...

## Fibonacci with a Twist - JavaScript

javascript,fibonacci
I was asked this question for a JavaScript interview. Implement fibonacci series to list the sequence up n numbers (n not included) where recursion happens only for even numbers. for example fib(10) -> fib(8) + fib (6) fib(8) -> fib(6) + fib(4) fib(6) -> fib(4) +fib(2) fib(4) -> fib(2) I...

## Python fibonacci code error

python,runtime-error,fibonacci
I'm trying to write code that iteratively finds the nth fibonacci number. I've written my code below (using a bottom-up approach) but I get the following error. Can you please explain what the error is? Thanks. def fib2(n): if n == 1 or n == 2: return 1 myarr =...

## APL return value of a function

return,return-value,apl
I want to know how to return a value after my function finishes running. I have, for example: FUNCTION X ? X ⍴ 10 //This means, generate X random numbers (X is the function's argument) within the range 1-10. I just want to know how I can return the value...

## Looping the Fibbonacci Sequence in Python

python,fibonacci
I am writing a program in Python 2.7.6 that calculates the Fibonacci Sequence(1,1,2,3,5,8,etc.). This is the code(so far): x = int(input("Enter a number: ")) y = int(input("Enter the number that comes before it:")) z = x + y a = z + x b = a + z c =...

## Taking input from user and returning an answer in TKinter

python,tkinter,fibonacci
This is my first question here so sorry for any mistakes :S. I have recently picked up python, and I have made some very simple text based application. Now I tried to make one with a proper GUI. I have the code bellow. I have made the GUI, and it's...

## fibonacci sequencing difficulties in python

python,fibonacci
(I'm in a basic computer science class, and this is homework) I am trying to create a basic fibonacci sequence with "n" as the parameter. what I have so far seems to be working fine when I run the program in idle def fibonacci(n): a=0 b=1 n = input("How high...