Dérivation arithmétique (partie 2)

Dans cet article, il est question d’approximer des réels par des rationnels et de calculer les dérivées arithmétiques. On étudiera le comportement de la suite des dérivées arithmétiques et on appliquera les différentes méthodes d’approximations sur des réels bien choisis.

DerivArithP2

[DerivArth] Optimisation du programme DerivArthN

Lors de mes recherches sur la dérivation arithmétique, j’ai buté sur un problème de temps d’exécution pour des nombres très grands (à propos des développements décimales de réel de plus en plus grand).

Ce problème de temps long d’exécution était gênant car je ne pouvais pas tester un nombre de cas trop grand (jusqu’à 10^{-13} près).

Voici l’ancienne version du programme DerivArthN (AV = ancienne version pour comparaison avec la nouvelle version) :

derivarthNAV(n):={
local m,p,L,D,N,s;
si n == 0 ou n==1 alors
retourne(0)
sinon
m := n;
p := 2;
s := 0;
L := []; D := []; N:=[];
tantque p <= m faire
tantque irem(m,p) == 0 faire
m := m/p;
L := [op(L),p];
ftantque
p := nextprime(p)
ftantque
tantque nops(L) <> 0 faire
D := [op(D),L(1)]
t := count_eq(L(1),L)
N := [op(N),t]
pour k de 1 jusque t faire
L := tail(L)
fpour
ftantque
pour k de 1 jusque nops(D) faire
s := s + N(k)/D(k)
fpour
retourne(n*s)
fsi}:;

Le problème de ce programme, c’est qu’il fait ce que Xcas peut faire automatiquement et très rapidement. En effet, le programme cherche la décomposition en facteurs premiers du nombre à dériver arithmétiquement. Cette décomposition en facteurs premiers d’un nombre entier n peut s’obtenir grâce à la commande ifactors(n).

Ainsi, la nouvelle version du programme DerivArthN est celle-ci (NV= Nouvelle Version pour comparaison avec l’ancienne version).

derivarthNNV(n):={
local m,p,L,D,N,s;
L := ifactors(n)
si n == 0 ou n==1 alors
retourne(0)
sinon
s := 0;
D := []; N:=[];
tantque nops(L) <> 0 faire
D := [op(D),L(1)]
N := [op(N),L(2)]
pour k de 1 jusque 2 faire
L := tail(L)
fpour
ftantque
pour k de 1 jusque nops(D) faire
s := s + N(k)/D(k)
fpour
retourne(n*s)
fsi}:;

On compare les résultats des deux versions :

> derivarthNNV(13293920192384920)

23903941725768044

> derivarthNAV(13293920192384920)

23903941725768044

On compare maintenant le temps d’exécution des deux versions :

> time(derivarthNNV(13293920192384920))

[0.0026,0.0022524218]

> time(derivarthNAV(13293920192384920))

[11.52,11.074820345]

Y’a pas photo !