Ad
finsternachtvs.alexanderpas

Factorial

Algorithms
Logic
Mathematics
Numbers
Code
Diff
  • from functools import reduce
from operator import mul
factorial = lambda n: reduce(mul, range(2, n+1), 1)
    • def factorial(x):
    • return 0**x or x*factorial(x-1)
    • from functools import reduce
    • from operator import mul
    • factorial = lambda n: reduce(mul, range(2, n+1), 1)
finsternachtvs.Zantyr

Find the nth Fibonacci number

Let's assume it was in the spirit of this ;)

My implementation calculates the matrix power using iteration instead of recursion.

To fit the old test cases I shift my output by one.
My implementation was based on the definition F_0 = 0, F_1 = 1.

Code
Diff
  • def _fib(n):
    k = n.bit_length()-1
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    for i in range(k, -1, -1):
        y2 = y0*y0
        y0, y1 = 2*y0*y1+y2, y2+y1*y1
        if (n>>i)&1:
            xy = x0*y0
            y0, y1 = x0*y1+x1*y0+xy, xy+x1*y1
    return y0
    
def fib(n):
    return _fib(n+1)
    • def _fib(n):
    • k = n.bit_length()-1
    • x0, x1 = 1, 0
    • y0, y1 = 0, 1
    • for i in range(k, -1, -1):
    • y2 = y0*y0
    • y0, y1 = 2*y0*y1+y2, y2+y1*y1
    • if (n>>i)&1:
    • xy = x0*y0
    • y0, y1 = x0*y1+x1*y0+xy, xy+x1*y1
    • return y0
    • def fib(n):
    • if n<0:
    • if n%2: return fib(-n)
    • else: return -fib(-n)
    • def transform(a,b,p,q,n):
    • if n==0: return a
    • if n%2==0:
    • return transform(a,b,p*p+q*q,q*q+2*p*q,n/2)
    • else:
    • return transform(a*q+a*p+b*q,b*p+a*q,p,q,n-1)
    • return transform(1,0,0,1,n)
    • return _fib(n+1)