Click here to Skip to main content
16,015,942 members
Home / Discussions / C#
   

C#

 
GeneralRe: Optimizing Fibonacci Calculation Pin
Kenneth Haugland18-Apr-13 4:16
mvaKenneth Haugland18-Apr-13 4:16 
GeneralRe: Optimizing Fibonacci Calculation Pin
Richard Deeming18-Apr-13 4:23
mveRichard Deeming18-Apr-13 4:23 
GeneralRe: Optimizing Fibonacci Calculation Pin
Kenneth Haugland18-Apr-13 4:26
mvaKenneth Haugland18-Apr-13 4:26 
GeneralRe: Optimizing Fibonacci Calculation Pin
Richard Deeming18-Apr-13 5:05
mveRichard Deeming18-Apr-13 5:05 
GeneralRe: Optimizing Fibonacci Calculation Pin
Kenneth Haugland18-Apr-13 5:14
mvaKenneth Haugland18-Apr-13 5:14 
GeneralRe: Optimizing Fibonacci Calculation Pin
Max Holder18-Apr-13 5:02
professionalMax Holder18-Apr-13 5:02 
GeneralRe: Optimizing Fibonacci Calculation Pin
Jasmine250118-Apr-13 6:38
Jasmine250118-Apr-13 6:38 
GeneralRe: Optimizing Fibonacci Calculation Pin
harold aptroot18-Apr-13 4:25
harold aptroot18-Apr-13 4:25 
Here is the matrix-power version, it's asymptotically faster but probably not real-life faster because `n` is always low. Worth a try though
C#
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;
}

By the way, is that XOR-swap really faster than a normal swap?
GeneralRe: Optimizing Fibonacci Calculation Pin
Max Holder18-Apr-13 21:20
professionalMax Holder18-Apr-13 21:20 
GeneralRe: Optimizing Fibonacci Calculation Pin
harold aptroot18-Apr-13 21:25
harold aptroot18-Apr-13 21:25 
GeneralRe: Optimizing Fibonacci Calculation Pin
PIEBALDconsult24-Apr-13 4:23
mvePIEBALDconsult24-Apr-13 4:23 
GeneralRe: Optimizing Fibonacci Calculation Pin
PIEBALDconsult20-Apr-13 6:31
mvePIEBALDconsult20-Apr-13 6:31 
GeneralRe: Optimizing Fibonacci Calculation Pin
harold aptroot20-Apr-13 6:41
harold aptroot20-Apr-13 6:41 
GeneralRe: Optimizing Fibonacci Calculation Pin
PIEBALDconsult20-Apr-13 9:36
mvePIEBALDconsult20-Apr-13 9:36 
GeneralRe: Optimizing Fibonacci Calculation Pin
harold aptroot20-Apr-13 9:58
harold aptroot20-Apr-13 9:58 
GeneralRe: Optimizing Fibonacci Calculation Pin
PIEBALDconsult20-Apr-13 10:22
mvePIEBALDconsult20-Apr-13 10:22 
GeneralRe: Optimizing Fibonacci Calculation Pin
Kenneth Haugland18-Apr-13 4:55
mvaKenneth Haugland18-Apr-13 4:55 
GeneralRe: Optimizing Fibonacci Calculation Pin
Richard Deeming18-Apr-13 5:09
mveRichard Deeming18-Apr-13 5:09 
AnswerRe: Optimizing Fibonacci Calculation Pin
Clifford Nelson18-Apr-13 5:15
Clifford Nelson18-Apr-13 5:15 
QuestionRe: Optimizing Fibonacci Calculation Pin
Kenneth Haugland18-Apr-13 6:29
mvaKenneth Haugland18-Apr-13 6:29 
AnswerRe: Optimizing Fibonacci Calculation Pin
harold aptroot18-Apr-13 6:39
harold aptroot18-Apr-13 6:39 
GeneralRe: Optimizing Fibonacci Calculation Pin
harold aptroot18-Apr-13 6:55
harold aptroot18-Apr-13 6:55 
GeneralRe: Optimizing Fibonacci Calculation Pin
Max Holder18-Apr-13 21:21
professionalMax Holder18-Apr-13 21:21 
GeneralRe: Optimizing Fibonacci Calculation Pin
PIEBALDconsult20-Apr-13 12:26
mvePIEBALDconsult20-Apr-13 12:26 
GeneralRe: Optimizing Fibonacci Calculation Pin
PIEBALDconsult20-Apr-13 6:24
mvePIEBALDconsult20-Apr-13 6:24 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.