Question BASIC MO5

Cette catégorie traite de développements récents pour nos vieilles machines, applications, jeux ou démos... Amis programmeurs, c'est ici que vous pourrez enfin devenir célèbres!

Modérateurs : Papy.G, fneck, Carl

Asic512
Messages : 128
Inscription : 30 juin 2019 21:13

Re: Question BASIC MO5

Message par Asic512 »

Merci pour vos réponse. Je n'ai pas de but précis si ce n'est de satisfaire ma curiosité.
__sam__ a écrit : 05 juin 2022 17:18 C'est une évaluation de polynômes à la Horner

Code : Tout sélectionner

* CALCULATE THE VALUE OF AN EXPANDED POLYNOMIAL
* EXPRESSION. ENTER WITH (X) POINTING TO A TABLE
* OF COEFFICIENTS, THE FIRST BYTE OF WHICH IS THE
* NUMBER OF (COEFFICIENTS-1) FOLLOWED BY THAT NUMBER
* OF PACKED FLOATING POINT NUMBERS. THE
* POLYNOMIAL IS EVALUATED AS FOLLOWS: VALUE =
* (((FPA0*Y0+Y1)*FPA0+Y2)*FPA0…YN)

***********
Eval_Series
***********

          BSR   Store_ACA_XC
          LDB   ,Y+
          STB   COEFCT
          TFR   Y,X

EvSe_10   BSR   Jmp_ACA_Mult_X
          LEAY  4,Y
          TFR   Y,X
          BSR   Jmp_ACA_Plus_X
          LDX   #INDEXC
          DEC   COEFCT
          BNE   EvSe_10

EvSe_Ret  RTS
Si je me fie aux commentaires en entête, c'est bien une évaluation à la Horner d'un polynôme. Mais je n'ai pas compris comment était produit ce dernier. Certaines valeurs semblent pré-calculées d'ailleurs : racine de 2 et son inverse, ln(2), pi/2 etc. (autour des lignes 6245 du source de Daniel.)
Asic512
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: Question BASIC MO5

Message par __sam__ »

Je ne suis pas sur de comprendre. Ta question est-elle: d'où sort le polynôme de Horner ? Et bien c'est une factorisation des "x" comme ceci : 5x⁴ + 4x³ + 3x² + 2x + 1 = (((5x + 4)x + 3)x + 2)x + 1.. Ainsi les puissances de "x" se calculent toutes seules. A chaque étape on multiplie l'accu précédent par X et on ajoute le coefficient suivant, ce qui fait peu d'opérations au total contrairement à la forme avec les puissances.

Dans le code ASM les Y0,Y1..,YN sont les coefficients du polynôme donnés par degré décroissant (Y0=5,Y1=4,Y2=3,..Y4=1 dans l'exemple ci-dessus) et FPA0 sont le point où l'on veut évaluer ce polynôme.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Asic512
Messages : 128
Inscription : 30 juin 2019 21:13

Re: Question BASIC MO5

Message par Asic512 »

Visiblement les calculs de sin, exp, log se font par évaluation de certains polynômes par la méthode de Horner "Eval_Series". La question est quel algorithme produit ces polynômes. Autrement dit je n'ai pas compris ce que fait la procédure FUNC_SIN etc.
Asic512
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: Question BASIC MO5

Message par __sam__ »

Je connais l'algorithme de Remez pour trouver les polynôme ayant une erreur max minimale sur un intervalle => http://www-lmpa.univ-littoral.fr/~smoch ... Fiche2.pdf

Je l'avais utilisé dans un de mes projets. Dans ce projet j'avais trouvé une page web qui permet de calculer un tel polynôme. Par exemple si tu entres la fonction sin(x) entre 0 et 3.1415926535897932384626433832795 en demandant un polynôme de degré 4, tu obtiens

Code : Tout sélectionner

y = 0.0005967705243762224 + x*(0.9865266069718226 + x*(0.049098182494357004 + x*(-0.23116896078970445 + x*(0.0367916827992043))))
qui est un polynôme de degré 4 dont l'erreur max par rapport à sin(x) sur l'intervalle [0,pi] est de 5.9e-4 par exemple. Bien évidemment plus l'intervalle est petit, meilleure est la précision. Pour sinus, à partir des symétrie, l'intervalle [0,pi/4] est pas mal.

Il y a plus d'infos dans la wikipédia anglaise: https://en.wikipedia.org/wiki/Approximation_theory

Sinon pour info j'ai trouvé le code d'une ROM basic 6809 sur github. Il utilise le développement de TAYLOR sur un polynôme de degré 11 pour approximer sinus. On peut remarquer que le code utilise le même FPA0 que le code de la ROM basic du MO5. Coïncidence ?

Code : Tout sélectionner

* SIN                          
* THE SIN FUNCTION REQUIRES AN ARGUMENT IN RADIANS AND WILL REPEAT ITSELF EVERY                      
* 2*PI RADIANS. THE ARGUMENT IS DIVIDED BY 2*PI AND ONLY THE FRACTIONAL PART IS                      
* RETAINED. SINCE THE ARGUMENT WAS DIVIDED BY 2*PI, THE COEFFICIENTS MUST BE                      
* MULTIPLIED BY THE APPROPRIATE POWER OF 2*PI.                      
                               
* SIN IS EVALUATED USING THE TRIGONOMETRIC IDENTITIES BELOW:                      
* SIN(X)=SIN(PI-X) & -SIN(PI/2-X)=SIN((3*PI)/2+X)                      
SIN       JSR  LBC5F          COPY FPA0 TO FPA1 
          LDX  #LBFBD         POINT (X) TO 2*PI 
          LDB  FP1SGN         *GET MANTISSA SIGN OF FPA1 
          JSR  LBB89          *AND DIVIDE FPA0 BY 2*PI 
          JSR  LBC5F          COPY FPA0 TO FPA1 
          BSR  LBF38          CONVERT FPA0 TO AN INTEGER 
          CLR  RESSGN         SET RESULT SIGN = POSITIVE 
          LDA  FP1EXP         *GET EXPONENT OF FPA1 
          LDB  FP0EXP         *GET EXPONENT OF FPA0 
          JSR  LB9BC          *SUBTRACT FPA0 FROM FPA1 
* NOW FPA0 CONTAINS ONLY THE FRACTIONAL PART OF ARGUMENT/2*PI                      
          LDX  #LBFC2         POINT X TO FP (.25) 
          JSR  LB9B9          SUBTRACT FPA0 FROM .25 (PI/2) 
          LDA  FP0SGN         GET MANTISSA SIGN OF FPA0 
          PSHS A              SAVE IT ON STACK 
          BPL  LBFA6          BRANCH IF MANTISSA POSITIVE 
          JSR  LB9B4          ADD .5 (PI) TO FPA0 
          LDA  FP0SGN         GET SIGN OF FPA0 
          BMI  LBFA9          BRANCH IF NEGATIVE 
          COM  RELFLG         COM IF +(3*PI)/2 >= ARGUMENT >+ PI/2 (QUADRANT FLAG) 
LBFA6     JSR  LBEE9          TOGGLE MANTISSA SIGN OF FPA0 
LBFA9     LDX  #LBFC2         POINT X TO FP (.25) 
          JSR  LB9C2          ADD .25 (PI/2) TO FPA0 
          PULS A              GET OLD MANTISSA SIGN 
          TSTA                * BRANCH IF OLD 
          BPL  LBFB7          * SIGN WAS POSITIVE 
          JSR  LBEE9          TOGGLE MANTISSA SIGN 
LBFB7     LDX  #LBFC7         POINT X TO TABLE OF COEFFICIENTS 
          JMP  LBEF0          GO CALCULATE POLYNOMIAL VALUE 
                               
LBFBD     FCB  $83,$49,$0F,$DA,$A2 6.28318531 (2*PI) 
LBFC2     FCB  $7F,$00,$00,$00,$00 .25 
                               
                               
LBFC7     FCB  6-1            SIX COEFFICIENTS 
LBFC8     FCB  $84,$E6,$1A,$2D,$1B * -((2*PI)**11)/11! 
LBFCD     FCB  $86,$28,$07,$FB,$F8 * ((2*PI)**9)/9! 
LBFD2     FCB  $87,$99,$68,$89,$01 * -((2*PI)**7)/7! 
LBFD7     FCB  $87,$23,$35,$DF,$E1 * ((2*PI)**5)/5! 
LBFDC     FCB  $86,$A5,$5D,$E7,$28 * -((2*PI)**3)/3! 
LBFE1     FCB  $83,$49,$0F,$DA,$A2 * 
Dernière modification par __sam__ le 07 juin 2022 00:49, modifié 1 fois.
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
__sam__
Messages : 7909
Inscription : 18 sept. 2010 12:08
Localisation : Brest et parfois les Flandres

Re: Question BASIC MO5

Message par __sam__ »

En fouillant sur github, je suis tombé sur les repos de Samuel Hocevar (oui je sais, un autre Samuel), qui est pas mal connu (il a fait, entre autres, la libCaCa, et des outils de conversion d'images pour Oric aussi). Or il se trouve qu'il a aussi utilisé l'algo de Remez pour faire des approximations numériques (c'est dingue, non?). Contrairement à moi il a fait un beau tuto qui explique comment obtenir les approximations. Ca vaut le coup de le lire: https://github.com/samhocevar/lolremez/wiki
Samuel.
A500 Vampire V2+ ^8^, A1200 (030@50mhz/fpu/64mb/cf 8go),
A500 GVP530(MMU/FPU) h.s., R-Pi, TO9, TO8D, TO8.Démos
Répondre