Bonjour,

--> dpi : oui, j'ai 12345678 en quelques secondes sur mon PC
Mais c'est par technique pure de programmation. Rapidité et réduction drastique de besoin en mémoire en exploitant une arborescence binaire symétrique. Programme en VisualBasic.net
Bonne recherche de votre côté.

>vham
On peut se tutoyer...
Pourrais-tu simplement me donner le nombre de digits ?
Merci

Bonjour,

J'espère ne pas m'attirer les foudres de Littlefox

 Cliquez pour afficher

C:\temp\Calculs2018.rtf 13/09/2018 11:37:37

nbdigits = 24
12345678 x ... = ...
Fin de programme 13/09/2018 11:37:40

Haha pas de soucis
Je ne comprends toujours pas pourquoi il insiste sur le nombre de digits au lieu de tester 24,25,... Il était déjà dans les 24 ^^.

Bravo pour ton 1234567891, celui-là me fait des memory error. Et à y regarder, mon algorithme n'est pas plus efficace que de parcourir toutes les représentations binaires puisque 2^30 < 1234567891. (Et c'est un nombre premier ce qui ne va pas aider dpi )

Ce que j'ai donc fait, en 13min14s pour confirmer ton résultat. Et j'ai le même .

Mon erreur est d'avoir cherché entre 31 et 32 digits avec un tableur qui se plante à 16,mais maintenant que  je sais 24 ce soir j l'aurai avec mon bidule congrual.....

J'ai nettement amélioré mes temps pour n grand avec une technique toute simple.
J'ai un programme en au lieu de ou précédemment (y étant le nombre de digit de m).
Il demande juste d'avoir une estimation de y.

L'idée est de couper m en deux partie : . Je calcule pour tout les les restes modulo n. Ensuite j'incrémente jusqu'à ce que soit dans les restes calculés précédemment. Une fois trouvé, je combine et pour avoir le résultat.

De cette façon je calcule m(1234567891) en 0.044s en python (même pas pypy)
m(12345678) ne me prend que 0.0037s

Ensuite,
m(12345678912345) x 891818925405682345826024403638 = 11010110101011111111100001110101011101111110 (44 digits, 6.7s)
m(123456789123456) x 899181899101479219377945934609375 = 111010110101000010110100001010001100100010000000 (48 digits, 29s)

Bonjour,
Malgré mes espoirs d'hier ,j'ai trop de "trous" entre les 16 digits et les  8 qu'il me manque;
il faudrait tester 520 restes cumulés à mes 32 768  trouvés.
Pour valider ma méthode je vérifierai avec le résultat de  vham

Bonjour. Par manque de temps je n'ai pas cherché ce problème. Une confirmation : pour gagner du temps d'exécution, avant d'être informaticien il faut être un peu mathématicien. Une question : comment faites-vous pour avoir un temps de calcul si précis ? La commande que j'utilise en Basic ne va pas en dessous de la seconde je crois.

J'utilise la commande process_time() de python qui est précise à la milliseconde. Quand mon programme va suffisamment vite je le fait tourner plusieurs fois dans une boucle de façon à avoir un temps de calcul dépassant la seconde, ensuite je fais une moyenne en divisant par le nombre d'itérations.

En Virtual Basic.Net je ferais un truc comme ceci :

Dim start as Datetime
start = Datetime.now
' Appel de la fonction à mesurer
Console.WriteLine((Datetime.now - start).TotalMilliseconds)

merci

J'attends donc 12345678

Bonjour,

en VB.net J'utilise le jour suivi de l'heure (à la seconde) en début et fin de programme
console.WriteLine(Format(Now, "dd/MM/yyyy") & " " & TimeString)

--> Je ne vois pas comment vous pourriez trouver sans une bonne programmation...
100010110000001110001010 = 12345678 * 8100819574267295

Merci vham

Je n'étais pas loin ,mais même en jouant sur les décimales et les congruences ,je
n'arrivais pas au bout.

Bonsoir,

---> LittleFox : Pourriez-vous détailler vos commentaires du 13-09-18 à 17:45 ?
comment vous combinez m_h et m_l en prenant m(1234567891) comme exemple serait apprécié.

@vham

Imaginons que m(1234567891) = 110111110100001000100001001111 ait 30 digits
L'idée est de décomposer dans ce cas ci, .

Pour les trouver je génère tous les et je stocke tous leurs restes modulo n. Il y en a ce qui est tout à fait raisonnable. Si l'un deux à un reste égal à 0. Alors on a trouvé un multiple et on s'arrête (m avait en fait moins de 15 digits). Sinon alors tous les restes sont différents (en effet, si alors et est un multiple plus petit que qui s'écrit avec des '0' et '1').

Ensuite je parcours les dans l'ordre croissant: 1,10,11,100,101,110,111,1000,1001,...
Si alors j'ai trouvé mon multiple (on pré-calcule pour être plus efficace). Sinon si est équivalent à un stocké alors j'ai trouvé mon multiple qui a la forme . En effet, si alors .
Sinon je passe au suivant.

Cette méthode est efficace quand on estime correctement le nombre de digits. Si l'estimation est trop petite, on perd du temps avec les , si elle est trop grande on perd du temps avec les . En effet, si est le nombre de digits de et le nombre de digits estimés alors mon algorithme est en .

Pour les résultats que j'ai obtenu, j'ai tâtonné un petit peu .

bonsoir,

Merci LittleFox, j'avais un peu cherché en essayant de décomposer N, et j'en étais arrivé à la conclusion que c'était bien sur m(n) (en digits 0 et 1) que vous agissiez :
Devoir estimer "a priori" le nombre de digits me semblait inconcevable en raison de la fluctuation importante du nombre de digits pour des n successifs.
Mais quand ça marche, alors Bravo.

Une autre façon de le voir c'est de se dire qu'un ordinateur fait un million de test assez rapidement. De sorte que si on est en dessous de la seconde. Donc en mettant 40 digits comme estimation, on est trop lent pour beaucoup de n mais si m est < 40 digits on aura la réponse en moins d'une seconde.

Bonjour à vous deux,

Je  n'ai pas assez patienté *,mais je l'avais avec Excel:
La seule donnée qui m'était nécessaire c'était le nombre de digits de m.

Mon bidule:

*aller jusqu'au bout des "vraies décimales" soit  16 digits
des  m  finissant par  0 soit  32768 d possibles avec décimales .
*bâtir un tableau des  24 digits  précédés de 8 chiffres significatifs soit 256 lignes
en cumulant les décimales nécessaires.(ce qui impose 256 lignes de 16 à24 digits).
*les tester en les mettant en constante additionnée à mes 16 digits.
*Tester 1.

RESULTAT
En arrivant à m1 100 010 110 000 000 000 000 000  ma constante est 0.0899108173 que je  teste * et qui me donne 0.99999999 un petit coup de calculatrice me donne :
d1 =8100 819 574 267 205.0899108173372687 et là un magnifique  1 avec m2= 1 110 001 010 d2=89.9100891862273 que je rajoute .
SOIT   d=8 100 819 574 267  295
et en additionnant les m (calculatrice) on obtient  100 010 110 000 001 110 001 010

*cette valeur était en  21 éme  position des 256  (24 digits) j'en ai testé une quinzaine
après avoir testé les 256 inférieures

Conclusion,
Comme je l'ai dit plus haut,dans une prochaine vie je me mets à la programmation

Et bien finalement tu as presque le même algorithme que moi mais en Excel
Je maintiens que tu aurais évité les erreurs d'arrondis en utilisant des modulo plutôt que les parties fractionnaires.

Sinon, vu ce que tu fais déjà, pourquoi attendre la prochaine vie? Il n'y a qu'un pas à faire. Pour ce premier pas, je te conseille cette référence (en français) :

merci Littlefox

Suite à tes conseils,je suis passé aux m puis à la congruence ,le tableau des parties décimales m'a permis  de tester les  8 premiers chiffres puisque j'étais sûr d'avoir
les 16 derniers.
Car auparavant  je ne savais pas l'ordre de grandeur de m , je redoutais ton 32 bits  du 5/9
à 11h59