Submission
Due Date
By Friday 19 October 2018 23:42
Directory Hierarchy
Create your git repository (replace john.smith by your own login).
$ git clone git@git.cri.epita.net:p/2022-spe-tp/tp02-john.smith
It must contain the following files and directories:
-
pw_02_basics/- AUTHORS
facto/fibo/isqrt/power_of_two/digit_count/divisor_sum/perfect_numbers/
Use only one directory per exercise and write all the files of an
exercise in its associated directory.
For instance, write all the files of the factorial exercise in the
facto directory.
Also, create an AUTHORS
file that contains the following information.
First Name
Family Name
Login
Email Address
For instance:
John
Smith
john.smith
john.smith@epita.fr
Be careful, if you do not follow all the given instructions, no point will be given to your answers.
Exercises
Unless otherwise stipulated, you will use the gcc compiler
with the following options and parameters for all the exercises:
$ gcc -Wall -Wextra -Werror -std=c99 -O1 -o main *.c
Check the documentation of gcc for more details.
Unless otherwise stipulated, the prototype of the main()
function will be:
int main();
The main() function will return zero if no error occurs.
Otherwise, it will return one.
You have to bear in mind that header files
have to be included only once even
if several #include
are encountered for the same header file.
So never forget to start header files with
the #ifndef
and #define pair of pseudo-instructions
and to end it with the #endif pseudo-instruction.
All header files should look like the following template:
#ifndef NAME_OF_THE_HEADER_FILE
#define NAME_OF_THE_HEADER_FILE
// FUNCTION PROTOTYPES
#endif
Factorial
You are going to write a program that works out the factorial of a number.
Your program will be made up of three files:
-
main.cthat contains themain()function. -
facto.cthat contains thefacto()function. -
facto.hthat is the header of thefacto.cfile.
Prototype of the facto() function:
unsigned long facto(unsigned long n);
-
Arguments:
- n: 64-bit unsigned integer.
- Return Value: the factorial of n.
- Note: this function should not print anything on the terminal.
For this first exercise, the facto.h file is given:
#ifndef FACTO_H
#define FACTO_H
unsigned long facto(unsigned long n);
#endif
Write the facto.c file.
Finally, write the main.c file.
Your main() function should invoke
your facto() function
and should print exactly the following output on the terminal:
$ ./main
facto(0) = 1
facto(1) = 1
facto(2) = 2
facto(3) = 6
facto(4) = 24
facto(5) = 120
facto(6) = 720
facto(7) = 5040
facto(8) = 40320
facto(9) = 362880
facto(10) = 3628800
facto(11) = 39916800
facto(12) = 479001600
facto(13) = 6227020800
facto(14) = 87178291200
facto(15) = 1307674368000
facto(16) = 20922789888000
facto(17) = 355687428096000
facto(18) = 6402373705728000
facto(19) = 121645100408832000
facto(20) = 2432902008176640000
Fibonacci Sequence
The Fn Fibonacci sequence is defined by the following recurrence relation:
- F0 = 0
- F1 = 1
- Fn = Fn-1 + Fn-2
You are going to write a program that works out the Fibonacci numbers.
Your program will be made up of three files:
-
main.cthat contains themain()function. -
fibo.cthat contains thefibo()function. -
fibo.hthat is the header of thefibo.cfile.
Prototype of the fibo() function:
unsigned long fibo(unsigned long n);
-
Arguments:
- n: 64-bit unsigned integer.
- Return Value: the nth number of the Fibonacci sequence.
- Note: this function should not print anything on the terminal.
Write the fibo.h and fibo.c files.
Finally, write the main.c file.
Your main() function should print exactly
the following output on the terminal (the three dots included):
$ ./main
fibo(0) = 0
fibo(1) = 1
fibo(2) = 1
fibo(3) = 2
fibo(4) = 3
fibo(5) = 5
fibo(6) = 8
fibo(7) = 13
fibo(8) = 21
fibo(9) = 34
fibo(10) = 55
...
fibo(81) = 37889062373143906
fibo(82) = 61305790721611591
fibo(83) = 99194853094755497
fibo(84) = 160500643816367088
fibo(85) = 259695496911122585
fibo(86) = 420196140727489673
fibo(87) = 679891637638612258
fibo(88) = 1100087778366101931
fibo(89) = 1779979416004714189
fibo(90) = 2880067194370816120
Integer Square Root
The integer square root of a non-negative integer n is the largest integer that is smaller than or equal to the square root of n.
To determine the integer square root (r) of a non-negative integer (n) you can use the Babylonian method:
- r = n
-
While r2 > n:
- r = r + n/r
- r = r / 2
You are going to write a program that works out the integer square root of a non-negative integer.
Your program will be made up of three files:
-
main.cthat contains themain()function. -
isqrt.cthat contains theisqrt()function. -
isqrt.hthat is the header of theisqrt.cfile.
Prototype of the isqrt() function:
unsigned long isqrt(unsigned long n);
-
Arguments:
- n: 64-bit unsigned integer.
- Return Value: the integer square root of n.
- Note: this function should not print anything on the terminal.
Write the isqrt.h
and isqrt.c files.
Finally, write the main.c file.
Your main() function should print exactly
the following output on the terminal:
$ ./main
isqrt(0) = 0
isqrt(8) = 2
isqrt(16) = 4
isqrt(24) = 4
isqrt(32) = 5
isqrt(40) = 6
isqrt(48) = 6
isqrt(56) = 7
isqrt(64) = 8
isqrt(72) = 8
isqrt(80) = 8
isqrt(88) = 9
isqrt(96) = 9
isqrt(104) = 10
isqrt(112) = 10
isqrt(120) = 10
isqrt(128) = 11
isqrt(136) = 11
isqrt(144) = 12
isqrt(152) = 12
isqrt(160) = 12
isqrt(168) = 12
isqrt(176) = 13
isqrt(184) = 13
isqrt(192) = 13
isqrt(200) = 14
Powers of Two
You are going to write a program that works out a power of two as fast as possible (no iteration, no recursion).
Your program will be made up of three files:
-
main.cthat contains themain()function. -
power_of_two.cthat contains thepower_of_two()function. -
power_of_two.hthat is the header of thepower_of_two.cfile.
Prototype of the power_of_two() function:
unsigned long power_of_two(unsigned char n);
-
Arguments:
- n: 8-bit unsigned integer.
- Return Value: two to the power of n.
- Note: this function should not print anything on the terminal.
Write the power_of_two.h
and power_of_two.c files.
Finally, write the main.c file.
Your main() function should print exactly
the following output on the terminal:
$ ./main
power_of_two(0) = 1
power_of_two(1) = 2
power_of_two(2) = 4
power_of_two(3) = 8
power_of_two(4) = 16
power_of_two(5) = 32
power_of_two(6) = 64
power_of_two(7) = 128
power_of_two(8) = 256
power_of_two(9) = 512
power_of_two(10) = 1024
power_of_two(11) = 2048
power_of_two(12) = 4096
power_of_two(13) = 8192
power_of_two(14) = 16384
power_of_two(15) = 32768
power_of_two(16) = 65536
power_of_two(17) = 131072
power_of_two(18) = 262144
power_of_two(19) = 524288
power_of_two(20) = 1048576
power_of_two(21) = 2097152
power_of_two(22) = 4194304
power_of_two(23) = 8388608
power_of_two(24) = 16777216
power_of_two(25) = 33554432
power_of_two(26) = 67108864
power_of_two(27) = 134217728
power_of_two(28) = 268435456
power_of_two(29) = 536870912
power_of_two(30) = 1073741824
power_of_two(31) = 2147483648
power_of_two(32) = 4294967296
power_of_two(33) = 8589934592
power_of_two(34) = 17179869184
power_of_two(35) = 34359738368
power_of_two(36) = 68719476736
power_of_two(37) = 137438953472
power_of_two(38) = 274877906944
power_of_two(39) = 549755813888
power_of_two(40) = 1099511627776
power_of_two(41) = 2199023255552
power_of_two(42) = 4398046511104
power_of_two(43) = 8796093022208
power_of_two(44) = 17592186044416
power_of_two(45) = 35184372088832
power_of_two(46) = 70368744177664
power_of_two(47) = 140737488355328
power_of_two(48) = 281474976710656
power_of_two(49) = 562949953421312
power_of_two(50) = 1125899906842624
power_of_two(51) = 2251799813685248
power_of_two(52) = 4503599627370496
power_of_two(53) = 9007199254740992
power_of_two(54) = 18014398509481984
power_of_two(55) = 36028797018963968
power_of_two(56) = 72057594037927936
power_of_two(57) = 144115188075855872
power_of_two(58) = 288230376151711744
power_of_two(59) = 576460752303423488
power_of_two(60) = 1152921504606846976
power_of_two(61) = 2305843009213693952
power_of_two(62) = 4611686018427387904
power_of_two(63) = 9223372036854775808
Digit Count
You are going to write a program that counts the number of digits in a base-10 non-negative integer.
Your program will be made up of three files:
-
main.cthat contains themain()function. -
digit_count.cthat contains thedigit_count()function. -
digit_count.hthat is the header of thedigit_count.cfile.
Prototype of the digit_count() function:
unsigned char digit_count(unsigned long n);
-
Arguments:
- n: 64-bit unsigned integer.
- Return Value: the number of digits of n in base 10.
- Note: this function should not print anything on the terminal.
Write the digit_count.h
and digit_count.c files.
Finally, write the main.c file.
Your main() function should print exactly
the following output on the terminal, that is,
the number of digits for 0 and for all the powers of two
from 20 to 263:
$ ./main
digit_count(0) = 1
digit_count(1) = 1
digit_count(2) = 1
digit_count(4) = 1
digit_count(8) = 1
digit_count(16) = 2
digit_count(32) = 2
digit_count(64) = 2
digit_count(128) = 3
digit_count(256) = 3
digit_count(512) = 3
digit_count(1024) = 4
digit_count(2048) = 4
digit_count(4096) = 4
digit_count(8192) = 4
digit_count(16384) = 5
digit_count(32768) = 5
digit_count(65536) = 5
digit_count(131072) = 6
digit_count(262144) = 6
digit_count(524288) = 6
digit_count(1048576) = 7
digit_count(2097152) = 7
digit_count(4194304) = 7
digit_count(8388608) = 7
digit_count(16777216) = 8
digit_count(33554432) = 8
digit_count(67108864) = 8
digit_count(134217728) = 9
digit_count(268435456) = 9
digit_count(536870912) = 9
digit_count(1073741824) = 10
digit_count(2147483648) = 10
digit_count(4294967296) = 10
digit_count(8589934592) = 10
digit_count(17179869184) = 11
digit_count(34359738368) = 11
digit_count(68719476736) = 11
digit_count(137438953472) = 12
digit_count(274877906944) = 12
digit_count(549755813888) = 12
digit_count(1099511627776) = 13
digit_count(2199023255552) = 13
digit_count(4398046511104) = 13
digit_count(8796093022208) = 13
digit_count(17592186044416) = 14
digit_count(35184372088832) = 14
digit_count(70368744177664) = 14
digit_count(140737488355328) = 15
digit_count(281474976710656) = 15
digit_count(562949953421312) = 15
digit_count(1125899906842624) = 16
digit_count(2251799813685248) = 16
digit_count(4503599627370496) = 16
digit_count(9007199254740992) = 16
digit_count(18014398509481984) = 17
digit_count(36028797018963968) = 17
digit_count(72057594037927936) = 17
digit_count(144115188075855872) = 18
digit_count(288230376151711744) = 18
digit_count(576460752303423488) = 18
digit_count(1152921504606846976) = 19
digit_count(2305843009213693952) = 19
digit_count(4611686018427387904) = 19
digit_count(9223372036854775808) = 19
Sum of Divisors
You are going to write a program that adds up all the divisors of a positive integer (excluding the integer itself).
Your program will be made up of three files:
-
main.cthat contains themain()function. -
divisor_sum.cthat contains thedivisor_sum()function. -
divisor_sum.hthat is the header of thedivisor_sum.cfile.
Prototype of the divisor_sum() function:
unsigned long divisor_sum(unsigned long n);
-
Arguments:
- n: 64-bit unsigned integer (0 excluded).
- Return Value: the sum of the divisors of n (excluding n).
- Note: this function should not print anything on the terminal.
Write the divisor_sum.h and
divisor_sum.c files.
For this program, you are going to pass the positive integer to your program by using the command-line arguments.
First, the prototype of your main() function becomes:
int main(int argc, char** argv);
-
Arguments:
- argc: number of the command-line arguments (program name included).
- argv: pointer to an array of strings that contains the command-line arguments.
- Return Value: Status code: 0 if no error occurs, otherwise 1.
Then, to get the first parameter that was passed to your program
in a param variable,
you can use this instruction.
unsigned long param = strtoul(argv[1], NULL, 10);
Do not worry if you do not know what a pointer is and if you do not understand the above instruction. We will see the pointers and the command-line arguments in more detail later on. For the time being, just use this instruction to get the first parameter as an unsigned long variable.
Now that we use a user input (i.e. the argument passed to the program by a user), we have to handle any potential errors. As it is your first time, let us do this in a simple way.
You will have to exit the program:
-
If
argcis different from two (the number of arguments is not valid). -
If
paramis equal to zero (the parameter is not valid).
In these two cases, you should exit the program
with the status code 1 and print an error message.
To do so, you can use the errx() function.
For instance:
errx(1, "Error");
The above instruction exits your program with the status code 1
and sends the "Error" message to the standard error.
To sum up:
- You have to use a new prototype for the main function.
-
You have to use two new functions of the standard library:
- The
strtoul()function. - The
errx()function.
- The
To use these two new functions, you have to include the right headers
at the beginning of your main.c file.
So, have a look at the man pages of the strtoul()
and errx() functions in order to
figure out which headers you need.
Finally, write the main() function so that it prints
the sum of the divisors for the number you pass as parameter.
Test it with different values.
Here are some examples.
$ ./main 0
main: Error
$ ./main abcd
main: Error
$ ./main 1 2
main: Error
$ ./main 1
divisor_sum(1) = 0
$ ./main 3
divisor_sum(3) = 1
$ ./main 6
divisor_sum(6) = 6
$ ./main 9
divisor_sum(9) = 4
$ ./main 11
divisor_sum(11) = 1
$ ./main 28
divisor_sum(28) = 28
$ ./main 30
divisor_sum(30) = 42
$ ./main 496
divisor_sum(496) = 496
$ ./main 8589869056
divisor_sum(8589869056) = 8589869056
$ ./main 137438691328
divisor_sum(137438691328) = 137438691328
Obviously, the result for a prime number is always one. We can also notice that for some numbers their sums are equal to themselves. Such numbers are called perfect numbers.
If your algorithm is not efficient, the computation for the last two numbers can take a lot of time (from one to twenty minutes).
Otherwise, if your algorithm is efficient, the computation can take only a few milliseconds; even for the last number (i.e. 137,438,691,328).
You can use the time command to obtain an approximation
of the elapsed time between invocation and termination of your program
(the real time).
$ time ./main 8589869056
divisor_sum(8589869056) = 8589869056
real 0m0.001s
user 0m0.000s
sys 0m0.000s
$ time ./main 137438691328
divisor_sum(137438691328) = 137438691328
real 0m0.005s
user 0m0.004s
sys 0m0.000s
You are not required to write the fastest algorithm, but at least, try to make it in under five seconds for the last number.
Perfect Numbers
For this last exercise, you are going to write a program that lists all the perfect numbers from 1 to 100,000.
To do so, you need to use the divisor_sum()
function you wrote in the previous exercise.
Several methods are possible.
For this exercise, you will use this function
as if you were using a library without any source files.
So, let us assume that the developer and the user of the library are different people. The developer wants to deploy his or her library without its source code. The user wants to use the library but is not allowed to access the source code. How is that possible? Presumably, you are only one person sitting in front of this computer, so you are going to play the two parts:
- First, the developer.
- Then, the user.
First let us assume that you are the developer of the library.
Go back to the directory of the previous exercise
(i.e. divisor_sum).
You want to deploy the divisor_sum() function
defined in the divisor_sum.c file.
You will not be able to generate an executable file
by compiling this source file,
because the main() function is missing.
For example:
$ gcc divisor_sum.c /usr/lib/gcc/x86_64-linux-gnu/5/../../../x86_64-linux-gnu/crt1.o: In function `_start': (.text+0x20): undefined reference to `main' collect2: error: ld returned 1 exit status
Actually, you can compile this code,
but you have to generate an object file and not an executable file.
To do so, you can use the -c option of the compiler.
$ ls
divisor_sum.c divisor_sum.h main main.c
$ gcc -c divisor_sum.c
$ ls
divisor_sum.c divisor_sum.h divisor_sum.o main main.c
As you see, a new file has been created: divisor_sum.o.
It is an object file and contains the machine code of the
divisor_sum() function.
You could stop here, but as you are concerned about doing things well, you should recompile this file by using the options you are supposed to use.
gcc -Wall -Wextra -Werror -std=c99 -O1 -c divisor_sum.c
Ok, now you are done. To deploy the library, you can provide the two following files only:
-
divisor_sum.h: the header file of your library (the function prototype). -
divisor_sum.o: the object file of your library (the machine code).
You are not required to provide the definition of the function,
that is, the divisor_sum.c file.
Now, let us assume that you are the user of the library.
Exit the directory of the previous exercise,
create the perfect_numbers directory
and set it as the current directory.
$ cd ..
$ mkdir perfect_numbers
$ cd perfect_numbers
As a user of the library, you have to get the files provided by the developer. You can simulate that by copying the files from the previous exercise into the current directory.
$ cp ../divisor_sum/divisor_sum.[ho] .
$ ls
divisor_sum.h divisor_sum.o
Now you are able to write the program that lists all the perfect numbers from 1 to 100,000.
Your program will be made up of five files:
-
main.cthat contains themain()function. -
is_perfect_number.cthat contains theis_perfect_number()function. -
is_perfect_number.hthat is the header of theis_perfect_number.cfile. -
divisor_sum.hfrom the previous exercise. -
divisor_sum.ofrom the previous exercise.
You are supposed to invoke the divisor_sum() function
in your is_perfect_number() function.
So the is_perfect_number.c
file should include the header of the library.
Actually, it should look like this:
#include "is_perfect_number.h"
#include "divisor_sum.h"
int is_perfect_number(unsigned long n)
{
// TODO
}
You will replace the TODO comment by your own code.
As you can see, the prototype of the
is_perfect_number() function is as follows:
int is_perfect_number(unsigned long n);
-
Arguments:
- n: 64-bit unsigned integer (0 excluded).
-
Return Value:
- If n is not a perfect number, return 0.
- If n is a perfect number, return an integer different from 0.
- Note: this function should not print anything on the terminal.
Write the is_perfect_number.h
and is_perfect_number.c files.
Finally, write the main.c file.
To compile your program,
you have to specify the object file to the linker
(through the compiler command).
gcc -Wall -Wextra -Werror -std=c99 -O1 -o main *.c *.o
The expected result is as follows:
$ ./main
6
28
496
8128
About performance:
$ time ./main
6
28
496
8128
real 0m0.152s
user 0m0.152s
sys 0m0.000s