Maybe this is a stupid question (I'm a novice) but how many

Also what is the fastest method?

*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

; =====================

There is a formula to solve it.

I know there is a formula but that's not what I asked and there

Btw I am learning asm on my own and I expected more help than that, so basically can someone answer

And before anyone tells me to go "Google it" I have looked and haven't found any good examples. :)

**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. :)

And before anyone tells me to go "Google it" I have looked and haven't found any good examples. :)

First result on Google. :grin:

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html

First result on Google. :grin:

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.

```
[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...

**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.

Anyway, on my google search, the 8th item was a link to a pdf from his site. If you follow it up you can find four routines. He should have downloads of the code available (you may have to download the HLA compiler to try it out, indeed you may have to download the entire example code zip file). I have not tried to explain each type of routine since I am learning HLA myself right now, but it is fully explained in 3 or four chapters in Randy's very large (>1500 pages) FREE book (which can also be downloaded from his site).

**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).

*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...

I wrote the app sometime ago to check

some libs, it just show the sequence.

May be you can find a use of it.

some libs, it just show the sequence.

May be you can find a use of it.

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

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

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!!!

Another run had these figures...

So the actual time is at most 689, 709, 729 respectively.

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

Another run had these figures...

```
29 695 15517 671562486
```

30 715 16598 1136735726

31 729 18195 1887330540

So the actual time is at most 689, 709, 729 respectively.

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

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

But anyways I'm really grateful for all the help and I hope this post will be useful to people like me or not. :)

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. :)

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...

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:

*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).

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

*Use ADC and another XADD for 64-bit.

(How fast is this

**Svin**'s example):```
fib PROC n:DWORD
```

; n only valid on [1,47]

mov edx, 1

mov eax, 0

mov ecx, n

@@: xadd eax, edx

dec ecx

jne @B

ret

fib ENDP

Many coders forget XADD. :)
*Use ADC and another XADD for 64-bit.

```
```

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

@@: xadd eax, edi

adc esi, 0

xadd edx, esi

dec ecx

jne @B

ret

fib64 ENDP

(How fast is this

**V Coder**? Should be faster than an uncached table lookup on most newer machines. :))