Lazi

Problème du remplacement par meilleur efficacité

Contexte

En sub-physique, pour savoir où on se trouve on peut raisonner sur l'efficacité des formules à explorer mieux que le fait "everything".

Question

Comment mesurer l'efficacité des fonctions relativement à "everything" ?

Étude

Essai 2

Soit une certaine fonction f calculée par everything. Il faut savoir pour un calcul élémentaire effectuée sur f combien de calculs élémentaires sont effectués sur everything. Comme on s'intéresse à des ratios énormes (de l'ordre de au moins 1080) entre les choses produites par les calculs, cela vient la pluspart du temps du fait de différences importantes entre les fonctions décrivant les évolutions des quantités au cours du temps. Donc on peut négliger les rations faibles.

Essai 1

Si n est le numéro du cycle, le pourcentage de calcul réservé à un sous-calcul est en 1/n. Si on regarde ça en terme de profondeur de formule, si on passe des formules de profondeur p à celles de profondeurs p+1, alors s'il y avait n formules à la profondeur p, il y a n2 formules à la profondeur p+1, et donc le temps réservé aux sous-calcul passe de 1/n à 1/n2. Est-ce que ça empêche même les calculs d'exploration exponentiellement meilleurs de supplanter "everything" ?

On a distribute x y z = ($F a → x a \ y a) z, donc on peut remplacer tout distribute.

Le calcul optimisé va plus vite proportionnellement au nombre de distribute et donc statistiquement à la taille de la formule. Comme le gain est exponentiel en fonction de la taille de la formule, la perte dû au cycle avançant est compensée par l'augmentation du gain dû aux grandeurs de la formule calculée.

Il y a deux manières de faire l'exploration :

  1. en reprenant l'algorithme d'everything puis en convertissant les distributes
  2. en élminant le mot clé "distribute" et en utilisant "recurse et "$F →"

Comme distribute se traduit toujours en fonction, il n'y a pas de réduction du champs d'exploration.

Pour comparer l'efficacité il faut connaître la proportion où il y a un gain du fait que l'on a des fonctions.
Il faudrait aussi prendre en compte le fait que certaines fonctions ont des calculs qui s'arrêtent et d'autres non, ce qui change tout de point de vue de la mesure de l'efficacité.

Réponse

Il faut savoir pour un calcul élémentaire effectuée sur f combien de calculs élémentaires sont effectués sur everything. Voir essai 2.