C#

Private Function GetFib3(ByVal n As Integer) As ULong
       Dim a As Int64 = 0
       Dim b As Int64 = 1

       If (n = 0) Then Return a
       If (n = 1) Then Return b

       For i As UInt64 = 2 To n
           a = a Xor b
           b = b Xor a
           a = a Xor b

           ' add
           b += a
       Next

       Return b
   End Function

Kenneth Haugland wrote:

Dim a As Int64 = 0
Dim b As Int64 = 1

Private Function GetFib3(ByVal n As Integer) As ULong
   Dim a As ULong = 0
   Dim b As ULong = 1

   If (n = 0) Then Return a
   If (n = 1) Then Return b

   For i As ULong = 2 To Convert.ToUInt64(n)
       a = a Xor b
       b = b Xor a
       a = a Xor b

       ' add
       b += a
   Next

   Return b
End Function

Private Function GetFib2(ByVal n As Integer) As Numerics.BigInteger
    Dim a As New Numerics.BigInteger
    a = 0
    Dim b As New Numerics.BigInteger
    b = 1

    If (n = 0) Then Return a
    If (n = 1) Then Return b

    For i As UInt64 = 2 To n
        a = a Xor b
        b = b Xor a
        a = a Xor b

        ' add
        b += a
    Next

    Return b
End Function

static ulong Fibonacci(uint n)
{
    ulong m00 = 1, m01 = 1, m10 = 1, m11 = 0;
    ulong x00 = 1, x01 = 1, x10 = 1, x11 = 0;

    while (n != 0)
    {
        if ((n & 1) != 0)
        {
            ulong t00 = m00 * x00 + m01 * x10;
            ulong t01 = m00 * x01 + m01 * x11;
            ulong t10 = m10 * x00 + m11 * x10;
            ulong t11 = m10 * x01 + m11 * x11;
            x00 = t00;
            x01 = t01;
            x10 = t10;
            x11 = t11;
        }

        ulong y00 = m00 * m00 + m01 * m10;
        ulong y01 = m00 * m01 + m01 * m11;
        ulong y10 = m10 * m00 + m11 * m10;
        ulong y11 = m10 * m01 + m11 * m11;
        m00 = y00;
        m01 = y01;
        m10 = y10;
        m11 = y11;

        n >>= 1;
    }

    return x01;
}

Max Holder wrote:

I tested the swap with a temp ulong too, it was a bit slower than the XOR swap.

harold aptroot wrote:

is that XOR-swap really faster than a normal swap?

PIEBALDconsult wrote:

How could it be?

harold aptroot wrote:

how that would help

Max Holder wrote:

Only up to n=200; n=201 result is bigger than ulong

checked { b += a; }

• n = 92: 7540113804746346429
• n = 93: 12200160415121876738
• n = 94: 1293530146158671551

private static ulong GetFib3(int n)
{
    ulong a = 0;
    ulong b = 1;

    if (n == 0) return a;
    if (n <= 2) return b;

    if ((n & 1) == 0)
    {
        a = 1;
        n--;
    }

    int i = n - 1;
    do
    {
        a += b;
        b += a;
        i -= 2;
    } while (i != 0);

    return b;
}

private static ulong
Fibo2
(
  int n
)
{
  ulong a = (ulong) n & 1 ;
  ulong b = a ^ 1 ;

  for ( n /= 2 ; n > 0 ; --n ) checked { a += b += a ; }

  return ( a ) ;
}

private static ulong[] a = new ulong [ 3 ] ;

private static ulong
Fibo
(
  int n
)
{
  a [ 0 ] = a [ 1 ] = 0 ;
  a [ 2 ] = 1 ;
  int x = 2 ;
  int y = 1 ;

  for ( ; n > 0 ; --n )
  {
    a [ 0 ] = a [ x ] += a [ y ] ;

    x ^= 3 ;
    y ^= 3 ;
  }

  return ( a [ 0 ] ) ;
}