[DerivArth] Optimisation du programme DerivArthN

Publié le Mis à jour le

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 !

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s