AeriesGuard Le Refuge des Créateurs Minecraftiens !

Le même code traduit directement en C ( segfault)

Le même code traduit directement en C.

// gcc -Os -o kheopful kheopful.c
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

uint32_t *a,*b,*c;
uint32_t n,p,s,t;
uint32_t x;

void pyramid(const uint32_t q,const uint32_t l,const uint32_t m)
{
  uint32_t r,d,i,j,u,v;
  if (q <= p) {
    r = l+1;
    while (r <= n) {
      d = a[r]; i = l; j = l-q+1;
      while (b[d] > l && i < m) {
        i++; j++; d = abs (d - a[j]);
      };
      if (i == m) {
        d = a[r]; i = l; j = l-q+1;
        while (b[d] > i && i < m) {
          i++;
          v = a[i]; u = b[d]; c[i] = v;
          a[i] = d; a[u] = v;
          b[d] = i; b[v] = u;
          j++; d = abs (d - a[j]);
        };
        if (i == m) pyramid(q+1,m,m+q+1);
        while (i > l) {
          v = a[i]; d = c[i]; u = b[d];
          a[i] = d; a[u] = v;
          b[d] = i; b[v] = u;
          i--;
        };
      };
      r++;
    }
  } else {
    printf("\r");   
    for (i = 1; i <= p; i++) printf("%u ",a[(i*i-i+2)/2]);
    printf("\n");   
    if (s > 0) printf("\r%u",t);
  }
}

uint32_t* alloc(uint32_t max)
{
  uint32_t* result;
  uint32_t i;
  result = calloc(max+1,sizeof(uint32_t));
  for (i = 0; i <= max; i++) result[i] = i;
  return result;
}

int main(void)
{
  printf("Copyright© 2005 Damien Guichard\n");
  printf("How many levels? "); scanf("%u",&p);
  if (p < 1) exit(1);
  printf("How many holes ? "); scanf("%u",&x);
  n = p*(p+1)/2+x;
  printf("What seed value? "); scanf("%u",&s);
  if (s == 0 || s > n) exit(1);
  a = alloc(n);
  b = alloc(n);
  c = alloc(n);
  for (t = s; t <= n; t++) {
    printf("\r%u",t);   
    a[1] = t; b[t] = 1;
    pyramid(1,0,1);
  }; 
  printf("\r    \r"); 
  return 0;
}

Oh oh un programme de SpiceGuid que je serais capable de relire.

Pour ma part je possède Delphi XE2 soit une version extrêmement supérieure à Delphi 5, tu pourrais éventuellement profiter des améliorations du compilateur pour peut-être gagner en performance. Néanmoins si tu as déjà écrit une bonne partie du code en assembleur, je doute que ce soit le cas.

Bon alors c'est plus facile à dire qu'à faire

Le benchmark est réalisé au cycle d'horloge cpu près grâce à Printtsc .

Après réflexion mon langage de choix est Delphi 5 .

Motivations :

Delphi 5 génère du code win32 et Windows est mieux équipé que Linux en matière de drivers pour la gestion de l'alimentation.

Possibilité d'intégrer du code x86 en ligne avec un débogage asm interactif.

Au début, idée géniale (gros espoir). Résultat : hausse du temps de calcul de 25% :'(

Puis autre idée plus modeste. Résultat : baisse du temps de calcul de 4‰. Pas grand chose mais mieux que rien du tout

 Bon j'ai rien d'autre à faire alors je vais vous expliquer mon idée modeste :

À priori, et ça ne vous étonnera pas beaucoup, le programme passe une grande partie de son temps à calculer des valeurs absolues. C'est la raison pour laquelle j'utilisais le type Integer , parce qu'il est signé, contrairement à Cardinal .

Mais où sont ces nombres négatifs ? Vous en voyez vous des nombres négatifs En vérité il n'y en a aucun. D'où mon idée folle : utiliser Cardinal au lieu de Integer .

Alors vous allez me dire mais comment calculer une valeur absolue sans les nombres négatifs

Hé bien en fait ça ne pose aucun problème. Faites le test.

var c,ca,cb : Cardinal;
ca := 7; cb := 3;
c := Abs (cb - ca);    // oui ça fonctionne, même ici où ca > cb

Non seulement ça fonctionne mais c'est plus rapide car il n'y a jamais à faire un saut qui vide le pipeline du cpu

Si vous ne comprenez rien ni comment ni pourquoi ça n'est pas grave, dites vous que c'est une astuce de gosu .

Tout ça c'était pour gagner 4‰ La vache, je sens que ça va pas être facile

Je vais tenter d'améliorer mon programme et probablement tirer parti du multi-cœur pour battre mon record

Par contre je ne dévoilerai pas le résultat, seulement le nombre d'étages atteint et le plus grand entier de la ou des pyramide(s).

La motivation pour ce petit secret c'est que j'ai besoin de booster mon CV.

@xila Oui j'ai transféré le contenu de mon (ancien) blog (sur pagesperso-orange.fr) sur AG.

De cette façon je n'ai plus à en assurer la maintenance (merci Ertaï qui travaille pour nous tous).

@Azrock C'est bien moi l'auteur du programme Kheopful donc je suis capable de t'expliquer comment il fonctionne. Il n'y a pas de formule magique. Il essaye tous les arrangements A(n,m) sur la ligne de base de la pyramide puis il remplit le reste en vérifiant qu'aucun entier n'est utilisé plus d'une fois. Plus 1 ou 2 super-astuces trop compliquées à expliquer.

Les trois dernières pyramides à 11 étages ont quand même demandé 3 mois de calcul 24/24h sur un portable PentiumIII sous-cadencé à 500Mhz (la fréquence constructeur étant de 750Mhz mais pour le 24/24h j'ai préféré prendre mon temps plutôt que prendre un risque de surchauffe).

Azrock a écrit :

J'ai étendu la définition, sinon il serait impossible de trouver des triangles absolus avec n > 5.

Spiceguid je ne sais pas si tu as écrit l'article sur tuttisoft.pagesperso-orange.fr, mais je pense qu'il valait le coup d'être cité

Et tu as oublié un détail plutôt important, c'est que le triangle absolu, d'après ce que j'ai compris, doit comporter des entiers compris entre 1 et (n²+n)/2, où n représente le nombre d'étage

J'aimerai savoir s'il y a un moyen de calculer d'avance pour pas retomber plusieurs fois sur le même nombre, enfin de savoir par quels nombres commencer la pyramide? J'imagine que le logiciel ne fait pas qu'essayer jusqu'a ce que ça marche et qu'il y a une formule ou autre pour les faire, et elle aurait surement pas mal sa place dans l'article.