Discussion :

[EricL]

Bonjour,

Dans mes temps libres, je m'amuse à résoudre les problèmes mathématiques proposés par le site https://projecteuler.net/

Dans le problème 540 (https://projecteuler.net/problem=540), il faut trouver le nombre de triangles de Pythagore pour lesquels le plus grand côté est un nombre très grand (> 10^16) et pour lesquels le PGCD des 3 côtés est égal à 1. Je sais comment générer tous ces triangles, mais le problème est que mon programme plante par manque de mémoire quand je crée le tableau dynamique pour les storer. Je suis incapable de créer un tableau dynamique de plus de 65 000 000 d'enregistrements de Record of A, B, C (3 variables Int64).

J'ai donc essayé une solution lente de storer mes triangles dans un file of Record.

Or, après de longues minutes à rouler, j'obtiens un message Erreur E/S 131 (Tentative de déplacement du pointeur de fichier avant le début du fichier).

Je ne comprends pas l'origine du problème. Y a-t-il une taille maximale pour un tel fichier?

Notez que j'ai aussi essayé d'utiliser une procédure récursive. La solution n'est pas possible (du moins, pas sur mon ordinateur), car j'ai aussi un problème de manque de mémoire étant donné l'utilisation de la pile.

Si le fichier ne fonctionne pas, j'essayerai peut-être un multi thread. J'ai déjà fait ça une fois, je devrais être capable de recommencer.

Merci à l'avance de votre input!

Éric

[ShaiLeTroll]

file of ... c'est un Integer qui gère la position donc limité à 2Go, suffit de regarder le prototype du Seek pour le voir

tu peux passer en TFileStream, c'est à toi de gérer comment est lu et écrit les record, c'est très facile, toujours Seek, Read, Write

nombre très grand (> 10^16) et pour lesquels le PGCD des 3 côtés est égal à 1

Tu vas devoir passez à un BigInt si tu veux en trouver plus
Dire que j'étais très bon en terminal sur l'arithmétique des nombres entiers, mais pour le PGCD, euh, avec de si grand nombre, il te faut presque à chaque fois deux nombres premiers sur trois non ?
la récursivité, ça coute vite avec une pauvre pile de 1Mo
Tient "65 000 000 d'enregistrements de Record of A, B, C (3 variables Int64)." la théorie des 2Go c'est rare, je crois que je montais au mieux à 1700Mo (ou 1900je sais plus) ça dépend du MM utilisé (qui lui même consomme de la mémoire, en plus de windows)
Avec un PC 64Bits, la différence en théorie c'est que tu peux avoir plusieurs tableaux de 2Go là où tu pouvais en avoir qu'un seul en 32Bits, je me suis amusé à monter à 8Go avec des GetMem, ça fonctionne.

Tu trouves autant de triangle avec ces conditions pour avoir besoin de tant de mémoire, moi qui aurait pensé cela rare
Pense à bufferiser, genre un array fixe de 1000 record ABC, tu l'écris cycliquement, sauf à la fin (lorsque Int64 aura explosé) où tu écris juste le bon nombre, ça donnera une accélération au programme
Même, tu peux parallèliser le calcul et l'écriture dans un thread pour gagner encore ... par contre en multi-thread, plus tu es en a plus ça coute en mémoire, alors aucune chance que cela résolve ton problème

[EricL]

Merci Monsieur Le Troll pour la clarté de la réponse et surtout, d'avoir pris le temps!

Je vais regarder le FileStream.

Pour votre information, pas besoin de calculer le PGCD, on n'a qu'à appliquer la méthode expliquée ici : https://en.m.wikipedia.org/wiki/Tree...gorean_triples : on part du primitif 3 4 5 et on génère tous les autres.

Éric

[Paul TOTH]

tu peux aussi stocker chaque noeud dans un fichier différent pour limiter le nombre d'informations

le fichier 3.4.5 contient (5.12.13), (15.8.17),(7.24.25)
le fichier 5.12.13 contient...

reste à voir combien de fichiers cela génère

[EricL]

Encore merci pour vos suggestions.

Il faudra que je trouve une autre façon de résoudre. J'ai trouvé une approximation sur le net ... Pour le problème en question, il doit avoir environ 5 x 10^14 triangles primitifs.

Ça m'aura au moins permis d'expérimenter les TFileStream.

À monsieur Le Troll : 3 nombres composés peuvent être premiers entre eux (PGCD =1 ). Par exemple 6, 35 et 143 sont premiers entre eux et 6 = 2x3, 35 = 5x7 et 143 = 11x13.