Maybe this is a stupid question (I'm a novice) but how many ways are there to solve this? I hear that there are more efficient methods than the two I use below, can this be solved in just three lines?

Also what is the fastest method?

``````
; =====================
; ===== FIBONACCI =====
; =====================
mov al,1  ; Set initial values
mov bl,0
mov cl,0
here:
add cl,al  ; CL contains the result
push   bl ; Copy BL into AL
pop al
push   cl ; Copy CL into BL
pop bl
jmp here ; Next step in the series
end
``````

``````
; =====================
;Solution using a RAM location.
; =====================
; ===== FIBONACCI =====
; =====================
mov al,1  ; Set initial values
mov bl,0
mov [40],bl
here:
add bl,al ; BL contains the result
mov al,[40]
mov [40],bl
jmp here  ; Next step in the series
end
; =====================
``````
Posted on 2003-07-09 17:34:56 by Alone
There is a formula to solve it.
Posted on 2003-07-09 18:00:50 by comrade
I know there is a formula but that's not what I asked and there are many ways to implement it so I have been told (methods involving recursion as well). Or do you suggest I use the formula without any translation to asm?

Btw I am learning asm on my own and I expected more help than that, so basically can someone answer all of my questions please without none of the bullshit (no offence to anyone but I would appreciate straight answers no matter how lame you think I am).

And before anyone tells me to go "Google it" I have looked and haven't found any good examples. :)
Posted on 2003-07-09 18:42:28 by Alone

And before anyone tells me to go "Google it" I have looked and haven't found any good examples. :)
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html

Posted on 2003-07-09 19:00:50 by bitRAKE

Thanks for the help but again not what I asked, I want practical examples of all/some of the different ways in assembly language not a page with a primer on the formula.

I want to know if there are infinite ways to implement this formula in asm and what is the most efficient way of doing so.
Posted on 2003-07-09 19:12:30 by Alone
``````[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]``````
oh I don't know, probably a pattern on each columns? :grin:

try pasting this on an editor that has a column mode which you can highlight a column and use a monospace font...
Posted on 2003-07-09 19:18:33 by arkane
Firstly,
It seems that no matter what question you ask, for someone to answer, they have to take quite some time to perform the search for you, since noone has all the code for everything stored in their minds: so they have to visit google just as you. But the good thing about assembly programming is that the answers for many questions, and algorithms for the same are on the net in abundance if you know how to look for them.

I just searched google for ... fibonacci assembly (No quotes, etc...)

I was not going to search the net, actually, since I downloaded Randall Hyde's "Art of Assembly Language" late last year, and he provides several different implementations, as I recall, each successive version is (much) faster than the previous:

straight search,
recursion
iterators
thunks

He has full source code for each routine (written in HLA - High Level Assembly) see another part of this Win32 site for information on it. But I did have to search my room for my printed copy to remind myself of how he programmed it.

Secondly,
It is always recommeded to search the Win32 site first (see the search button at the top right hand) for help on any topic before posting:
"I am new here" "If you have a question, please first try to solve it with our search function. It's very fast and may point you to a thread where the same question was already asked."

When you search you will find test code by The Svin for fibonacci posted (to test another algorithm)...

Thirdly,
Your algorithm should fail pretty quickly since it only copes with 8-bit numbers in al, bl, etc. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
144 and 233 are valid unsigned numbers but not signed. They cause a signed overflow. 377 causes an unsigned overflow.

Fourthly,
Since this is Win32 programming, you will need to get away from the 8-bit and 16-bit programming paradigm very quickly. We scarcely use 8-bit registers. Only when absolutely necessary. 32-bit numbers have a higher unsigned limit >4 billion, and signed limit from less than -2 billion to more than 2 billion.
That can handle many more iterations of the fibonacci sequence...

Fifthly,
Patience, patience! To respond to any post means that someone must divert his attention at least 5 minutes from what he was doing before. Some people do not have the time or interest in the algorithm or knowledge of where to get specific answers to help. I have a little time (I have spent >30 minutes here), some knowledge of the algorithm, and knowledge of where to get some answers (Randall Hyde's book), but NO interest in fibonacci!!! I executed Randy's fibonacci program some time ago, while learning about the features in the program. Now I am using HLA for one particular project, and learning only what is essential for my project.

Sixthly,
If you want to interest people in a programming problem, it is better to follow the counsel given in the Frequently Asked Questions...
"Help me with my Homework" "Do it yourself then post your questions."
If you post a complete program, many people are likely to test it and tell you how to improve it.

Finally,
Since this topic is about algorithms, it may better have been posted on the algorithm page - no problem. You can ask the moderator to move it (or they will eventually anyway).
Posted on 2003-07-09 19:33:37 by V Coder
Originally posted by arkane
oh I don't know, probably a pattern on each columns? :grin:

Arkane, you are a genius!!! (Or maybe not)... :cool:

Might this be a way to determine an arbitrary value in the sequence? That's something to look into. However, the pattern of the most significant bit might not be known beforehand...
Posted on 2003-07-09 19:42:02 by V Coder
I wrote the app sometime ago to check
some libs, it just show the sequence.
May be you can find a use of it.
Posted on 2003-07-09 19:51:09 by The Svin
Here are 4 algorithms from Randy's book. The first program is a straight search. The second compares Recursion, Iteration and Thunks...

``````// 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

mov( LastFib, ebx );
mov( TwoFibsAgo, 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:

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]:

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.

// 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;
``````
Posted on 2003-07-09 20:01:37 by V Coder
Here are the run-time cycles for the Iterator function, the Thunk function, and Recursion, respectively, for each fib nunmber. The second program above was compiled and run (console mode) on my Pentium III 1066...(with my browser open and internet connected so some RDTSC times (eg. 20, 22, 24, 28, 30 for Iterator) are obviously wrong - however much processor time going to different threads. The value for 31 is also too far from 30 to be correct. No problem: 1000 cycles is still less than a microsecond!!! In comparison to 2 seconds for the last recursion!!!

`````` 1       136           131              92
2       166           160             106
3       192           272             287
4       207           402             494
5       236           577             984
6       245           797            1734
7       262          1009            3836
8       281          1236            6883
9       301          1523           12239
10       323          1848           22359
11       340          2188           39788
12       359          2569          255628
13       380          3318          122914
14       400          3421          215023
15       423          3891          372133
16       439          4397          982422
17       457          4961         1104284
18       475          5539         2252104
19       504          6158         4020264
20       703          7087         6590072
21       540          7731        47901252
22       793          8759        17851868
23       571          9584        32153729
24       741         10219        51990931
25       621         11337        83777375
26       627         12141       144056904
27       658         13226       242948164
28      1180         14662       454582274
29       689         15358       678341147
30       709         16427      1141638934
31       986         17789      1868647883``````

``````29       695         15517       671562486
30       715         16598      1136735726
31       729         18195      1887330540``````

So the actual time is at most 689, 709, 729 respectively.
Posted on 2003-07-09 20:14:27 by V Coder
Thanks everyone for your help and I appreciate all the time and effort you guys spent!

Yeah about the 8bit examples I posted, I want to get a grasp on the basic concepts first before I progress to using more registers. (bad idea?)

Ok fair enough I will try and help myself before asking but obviously if I could then I wouldn't be asking, I am not usually one to ask for help and I didn't know anywhere else to go (I searched the entire board and the web beforehand) but just so you know it is not homework, as I mentioned previously I'm learning on my own.

About HLA, I know what it is and I have heard of the book AoA but I did not know those examples were in there since I'm not learning HLA.

Most of you guys have way more experience than me so I kinda expected some help even if you think I should be able to figure it out on my own, should I feel guilty that I asked for help? Have you guys forgotten where you started or am I just that stupid?

But anyways I'm really grateful for all the help and I hope this post will be useful to people like me or not. :)
Posted on 2003-07-09 21:49:08 by Alone

Arkane, you are a genius!!! (Or maybe not)... :cool:

Might this be a way to determine an arbitrary value in the sequence? That's something to look into. However, the pattern of the most significant bit might not be known beforehand...
first, please don't call me a genius, 'cause I hate it :grin: :grin: :grin: just call it a good idea... :grin:

second, well probably you are right but I haven't really studied the pattern very well just a glance from the few columns starting on the right... which I can see a pattern on columns 0, 1 and 2.

what I had in mind was if someone will find an algorithm to this pattern or any other pattern in binary, we can generate easily the number sequence without using complex addition.

example: we can generate numbers with 1 to X digits on a table easily without addition, of course memory management comes into mind here...

theoritically, it should be *faster* but I can't guarantee in real world tests.

just a thought. :grin: I could be wrong... :grin:
Posted on 2003-07-09 22:21:58 by arkane
Originally posted by Alone
Yeah about the 8bit examples I posted, I want to get a grasp on the basic concepts first before I progress to using more registers. (bad idea?)

Yes, jump in at 32 bit Windows code, unless you intend to program for DOS. Anyway, try using the best tools for the job, in this case 32 bit...
What Assembler are you using?
Originally posted by Alone Ok fair enough I will try and help myself before asking but obviously if I could then I wouldn't be asking, I am not usually one to ask for help and I didn't know anywhere else to go (I searched the entire board and the web beforehand) but just so you know it is not homework, as I mentioned previously I'm learning on my own.

I did not think it was homework, but the principle still applies.
Originally posted by Alone About HLA, I know what it is and I have heard of the book AoA but I did not know those examples were in there since I'm not learning HLA.

Your loss, since it is a really good way to learn many aspects of Assembly programming.
Originally posted by Alone Most of you guys have way more experience than me so I kinda expected some help even if you think I should be able to figure it out on my own, should I feel guilty that I asked for help? Have you guys forgotten where you started or am I just that stupid?

I'm not sure anyone thinks you're stupid. But I was irritated at your second post. There was no need to get so hot-headed, especially since you got an answer pretty quickly...It really takes time for people to search for answers to help you, even if they are experienced. (I'm just a beginner myself). Sometimes the people with the answers may not log on during the day, or at the time you expect answers.
Originally posted by Alone But anyways I'm really grateful for all the help and I hope this post will be useful to people like me or not. :)

The whole point of this (community) forum is to benefit all the forum users. You can probably try to convert the first program above to MASM32 and post it here for others to benefit. Not so sure about the second one. It involves advanced HLA and Assembly concepts. In fact, I'm not sure if the iterator feature or thunks are available in other Assemblers (someone else would probably know).
Posted on 2003-07-09 22:54:11 by V Coder
There are infinite ways to do this in ASM. This is my favorite sequence in all the world. Here is another method (also used in Svin's example):
``````fib PROC n:DWORD
; n only valid on [1,47]
mov	edx, 1
mov	eax, 0
mov	ecx, n
dec	ecx
jne	@B
ret
fib ENDP``````

``````
fib64 PROC USES esi edi, n:DWORD
; n only valid on [1,93]
mov	eax, 0
mov	edi, 1
mov	edx, 0
mov	esi, 0
mov	ecx, n