Reprise du message précédent :
Tout cela m'a l'air bien confus...
Je n'ai jamais dit (en tout cas il ne me semble pas) qu'il fallait, ni même qu'on pouvait, stocker des chaines de caractères dans des entiers.
Simplement, pour représenter de façon exacte un entier de 120 chiffres décimaux, un entier 32 bits ne suffit pas, car il faut 400 bits. Eh bien OK, dans un tableau de 13 entiers 32 bits, tu les as, tes 400 bits. Bien sûr, après, pour faire une addition entre 2 tableaux, c'est pas aussi simple que "a + b", mais c'est le but du jeu...
 
Mais quel rapport avec les chars ? Ou "la methode de 8bits de char dans 32 bits de int... en les decalants " ?

>theodamien
tu recois a l origine une chaine de caractere (expr)
tu balades des pointeurs dessus ...
et tu en resort 2 chaines de caracteres (les deux operandes)
ensuite il effectuer les operations sur ces deux chars
( tu calcules digit par digit avec des systemes de retenues,etc)
donc a la sortie si tu t es bien debrouye, tu obtiens un  ... char !!!
donc tu ne passe pas par les entiers (ormis les digits)

Bemixam parlait tout à l'heure de piles et d'arbres
 
piles ==> ok je sais ce que c
arbres ==> ???
 
si qq'un peut expliquer...

Si on considère simplement des opérations binaires (+,-,*,/) par exemple, l'arbre d'une expression peut ressembler à ça:
a (7+8)*(3+6)-6 correspond l'arbre:
        -
       /  
      *   6
    /  
   +    +
  /    /
 7   8 3  6
 
Chaque noeud est une opération et chaque feuille un nombre.
L'évaluation a lieu récursivement: la valeur d'un noeud est la valeur de l'opération appliqué aux valeurs des fils.
La valeur d'une feuille est le nombre.
 
Donc en gros il y a 2 étapes pour évaluer une expression:
- construire l'arbre à partir de l'expression
- évaluer la racine de l'arbre (et donc l'arbre par récursiivité)
 
 
 

--Message édité par Verdoux--

Très bonne explication par l'exemple, Verdoux.

Si tu veux faire une bistro qui marche bien, il faut obligatoirement faire un arbre qui te permettra de réduire ton nombre de calculs (si tu as 42*0 à un endroit, tu peux virer toute une partie de l'arbre). C'est la partie la plus dure.
Il te restera ensuite à faire tes algos pour les opérations, les plus optimisés possible.
Par exemple, pour la multiplication, il y a une méthode qui te permet de réaliser l'opération d'une seule traite en faisant des multiplications croisés en fonction des indices des chiffres des nombre à multiplier.
Je pense cependant que ta meilleur source de renseignements reste les ACUs. Ils sont là pour t'aider. C'est grace à eux que j'ai tant appris en Tech1.

titoine> Mouais... Les simplifications d'expressions, c'est pour la fin, et c'est loin d'être obligatoire. L'important, c'est d'abord d'avoir un truc qui marche, et sans simplification, ça marche très bien. On fait plus de calculs, c'es tout.
 
Et puis pour les algos, je les ai déjà donnés. Je ne connais pas beaucoup plus optimisé que ceux-là. Et si je peux me permettre, (en particulier pour la division) les algos n'ont pas grand chose avec ceux qu'on trouve dans une ACU. Voir le post en question.

Hey Bemixan !!
tu savais que ca doit tourner sur Mips & Alpha aussi ?
alors ta interer a optimiser !

Les alphas c'est pas un problème car elles sont très rapides (genre solaria) et les librairies diffèrent peu de celles des pc.
Par contre, pour les mips, c'est la misère car c'est très lent et les librairies et includes sont très différents.
Pour te faire une idée, voilà le .h de mon shell qui fonctionne sur les trois archis :
/*
** shell.h for  in  
**  
** Made by antoine laurent
** Login   <antoine laurent@epita.fr>
**  
** Started on  Thu Jun  1 12:38:41 2000 antoine laurent
** Last update Wed Jun 28 18:43:10 2000 Udilow
*/
 
# ifndef __SHELL__
# define __SHELL__
 
# ifdef __alpha
# include <dirent.h>
# endif
 
# ifdef mips
char  *getenv(char *name);
void  *getwd(void *path);
# include </bsd43/usr/include/sys/types.h>
# include <sys/dir.h>
# ifndef _SYS_STAT_
# include </bsd43/usr/include/sys/stat.h>
# endif /* _SYS_STAT_ */
# include </usr/include/sys/wait.h>
# include </usr/include/sys/signal.h>
# include </usr/include/stdio.h>
# include </usr/include/time.h>
# include </usr/include/sysv/pwd.h>
# include </usr/include/sysv/grp.h>
# include </bsd43/usr/include/sys/file.h>
# include </usr/include/sys/termio.h>
# include </usr/include/sys/stropts.h>
# define dirent  direct
# define remove  unlink
# define WEXITSTATUS(x)  ((int)(((unsigned int)_W_INT(x)) >> 8) & 0xff)
# define _W_INT(w)       (*(int *)(void *)&(w))
# else
# include <sys/types.h>
# include <sys/stat.h>
# include <sys/dir.h>
# include <sys/ioctl.h>
# include <fcntl.h>
# include <pwd.h>
# include <stdio.h>
# include <time.h>
# include <signal.h>
# include <grp.h>
# include <setjmp.h>
# include <errno.h>
# include <sys/wait.h>
# include <unistd.h>
# include <stdlib.h>
# include <sys/uio.h>
# include <sys/termios.h>
#endif /* mips */
 
# include "my/my.h"
# include "list/list.h"
 
typedef struct s_get_prog_result
{
  struct s_list *prog;
  struct s_list *next;
}  t_get_prog_result;
 
typedef struct s_static
{
  char  *hostname;
  char  *username;
  int  init_flag;
}  t_static;
 
typedef struct  s_flag
{
  int  sup;
  int  supsup;
  int  inf;
  int  infinf;
  int  point_virgule;
  int  et;
  int  ou;
  int  pipe1_in;
  int  pipe1_out;
  int  pipe2_in;
  int  pipe2_out;
  int  bg;
  int  status;
}  t_flag;
 
typedef struct s_redirect
{
  char  *source;
  char  *target;
  int  tube1[2];
  int  tube2[2];
}  t_redirect;
 
 
#ifndef mips
typedef struct  s_builtin
{
  char          *builtin;
  int           (*f)(char **args);
}               t_builtin;
#else
typedef struct  s_builtin
{
  char          *builtin;
  int           (*f)();
}               t_builtin;
#endif
 
int   main(int argc, char **argv);
int   shell_core();
int   aff_prompt();
t_list   *scan_cmd(char *cmd);
t_list   *parse_point_virgule(char *cmd);
t_list   *parse_et_logique(t_list *liste);
t_list   *parse_ou_logique(t_list *liste);
t_list   *parse_et(t_list *liste);
t_list   *parse_pipe(t_list *liste);
t_list   *parse_sup(t_list *liste);
t_list   *parse_sup_sup(t_list *liste);
t_list   *parse_inf(t_list *liste);
t_list   *parse_inf_inf(t_list *liste);
t_list   *parse_espaces(t_list *liste);
int   kill_spaces_in_list(t_list *liste);
t_list   *meta(t_list *liste);
int   check_meta(char *elem);
char   **replace_meta(char *elem);
int   my_match(char *crit, char *word);
int   exec_list(t_list *liste);
int   signaux();
void   segfault();
t_get_prog_result *get_prog(t_list *liste);
int   check_end_prog(char *elem);
int   init_env();
int   scan_prog(t_list *liste);
int   scan_elem(t_list *liste);
int   check_sup(t_list *liste);
int   check_supsup(t_list *liste);
int   check_inf(t_list *liste);
int   check_infinf(t_list *liste);
void   init_flags();
void   set_redirect();
char   **get_bin(t_list *liste);
int   final_exec();
void   redirect_fct();
void   aff_flags();
void   infinf();
void   init_redirect();
int   check_if_builtin(char **cmd);
int   b_exit(char **args);
int   b_cd(char **args);
int   b_echo(char **args);
int   b_history(char **args);
int   b_builtins(char **args);
void   pipe_fct();
void   pipe2_fct();
void   remove_pipe();
 
int   crochets(char *normal, char *complique);
int   crochets_oui(char *normal, char *complique);
int   crochets_non(char *normal, char *complique);
char   *get_next_occurence_of(char *normal, char *complique);
char   *got_to_the_end_of_accolade(char *str);
char   *go_to_the_end_of_crochets(char *complique);
char   *go_to_the_end_of_stars(char *str);
char   *get_end_of_stars(char *);
int   are_they_matching(char *normal, char *complique);
int   matching_chars(char *normal, char *complique);
int   cd_olive(char *args);
 
# ifdef __STATIC__
char   meta_tab[] =
{
  '*',
  '?',
  '[',
  ']',
  '{',
  '}',
  0
};
t_builtin       tab_builtin[]=
{
  {"cd", b_cd},
  {"echo", b_echo},
  {"exit", b_exit},
  {"builtins", b_builtins},
  {0, 0}
};
t_static  *statics;
t_flag   *flags;
t_redirect  *redirect;
t_list   *cmd_history_list;
# else
extern char  meta_tab[];
extern t_builtin tab_builtin[];
extern t_static  *statics;
extern t_flag  *flags;
extern t_redirect *redirect;
extern t_list  *cmd_history_list;
# endif
# endif
 
Aller bon courage, ce n'est que le début.
Tu verras, à la fin de l'année tu penseras que la bistro c'était de la rigolade.

 
Merci verdoux pour l'explication de l'arbre mais j'ai encore une petite question, c'est quoi des multiplication croisées (j'ai pas compris le poste de titoine42

Son truc à propos des multiplications croisées n'a rien à voir avec l'arbre en lui-même mais avec la manière dont tu vas calculer le produit de 2 grands nombres.
Ca dépend évidemment de la manière que tu as choisie pour représenter les grands nombres.
Dans un premier temps, pour les opérations arithmétiques, tu peux ne mettre que des algos simples, et ne les optimiser que dans un deuxième temps.

et ta eu combien au shell TItoine42 ?

 
Ce que je veux savoir, c'est comment ça marche une multiplication croisée ? c'est juste pour ma culture...

Je vois pas trop ce qu'il entend par multiplications croisées, il est pas très explicite sur sa méthode.

je crois que le calcul se fait sur une seul passe
contrairement a la mult classik ou la fin on additionne les
resultats intermediaires  
pour l algo faut attendre kelk 1 d otre
sinon le tecknik du bouclier chinoise est tres efficace ossi!
est plus simple a comprendre je pense

Ben oui. Et s'il y avait un algo plus rapide et plus simple que:
 
pour chaque chiffre ca du grand entier A
    pour chaque chiffre cb du grand entier B
        je multiplie ca par cb,
        je décale ce résultat partiel de ce qu'il faut.
        je l'ajoute au grand entier résultat au bon endroit (ce qui revient à décaler le résultat partiel correctement).
 
on l'aurait déjà appris aux enfants qui sont à l'école primaire...
 
Alors bien sûr, il n'y a pas besoin de stocker les résultats intermédiaires, on peut faire la somme en même temps qu'on fait les multiplications, mais plus efficace que cela, je ne vois pas..
 
Titoine> Pour avoir bossé et continuer à bosser avec des SGI, je ne vois pas ce que les processeurs MIPS ont de lent...
 
Par contre, ce qui est sûr, c'est que si tu veux que ton programme tourne sur Solaris, IRIX, et NT, il va falloir programmer de façon portable. Ce n'est pas très compliqué, mais cela requiert un minimum de discipline.
Le meilleur conseil que je puisse te donner, c'est d'utiliser le C ANSI pur autant que possible (puisque tu programmes en C), et dès qu'il y a des différences entre les plate-formes, tu écris une ou 2 fonctions séparées du reste du programme pour encapsuler ces différences (pour les isoler, si tu préfères). Ainsi, dans le gros de ton programme, tu n'auras pas à te préoccuper des différences de comportements, puisque tu appeleras des fonctions à toi, d'un module spécialisé (dont le seul but est de gérer cette portabilité), et qui uniformiseront le comportement.
 
Comme je ne suis pas sûr d'être clair, je donne un exemple. Imagine que tu veuilles créer et utiliser des threads dans un programme qui doit tourner sur UNIX et NT. Les fonctions de gestion de threads ne sont pas les mêmes sur ces 2 plate-formes. Au lieu de faire, à chaque fois que tu veux créer un thread :
#ifdef je suis sur UNIX  
   pthread_create(les paramètres UNIX)
#else
#ifdef je suis sur NT  
CreateThread(hThread, ...)
#endif
#endif
ce qui est bien peu lisible et tout sauf bug-proof, tu vas donc écrire un module à part, qui va définir un type Thread à toi, et des fonctions creeThread(), termineThread()donneThreadCourant(), ... qui vont appeler la bonne fonction selon la plate-forme.
Ainsi, dans ton programme, la complexité ajoutée par le problème de la portabilité se retrouve isolé (donc les bugs aussi, ce qui simplifie le boulot), et quand tu écris ton vrai programme, cette complexité-là, tu peux l'oublier (ce qui facilite aussi beaucoup le boulot).

 
J'ai eu 30 mais comme je suis pas salaud et que je savais que je passais, j'ai filé 60% des points à mes 2 binomes.
 
Pour récompense, l'adm a été foutu de se planter dans les notes et m'a reporté 9 sur mon bulletin!
Mais bon, je passe sans rattrapage et c'est le principal.

D'ailleurs, si qqn veut les sources, elles sont disponibles :
42sh
 
Mais il est fortement déconsseillé de le resortir pour la soutenance, vu la méthode que j'ai utilisé pour les pipes, Nico risque de repérer le code.

 
ca me rapelle kelk 1 qui a eu 30 aussi mais n a pas partager
les points :-p

 
Je peux comprendre ce genre d'attitude car quand tu reçois ton bulletin et tu te rends compte que tu as à peine au dessus de la moyenne de la promo, alors que tu aurais pu avoir 18 de moyenne, ça fout un peu les b...
Mais bon, c'est fait et puis j'espère bien qu'un de mes deux ex-binomes profitera de cette chance pour mettre les bouchées doubles et réussir ses études.

Alors vous en êtes où dans la bistro.
J'ai vu que Nico organisait un soutient pour l'addition

Allo?

 
Je sais que les mips sur SGI sont super mais celles de l'école, c'est genre des 33Mhz (et encore je suis gentils).
Il leur faut 5 min pour compiler mon shell qui pourtant n'a pas un code source monstrueux.
 
Sinon, pour la portabilité, "il n'y pas trop de problème" car c'est NetBSD que se soit sur PC, Alpha ou Mips, si ce n'est le fait que les librairies ne sont pas installées aux mêmes endroits et qu'elles ne portent pas toujours les mêmes noms...

pour multiplication y a l algo de karatsuba qui est en O(n^1.53)
ce qui est pas mal compare au O(n^2) de la multiplication normale
ca utilse des multiplications croisees
pour en savoir plus -> google.com
peut etre que le man en parle!!!!!!

Je suis en train de regarder cet algo récursif.
Je ne le connaissais pas (on en apprend tous les jours ). Il a l'air intéressant, mais je suis surpris des résultats annoncés... Je vais l'essayer chez moi !
 
Si c'est concluant, j'explique cet algo ici !

bon pour nous la bistro c est termine et je pense que la note va pas etre loin de -42. Mais bon on ce decourage pas.
Allez a plus pour la programmation du shell
 
-----------------------------------------------*-*-*-*-*-*
EPITECH en fete  

Pour ceux que cela intéresse, la "multiplication croisée", comme l'a appelé titoine (je crois) est l'algorithme qu'a proposé Karatsuba (un mathématicien russe, toujours vivant) pour la multiplication des grands entiers. Il est fondé sur le raisonnement suivant :
 
Supposons que les 2 grands entiers A et B, dont on veut calculer le produit, puissent s'écrire avec N chiffres en base ß. On peut donc "couper" A et B en 2, et écrire ('^' est ici l'opérateur puissance) :
   A = Ag * ß ^ (N/2) + Ad
   B = Bg * ß ^ (N/2) + Bd
'g' comme 'gauche' et 'd' comme 'droite', bien sûr.
 
Le produit A*B s'écrit alors :
   A*B = (Ag * ß ^ (N/2) + Ad) * (Bg * ß ^ (N/2) + Bd)
          = ß ^ N         *  (Ag * Bg) +
             ß ^ (N / 2) * ((Ag * Bd) + (Bg * Ad)) +
             ß ^ 0          *  (Ad * Bd)
 
Rien que de très classique. Un poil fastidieux à taper et à lire, mais classique.
Vous voyez au passage qu'ici, on fait 4 multiplcations, en coupant en 2 les 2 nombres. Une analyse de complexité pas très compliquée montre en effet que l'algorithme de calcul est en O(N^2).
 
Si vous permettez, posons PG = Ag * Bg et PD = Ad * Bd. Le produit des moitiés gauches et droites, donc. Cela ne change pas grand chose. On peut juste écrire :
   A*B = (PG * ß ^ N) + (PD) + (ß ^ (N / 2) * ((Ag * Bd) + (Bg * Ad)))
Cela allège un poil l'écriture, mais si vous me permettez, il nous reste quand même ce produit croisé sur les bras...
 
L'idée géniale de Karatsuba est "on peut faire aussi quelque chose pour ce produit croisé", en disant : posons également SA = Ag + Ad et SB = Bg + Bd. Oui, oui, la somme des moitiés de A, et la somme des moitiés de B. Alors, dans ce cas :
   SA * SB = (Ag + Ad) * (Bg + Bd)
                  = (Ag * Bg) + (Ag * Bd + Bg * Ad) + (Ad * Bd)
                  = PG + PD + (Ag * Bd + Ad * Bg)
Ou, si vous préférez :
   Ag * Bd + Ad * Bg = (SA * SB) - PG - PD
 
On peut alors écrire, dans la formule du produit de A et B :
   A * B = (PG * ß ^ N) + (PD) + (ß ^ (N / 2) *  ((SA * SB) - PG - PD))
 
Vous allez me dire : à part l'écriture encore un peu plus courte, quelle est la différence ? Elle est simple : au dessus, pour calculer le produit croisé des moitiés, il fallait faire 2 multiplications : Ag * Bd et Ad * Bg. Dans cette dernière expression, il n'en suffit plus que d'une seule, SA * SB, une fois qu'on a calculé PG=Ag*Bg et PD=Ad*Bd, et avec juste quelques additions en plus. Or chacun sait que la complexité de l'addition est O(N), donc bien plus faible que celle de la multiplication.
Et effectivement, quand on calcule la complexité de l'algorithme dérivé de cette dernière formule, on trouve O(N ^ 3/2). C'est donc un algorithme plus rapide que l'algorithme de multiplication standard.
 
Note : attention, c'est un algorithme récursif à 3 appels récursifs (puisqu'il faut calculer les 2 produits des moitiés, puis le produit des sommes des moitiés, pour calculer le produit croisé), et qui fait des additions supplémentaires par rapport à l'algorithme de multiplication standard. Il est plus efficace en général, certes, mais il ne l'est plus pour des petits nombres, car le surcoût lié à la récursivité et aux additions supplémentaires devient alors non négligeable, voire supérieur au temps gagné en ne faisant pas de 4ème multiplication.
Donc si, pour des raisons d'efficacité, vous voulez implémenter la multiplication de Karatsuba, il faudra quand même implémenter la multiplication standard, qui sera utilisée pour les petits nombres (avec un test au début de la fonction Karatsuba "si la taille de mes nombres est plus petite que ..., alors on appelle la fonction de multiplication standard et on sort" ).
 
Voilà.

Chapeau bas

Bah, c'est pas moi, le bon, c'est Karatsuba... Moi je n'ai fait qu'expliquer sa méthode après avoir lu l'algo...

Up, pour éviter que ce topic intéressant ( ) ne se perde dans les bas-fonds du forum...  

'lut les gars,
 
Un parseur de fonctions mathématiques en C++, vous avez déjà fait ça ?
 
Merci pour vos réponses

comprend rien a ce que vous dites dans ce poste    
 
ahhhhhhhhh les maths.....
 
quand je pense aux premiers mecs qui ont trouves/inventes les trucs dont vous parlez... ca me donne mal au crane    
 
bon allez j`arrete de vous embetez...

Cho les cocos cho !!!!
On ma poser le pb.. c t un gars de l'epita...
Bravo a vous tous ki avez su trouver la soluce !!!
Quant aux algos.. très très interessant
 

C'est décidé, ce topic inaugure mon "meilleur-des" posts/topics: http://forum.hardware.fr/forum2.ph [...] 0&#t232727
 
Il manque un système de classement par qualité à ce forum...

On les voit les premières années Epita ! ! ! Sitôt sorti de la piscine avec leur -42 de moyenne.

Maintenant oui©

Cherrytree a écrit a écrit : On les voit les premières années Epita ! ! ! Sitôt sorti de la piscine avec leur -42 de moyenne.

 
 
15/20

oh le up de la mort

Fnifff ...    
Tant de souvenirs ...    
 

Ohhhhh ... mes petites MIPS chéries ... ... ils les ont pas mises à la casse ... ....