big.mul.small <- function(a,b) {
  i <- 1
  carry <- 0
  while (i <= length(a) || carry) {
    temp <- ifelse(i <= length(a), a[i]*b+carry, carry)
    carry <- temp %/% 10
    a[i] <- temp %% 10
    i <- i + 1
  }
  return(a)
}

pow <- 1
for(i in 1:100) pow <- big.mul.small(pow,99)
print(paste(rev(pow),collapse=""))

[1] "36603234127322950493061602657251738618971207663892369140595737269931704475072474818719654351002695040066156910065284327471823569680179941585710535449170757427389035006098270837114978219916760849490001"

primes_up_to_n=lambda n:[2, 3]+[x for x in range(3,n,2) if all(n%y>0 for y in primes_up_to_n(x))]
print(primes_up_to_n(13))

[2, 3, 3, 5, 7, 9, 11]

Real time: 30.353 s
User time: 30.022 s
Sys. time: 0.015 s
CPU share: 98.96 %
Exit code: 0

num <- 1; denom <- 1
count <- 0
for(i in 1:1000){
  temp <- num + denom
  num <- temp + denom
  denom <- temp
  if(floor(log10(num)) > floor(log10(denom))) count <- count + 1
  if(denom > 1e100) {num <- num/1e100; denom <- denom/1e100}
}
print(count)

def first_a_fibonacci(a):
	result = []
	if a == 0: return [0]
	elif a==1: return [0,1]
	elif a==2: return [0,1,1]
	else:
		x,y = 0,1
		result += [x,y]
		while a-2>=0:x,y=y,x+y;a-=1;result.append(y)
		return result

import time

def first_a_fibonacci(a):
	result = []
	if a == 0: return [0]
	elif a==1: return [0,1]
	elif a==2: return [0,1,1]
	else:
		x,y = 0,1
		result += [x,y]
		while a-2>=0:x,y=y,x+y;a-=1;result.append(y)
		return result

start = time.time()
n = 100000
for _ in range(n): a = first_a_fibonacci(10)
end = time.time()
print((end-start)/n)

2.490081787109375e-06

import timeit

def first_a_fibonacci(a):
	result = []
	if a == 0: return [0]
	elif a==1: return [0,1]
	elif a==2: return [0,1,1]
	else:
		x,y = 0,1
		result += [x,y]
		while a-2>=0:x,y=y,x+y;a-=1;result.append(y)
		return result

print(timeit.timeit('first_a_fibonacci(100000)','from __main__ import first_a_fibonacci',number=1))

import timeit

def first_a_fibonacci_1(a):
	result = []
	if a == 0: return [0]
	elif a==1: return [0,1]
	elif a==2: return [0,1,1]
	else:
		x,y = 0,1
		result += [x,y]
		while a-2>=0:x,y=y,x+y;a-=1;result.append(y)
		return result

def first_a_fibonacci_2(a):
	if a<3: return [0,1,1][:a+1]
	result = [0]*a
	x,y = 0,1
	for i in range(1,a): result[i]=y; x,y=y,x+y;
	return result

print(timeit.timeit('first_a_fibonacci_1(100000)','from __main__ import first_a_fibonacci_1',number=10))
print(timeit.timeit('first_a_fibonacci_2(100000)','from __main__ import first_a_fibonacci_2',number=10))

4.295146663003834
4.000230653997278

fib_cache = {0:0, 1:1, 2:1}

def Fib(n):
    global fib_cache
    if n in fib_cache:
        return fib_cache[n]
    else:
        result = fast_fib(n)[1]
        fib_cache[n] = result
        return result

# F(2n) = (F(n-1) + F(n+1)) * F(n)
#       = (F(n-1) + F(n-1) + F(n)) * F(n)
#       = (2F(n-1) + F(n)) * F(n)

# F(2n-1) = F(n-1)*F(n-1) + F(n)*F(n)

# this returns [F(n-1), F(n)], so
# the implementation should be
# fast_fib(1000)[1]
def fast_fib(n):
    global fib_cache
    if n==0: return 1,0