Discussion :

[CinePhil]

J'aimerais étudier les restes sur ce nombre ... et j'arrive pas à trouver plus que ce que je j'ai pu lire sur la doc officielle

Tu veux dire que tu cherches le reste de la division de ce nombre géant par un autre ?

Comment faisais-tu à l'école primaire ?

En prenant ton nombre géant en tant que chaîne de caractères et en extrayant petit à petit les morceaux qui vont coller avec ton diviseur, tu dois pouvoir trouver un algorithme qui te permettra de diviser tout le nombre, quelle que soit sa taille et celle de ton diviseur.

Je prends juste le début du nombre : 1350664108...
J'imagine que tu souhaites le diviser par un nombre premier (pas trop grand quand même) : 53
Retournons en CM2 :
1 / 53 --> Ca marche pas, je descend le 3
13 / 53 --> Ca marche pas, je descend le 5
135 /53 = 2 et il reste 29 ; je descend le 0
290 / 53 = 5 et il reste 25 ; je descend le 6
...

[Superne0]

Ce qui m'embête dans cette solution, c'est que le programme devra faire une division avec reste pour tout les digits, tandis que ce que je veux modifier, c'est justement le diviseur ... avec cette solution ça me prend beaucoup, beaucoup plus de temps.
Mais sinon je suis en train de chercher une solution avec GMP, mais je ne vois pas comment : j'ai déclaré l'entier (à 309 digits, voir mon premier post) en tant que mpz_t.
Je n'oublie ni la librairie gmp, ni la commande de compilation, donc étrange.
Aussi, à la ligne où je déclare le nombre, j'ai à la compilation :

attention : l'argument vecteur SSE sans autorisation SSE modifie l'ABI

[totaliou]

Comment faisais-tu à l'école primaire ?

Un peu lent...

Poste ton code cela pourrai aider à comprendre l'erreur...


Sinon ce que tu cherche ce sont des algo de "multi-précision". Pour en savoir plus => recherche google.

[Melem]

Tu dois implémenter un nouveau de type de données c'est-à-dire une nouvelle manière de représenter des données. Tu peux faire ça à l'aide d'un tableau, une structure, un champ de bit, etc. mais le plus simple c'est de représenter les nombres directement sous forme de chaîne. L'avantage c'est que c'est la représentation la plus proche de ce que nous les humains utilisons donc très facile à manipuler. Le principal inconvénient c'est que ca bouffe pas mal de mémoire (un octet pour chaque chiffre !). J'ai fais une source relativement simple qui montre comment manipuler de très grand nombres en langage C : http://www.developpez.net/forums/sho...d.php?t=467267

[Superne0]

Salut à tous,
Greatns s'utilise comme une librairie quelconque ?

[Okdokey]

Si tu n'as pas de contrainte du langage tu peux aussi utiliser python qui accepte nativement ce genre d'entier "long". Sauf erreur de saisie, ce nombre est divisible par 3 donc non premier mais peut etre que ce n'est pas ca qui t'interesse ici.

[Superne0]

Effectivement, ce qui m'interesse est bien l'étude des restes.
je m'entête avec GMP, parce que je ne conaissais pas cette librairie avant, mais c'est vrai que même si j'arrive pas à résoudre mon prob, il y a pas mal de trucs intéressants ...
Sinon, j'ai pas de contraintes de langages, donc je verrai avec Python ou Lisp si je n'y arrive vraiment pas avec GMP.
Pas d'utilisateurs de GMP ici ?
Parce que j'ai vraiment pas l'habitude d'utiliser ce genre de librairie, et j'ai une conaissance limité du C.

[acx01b]

salut

nous poster ton code qui ne fonctionne pas aurait évité 2 pages de discussion pour rien

gmp est une librairie très bien faite, et c'est intéressant de savoir l'utiliser

[Superne0]

Voici mon code.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <gmp.h>
 
int mpz_t calcul(mpz_t a,mpz_t acc){
	if((a%acc)==0){
		gmp_printf("%Zd\n",acc);
		return(acc);
	}else{
		gmp_printf("%Zd\n",acc);
		gmp_return(calcul(a,acc+1));
	}
}
 
int main(){
	mpz_init(mpz_t a);
	a = 1350664108659952233496032162788059699388814756056670275244851438515265106048595338339402871505719094417982072821644715513736804197039641917430464965892742562393410208643832021103729587257623585096431105640735015081875106765946292055636855294752135008528794163773285339061097054433499981115005697236890927563;
	gmp_printf("%Zd\n",calcul(a,2));
	gmp_return(0);
}

J'ai vraiment du mal avec la doc officielle de GMP

[hegros]

c'est quoi le problème avec ce code, compilation/edition des liens/execution???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
mpz_init(mpz_t a);
a = 1350664108659952233496032162788059699388814756056670275244851438515265106048595338339402871505719094417982072821644715513736804197039641917430464965892742562393410208643832021103729587257623585096431105640735015081875106765946292055636855294752135008528794163773285339061097054433499981115005697236890927563;

je ne le sens pas trop, je n'ai pas regardé la doc mais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
mpz_t a;
mpz_init(a);
a = 1350664108659952233496032162788059699388814756056670275244851438515265106048595338339402871505719094417982072821644715513736804197039641917430464965892742562393410208643832021103729587257623585096431105640735015081875106765946292055636855294752135008528794163773285339061097054433499981115005697236890927563;

me semble plus usuel

[Superne0]

Le problème est à l'éxécution.
En remplaçant par la nouvelle déclaration de l'entier, et en compilant avec l'option -lgmp, j'obtiens

4: erreur: expected «=", «,", «;", «asm" or «__attribute__" before «calcul"
17:6: attention : constante entière trop grande pour tenir dans son type
In function «main":
17: attention : integer constant is too large for «long" type
17:erreur: incompatible types in assignment
18: attention : implicit declaration of function «calcul"

Il y aurait pas un malloc spécial relatif à GMP à faire, ou quelque chose du genre ... ?

[hegros]

si tu as un lien vers la doc que tu utilises on peut regarder parce que pour l'instant

GMP= Groupe de Métabolisme et Pharmacocinétique

[Superne0]

Oui c'est vrai que Google boycotte ce genre d'infos ...
La doc se trouve ici
Ce qui m'étonne est qu'il n'y a pas d'équivalent à mpz_t (qui déclare un entier relatif), pour déclarer un entier naturel (qui serait l'équivalent d'un unsigned avec GMP je pense)

[Thierry Chappuis]

si tu as un lien vers la doc que tu utilises on peut regarder parce que pour l'instant

GMP= Groupe de Métabolisme et Pharmacocinétique

Ou alors "Good Manufacturing Practice"!

Plus sérieusement, la page officielle de GMP arrive en 3ème position dans ma recherche Google:

http://www.google.ch/search?hl=fr&q=...e+Google&meta=

...et avant "Groupe de Métabolisme et Pharmacocinétique".

Thierry

[acx01b]

le secret que je vais dévoiler est la fonction
int mpz_set_str (mpz_t rop, char *str, int base)

mpz_t n;
mpz_init(n);
mpz_set_str(n,"98798798749837498739873987439847398793874", 10);
gmp_printf("%Zd", n);

[Melem]

C'est pas loin non plus avec greatns :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
#include "greatns.h"
 
int main()
{
    char * a = "1234567890", * b = "9876543210", * somme;
 
    somme = gns_addi(a, b);
    if (somme != NULL)
    {
         printf("%s + %s = %s\n", a, b, somme);
         free(somme);
    }
    else
         printf("erreur.\n\n");
 
    return 0;
}

[acx01b]

salut, c'est plutôt pauvre par rapport à gmp greatns !

[Melem]

Pauvre dans quel sens? Dans tous les cas c'est plutôt normal vu que j'ai pas que ça à faire. Mais si tu remarques bien j'ai pris le soin de nommer les fonctions "opérations" gns_addi, gns_multi, etc. ce n'est pas par hasard : c'est i pour int (en fait ici c'est unsigned int mais bref). C'est très facile d'implémenter un gns_addf, gns_multf (f pour flottant ) à l'aide des fonctions **i étant donné que les calculs sur flottants se font de la même manière que les calculs sur entiers sauf qu'il faut bien aligner le point décimal. Ensuite, on peut se faire toutes les opérations et les fonctions qu'on veut à l'aide de l'addition et la multiplication. En fait, si on veut optimiser on va plutôt recoder chaque fonction mais en partant chaque fois de morceaux de codes déjà existant. Ensuite, si on embarque ça dans un intérpréteur d'expressions mathématiques (comme celui que j'ai fait par exemple), ça donne ... une arme fatale.

[Trap D]

Si tu n'as pas de contrainte du langage tu peux aussi utiliser python qui accepte nativement ce genre d'entier "long".

Je pense que Lisp, Scheme ou Haskell traitent très bien ce genre de problème aussi.

[acx01b]

pour greatns il reste la multiplication par fft à implémenter !