division rapide des grands nombres

[Pole]

Bonjour,
je me fais des bibliothèque sur les grands nombres et je bloque sur les divisions. J'ai déja posé cette question mais l'algorithme donné était assez efficace pour les nombres dans une petite base. Et moi, je travaille en base 10 000. Je cherche un algorithme assez rapide, et dont la complexité ne dépend pas de la base où je travaille.
Merci.

[shokin]

Salut,

désolé, je n'ai pas la folie des grandeurs

J'ai simplement vu que ce message n'avait reçu aucune réponse.

PS : En voilà une en espérant qu'une personne puisse trouver confort en ce problème ténu et tenu.

Shokin

[Moma]

dont la complexité ne dépend pas de la base où je travaille.
Merci.

Bonjour,

a priori, la complexité va être polynomial, et donc en puissance de log(n) si n est ta donnée. Changé la base revient à changer la base du logarithme, et la complexité ne change pas... Mais je ne suis pas sûr d'avoir compris ce que tu voulais dire.

JPour reprendre ton problème, j'ai été confronté au même problème. Je suis d'abord passé par des chaines d'entiers, mais le procédé était plutôt lent. J'ai ensuite opté pour des approximation flotantes. en fait, je détermine les chiffres du quotient par "tranche" de la longueur du nombres de décimales des flotants. (soustraction, puis détermination du quotient pour un nombre plus petit...). Sinon, peut-être que tu pourrais consulter le bouquin de Knuth (je ne sais plus exactement son titre, mais c'est un bouquin fondamental en info, je pense que tu trouveras). Sinon, un bouqin plus récent sur les algos utiles en théories des nombres est paru recement. Un des auteurs est pomerance il me semble (je dois avoir la référence qqe part, mais je sais vraient plus où).

Voilà à peu près ce que je peux dire pour t'aider.

Amicalement
Moma

[Pole]

J'aimerai bien trouver un algorithme polynomial.

Complexité de la base :

c=nombre de chiffres de a - nombre de chiffres de b - 1;
b1=b*base^c;
r=0;
while (b1>=b){
while (a>=b1){
r=r+1;
a=a-b1;
}
b1=b1/base;
if (b1>=b) alors r=r*base;
}

Voilà un algo assez lent pour les grandes bases.

Moma : je ne sais pas lire l'anglais.