Fibonacci Sequence using Recursion with Memoisation

Question

File fibonacci.aec:

syntax GAS ;We are, of course, targeting GNU Assembler here, rather than FlatAssembler, to be compatible with GCC. verboseMode on ;Tells ArithmeticExpressionCompiler to output more comments into the assembly code it produces (fibonacci.s). AsmStart .global fibonacci #We need to tell the linker that "fibonacci" is the name of a function, and not some random label. fibonacci: AsmEnd If not(mod(n,1)=0) ;If 'n' is not a integer, round it to the nearest integer. n := n + ( mod(n,1) > 1/2 ? 1-mod(n,1) : (-mod(n,1))) EndIf If n<2 ;The 1st Fibonacci number is 1, and the 0th one is 0. returnValue := n > -1 ? n : 0/0 ;0/0 is NaN (indicating error), because negative Fibonacci numbers don't exist AsmStart .intel_syntax noprefix ret #Far return (to the other section, that is, to the C++ program). The way to do a same-section return depends on whether we are in a 32-bit Assembler or a 64-bit Assembler, while the far return is the same (at least in the "intel_syntax mode"). .att_syntax AsmEnd ElseIf not(memoisation[n]=0) ;Has that Fibonacci number already been calculated? returnValue:=memoisation[n] AsmStart .intel_syntax noprefix ret .att_syntax AsmEnd EndIf ;And now comes the part where we are tricking ArithmeticExpressionCompiler into supporting recursion... topOfTheStackWithLocalVariables := topOfTheStackWithLocalVariables + 2 ;Allocate space on the stack for 2 local variables ('n', the argument passed to the function, and the temporary result). temporaryResult := 0 ;The sum of fib(n-1) and fib(n-2) will be stored here, first 0 then fib(n-1) then fib(n-1)+fib(n-2). stackWithLocalVariables[topOfTheStackWithLocalVariables - 1] := temporaryResult ;Save the local variables onto the stack, for the recursive calls will corrupt them (as they are actually global variables, because ArithmeticExpressionCompiler doesn't support local ones). stackWithLocalVariables[topOfTheStackWithLocalVariables] := n n:=n-1 AsmStart .intel_syntax noprefix call fibonacci .att_syntax AsmEnd temporaryResult := stackWithLocalVariables[topOfTheStackWithLocalVariables - 1] temporaryResult := temporaryResult + returnValue ;"returnValue" is supposed to contain fib(n-1). ;And we repeat what we did the last time, now with n-2 instead of n-1... stackWithLocalVariables[topOfTheStackWithLocalVariables - 1] := temporaryResult n := stackWithLocalVariables[topOfTheStackWithLocalVariables] n := n - 2 AsmStart .intel_syntax noprefix call fibonacci .att_syntax AsmEnd temporaryResult := stackWithLocalVariables[topOfTheStackWithLocalVariables - 1] temporaryResult := temporaryResult + returnValue stackWithLocalVariables[topOfTheStackWithLocalVariables - 1] := temporaryResult n := stackWithLocalVariables [topOfTheStackWithLocalVariables] returnValue := temporaryResult memoisation[n] := returnValue topOfTheStackWithLocalVariables := topOfTheStackWithLocalVariables - 2 AsmStart .intel_syntax noprefix ret .att_syntax AsmEnd 

File let_gcc_setup_gas.cpp:

/*The C++ wrapper around "fibonacci.aec". Compile this as: node aec fibonacci.aec #Assuming you've downloaded aec.js from the releases. g++ -o fibonacci let_gcc_setup_gas.cpp fibonacci.s */ #include <algorithm> //The "fill" function. #include <cmath> //The "isnan" function. #include <iostream> #ifdef _WIN32 #include <cstdlib> //system("PAUSE"); #endif extern "C" { // To the GNU Linker (which comes with Linux and is used by GCC), // AEC language is a dialect of C, and AEC is a C compiler. float n, stackWithLocalVariables[1024], memoisation[1024], topOfTheStackWithLocalVariables, temporaryResult, returnValue, result; // When using GCC, there is no need to declare variables in the same // file as you will be using them, or even in the same language. So, // no need to look up the hard-to-find information about how to // declare variables in GNU Assembler while targeting 64-bit Linux. // GCC and GNU Linker will take care of that. void fibonacci(); // The ".global fibonacci" from inline assembly in // "fibonacci.aec" (you need to declare it, so that the C++ // compiler doesn't complain: C++ isn't like JavaScript or AEC // in that regard, C++ tries to catch errors such as a // mistyped function or variable name in compile-time). } int main() { std::cout << "Enter n:" << std::endl; std::cin >> n; topOfTheStackWithLocalVariables = -1; if (n >= 2) std::fill(&memoisation[0], &memoisation[int(n)], 0); // This is way more easily done in C++ than in AEC here, // because the AEC subprogram doesn't know if it's being // called by C++ or recursively by itself. fibonacci(); if (std::isnan(returnValue)) { std::cerr << "The AEC program returned an invalid decimal number." << std::endl; return 1; } std::cout << "The " << n << ((int(n) % 10 == 3) ? ("rd") : (int(n) % 10 == 2) ? ("nd") : (int(n) % 10 == 1) ? ("st") : "th") << " Fibonacci number is " << returnValue << "." << std::endl; #ifdef _WIN32 std::system("PAUSE"); #endif return 0; } 

The executable files for Windows and Linux are available here, and the assembly code that my compiler for AEC generates is available here.
So, what do you think about it?

Answer 1

Why would you do such a thing?

I understand that you wrote the Arithmetic Expression Compiler, and perhaps want to show it off. But who would ever want to write a function as simple as a Fibonacci sequence generater using three programming languages (AEC, Intel assembly, and C++) mixed together, and type way more code than it would take in either C++ or even pure Intel assembly itself to implement it?

AEC doesn't provide any benefits here. Looking at the generated assembly, AEC does not perform any kind of optimization.

fibonacci.aec syntax

The syntax in fibonacci.aec looks quite bad. There's assembly code mixed with AEC's own language. It seems AEC generates ATT syntax, and your inline assembly uses Intel syntax, and you have to manually switch between the two. Also, the instructions you do have to add manually seem very trivial: call and ret. It would be much nicer if the AEC language allowed you to express these operations, so you wouldn't need to add assembly.

Comments about your C++ code

Use of global variables

I suppose it is a limitation of AEC that you have to use global variables to communicate between the generated assembly code and the C++ code. However, now you have the problem that you cannot call fibonacci() from different threads simultaneously. There's also a compile-time limit on how many elements of the Fibonacci sequence you can generate, due to the size of stackWithLocalVariables[] and memoisation[].

Floats vs. ints

Your AEC only deals with 32-bit floating point values, but the C++ program deals with integers, and now has to convert to and from floating point variables to satisfy the assembly code. But a lot of conversions are there only because you are reusing float n to store the user's input, even if you clearly expect an integer. Far better would be to declare an int variable in main(), and copy it to n to satisfy fibonacci(), but avoid all the int(n) casts.

Elevenst, twelfnd, thirteenrd

The suffix you add to print out "The n-th Fibonacci number is" is calculated using an expression that doesn't catch all the edge cases. I suggest you just do not try to add such a suffix at all, and instead write something like:

std::cout << "Element " << n << " in the Fibonacci sequence is equal to " << returnValue << ".\n"; 

Use "\n" instead of std::endl

I strongly suggest you use "\n" instead of std::endl; the latter is equivalent to "\n", but it also forces a flush of the output stream. That is usually unnecessary and can be detrimental to performance.

Avoid using std::system() for trivial things

Using std::system() is usually wrong. has a huge overhead: it has to create a new shell process, that process has to parse the command you gave, and if that command is not a built-in function of the shell, then it has to start yet another process. As you already have noticed, it also is not portable between different operating systems. And something trivial as std::system("PAUSE") can be replaced by a simple C++ statement like:

std::cin.get();