Comment factoriser un nombre ?

Je travailles avec la lib gmp, avec de gros nombres pouvant atteindre plus de 30 chiffres.

Au lieu de stocker tout ces chiffres dans ma base de données, j'avais idée de factorise ce nombre, mais je ne sais pas comment m'y prendre.

Je voudrais d'un nombre x obtenir une formule qui représente ce nombre si on exécute la formule.

Par exemple le nombre x (de 30 digits) serait genre: (2^x) * y^z + a

ou un truc du genre. Ce que je cherches à faire c'est d'utiliser moins d'octets que le chiffre pour le représenter, en supposant qu'un digit == 1 octet. J'imagine qu'il doit y avoir moyen d'obtenir une formule simple. Sans tomber dans les nombre à virgule qui serait plus long que le nombre original. :?:

Avec 30 chiffres, tu peux écrire 10^30 nombres, ton codage doit donc permettre d'écrire 10^30 nombres... ce qui nécessite 30 chiffres !

Néanmoins il peut exister des solutions moins gourmandes :
1) travailler en base 256 --> avec 13 octets tu vas jusqu'à 2x10^31
2) tes nombres ne sont pas répartis de façon régulière, voire ne sont pas tous possibles --> tu peux gagner de la place (principe du codage de Huffman)
3) tu peux te permettre certaines approximations (principe du codage JPEG)

Tu écris "Au lieu de stocker tout ces chiffres dans ma base de données", question naïve : pourquoi ?

Je ne comprends pas ce que tu veux dire par travailler en base 256, comment je peux aller chercher tout les nombres avec 2x10^31 ?

Ce que j'avais idée de faire c'est admettons que j'ai un nombre, par exemple: 1770887431076116955136

On sait que ce nombre se trouve entre 2^70 et 2^71 donc il ne me reste qu'a trouver une formule qui serait == 590295810358705651712

Car 2^71 - 1770887431076116955136 == 590295810358705651712

À moins d'avoir un nombre juste, j'aurai toujours un nombre entre 2^x et 2^x+1

Mais je bloques, il doit y avoir une façon simple d'exprimer ce nombre dans une formule mathématique.

Pourquoi ? Et bien dans une grande base de données, plus les données sont courte, moins la bd est grosse. :wink:

Citation:

---

Envoyé par AsmCode

Je ne comprends pas ce que tu veux dire par travailler en base 256, comment je peux aller chercher tout les nombres avec 2x10^31 ?

---

1 octet = 8 bits prenant les valeurs entre 0 et 255, c'est à dire réalise une numération en base 256., c'est bien comme cela que sont stockés les entiers (restons avec les UNSIGNED), avec 13 octets tu vas jusqu'à 2 10^31.

[Edit]
Juste un peu de dyslexie (13 au lieu de 31)
[/Edit]

Ou encore 256^13 :wink:

Mais n'empêche qu'il me rester a trouver une formule de math pour représenter un nombre x compris entre 256^13 et 256^(13+1)

Mais en fait, je ne le calcul pas comme cela.

Car par exemple, prenons un nombre sur 5 octets. Qui peut atteindre au plus: 1099511627776

Admettons que sur 5 octets, selon les bits, j'ai le nombre: 4899967297

Ce qui veut dire en partant, que j'ai un nombre qui doit s'exprimer entre 2^32 et 2^33

Sachant cela, il me reste donc qu'a trouver la formule pour représenter le nombre: 605000001

Car c'est un genre de offset, car je sais que mon nombre de départ commence au moins à 2^32 et se termine avant 2^33, donc mon nombre est de (2^32) + 605000001

Mais c'est cette partie dont je dois trouver la formule.

J'avais pensé à faire une suite de: 2^x + 2^y + 2^z, ... mais ça revient à écrire cela pour chaque bits, donc je suis pas gagnant en espace :wink:

Moi je comprends toujours pas vraiment ce que tu veux faire.
Si les grands entiers que tu cherches à coder de la manière la plus concise possible sont quelconques (hasard=sans propriété connue), alors ce sera impossible de les coder mieux (en moyenne) que leur représentation binaire.

Si par exemple tu sais qu'ils sont du même ordre de grandeur tu peux peut-être coder:
-leur différences à une moyenne globale
-leur différences successives

Si tu sais juste que le nombre est compris entre 2^32 et 2^33, tu ne peux economiser que un seul bit pour le codage (le 33ème)

Hmm, je cherches une formule de math pouvant trouver le nombre de bits nécessaire d'un nombre x

Je sais que ça donnerait une nombre à virgule mais j'ai juste besoin de l'entier avant la virgule :D

Quelqu'un peut-il m'aider ? :wink:

Citation:

---

Envoyé par AsmCode

Mais c'est cette partie dont je dois trouver la formule.

---

Relis ma première intervention !
Soit tes nombres sont tous possibles et avec une probabilité d'apparition identique, et dans ce cas, il n'y a pas moyen de diminuer le nombre de bits nécessaires, soit

2) tes nombres ne sont pas répartis de façon régulière, voire ne sont pas tous possibles --> tu peux gagner de la place (principe du codage de Huffman)
3) tu peux te permettre certaines approximations (principe du codage JPEG)

Citation:

---

Envoyé par AsmCode

Hmm, je cherches une formule de math pouvant trouver le nombre de bits nécessaire d'un nombre x

---

ln(x)/ln(2)

Merci :D

En fin de compte, je vais stocker les bits dans ma bd :wink:

J'ai pas de si gros nombres que cela après tout heheh

Encore une chose :)

Comment calculer le nombre de caractères que peux prendre un nombre en décimal ?

Si par exemple j'ai un nombre sur 64 bits, comment savoir le nombre de digits ?

Citation:

---

Comment calculer le nombre de caractères que peux prendre un nombre en décimal ?

---

Je suppose que tu parles de la base 10 :

Code:

---

Ceil(64*log(2)) = 20

---

Citation:

---

Envoyé par AsmCode

Hmm, je cherches une formule de math pouvant trouver le nombre de bits nécessaire d'un nombre x

---

Y'a pas de l'abus, là ? C'est du cours de terminale tout de même !

Quelle pourrait être la formule pouvant retirer 1 bit par octet sur un nombre x d'octets de départ, sur un nombre y de fois ?

Par exemple à la main, cela ressemblerait à ceci: x = 10 octets

10 octets - 10 bits == 9 octets. (1ere fois)

9 octets - 9 bits == 8 octets (2e fois)

8 octets - 8 bits == 7 octets (3e fois)

Merci :D

Tu ne peux pas descendre en dessous d'un certain nombre, c'est ce qu'on appelle l'entropie. Si tu descends en-dessous, c'est un codage destructif.
C'est pour ça qu'on a conseillé un codage d'Huffman, c'est ce qui se rapproche le plus de ce que tu recherches - avec les compressions par dictionnaire ou les compression arithmétiques -