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?
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 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. :)
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).
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:
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 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. :)
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?)
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 Svin's example):
*Use ADC and another XADD for 64-bit.
(How fast is this V Coder? Should be faster than an uncached table lookup on most newer machines. :))
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. :))