```
package main
import (
"fmt"
"math/big"
)
func fibonacci(n int) *big.Int {
if n < 2 {
return big.NewInt(int64(n))
}
a, b := big.NewInt(0), big.NewInt(1)
c := big.NewInt(0)
for i := 1; i < n; i++ {
c.Set(a)
a.Set(b)
b.Add(b, c)
}
return b
}
func main() {
fmt.Printf("%s\n", fibonacci(100).String())
}
```

I confirm that the result is **354224848179261915075**.

PS: The Go bigNum library is a mess and the lack of operator overloading is annoying.

]]>@adnan your f(n) function, the slow one, uses a simple recursion.

It's slow because for f(n) it will store "big formulae to calculate " in the memory starting from the unkown f(n) and decrementing n, all the formulas that the compiler calculates only contains f(0) and f(1) (which are defined) or formulas leading to f(0) and f(1) and finally your f(n) will be returned.]]>

```
#!/usr/bin/python
def fibbo():
for i in xrange(0,100):
i=??????????
yield i
for i in fibbo():
print i
```

Okay now I guess this is list-less, but I have to figure out what to put in there, or maybe it's just plain impossible this way.

Trying ...

I stole this one from Stackoverflow after understanding it. It doesn't contain lists, but it's too slow.

```
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
print F(100)
```

And how about switching from list to tuple ?

I'll have to continue reading more documentations after I finish with schoolwork. But for now I'm trying to see what I can do with what I already know, and do some research for something when it's needed. I also read your answer on the other topic.

Many, many thanks to you and to NuclearVision, your help is really significant !

]]>You're creating a list object[1]. Object creation is an expensive operation in terms of CPU cycles and memory consumption. Can you rewrite your code so that you don't need to create the list at all?

The goal of this exercise is also to calculate the result of a very large computation. You'll notice that your code gives a rounded value of the result. How can you improve your precision?

[1]: Actually, as your list grows and more items are added to it, CPython might create many new lists. But that's an implementation detail you shouldn't care about too much.

]]>```
li=[0,1]
while True:
n=li[-2]+li[-1]
li.append(n)
if len(li)==101:
break
print li[-1]
```

I've checked other people's posts but wanted to share mine as I first wrote it before checking the solutions. I can see that I did a few unnecessary stuff.

]]>```
import java.math.*;
public class Main {
public static void main(String [] args){
System.out.print("the number is:"+fab(100));
}
public static String fab(int number){
BigDecimal a= new BigDecimal("0");
BigDecimal[] fb= new BigDecimal[2];
fb[0]=new BigDecimal("0");
fb[1]=new BigDecimal("1");
if (number == 1){
return "1";
}
else{
for(int i=1;i<number;i++){
a=fb[0].add(fb[1]);
fb[0]=fb[1];
fb[1]=a;
}
return a.toString();
}
}
}
```

Java.

i had a problem with precision so i used "BigDecimal" to solve it,now the program gives exact results in form of strings(i can change that but since the only purpose here is printing so a string is fine),and i added the if statement since fab(1) was returning 0 (instead of 1),so now it's bugs free and precision perfect,the method can be used in other programs as well.it's pretty fast too,calculating fab(100) in 1 to 2 ms and fab(1000) in 4 to 5 ms.

I didn't use Any external libraries.

```
#include <iostream>
#include <math.h>
using namespace std;
long long unsigned fib( int n)
{
long double fib[100];
fib[0]=0.00;
fib[1]=0.01;
int i=2;
for(i; i<=n; i++)
{ fib[i]=fib[i-1]+fib[i-2];
}
return fib[n];
}
int main(void)
{
int i=100;
cout<<fib(i)<<"e+2"<<endl;
return 0;
}
```

It doesn't uses double as the famous formula floor(phi^n/sqrt(5)+0.5) which is also O(logn)

```
#include <iostream>
#include <vector>
using namespace std;
/*
2 by 2 matrix multiplication function modulo M:
*/
vector<long long> mul(vector<long long> A, vector<long long>B, long long Modulo)
{
vector<long long> R(4,0);
R[0]=(A[0]*B[0]+A[1]*B[2]) % Modulo;
R[1]=(A[0]*B[1]+A[1]*B[3]) % Modulo;
R[2]=(A[2]*B[0]+A[3]*B[2]) % Modulo;
R[3]=(A[2]*B[1]+A[3]*B[3]) % Modulo;
return R;
}
/*
Matrix exponentiation by sqaring modulo M:
*/
vector<long long> poww(vector<long long> A, long long m, long long Modulo)
{
if(m==1)
return A;
vector<long long> Z = poww(A,m/2,Modulo);
if(m%2==0)
{
return mul(Z,Z,Modulo);
}
else
{
return mul(mul(Z,Z,Modulo),A,Modulo);
}
}
/*
function to set a 2*2 matrix in a vector<int> of size 4
*/
vector<long long> setM(long long a, long long b, long long c, long long d)
{
vector<long long> R(4,0);
R[0]=a;
R[1]=b;
R[2]=c;
R[3]=d;
return R;
}
/*
compute the nth Fibonacci number modulo M
*/
long long F(long long n, long long Modulo)
{
if(n<=1)return n;
n=n-1;
vector<long long> A=setM(1,1,1,0);
vector<long long> B=setM(1,0,0,0);
vector<long long> C=mul(poww(A,n,Modulo),B,Modulo);
return C[0];
}
int main()
{
cout << F(100000,100000)<< endl;
}
```

```
f=[0]
i=0
while True:
i+=1
if i==1:
f.append(1)
elif i==2:
f.append(1)
else:
f.append(f[i-1]+f[i-2])
if len(f)==101:
break
print f[i]
```

```
using System;
using System.Collections.Generic;
using System.Numerics;
namespace tmp2
{
class Program
{
static void Main(string[] args)
{
using (System.IO.FileStream fs = new System.IO.FileStream
(System.IO.Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.Desktop),"Fiblog.txt")
, System.IO.FileMode.Create))
using (System.IO.StreamWriter sw = new System.IO.StreamWriter(fs))
{
Console.SetOut(sw);
foreach (BigInteger someint in Fibonacci(100))
Console.WriteLine(someint);
}
}
static IEnumerable<BigInteger> Fibonacci(int limit)
{
int counter = 1;
BigInteger current = 1;
BigInteger previous = 1;
yield return 1;
while (counter < limit)
{
yield return current;
BigInteger next = current + previous;
previous = current;
current = next;
counter++;
}
}
}
}
```

won't get any better than this, its Fibonacci with internal state utilizing bigInteger in the system.numerics name space (the bound of the number is theoretically the computer RAM = numbers can get astronomically huge), plus it uses Lazy enumeration which does have some benefits, particularly if you are dealing with very large quantities of information. Lazy enumeration makes it possible to start processing data as soon as the first item becomes available.

It's written by me, hope it's be helpfull

This would be

```
> ( 0,1, {$^a+$^b} ... Inf )[100].say;
354224848179261915075
```

I could still shave off a dozen characters off of that... but this is not an golf contest :-)

]]>```
#Python
from math import sqrt
phi = (1+sqrt(5))/2
psi = (1-sqrt(5))/2
def F(n):
return (phi**n-psi**n)/(phi-psi)
F(100)
```

]]>```
function fibiter (n, count, total, last)
if n == 0 or n == 1 then return n
elseif count and count > n then return total
else
local count = count or 2
local total = total or 1
local last = last or 0
return fibiter(n, count+1, total+last, total)
end
end
```

Also the Lua interpreter had no problem computing (a rounded value of) the large number:

>= fibiter(100)

3.5422484817926e+20

>= fibiter(100) == fibiter(100) -1

true

print(fibiter(100))

]]>```
def F(n):
a = 0
b = 1
for i in range(n):
a,b = b,a+b
return a
```

This is the one-liner equivalent:

`F = lambda n : reduce(lambda a,dummy: (a[1],sum(a)), [(0,1)] + range(n))[0]`

Some output:

```
>>> map(F, [0, 1, 2, 3, 100, 200])
[0, 1, 1, 2, 354224848179261915075L, 280571172992510140037611932413038677189525L]
```

PS: I have some code lying around somewhere that uses gmp to compute really large values of the fibonacci sequence in C. At the time I wrote it, I tested 3 versions of the same code C/gmp python/int and Java/BigInteger. As far as speed goes, taking the C implementation as reference, they ran something like this(more is worse):

C/gmp: 1x

python/int: 2x

Java/BigInteger: ~4x

I don't know if the java bigint implementation has improved since, but apparently the default int class of python is pretty damn performant

]]>I have a few remarks concerning the style of your writing:

- Since the requirements already stated it's a Fibbonacci sequence, you can assume that 0term == 0 and 1term == 1. Filling them with a scanf seems weird.

- I tend to write separate functions that I call from the main. Not only is this general good practice, but it also helps others re-use the code your produce more easily. And it also provides a more straight up answer to the exercise (you should have a **int fibbonacci (int x)** somewhere).

- You should name your variables in a more expressive way; it's such a short program yet I'm already confused by the naming scheme. A good naming convention should completely replace the comments.

I really liked your early representation of F(x), so I wrote a small piece of recursive code based on it.

F(x) = A*F(0) + B*F(1)

```
class fibtuple:
''' fibtuple is a representation of F(x) following:
F(x) = A * F(0) + B * F(1). It can be represented as a tuple (A, B)'''
def __init__(self, x):
if x == 0:
self.A, self.B = 1, 0
elif x == 1:
self.A, self.B = 0, 1
else:
self.A = fibtuple(x-1).B
self.B = self.A + fibtuple(x-1).A
def Fib(x):
''' The real value should be F(0) * A + F(1) * B
but F(0) == 0, allowing us to write the simple following'''
return fibtuple(x).B
```