Coder une adition de 2 nombres de taille in(def?)finie - Page 1

Voilà, je suis en train d'essayer de refaire les opperations élémentaires d'une calculatrice scientifique, dont la particulartité serait qu'elle travaille avec des nombres de taille in(de?)inie (comme sur HP49).
bon j'ai reflechis (si ca m'arrive), et j'ai plusieurs solutions, mais je les trouve pas tres bonnes (vitesse..).
la premiere c la solution bateau, un chiffre un octet... (ca prend de la place et c lent...)
la deuxieme c de divisionner les chiffres en long dont seul le poid faible est utilisé.. pour gerer les depassement etc. suffit de faire un swap etc.. mais je trouve cette methode pas top non plus

Si vous avez des idées ou des urls, ce serait le bienvenu

Utilise la représentation de AMS. TI a fait le travail de recherche pour toi, profites-en!
http://tigcc.ticalc.org/doc/estack.html#top_estack

Kevin> erf, je pense pas qu'ils aient fait le moindre "travail de recherche" pour la rapidité. En plus je soupçonne que JS veut le faire pour des flottants aussi...

JS> je pense que prendre des word serait un bon compromis (voire même prendre des longs pour les add/move et éventuellement travailler sur des word pour certaines opérations [multiplication...]; mais évidemment ça demande alors de faire des suppositions sur l'endianness de la machine cible)

Et j'imagine que tu veux stocker ça en base puissance de 2, pas en base 10, non?

Si je prend des words... je suis obligé de les caster en long pour les depassements lors de l'addition etc.. non?
Sinon oui je souhaiterai les stoquer en base 2 et la machine cible c les ti68k.

Ouais enfin je te conseille de bien mettre des commentaires autour de chaque bout qui dépend de l'endianness.

Pour l'addition, ben soit tu fais de l'asm (addx...), soit tu peux faire à la barbare du genre :

int c;
while (blah) {
  res=x1+x2+c;
  c=!!((x1&x2)&0x8000);
}

Mais c évidemment bcp moins efficace...

Mais même avec les float de TI, tu ne peux pas gérer des nombres de taille infinie
Ni avec aucune méthode je pense.
Vous comptez faire comment ?

Je ne sais pas si Jackos veut faire des floats de taille "infinie". En fait, pas infinie, juste "non bornée" (i.e. tu peux régler la calc pour te mettre en 50 chiffres après la virgule)

la virgule a la limite ca m'importe peut, mais il faut forcement une limite (definie par l'utilisateur de toute maniere une fois que l'algo est fait c juste un probleme de ram...)
en revanche pour la partie entiere, je veux pas de borne (ex 999! doit passer.. (en fonction de la ram))
bon sinon je regarderai ton code pollux thx (la j'ai plus le tmps)

Comment comptes-tu faire pour qu'il n'y ait pas de limite ?

Jackos> si tu veux gérer les float et les entiers, je te conseillerais de faire deux types différents : pour les floats, on borne le nombre de chiffres (y compris dans la partie non-fractionnaire, i.e. Gamma(1000.0) ne doit pas avoir 2560 chiffres mais uniquement une centaine), et pour les entiers, on ne le borne pas (mais on n'accepte pas de partie fractionnaire). Sinon, ça risque de poser des problèmes (si tu bornes après la virgule mais pas avant). Et mon "code", y a rien

Sasume> je pense qu'il y aura au moins une limite de 158000 chiffres (éventuellement le double sous Pedrom)

Pour les entiers, je sais pas trop ce que ça vaut pour du calcul, mais tu peux tjrs tester ça (ça s'appelle variable-length encoding, je crois):
-Tu choisis une taille de bloc de données de base (byte, word ou long, pas plus )
-Tu fractionnes ton bloc de cette façon:

n    n-1  n-2  n-3    2    1    0
+----++----+----+-...-+----+----+
| C  ||         données         |
+----++----+----+-...-+----+----+

(n c'est la taille du blac de données )
Là le bit 'C' t'indiques si le nombre continue sur le bloc suivant
Avec ça, je pense que, c'est pas trop compliqué de faire des calculs.

Tu veux dire que c'est juste une liste chaînée? Le problème c'est que 1) tu vas devoir mettre ton bit qui dit que c'est pas fini partout => n bits de perdus (au lieu de 16) et 2) tu peux pas te permettre de stocker le bit "en même temps" que les données, sinon avec les histoires d'alignement tu perds 1 octet ou 1 mot à chaque fois...

Et sinon pour tester la condition d'arrêt, c'est bien plus rapide de faire un dbf qu'un add/bcc (sans compter les accès mémoire supplémentaire). Je ne vois pas trop l'intérêt de ta méthode, en fait... (à moins que tu veuilles faire une _vraie_ liste chaînée, auquel cas ça va bouffer pas mal de mémoire à moins d'avoir de gros blocs)

Pollux
: Tu veux dire que c'est juste une liste chaînée? Le problème c'est que 1) tu vas devoir mettre ton bit qui dit que c'est pas fini partout => n bits de perdus (au lieu de 16) et 2) tu peux pas te permettre de stocker le bit "en même temps" que les données, sinon avec les histoires d'alignement tu perds 1 octet ou 1 mot à chaque fois...

Tu peux les stocker avec. Pour tester le bit de poids fort, c'est un simple test de signe, et pour le virer (pour pouvoir faire des calculs), c'est un shift vers la gauche et un vers la droite. Pas si déraisonnable que ça en taille de code.

Et sinon pour tester la condition d'arrêt, c'est bien plus rapide de faire un dbf qu'un add/bcc (sans compter les accès mémoire supplémentaire). Je ne vois pas trop l'intérêt de ta méthode, en fait... (à moins que tu veuilles faire une _vraie_ liste chaînée, auquel cas ça va bouffer pas mal de mémoire à moins d'avoir de gros blocs)

L'intérêt de sa méthode, c'est d'éliminer la limite arbitraire de ₂₅₆(2ⁿ), n étant le nombre de bits réservé pour le comptage d'octets significatifs.

Je ne m'y connais pas vraiment là-dedans mais je ne vois pas l'intérêt d'une liste chaînée (en tous cas pas pour les gros nombres). Simple proposition; pourquoi ne pas stocker comme ça:
nombre d'octets (mot) | nombre (chaîne)

ba, une liste chaînée (quoique j'appelerais pas ça comme ça), ça a des avantages sur les nombres de taille inférieure à la taille (byte, word ou long) du bloc que tu as choisie. Par exemple, avec le système que tu proposes, tu aurais ça pour stocker un octet: (c shématique)
[WORD][1][BYTE][X], alors qu'avec une "liste chaînée", tu aurais juste [BYTE][X], soit 1 octet au lieu de 3 (et c le même principe chose pour les tailles de blocs plus grandes)
ça a simplement l'avantage de favoriser les nombres plus petits, qu'on utilise plus souvent en principe

Est ce que tu comptes coder tes entiers en base 2 ou en base 10 ? (Le problème de la base 2 c'est la lourde conversion en décimal pour l'affichage, d'ailleur je trouve que les Ti affichent excessivement lentement les grands entiers...)

Une solution intermédiaire est de stocker les entiers en base 10^n, chacun des "chiffres" de cette base (compris entre 0 et 10^n-1) étant un entier du microprocesseur. Le dilemme est alors de choisir le n qui va bien avec les débordements. C'est la solution qu'avait adopté Jean Michel Ferrard sur un petit projet de ce genre, pour HP48, il y a assez longtemps....

Sinon, as tu réfléchi à ce que tu vas faire après l'addition? Et notamment, comptes tu faire une multiplication "basique", ou bien avec un algorithme qui va vite (FFT) ?

Il te suffit juste de convertir chaque chiffre en son code ASCII.

quand vous dites base 1à vous voulez dire 1 chiffre = 1 octet? je vois pas trop..

Martial Demolins :
Et quel est le ROM_CALL correspondant? Je ne veux pas de sprintf, je veux juste convertir un nombre en chaine de caractère

Le ROM_CALL correspondant est sprintf. Cf. http://tigcc.ticalc.org/doc/faq.html#18.

Non mais plus sérieusement, quel est le meilleur algo pour coder ça?

http://tigcc.ticalc.org/doc/faq.html#19

Je me demande pourquoi on met tout ça dans notre FAQ... (Il faudra d'ailleurs que je mette à jour certains trucs...)

Euh, j'y connais pas grand chose au C, mais j'interprète ça comme ça :

D'abord tu crées une chaine de 10 caractères (mais je pense que tu peux en mettre plus, si ton nombre est plus grand qu'un milliard), puis un pointeur à la fin de la chaine.
Ensuite, tant que l'entier à convertir n'est pas nul, tu :
- mets à l'endroit de ton pointeur le caractère qui correspond au chiffre des unités en base 10 de ton nombre (le +'0', ça veut dire que tu ajoutes au chiffre le code ascii de 0, pour obtenir le code ascii de ton chiffre)
- décrémentes ton pointeur
- divise ton entier par 10
A la fin, tu retournes le pointeur, qui pointe vers la chaîne voulue.

J'ai bon ?

Martial Demolins :
Au fait, ça serait possible de me traduire ce morceau de code en algo??? (moi et le C)


char *IntToStr (unsigned long an_integer)
{
static char result [] = " \0"; // 10 spaces and \0
char *ptr = result + 10;
while (an_integer)
{
*ptr-- = an_integer % 10 + '0';
an_integer/=10;
}
return ptr; }

tigcc -S et tu l'as en assembleur. Rajoute aussi -Os -fomit-frame-pointer si tu veux avoir du code efficace en sortie. Résultat:

result.0:
	.ascii "          \0\0"
	.text
	.even
	.globl	IntToStr
IntToStr:
	move.l %a2,-(%sp)
	move.l %d3,-(%sp)
	move.l 12(%sp),%d3
	lea result.0+10,%a2
	jbra .L2
	.even
.L5:
	pea 10.w
	move.l %d3,-(%sp)
	jbsr __umodsi3
	addq.l #8,%sp
	add.b #48,%d0
	move.b %d0,(%a2)
	subq.l #1,%a2
	pea 10.w
	move.l %d3,-(%sp)
	jbsr __udivsi3
	addq.l #8,%sp
	move.l %d0,%d3
.L2:
	tst.l %d3
	jbne .L5
	move.l %a2,%a0
	move.l (%sp)+,%d3
	move.l (%sp)+,%a2
	rts

Kevin Kofler
:

Pollux
: Tu veux dire que c'est juste une liste chaînée? Le problème c'est que 1) tu vas devoir mettre ton bit qui dit que c'est pas fini partout => n bits de perdus (au lieu de 16) et 2) tu peux pas te permettre de stocker le bit "en même temps" que les données, sinon avec les histoires d'alignement tu perds 1 octet ou 1 mot à chaque fois...

Tu peux les stocker avec. Pour tester le bit de poids fort, c'est un simple test de signe, et pour le virer (pour pouvoir faire des calculs), c'est un shift vers la gauche et un vers la droite. Pas si déraisonnable que ça en taille de code.

Si tu le stockes avec, alors tu es obligé de faire tes calculs en base 2^15. Ca peut poser un nombre invraisemblable de problèmes (le premier étant que tu ne peux pas utiliser un simple addx pour faire une addition, mais il y a autant de variantes qu'on peut l'imaginer, par exemple la multiplication : pour faire résultat 30 bits -> 2 résultats 15 bits, on doit faire un swap/rol.l #1... [+10 cycles!]; sans compter aussi qu'il faudra éliminer le bit qui indique la fin du nombre lorsqu'on le rencontre, sinon ça posera des pbs dans les calculs...)

Et sinon pour tester la condition d'arrêt, c'est bien plus rapide de faire un dbf qu'un add/bcc (sans compter les accès mémoire supplémentaire). Je ne vois pas trop l'intérêt de ta méthode, en fait... (à moins que tu veuilles faire une _vraie_ liste chaînée, auquel cas ça va bouffer pas mal de mémoire à moins d'avoir de gros blocs)

L'intérêt de sa méthode, c'est d'éliminer la limite arbitraire de ₂₅₆(2ⁿ), n étant le nombre de bits réservé pour le comptage d'octets significatifs.

Si tu prends n=32 ou 24, tu n'as _vraiment_ aucune limitation (en tout cas tant que tu le fais sur 68k ). Encore un de ces rêves d'implémentation "mathématiquement parfaite" ?

S'il y a une limite arbitraire, quelle qu'elle soit, ça ne correspond pas aux contraintes. Cf. ./8:

JackosKing :
en revanche pour la partie entiere, je veux pas de borne (ex 999! doit passer.. (en fonction de la ram))

(C'est moi qui ai rajouté la mise en relief.)
(D'ailleurs, s'il avait précisé cette contrainte dès le départ, j'aurais tout de suite conseillé un format comme celui de GoldenCrystal et pas celui de AMS qui a le problème de la taille de départ.)

Sinon, il y a une autre solution, plus économique en mémoire:
On code le nombre en base 255 (oui, 255, pas 256!), et on code 0 pour "stop", et 1-255 pour 0-254.

je saisie pas tout tu peux donner un ex stp?

255 est représenté 0xFF.
256 est représenté 0x0100.

Justement non!!!
254 est représenté FF 00
255 est représenté 01 02 00
256 est représenté 02 02 00