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

La TI adresse sur 23 Bits niveau BUS mais représenté sur 24 Bits

geogeo
: La TI adresse sur 23 Bits niveau BUS mais représenté sur 24 Bits

normal, A0 est remplacé par la paire US/LS ou qqch du genre... C'est un bus 16bits en externe, on ne peut donc pas adresser en 24 bits - c'est d'ailleurs ça qui cause les erreurs d'alignement résolus dans le 030 -

Kevin> Je pensais pas que t'irais jusqu'à coder en base 255 pour avoir une "perfection mathématique" complètement ridicule... (surtout qu'asymptotiquement, le codage est moins efficace, même s'il l'est plus pour des petits entiers) Jusqu'à preuve du contraire, en dessous de 8 Go de RAM, 32 bits suffisent (si on code le nb de mots). Et comme il veut une solution 68k-only, je doute _franchement_ qu'il veuille gérer plus de 8 Go de RAM
Je vois pas pkoi tu cherches midi à 14 heures avec des "solutions" carrément inefficaces (calculer un modulo 255 à chaque fois, miam ), alors que la solution triviale marche incroyablement bien.

Timad> il y a aussi une question que tu devrais te poser, c'est l'ordre des octets. Ca peut être une bonne idée de garder la même endianness que le 68k (ça permet de manipuler long par long au lieu de short par short pour les additions), mais il faut aussi considérer le fait que -(An) est plus lent que (An)+...

Pollux
: Kevin> Je pensais pas que t'irais jusqu'à coder en base 255 pour avoir une "perfection mathématique" complètement ridicule...

(surtout qu'asymptotiquement, le codage est moins efficace, même s'il l'est plus pour des petits entiers)

Au contraire, c'est pour les petits entiers qu'il est moins efficace que celui de GoldenCrystal, et plus les entiers sont grands, plus il deviendra plus efficace!
1 -> mon codage: 02 00, celui de GoldenCrystal: 01
255 -> mon codage: FF 01 00, celui de GoldenCrystal: FF 01
256⁸ -> mon codage: int(₂₅₅log(256⁸))+2=10 octets, celui de GoldenCrystal: int(₁₂₈log(256⁸))+1=10 octets
256¹⁶ -> mon codage: int(₂₅₅log(256¹⁶))+2=18 octets, celui de GoldenCrystal: int(₁₂₈log(256⁸))+1=19 octets
256¹⁰⁰ -> mon codage: int(₂₅₅log(256¹⁰⁰))+2=102 octets, celui de GoldenCrystal: int(₁₂₈log(256¹⁰⁰))+1=115 octets
Quant à celui que tu défends, il n'est pas dans la même ligue parce qu'il est limité en taille.

Et comme il veut une solution 68k-only

Tu as lù ça où?

Je vois pas pkoi tu cherches midi à 14 heures avec des "solutions" carrément inefficaces (calculer un modulo 255 à chaque fois, miam ), alors que la solution triviale marche incroyablement bien.

Je cherche une solution qui répond à ses contraintes, ce qui n'est pas le cas de celle que tu défends.

Timad> il y a aussi une question que tu devrais te poser, c'est l'ordre des octets. Ca peut être une bonne idée de garder la même endianness que le 68k (ça permet de manipuler long par long au lieu de short par short pour les additions), mais il faut aussi considérer le fait que -(An) est plus lent que (An)+...

En source de move seulement. Aucune différence partout ailleurs. Du moins à en croire ma taille de timings. Et puis on n'est pas à 2 cycles près...

c en effet a68K Only (j'ai pas preciser...).
Au debut je voulais coder ca en C, mais bon je pense finalement que je vais devoir me remettre a l'asm, parce que mes essais en C sont pas satisfaisants

Kevin Kofler
:

(surtout qu'asymptotiquement, le codage est moins efficace, même s'il l'est plus pour des petits entiers)

Au contraire, c'est pour les petits entiers qu'il est moins efficace que celui de GoldenCrystal, et plus les entiers sont grands, plus il deviendra plus efficace!
1 -> mon codage: 02 00, celui de GoldenCrystal: 01
255 -> mon codage: FF 01 00, celui de GoldenCrystal: FF 01
256⁸ -> mon codage: int(₂₅₅log(256⁸))+2=10 octets, celui de GoldenCrystal: int(₁₂₈log(256⁸))+1=10 octets
256¹⁶ -> mon codage: int(₂₅₅log(256¹⁶))+2=18 octets, celui de GoldenCrystal: int(₁₂₈log(256⁸))+1=19 octets
256¹⁰⁰ -> mon codage: int(₂₅₅log(256¹⁰⁰))+2=102 octets, celui de GoldenCrystal: int(₁₂₈log(256¹⁰⁰))+1=115 octets

Oui enfin je ne parlais même pas de celui de GoldenCrystal parce qu'il est encore plus inefficace niveau mémoire... Cela dit, il est moins horriblement lent dans les calculs (même si ça reste bcp trop lent)

Et comme il veut une solution 68k-only

Tu as lù ça où?

J'ai lu ça dans le ./4 :

Sinon oui je souhaiterai les stoquer en base 2 et la machine cible c les ti68k.

(en réponse à ma question sur l'endianness)

Je vois pas pkoi tu cherches midi à 14 heures avec des "solutions" carrément inefficaces (calculer un modulo 255 à chaque fois, miam ), alors que la solution triviale marche incroyablement bien.

Je cherche une solution qui répond à ses contraintes, ce qui n'est pas le cas de celle que tu défends.

Si, justement

Timad> il y a aussi une question que tu devrais te poser, c'est l'ordre des octets. Ca peut être une bonne idée de garder la même endianness que le 68k (ça permet de manipuler long par long au lieu de short par short pour les additions), mais il faut aussi considérer le fait que -(An) est plus lent que (An)+...

En source de move seulement. Aucune différence partout ailleurs. Du moins à en croire ma taille de timings.

Justement non (moi aussi j'avais une table de timing qui racontait n'importe quoi là-dessus). Regarde 68kUM, tu verras que y a 2 cycles de + partout sauf en destination de move...

Et puis on n'est pas à 2 cycles près...

Tu n'es jamais à 2 cycles près (ni d'ailleurs à N cycles près pour tout N positif )

Jackos> Non, tu l'avais dit en ./4 Et c clair que l'addition/multiplication/division tu dois le faire en ASM... Tu peux tjs faire les routines moins importantes en C (genre la fonction 'puissance'...)

JackosKing: quand t'aura un truc qui marche, je serais interessé de comparer la vitesse face à une solution en C (ma bistromathique d'Epita)...

je suis sur que meme code en asm mon truc sera plus lent enfin je vais essayer de coder l'addition rapidement...

heu grave probleme, si je code mes nombres en base 2.. comment je vais faire pour les afficher apres ?

Bah le tradeoff entre base 2 et base 10, c'est que la base 10 est bcp plus rapide/simple à afficher, mais que la base 2 est bcp plus rapide/simple pour les calculs...

Pour afficher tout ça, la solution la plus simple doit être de faire un div+mod par 10 et itérer jusqu'à ce qu'il n'y ait plus de chiffres à afficher...

bon en gros je dois faire fasse a 2 problemes actuellement:
la simplifiaction de fraction (je bosse en valeur exacte) et l'affichage
j'y reflechis.

En quoi l'affichage est difficile ?
Si j'ai bien compris, tu dois simplement coder un itoa ?

Oui, rien de bien difficile... A moins de vouloir faire vraiment dans l'optimisé, et encore, je ne suis même pas sûr que ça soit possible de faire bcp mieux que la méthode bourrin.

bon en gros le probleme:
j'ai 0b10101110010 -> sur par exemple 30 Octets.
pour obtenir la base 10, c tout simplement: sum(2^i*EtatBit(i))
pour afficher la base 10 ca ca finger in the nose.
le probleme c que je sais afficher en base 10 un nombre en base 10 mais pas un nombre en base 2 (la conversion base 2 ->10 depasse les types de données)

Si tu sais faire une division euclidienne avec ton format (ce que tu as intérêt à savoir faire ), alors tu fais la division euclidienne par 10 de manière répétée et c'est bon.
Ou alors, tu fais des additions et multiplications répétées avec tes chaînes de caractères en base 10 comme le fait Tokens89.
Il faut savoir ce qui est plus lent: les divisions/modulo en base 2 ou les additions/multiplications en base 10.

ok je vais voir thx

Je sais pas si tu es interrese mais il y existe GMP ( http://www.swox.com/gmp ) pour la gestion rapide des entiers de taille indefinie (aussi la rationnels et les flottants). C'est ce qui est utilise dans Maple, et dans plein d'applications necessitant une grande vitesse de calcul. (Et le portage pour ti est possible).

Je vais regarder merci.

(Et le portage pour ti est possible).

mais difficile car la lib c est pas vraiment conforme.

Et d'ailleurs celle de PedroM l'est déjà plus que celle de AMS+TIGCCLIB, donc le portage sera encore plus lourd pour AMS+TIGCCLIB.