Enigme Arithmétique et informatique 2 @ Prise2Tete

scarta · #1

Toujours sur le même thème, voici quelques questions un peu différentes.
Petite définition pour ceux qui ne connaissent pas tout ça:
une fonction informatique est une liste d'instructions qui prend un ou plusieurs paramètres en entrée, et renvoie un résultat. Un peu comme en math: f(a,b,c,d)=e

1) Je souhaite écrire une fonction informatique pour savoir si un nombre est premier. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?

2.1) Je souhaite écrire une fonction informatique pour savoir si un nombre est un carré parfait. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?
2.2) Quelle autre instruction me permettrait d'éliminer encore plus de cas après la précédente ?

3) Je peux faire des boucles (répéter une série d'instructions plusieurs fois). Je n'ai pas le droit de faire de multiplication, comment calculer m*n ?

4) Pareil, je souhaite faire m/n (division euclidienne).

Nicouj · #2

1) on élimine les pairs
x & 1 = 0 : pas un premier

2.1) 00^2 = 10^2 = 00 et 01^2 = 11^2 = 01
On élimine les cas où le deuxieme bit de poid faible est nul
x & 2 = 1 : pas un carré
2.2)Pas d'idée

3) On fait la somme des 2^i*n pour les bits i de l'ecriture de m
1: s = 0
2: si m = 0 goto 8
3: si m & 1 = 0 goto 5
4: s = s + n
5: n = n << 1
6: m = m >> 1
7: goto 2
8: suite

4) faire des soustractions de n a m jusqu'a atteindre 0
ça semble aussi trop trivial pour être la solution attendue

gabrielduflot · #3

1) si a est pair et a différent de 2 alors a n'est pas premier
2) si le chiffre des unités est 2;3;7;8 alors ce nombres n'est pas un carré parfait
si le chiffre des unités est 5 et que le chiffre des dizaines est différent de 2 alors ce nombre n'est pas un carré parfait
si le chiffre des unités est 0 et que le chiffre des dizaines est différent de 0 alors ce nombre n'est pas un carré parfait
3) on fait une boucle m fois en rajoutant n a chaque fois m*n=n+n+.....+n
4) q:=0
tant que m>n
faire m:= m-n et q:=q+1
m/n le quotient sera q et le reste sera le dernier m de la boucle

dhrm77 · #4

1) Je souhaite écrire une fonction informatique pour savoir si un nombre est premier. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?

int prime( unsigned n)
{
if (n==2) return(1);
if ((n&1)==0) return(0);
/* continuer avec les nombres impairs */
}

2.1) Je souhaite écrire une fonction informatique pour savoir si un nombre est un carré parfait. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ?
2.2) Quelle autre instruction me permettrait d'éliminer encore plus de cas après la précédente ?

en hexadecimal tous les carrés se terminent par 0, 1, 4 ou 9. donc on peut commencer par tester la presence de 2, puis la presence de 12.
int issquare(int n)
{
if (n&2) return 0; /* elimine 8/16 */
if ((n&12)==12) return 0; /* elimine 2/16 */
... continue a tester...
}
/* ou encore: */
int issquare(int n)
{
if (n&2) return 0; /* elimine 8/16 */
if ((n&5)==5) return 0; /* elimine 2/16 */
if ((n&9)==8) return 0; /* elimine 2/16 */
... continue a tester...
}

3) Je peux faire des boucles (répéter une série d'instructions plusieurs fois). Je n'ai pas le droit de faire de multiplication, comment calculer m*n ?

union { long l; int x,y; } t;
long res;
char a;
long mul( int m, int n)
{
long res;
res=0;
t.x=n; t.y=0;
for (a=0; a<16; ++a)
{
t.l<<=1;
res<<=1;
if (t.x&1) res+=m;
}
return(res);
}

4) Pareil, je souhaite faire m/n (division euclidienne).

union { long l; int x,y; } t;
char a;
int div( int m, int n)
{
t.x=m; t.y=(m<0) ? -1 : 0;
for (a=0; a<16; ++a)
{
t.l<<=1;
if (t.y>=n) { t.y-=n; ++t.x; }
}
return (t.x);
}

rivas · #5

Salut scarta,

Merci pour cette série.

1) La chose à plus rapide à éliminer ce sont les nombres pairs (sauf 2). Ce "sauf 2" m'ennuie: cela veut dire qu'il faut faire un test supplémentaire. Mais bon on élimine tout de même la moitié des cas. Pour tester les nombres pairs il suffit de tester le bit de poids faible du nombre. J'écrirais quelque chose du genre:

Code:

if ((n & 1) == 0 && n != 2) return;

Ce qui veut dire: si n est pair mais ne vaut pas 2 on ne continue pas l'évaluation. Il vaut mieux tester la parité en premier plutôt que l'égalité à 2, celle-ci ayant la plus forte probabilité.

2.1) On utiliser le résultat sur la congruence modulo 4 des carrés. Un carré ne peut être congru qu'à 0 ou 1 modulo 4 (0->0, 1->1, 2->0, 3->1, n+4->n). Si on considère donc les 2 derniers bits, il ne peuvent être que 00 ou 01. Le bit 1 vaut toujours 0.
Il suffit donc de rajouter un test comme celui-ci au début pour éliminer la moitié des cas (nombres congrus à 2 ou 3 modulo 4):

Code:

if ((n & 2) != 0) return;

(Le != 0 est facultatif mais c'est une bonne pratique de l'écrire)

2.2) Regardons les carrés modulo 8: 0, 1, 4, 1, 0, 1, 4, 1
Le test précédent a permis d'éliminer les congruences à 2, 3, 6 et 7 modulo 8 .
On voit qu'un carré n'est jamais congru à 5 modulo 8. On peut donc aussi éliminer ces cas:

Code:

if ((n & 7) == 5) return;

Est-ce à ça que tu pensais?

3) On se base sur l'écriture en base 2 (naturelle pour l'ordinateur) du multiplicateur.
On écrit: [latex]m=\sum{a_k2^k}[/latex] donc [latex]m.n=\sum{a_k(n.2^k)}[/latex]
Chaque ak est un chiffre en base 2 donc 0 ou 1.
On procède par "accumulation". On part de n. Si a0 vaut 1, on ajoute n à l'accumulation. On mutiplie n par 2 et on regarde a1 cette fois. Si a1 vaut 1 on ajoute 2n à l'accumulation et on multiplie n par 2 et on continue jusqu'à avoir épuisé les ak. On a donc calculé exactement: [latex]\sum{a_k(n.2^k)}[/latex] c'est-à-dire m.n.
La multiplication par 2 à chaque étape se fait par décalage à gauche d'un bit (opération élémentaire).
On choisit le plus grand nombre pour faire l'accumulation et on teste les bits du plus petit, cela permet de réduire encore le nombre de passes dans la boucle. Ici on a décomposé m, la complexité maximale est donc de l'ordre de log2(m) additions et décalages. Il faut faire attention à éviter le "débordement", c'est-à-dire un résultat trop grand pour être stocké dans un entier "informatique".
Voici un petit exemple de comment le faire. Pour des raisons de simplicité, je ne gère ni les signes, ni le débordement mais ce n'est pas difficile.

Code:

int mult(int m, int n)
{
  int r;
  if (m > n) // On échange m et n si nécessaire pour travailler sur le plus petit
  {
    int tmp;
    tmp=m; m=n; n = tmp;
  }
  r = 0; // On met l'accumulateur à 0
  while (m != 0)
  {
    if (m & 1) // Si le bit en cours d'analyse est non nul on ajoute n.2^k à l'accumulateur
      r += n;
    m >> =1; // On regarde le bit suivant de m (en fait décale m à chaque tour et on regarde toujours le bit 0)
    n <<= 1; // On multiple n.2^k par 2 pour passer a n.2^(k+1)
  }
  return r;
}

4) On utilise la aussi la décomposition en base 2. Mais cette fois-ci du quotient avant de le connaître.
On peut aussi dire que l'on fait exactement comme lorsque l'on pose la division de façon habituelle mais on le fait en base 2, pas 10 (ce qui oblige à bien comprendre ce que l'on fait quand on pose une division ).
En fait on multiplie n par 2 jusqu'à ce que ça ne soit plus possible (jusqu'à ce que le multiple suivant soit plus grand que m).
C'était la phase d'initialisation. A partir de là on entre dans un boucle:

Si on peut soustraire n.2^k à m (n.2^k est <= m), on le fait, on obtient une nouvelle valeur de m et on écrit un chiffre 1 au quotient, sinon on écrit un chiffre 0 au quotient.
Dans les 2 cas, si k n'était pas déjà revenu à 0, on divise n.2^k par 2 (décalage à droite), on diminue k (pour savoir lorsqu'on doit arrêter, on peut aussi ne pas avoir besoin de k en tester n.2^k jusqu'à ce qu'il vaille le n initial)
J'ecrirai l'algo en C un peu plus tard, je dois partir...

FifiCalin · #6

if X mod 2 = 0 then NombrePremier=False

dim RacineCarré
RacineCarré=sqr(X)
if RacineCarré=int(RacineCarré) then CarréParfait=True

Function Multiplication (Valeur, Nfois)
dim i,Total
for i=1 to Nfois
Total=Total+Valeur
next i
Multiplication = Total
end function

scarta · #7

Pour le moment, un seul carton plein (rivas, bravo à lui)

Pour les autres: je me vois mal faire m*n en ajoutant m à lui-même n fois... Je sais pas vous, mais moi si je dois faire par exemple 107894 * 3412512 sans calculatrice, j'ai un moyen super simple avec un papier et un stylo !
Et sinon, je ne l'ai pas précisé mais si la multiplication n'est pas autorisée, alors la division ne l'est pas non plus (et la racine carrée encore moins )

dhrm77 · #8

c'est vrai que j'avais pas fait tres fort sur ce coup la.... je l'ai refait avec des shifts..
Evidement, pour la multiplication et la division, on suppose qu'un int a 16 bits et un long a 32 bits.
sinon, on peut transposer avec des longs a 32 bits et des long longs a 64 bits...
ou encore avec n'importe quelle taillede nombre, en ajustant les variables et le compteur.

Yannek · #9

(1) on renvoie si (n mod 2=0) on renvoie faux si (n<>2) et vrai sinon.
(2.1) on renvoie faux si (n mod 4=2) ou (n mod 4=3)
(2.2) ??
(3) somme=m, pour i=1 a n-1 faire somme=somme+m
(4) q=0, tant que (q*n<m) faire q=q+1.

scarta · #10

Bravo aux participants, et double bravo aux participants qui ont donné une ou des bonnes réponses Voici les miennes

1) SI (N&1 == 0) RENVOIE N==2
Explications:
Si un nombre est pair, alors il est premier s'il vaut 2.

2.1) SI (N&2 == 2) RENVOIE FAUX
Explications:
Soit un nombre n quelconque,
- si n est congru à 0 modulo 4, son carré aussi
- si n est congru à 1 modulo 4, son carré aussi
- si n est congru à 2 modulo 4, son carré est congru à 0 modulo 4
- si n est congru à 3 modulo 4, son carré est congru à 1 modulo 4
Conclusion: aucun carré n'est congru à 2 ou 3 modulo 4.
En base deux, un carré peut être congru à 00 ou 01 modulo 4 mais pas 10 ou 11.
Autrement dit, le deuxième bit en partant de la droite doit être nul, sinon ça n'est pas un carré

2.2) SI (N&7 == 5) RENVOIE FAUX
Explications:
On peut faire la même analyse que ci-dessus, pour remarquer que modulo 8, on n'autorise que 3 valeurs en base 2: 000, 001 et 100
N&7: N%8 en binaire. Les différentes valeurs binaires modulo 8 sont
000 (ok),
001 (ok),
010 (éliminé au cas précédent),
011 (pareil),
100 (ok)
101 (éliminé car =5),
110 (éliminé au cas précédent),
111 (pareil)

3)Les x: correspondent à l'instruction n°x
1: resultat = 0
2: SI (m&1 <> 0) alors résultat += n
3: n <<= 1
4: m =>> 1
5: SI (m <> 0) alors retourner en 2

Explications (a+=b signifie a = a+b, a<<=b signifie a = a<<b et a>>=b signifie a = a>>b):
Comment pose-t'on une multiplication en base 10 ?

Code:

        abcde
      x  fghi
----------------
    (abcde*i)
 + (abcde*h)0
+ (abcde*g)00
....

En base 2, on peut faire pareil, mais c'est beaucoup plus simple: en effet, chaque chiffre vaut 0 (dans ce cas, n*0 = 0) ou 1 (dans ce cas, n*1=n)
Donc,
- on part d'un résultat nul
- si le chiffre considéré est 1, on ajoute n avec un certains nombres de zéros derrière (autant que d'étapes)
- on passe au chiffre suivant et on recommence tant qu'il en reste
Ici, "si le chiffre considéré est 1" correspond à "SI (m&1 <> 0)", et "n avec un certains nombres de zéros derrière (autant que d'étapes)" correspond à "n<<=1", autrement dit on ajoute 1 zéro à n à chaque étape (même si ça ne sert à rien pour ce coup-ci), ça nous évite d'avoir à le faire ensuite. Enfin, "on passe au chiffre suivant" correspond à "m>>=1" (en vrai, on supprime le dernier chiffre de m et on décale les autres vers la droite)
Pour des nombres sur 16 bits, faire m+m+m+m... n fois représente jusqu'à 65536 additions, ici 16 additions au maximum.

4) on veut faite n/m
1: resultat =0, m'=m
2: m' <<=1
3: SI (m'<n), alors retourner en 2
4: resultat <<=1
5: SI (m'>n), alors aller en 8
6: n -=m'
7: resultat |= 1
8: m'>>=1
9: SI (m' >= m), alors retourner en 4
(accessoirement, le reste de la division est n)
Explications:
Quand on pose une division en base 10, on regarde si on peut ôter le diviseur au dividende sur les premiers chiffres du nombres, et si oui combien de fois, puis on calcule le reste et on "descend" le chiffres suivant. Plus formellement, on regarde le plus grand n et le plus grand k tels que dividende > diviseur* k * 10^n, puis on calcule un nouveau dividende en lui otant "diviseur* k * 10^n", on écrit k pour le quotient (ou à la fin du quotient déjà trouvé), et on passe à 10^(n-1), on cherche le k suivant, etc...
Ici, c'est tout pareil, en base 2. Je rajoute plein de 0 derrière m jusqu'à avoir m>n. A ce moment là, je suis un cran trop loin mais c'est pas bien grave, on ajoutera juste 0 au résultat, donc ça change rien.
Ensuite, l'avantage de la base 2, c'est que notre k n'a que 2 valeurs possibles: 0 ou 1. Si c'est 0, alors m>n, donc on ajoute un 0 au résultat et on en barre un au diviseur (resultat <<=1 et m' >>=1). Si par contre c'est 1, alors m<n, donc je retranche m à n, j'ajoute un 1 au quotient et j'ôte le dernier chiffre du diviseur ( n-=m, resultat <<=1 et resultat |= 1 qui signifient "ajouter 1 au résultat" et m'>>=1)
Pour des nombres sur 16 bits, faire n-m-m-m-m-m q fois représente q soustractions (soit jusqu'à 65536, pour 65536 / 1) , ici 16 soustractions au maximum.

RL · #11

1) passer n si n est pair (i.e. n/2=n\2 ou E(n/2)=n/2).

2.1) passer n si son dernier chiffre est 2, 3, 7 ou 8.

2.2) aucune idée d'instruction simple.

3) fonction (m*n) :
p:=0
de i=1 à n {
p:=p+m
}

4) fonction (m\n) :
d:=0
si m<n alors stop
si m=n alors d:=1 : stop
x:=0
boucle :
si x+n>m alors stop
d:=d+1
x:=x+n
fin de boucle

dhrm77 · #12

Quel festival de langages...
On voit du Basic, du C, du Pascal et du pseudo-code...
enfin je crois...

rivas · #13

@scarta:

Merci pour cette rédaction.
Dans la division, si on inverse 6 et 7, on peut ajouter un optimisation en 6.5 en utilisant directement le bit de résultat à zéro de la soustraction pour arrêter dans ce cas...

A bientôt pour la suite?

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 12-11-2010 12:41:03

Arithméitque et informatique 2

#0 Pub

#2 - 12-11-2010 14:04:35

Arithmétique et informatique

#3 - 12-11-2010 19:10:25

Arithmétiquee et informatique 2

#4 - 13-11-2010 00:45:12

arithmétuque et informatique 2

#5 - 13-11-2010 12:41:57

arithmétique et onformatique 2

Code:

Code:

Code:

Code:

#6 - 13-11-2010 15:01:02

Arithmétique t informatique 2

#7 - 13-11-2010 21:56:17

Arithmétique et informatiqu 2

#8 - 13-11-2010 22:20:20

Arithmétiue et informatique 2

#9 - 15-11-2010 10:42:21

Arithmétiquue et informatique 2

#10 - 15-11-2010 12:42:59

Arithhmétique et informatique 2

Code:

#11 - 15-11-2010 12:52:45

Arithmétique et inforrmatique 2

#12 - 15-11-2010 13:21:46

arithmétique zt informatique 2

#13 - 16-11-2010 11:37:13

Arthmétique et informatique 2

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums