Quiz: Computing the factorial recursively
Having subprograms that can call other subprograms is sufficient to implement a program that computes the factorial recursively. Use the C code below as a pseudo code description for your assembly program factorial.s.
On theon submit your program with the command
submit hpc quiz11 factorial.s
Of course it is intended that you make use of the example program from the previous page.
C code as pseudo code for your program
This code describes a program with subprograms factorial, getui, puts, putui and main that use the global variable arg for communication. Execution of the program begin with a call of main.
// for passing an argument and receiving a return value
uint64_t arg;
void
factorial()
{
uint64_t n;
if (arg == 0) {
arg = 1;
} else {
n = arg;
arg = n-1;
factorial();
arg = arg * n;
}
}
void
getui()
{
// implementation of subprogram getui
}
void
puts()
{
// implementation of subprogram puts
}
void
putui()
{
// implementation of subprogram putui
}
// some strings
char msg0[] = "n = ";
char msg1[] = "! = ";
void
main()
{
// local variable
uint64_t n;
// copy pointer to string literal to arg, call puts
arg = msg0;
puts();
// call subprogram getui, copy return value to local variable
getui();
n = arg;
// copy local variable to arg, call putui
arg = n; // could be "optimized away"
putui();
// copy pointer to string literal to arg, call puts
arg = msg1;
puts();
// copy local n to global arg, call subprogram factorial
arg = n;
factorial();
// copy local variable to arg, call putui
//arg = n;
putui();
// for convenience
putchar('\n');
}
Some suggestions for “how to approach”
Personally I would begin with an “empty” function factorial, i.e. an implementation that can be called but just returns:
1 2 | factorial:
jmp %RET, %0
|
Then I would complete the subprogram main, so that all this tedious calling of subprograms, passing and receiving arguments is done. All this stuff is just copy and paste from the example on the previous page. The desired result after that step would be a program that could be used on the command line as follows:
1 2 3 | theon$ ./factorial
n = 5
5! = 5
|
Having completed that would mean that I have a working framework. After checking in the debugger that everything works and observing how it works I would begin with the implementation of the function factorial. Now the trick is to figure out the right strategy for more sub-steps for doing that. Each sub-step should be going into the right direction, easy to accomplish and easy to validate. Easy to validate means, that you should have an idea how you can check if it is working without spending hours in the debugger. In my opinion, a good next step would be to implement this non-sense in assembly:
1 2 3 4 5 6 7 8 9 10 11 12 | void
factorial()
{
uint64_t n;
n = arg;
arg = arg - 1;
putui();
putchar('\n');
arg = n;
}
|
If you do it right then the program would do the following
1 2 3 4 | theon$ ./factorial
n = 5
5! = 4
5
|
This 4 would show up because my non-sense factorial prints the argument minus one. You still would see the last 5 in “5! = 5” because my non-sense factorial restored the argument with the value stored in the local variable. So it would be easy to check if my implementation can do the most relevant things: Store something in a local variable, call a function, fetch something from a local variable. Even if some of this is not working at first it would be easy to figure out the problem and fix it.
However, what strategy is most suitable for you depends on your experience and personal preferences.
Some variant that compiles with gcc and works
// just needed so you actually can compile this with gcc
typedef unsigned long uint64_t;
// for passing an argument and receiving a return value
uint64_t arg;
void
factorial()
{
uint64_t n;
n = arg;
arg = n-1;
if (arg == 0) {
arg = 1;
} else {
factorial();
arg = arg * n;
}
}
void
getui()
{
// implementation of subprogram getui
scanf("%lu", &arg);
}
void
puts()
{
// implementation of subprogram puts
printf("%s", arg);
}
void
putui()
{
// implementation of subprogram putui
printf("%lu", arg);
}
// some string literals
char msg0[] = "n = ";
char msg1[] = "! = ";
void
main()
{
// local variable
uint64_t n;
// copy pointer to string literal to arg, call puts
arg = msg0;
puts();
// call subprogram getui, copy return value to local variable
getui();
n = arg;
// copy local variable to arg, call putui
arg = n; // could be "optimized away"
putui();
// copy pointer to string literal to arg, call puts
arg = msg1;
puts();
// copy local n to global arg, call subprogram factorial
arg = n;
factorial();
// copy local variable to arg, call putui
//arg = n;
putui();
// for convenience
putchar('\n');
}
theon$ gcc -o factorial factorial_gcc.c factorial_gcc.c: In function 'getui': factorial_gcc.c:26:5: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration] scanf("%lu", &arg); ^~~~~ factorial_gcc.c:26:5: warning: incompatible implicit declaration of built-in function 'scanf' factorial_gcc.c:26:5: note: include '<stdio.h>' or provide a declaration of 'scanf' factorial_gcc.c: At top level: factorial_gcc.c:30:1: warning: conflicting types for built-in function 'puts' [-Wbuiltin-declaration-mismatch] puts() ^~~~ factorial_gcc.c: In function 'puts': factorial_gcc.c:33:5: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration] printf("%s", arg); ^~~~~~ factorial_gcc.c:33:5: warning: incompatible implicit declaration of built-in function 'printf' factorial_gcc.c:33:5: note: include '<stdio.h>' or provide a declaration of 'printf' factorial_gcc.c: In function 'putui': factorial_gcc.c:40:5: warning: incompatible implicit declaration of built-in function 'printf' printf("%lu", arg); ^~~~~~ factorial_gcc.c:40:5: note: include '<stdio.h>' or provide a declaration of 'printf' factorial_gcc.c: In function 'main': factorial_gcc.c:55:9: warning: assignment makes integer from pointer without a cast [-Wint-conversion] arg = msg0; ^ factorial_gcc.c:67:9: warning: assignment makes integer from pointer without a cast [-Wint-conversion] arg = msg1; ^ factorial_gcc.c:79:5: warning: implicit declaration of function 'putchar' [-Wimplicit-function-declaration] putchar('\n'); ^~~~~~~ theon$