Voir la source de 20170918:Practical:C:HomeWork

[[category:EPITA:TP:20172018]]

== Introduction ==

This homework serves as a quick introduction to C and Linux in our environment.
* S3: It is due on '''Monday, October 2, 2017''' at 2pm.
* S3#: It is due on '''Friday, February 9, 2018''' at 2pm. 

=== Code submission instructions ===

First, you must set-up your git repository for practical session by following instructions here [[Practical:GIT]] (''repositories for projects are not yet set-up, only practical session repositories are ready'').

You must add a directory called <tt>20170918_home_work</tt> to your repository with the content described in the next section (no extra files). You must have pushed the code before the due date, we'll clone your repository few minutes after the due date, thus only code available at that time will be evaluated.

For more information on GIT, you can check the command line help or official documentations[https://git-scm.com/documentation]. For a quick help, here the git command you need:

* <tt>add</tt>: add new files or register modified files
* <tt>commit</tt>: make a ''commit'' (a batch of modification since the last commit.)
* <tt>push</tt>: send commits from your local copy of the repository to the remote repository (used to ''submit'' your code).
* <tt>pull</tt>: apply commit from the remote repository
* <tt>status</tt>: see which files have been modified, which are new …

== Directory content ==

The submitted directory must contain the following files, no more, no less:

* <tt>20170918_home_work</tt>
** <tt>AUTHORS</tt>
** <tt>Makefile</tt> (provided file)
** <tt>main.c</tt> (provided file)
** <tt>math_func.h</tt> (provided file)
** <tt>math_func.c</tt> (your work)

The <tt>AUTHORS</tt> file will contains your login preceded by a star (<tt>*</tt>) like this:

<pre>
* login
</pre>

It's important that this file contains one single newline character, you can check it using the <tt>-e</tt> option of <tt>cat</tt>, this way:

<pre>
shell> cat AUTHORS 
* login
shell> cat -e AUTHORS
* login$
shell>
</pre>

If you want to be sure that you've submitted correctly all the needed files, you can clone your repository into another location and see the content of the file, you can also use the <tt>status</tt> command to see uncommitted changes.

Here is an example of checking submitted content, assuming you've clone your repository in the <tt>~/afs/login</tt>:

<pre>
shell> 
shell> cd /tmp
shell> git clone git clone git@git.cri.epita.net:p/2021-s3-tuto/login
shell> cd login/
shell> diff 20170918_home_work ~/afs/login/20170918_home_work
shell>
</pre>

== Provided Files ==

These files provide element for testing your code.

=== <tt>Makefile</tt> ===

<source lang="make">
# EPITA Practical Programming S3 - 2016/2017
# Makefile
# Marwan Burelle

# Compilers and options
CC=gcc
CPPFLAGS= -MMD
CFLAGS= -Wall -Wextra -std=c99 -pedantic -O2
LDFLAGS=
LDLIBS=

SRC = math_func.c main.c
OBJ = ${SRC:.c=.o}
DEP = ${SRC:.c=.d}

all: main

main: ${OBJ}

-include ${DEP}

clean:
	rm -f ${OBJ} ${DEP}
	rm -f main

# END
</source>

All files in this directory must have the proper encoding (ASCII for Unix with single newline character).

=== <tt>main.c</tt> ===

<source lang="C">
# include <err.h>
# include <stdlib.h>
# include <stdio.h>

# include "math_func.h"

typedef unsigned long (*functype)(unsigned long);

const functype ops[] = {
  fact,
  fibo,
  int_sqrt,
  digit_number,
  binary_digit_number,
  power_of_2,
  divisor_sum
};

const char *op_names[] = {
  "fact",
  "fibo",
  "int_sqrt",
  "digit_number",
  "binary_digit_number",
  "power_of_2",
  "divisor_sum"
};

const char usage[] =
  " <op> <min> <max>\n"
  "\tOperators:\n"
  "\t\t0: factorial\n"
  "\t\t1: fibonacci\n"
  "\t\t2: integer square root\n"
  "\t\t3: number of digits\n"
  "\t\t4: number of binary digits\n"
  "\t\t5: power of 2\n"
  "\t\t6: sum of divisors\n";

static
void test(size_t op, unsigned long minval, unsigned long maxval) {
  for (size_t i = minval; i <= maxval; ++i) {
    printf("%s(%lu) = %lu\n", op_names[op], i, ops[op](i));
  }
}

int main(int argc, char *argv[]) {
  if (argc < 4)
    errx(1, "%s", usage);
  unsigned long op, minval, maxval;
  op = strtoul(argv[1], NULL, 10);
  minval = strtoul(argv[2], NULL, 10);
  maxval = strtoul(argv[3], NULL, 10);
  test(op, minval, maxval);
  return 0;
}
</source>

=== <tt>math_func.h</tt> ===

<source lang="C">
/* math_func.c: some  maths fuctions */

# ifndef EPITA_IP_S3_20160926_HOMEWORK_MATH_FUNC_H_
# define EPITA_IP_S3_20160926_HOMEWORK_MATH_FUNC_H_

/* fact(n) computes factorial of n              */
unsigned long fact(unsigned long n);

/* fibo(n) computes fibonacci number of rank n  *
 * fibo(0) is defined as 0                      *
 * fibo(1) is defined as 1                      *
 * fibo(n) is defined as fibo(n-1) + fibo(n-2)  */
unsigned long fibo(unsigned long n);

/* int_sqrt(n) returns the integer part of the  *
 * square root of n using the heron method      */
unsigned long int_sqrt(unsigned long n);

/* digit_number(n) compute the number of digits *
 * of n in base-10                              */
unsigned long digit_number(unsigned long n);

/* binary_digit_number(n) compute the required  *
 * number of bits of n in base 2                */
unsigned long binary_digit_number(unsigned long n);

/* power_of_2(n) returns 2 to power the power n */
unsigned long power_of_2(unsigned long n);

/* divisor_sum(n) returns the sum of all the    *
 *  divisors of n including 1 but not n         */
unsigned long divisor_sum(unsigned long n);

# endif
</source>

== Task: <tt>math_func.c</tt> ==

Your job is to implement the function listed in <tt>math_func.h</tt>.

Here is a template for the file <tt>math_func.c</tt> (containing only functions' prototypes.)

<source lang="C">
/* Home Work */

# include <stdlib.h>

# include "math_func.h"

unsigned long fact(unsigned long n) {
  // FIX ME
}

unsigned long fibo(unsigned long n) {
  // FIX ME
}

unsigned long int_sqrt(unsigned long n) {
  // FIX ME
}

unsigned long digit_number(unsigned long n) {
  // FIX ME
}

unsigned long binary_digit_number(unsigned long n) {
  // FIX ME
}

unsigned long power_of_2(unsigned long n) {
  // FIX ME
}

unsigned long divisor_sum(unsigned long n) {
  // FIX ME
}
</source>

The header file <tt>math_func.h</tt> contains comments giving quick descriptions for each functions, more details follows.

=== <tt>fact(n)</tt> ===

The classical factorial function for unsigned long integers (64bits wide in our env).

Running using provided tests:

<pre>
shell> ./main 0 0 19
fact(0) = 1
fact(1) = 1
fact(2) = 2
fact(3) = 6
fact(4) = 24
fact(5) = 120
fact(6) = 720
fact(7) = 5040
fact(8) = 40320
fact(9) = 362880
fact(10) = 3628800
fact(11) = 39916800
fact(12) = 479001600
fact(13) = 6227020800
fact(14) = 87178291200
fact(15) = 1307674368000
fact(16) = 20922789888000
fact(17) = 355687428096000
fact(18) = 6402373705728000
fact(19) = 121645100408832000
</pre>

=== <tt>fibo(n)</tt> ===

The fibonacci sequence using unsigned long. Here is the recursive definition:

<pre>
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n - 1) + fibo(n - 2)
</pre>

'''Note:''' we're using unsigned long integer, thus we should be able to compute <tt>fibo(93)</tt> which is not possible using the naive recursive version.

Running using provided tests:

<pre>
shell> ./main 1 73 93
fibo(73) = 806515533049393
fibo(74) = 1304969544928657
fibo(75) = 2111485077978050
fibo(76) = 3416454622906707
fibo(77) = 5527939700884757
fibo(78) = 8944394323791464
fibo(79) = 14472334024676221
fibo(80) = 23416728348467685
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
fibo(91) = 4660046610375530309
fibo(92) = 7540113804746346429
fibo(93) = 12200160415121876738
</pre>

=== <tt>int_sqrt(n)</tt> ===

Integer part of the square root of <tt>n</tt>.

The integer square root verifies the following equations:

<pre>
r = int_sqrt(n)
r * r <= n && n < (r + 1) * (r + 1)
</pre>

The best algorithm for that is Heron's method (a variant of Newton's method):

<pre>
let x be a first approximation of the square root such that r <= x <= n (where r is the root)
(n is a good starting value)
While x is greater than the root, replace x with the average of x and n/x:
    x = (x + n/x) / 2
</pre>

Note that the root is located between <tt>x</tt> and <tt>x/n</tt>, thus we found the root when <tt>x <= n/x</tt> for the first time.

Don't forget to handle the special case for <tt>n = 0</tt>.

Running using provided tests:

<pre>
shell> ./main 2 40 60
int_sqrt(40) = 6
int_sqrt(41) = 6
int_sqrt(42) = 6
int_sqrt(43) = 6
int_sqrt(44) = 6
int_sqrt(45) = 6
int_sqrt(46) = 6
int_sqrt(47) = 6
int_sqrt(48) = 6
int_sqrt(49) = 7
int_sqrt(50) = 7
int_sqrt(51) = 7
int_sqrt(52) = 7
int_sqrt(53) = 7
int_sqrt(54) = 7
int_sqrt(55) = 7
int_sqrt(56) = 7
int_sqrt(57) = 7
int_sqrt(58) = 7
int_sqrt(59) = 7
int_sqrt(60) = 7
</pre>

=== <tt>digit_number(n)</tt> ===

The number decimal (base 10) digits in <tt>n</tt>.

Running using provided tests:

<pre>
shell> ./main 3 90 110
digit_number(90) = 2
digit_number(91) = 2
digit_number(92) = 2
digit_number(93) = 2
digit_number(94) = 2
digit_number(95) = 2
digit_number(96) = 2
digit_number(97) = 2
digit_number(98) = 2
digit_number(99) = 2
digit_number(100) = 3
digit_number(101) = 3
digit_number(102) = 3
digit_number(103) = 3
digit_number(104) = 3
digit_number(105) = 3
digit_number(106) = 3
digit_number(107) = 3
digit_number(108) = 3
digit_number(109) = 3
digit_number(110) = 3
</pre>

=== <tt>binary_digit_number(n)</tt> ===

Computes the number of binary digit (base 2) of <tt>n</tt>.

Running using provided tests:

<pre>
shell> ./main 4 7 33
binary_digit_number(7) = 3
binary_digit_number(8) = 4
binary_digit_number(9) = 4
binary_digit_number(10) = 4
binary_digit_number(11) = 4
binary_digit_number(12) = 4
binary_digit_number(13) = 4
binary_digit_number(14) = 4
binary_digit_number(15) = 4
binary_digit_number(16) = 5
binary_digit_number(17) = 5
binary_digit_number(18) = 5
binary_digit_number(19) = 5
binary_digit_number(20) = 5
binary_digit_number(21) = 5
binary_digit_number(22) = 5
binary_digit_number(23) = 5
binary_digit_number(24) = 5
binary_digit_number(25) = 5
binary_digit_number(26) = 5
binary_digit_number(27) = 5
binary_digit_number(28) = 5
binary_digit_number(29) = 5
binary_digit_number(30) = 5
binary_digit_number(31) = 5
binary_digit_number(32) = 6
binary_digit_number(33) = 6
</pre>

=== <tt>power_of_2(n)</tt> ===

Computes <math>2^n</math> as fast as you can (don't need to be iterative or recursive … )

Running using provided tests:

<pre>
shell> ./main 5 0 32
power_of_2(0) = 1
power_of_2(1) = 2
power_of_2(2) = 4
power_of_2(3) = 8
power_of_2(4) = 16
power_of_2(5) = 32
power_of_2(6) = 64
power_of_2(7) = 128
power_of_2(8) = 256
power_of_2(9) = 512
power_of_2(10) = 1024
power_of_2(11) = 2048
power_of_2(12) = 4096
power_of_2(13) = 8192
power_of_2(14) = 16384
power_of_2(15) = 32768
power_of_2(16) = 65536
power_of_2(17) = 131072
power_of_2(18) = 262144
power_of_2(19) = 524288
power_of_2(20) = 1048576
power_of_2(21) = 2097152
power_of_2(22) = 4194304
power_of_2(23) = 8388608
power_of_2(24) = 16777216
power_of_2(25) = 33554432
power_of_2(26) = 67108864
power_of_2(27) = 134217728
power_of_2(28) = 268435456
power_of_2(29) = 536870912
power_of_2(30) = 1073741824
power_of_2(31) = 2147483648
power_of_2(32) = 4294967296
</pre>

=== <tt>divisor_sum(n)</tt> ===

Computes the sum of the divisors of <tt>n</tt> including <tt>1</tt> but not <tt>n</tt> itself.

Special cases for <tt>0</tt> and <tt>1</tt> should return <tt>1</tt>.

You can check your results with some hints: prime numbers will have a sum of <tt>1</tt>, perfect numbers (6, 28, 496, 8128 … ) will have a sum equals to themselves.

Running using provided tests:

<pre>
shell> ./main 6 0 30
divisor_sum(0) = 1
divisor_sum(1) = 1
divisor_sum(2) = 1
divisor_sum(3) = 1
divisor_sum(4) = 3
divisor_sum(5) = 1
divisor_sum(6) = 6
divisor_sum(7) = 1
divisor_sum(8) = 7
divisor_sum(9) = 4
divisor_sum(10) = 8
divisor_sum(11) = 1
divisor_sum(12) = 16
divisor_sum(13) = 1
divisor_sum(14) = 10
divisor_sum(15) = 9
divisor_sum(16) = 15
divisor_sum(17) = 1
divisor_sum(18) = 21
divisor_sum(19) = 1
divisor_sum(20) = 22
divisor_sum(21) = 11
divisor_sum(22) = 14
divisor_sum(23) = 1
divisor_sum(24) = 36
divisor_sum(25) = 6
divisor_sum(26) = 16
divisor_sum(27) = 13
divisor_sum(28) = 28
divisor_sum(29) = 1
divisor_sum(30) = 42
</pre>

== Testing with provided code ==

The provided files will help you testing your code.

The first step is to be sure (at least) that the file <tt>math_func.c</tt> compiles (you can just add a default return statement or something similar).

The files <tt>main.c</tt> describes a small program for testing your functions with some basic parameters: the function index (from 0 to 6) a min and a max value. The program will run your function with all integers from the min to the max value (included).

Here is a tiny test session (with a complete working <tt>math_func.c</tt> file):

<pre>
shell> ls
AUTHORS  Makefile  main.c  math_func.c  math_func.h
shell> make
gcc -Wall -Wextra -std=c99 -pedantic -O2 -MMD  -c -o main.o main.c
gcc -Wall -Wextra -std=c99 -pedantic -O2 -MMD  -c -o math_func.o math_func.c
gcc   main.o math_func.o   -o main
shell> ./main 
main:  <op> <min> <max>
	Operators:
		0: factorial
		1: fibonacci
		2: integer square root
		3: number of digits
		4: number of binary digits
		5: power of 2
		6: sum of divisors

shell> ./main 0 0 5
fact(0) = 1
fact(1) = 1
fact(2) = 2
fact(3) = 6
fact(4) = 24
fact(5) = 120
shell> ./main 6 495 497
divisor_sum(495) = 441
divisor_sum(496) = 496
divisor_sum(497) = 79
shell> make clean
rm -f math_func.o main.o math_func.d main.d
rm -f main
shell>
</pre>