ASM Community

[size=9]0               - 0000000000000000000000000000000

1               - 0000000000000000000000000000001



1               - 0000000000000000000000000000001

2               - 0000000000000000000000000000010

3               - 0000000000000000000000000000011

5               - 0000000000000000000000000000101

8               - 0000000000000000000000000001000

13              - 0000000000000000000000000001101

21              - 0000000000000000000000000010101

34              - 0000000000000000000000000100010

55              - 0000000000000000000000000110111

89              - 0000000000000000000000001011001

144             - 0000000000000000000000010010000

233             - 0000000000000000000000011101001

377             - 0000000000000000000000101111001

610             - 0000000000000000000001001100010

987             - 0000000000000000000001111011011

1597            - 0000000000000000000011000111101

2584            - 0000000000000000000101000011000

4181            - 0000000000000000001000001010101

6765            - 0000000000000000001101001101101

10946           - 0000000000000000010101011000010

17711           - 0000000000000000100010100101111

28657           - 0000000000000000110111111110001

46368           - 0000000000000001011010100100000

75025           - 0000000000000010010010100010001

121393          - 0000000000000011101101000110001

196418          - 0000000000000101111111101000010

317811          - 0000000000001001101100101110011

514229          - 0000000000001111101100010110101

832040          - 0000000000011001011001000101000

1346269         - 0000000000101001000101011011101

2178309         - 0000000001000010011110100000101

3524578         - 0000000001101011100011111100010

5702887         - 0000000010101110000010011100111

9227465         - 0000000100011001100110011001001

14930352        - 0000000111000111101000110110000

24157817        - 0000001011100001001111001111001

39088169        - 0000010010101000111000000101001

63245986        - 0000011110001010000111010100010

102334155       - 0000110000110010111111011001011

165580141       - 0001001110111101000110101101101

267914296       - 0001111111110000000110000111000

433494437       - 0011001110101101001100110100101

701408733       - 0101001110011101010010111011101

1134903170      - 1000011101001010011111110000010

1836311903      - 1101101011100111110010101011111[/size]

// This program generates the fibonocci

// sequence for n=1..40.

//

// The fibonocci sequence is defined recursively

// for positive integers as follows:

//

//  fib(1) = 1;

//  fib(2) = 1;

//  fib( n ) = fib( n-1 ) + fib( n-2 ).

//

//  This program provides an iterative solution.





program fib;

#include( "stdlib.hhf" );



static



    FibCntr:    int32;

    CurFib:     int32;

    LastFib:    int32;

    TwoFibsAgo: int32;



begin fib;



    // Some simple initialization:



    mov( 1, LastFib );

    mov( 1, TwoFibsAgo );



    // Print fib(1) and fib(2) as a special case:



    stdout.put

    (

        "fib( 1) =         1", nl

        "fib( 2) =         1", nl

    );



    // Use a loop to compute the remaining fib values:



    mov( 3, FibCntr );

    while( FibCntr <= 40 ) do



        // Get the last two computed fibonocci values

        // and add them together:

        

        mov( LastFib, ebx );

        mov( TwoFibsAgo, eax );

        add( ebx, eax );

        

        // Save the result and print it:

        

        mov( eax, CurFib );

        stdout.put( "fib(",FibCntr:2, ") =", CurFib:10, nl );

        

        // Recycle current LastFib (in ebx) as TwoFibsAgo,

        // and recycle CurFib as LastFib.



        mov( eax, LastFib );

        mov( ebx, TwoFibsAgo ); 



        // Bump up our loop counter:



        add( 1, FibCntr );



    endwhile;



end fib;

program fibIter;

#include( "stdlib.hhf" )



// Fibonocci function using a thunk to calculate fib(n-2)

// without making a recursive call.



procedure fib( n:uns32; nm2:thunk ); @nodisplay; returns( "eax" );

var

    n2: uns32;      // A recursive call to fib stores fib(n-2) here.

    t:  thunk;      // This thunk actually stores fib(n-2) in n2.



begin fib;



    // Special case for n = 1, 2.  Just return 1 as the

    // function result and store 1 into the fib(n-2) result.



    if( n <= 2 ) then



        mov( 1, eax );  // Return as n-1 value.

        nm2();          // Store into caller as n-2 value.



    else



        // Create a thunk that will store the fib(n-2) value

        // into our local n2 variable.



        thunk   t :=

                #{

                    mov( eax, n2 );

                }#;



        mov( n, eax );

        dec( eax );

        fib( eax, t );  // Compute fib(n-1).



        // Pass back fib(n-1) as the fib(n-2) value to a previous caller.

         

        nm2();





        // Compute fib(n) = fib(n-1) [in eax] + fib(n-2) [in n2]:



        add( n2, eax );



    endif;



end fib;





// Standard fibonocci function using the slow recursive implementation.



procedure slowfib( n:uns32 ); @nodisplay; returns( "eax" );

begin slowfib;



    // For n= 1,2 just return 1.



    if( n <= 2 ) then



        mov( 1, eax );



    else



        // Return slowfib(n-1) + slowfib(n-2) as the function result:



        dec( n );

        slowfib( n );   // compute fib(n-1)

        push( eax );    // Save fib(n-1);



        dec( n );       // compute fib(n-2);

        slowfib( n );



        add( [esp], eax );  // Compute fib(n-1) [on stack] + fib(n-2) [in eax].

        add( 4, esp );      // Remove old value from stack.



    endif;



end slowfib;





// FibNum-

//

//  Iterator that generates all the fibonacci numbers between 1 and n.



iterator FibNum( n:uns32 ); @nodisplay;

var

    Fibn_1: uns32;      // Holds Fib(n-1) for a given n.

    Fibn_2: uns32;      // Holds Fib(n-2) for a given n.

    CurFib: uns32;      // Current index into fib sequence.

    

begin FibNum;



    mov( 1, Fibn_1 );   // Initialize these guys upon initial entry.

    mov( 1, Fibn_2 );

    mov( 1, eax );      // Fib(0) = 1

    yield();

    mov( 1, eax );      // Fib(1) = 1;

    yield();

    mov( 2, CurFib );

    forever

    

        mov( CurFib, eax );     // Compute sequence up to the nth #.

        breakif( eax > n );

        mov( Fibn_2, eax );     // Compute this result.

        add( Fibn_1, eax );



        // Recompute the Fibn_1 and Fibn_2 values:

        

        mov( Fibn_1, Fibn_2 );

        mov( eax, Fibn_1 );

        

        // Return current value:

        

        yield();

        

        // Next value in sequence:

        

        inc( CurFib );

        

    endfor;

    

end FibNum;

    





var

    prevTime:dword[2];      // Used to hold 64-bit result from RDTSC instr.

    qw: qword;              // Used to compute difference in timing.

    dummy:thunk;            // Used in original calls to fib.



begin fibIter;



    // "Do nothing" thunk used by the initial call to fib.

    // This thunk simply returns to its caller without doing

    // anything.



    thunk dummy := #{ }#;





    // Call the fibonocci routines to "prime" the cache:



    fib( 1, dummy );

    slowfib( 1 );

    foreach FibNum( 1 ) do

    endfor;







    // Okay, compute the running times for the three fibonocci routines to

    // generate a sequence of n fibonacci numbers where n ranges from

    // 1 to 32:



    for( mov( 1, ebx ); ebx < 32; inc( ebx )) do



        // Emit the index:

        

        stdout.put( (type uns32 ebx):2, stdio.tab );

        

        // Compute the # of cycles needed to compute the Fib via iterator:



        rdtsc();

        mov( eax, prevTime );

        mov( edx, prevTime[4] );



        foreach FibNum( ebx ) do

        

        endfor;

        

        rdtsc();

        sub( prevTime, eax );

        sbb( prevTime[4], edx );

        mov( eax, (type dword qw));

        mov( edx, (type dword qw[4]));



        stdout.putu64Size( qw, 4, ' ' );

        stdout.putc( stdio.tab );









        // Read the time stamp counter before calling fib:

        

        rdtsc();

        mov( eax, prevTime );

        mov( edx, prevTime[4] );



        for( mov( 1, ecx ); ecx <= ebx; inc( ecx )) do

        

            fib( ecx, dummy );



        endfor;



        // Read the timestamp counter and compute the approximate running

        // time of the current call to fib:



        rdtsc();

        sub( prevTime, eax );

        sbb( prevTime[4], edx );

        mov( eax, (type dword qw));

        mov( edx, (type dword qw[4]));



        // Display the results and timing from the call to fib:



        stdout.putu64Size( qw, 10, ' ' );

        stdout.putc( stdio.tab );





        // Okay, repeat the above for the slowfib implementation:



        rdtsc();

        mov( eax, prevTime );

        mov( edx, prevTime[4] );



        for( mov( 1, ecx ); ecx <= ebx; inc( ecx )) do

        

            slowfib( ebx );



        endfor;

        

        rdtsc();

        sub( prevTime, eax );

        sbb( prevTime[4], edx );

        mov( eax, (type dword qw));

        mov( edx, (type dword qw[4]));



        stdout.putu64Size( qw, 10, ' ' );

        stdout.newln();

        

        



    endfor;



end fibIter;