I.G.Y, petit, petit, petit.

[BIOGRAPHIE]

https://www.texmacs.org/joris/gdrim/gdrim.html#grafsteen
.
T’as quelque chose à dire sur toutes ces histoires? Je veux dire que t’es capable de m’expliquer pourquoi il n’est jamais question de chercher à en passer par une différence entre deux carrés ou bien ça te dépasse?

[I.G.Y]

En parcourant rapidement l’article, je constate d’abord qu’il est bien question « d’en passer par une différence de deux carrés » : c’est ce qu’il fait dans la partie sur les cyclonômes (la factorisation par la différence de deux carrés x^2-1 n’étant qu’un cas particulier de x^L-1, plus général. C’est aussi ce qui se passe dans la partie sur la FFT où il en passe pas x^(2L)-1 qui est aussi la différence de deux carrés).

Et d’autre part en essayant d’interpréter ta question : si ce qui t’intéresse est plutôt le cas particulier v^2-w^2 = (v-w)*(v+w), se ramener au sujet de l’article signifie supposer que v-w et v+w sont des nombres de taille n (avec bien sûr v>w) et espérer réduire l’ordre de complexité de la multiplication des deux (donc faire mieux que le O(n^2) de l’algo « force brute ») avec l’opération v^2-w^2. Or la complexité de v^2-w^2 est dominée par la longueur de v qui est de taille supérieure ou égale à celle de w, et sera donc O(V^2) si V est la longueur de v. On montre rapidement par l’absurde en posant v de taille n+k avec k un entier relatif, que sachant v+w et v-w par hypothèse tous deux de taille n on trouve k=0, donc v ne peut être que de taille n. Ainsi l’opération v^2-w^2 est-elle de complexité O(V^2)=O(n^2), soit la même que l’algo « force brute » que l’on souhaitait améliorer au départ.
.
Enfin, avoir quelque chose à dire sur un article de recherche d’un type qui semble-t-il est une pointure mondiale en théorie des nombres, c’est beaucoup demander. En revanche oui je comprends a minima de quoi il est question (même si je n’ai pas travaillé sur ce genre de choses depuis un peu moins de 15 ans, d’autant que j’ai déjà dit faire des mathématiques appliquées et de la physique et non être mathématicien de métier, encore moins en théorie des nombres/algèbre). Et si jamais le but est de me piéger, tu y arriveras facilement, il n’y a là aucun suspense puisque tu arriveras même à piéger un médaille Fields en lui envoyant des travaux d’une autre médaille Fields.
.
Sur ce je retourne bouffer des graines

[BIOGRAPHIE]

I.G.Y: « Et si jamais le but est de me piéger, tu y arriveras facilement, il n’y a là aucun suspense puisque tu arriveras même à piéger un médaille Fields en lui envoyant des travaux d’une autre médaille Fields. »
.
Si j’avais les moyens de te piéger sur ce terrain, je ne me ferais pas chier à ouvrir un thread pour capter ton attention dans l’espoir d’y voir un peu plus clair dans cette histoire. Et comme je ne comprends pas vraiment ce que tu me racontes, je vais prendre la peine de te brider un peu en précisant que ce qui m’intéresse c’est cet algorithme:
.

.
Algorithme qui ne fait jamais intervenir de différence entre deux carrés. Et comme je suis un gros con, parce que je n’ai pas de problème avec ça, je propose qu’on prenne la peine de discuter de cette histoire de façon très concrète, à savoir en partant de la multiplication proposée pour illustrer l’algorithme qui est 1234 x 5678
.
Et donc pour opérer cette multiplication sous forme d’une différence entre 2 carrés on fait:
.
((1234 + 5678)/2) = 3456
((5678 – 1234)/2) = 2222
.
Puis là dessus on fait 3456² – 2222² et je veux bien entendre qu’au premier abord on a reculé puisqu’on se retrouve à devoir faire 2 multiplications de nombres à 2 chiffres pour calculer nos carrés avant de pouvoir faire la différence entre les deux carrés mais j’ai quand même tendance à croire que dans cette histoire il serait question de reculer pour mieux sauter puisque diviser ou multiplier par une puissance de 2 ça ne coûte rien et que rajouter un 1 à la fin d’un décalage de bits ça reste assez basique comme opération pour être tout aussi négligeable.
.
3456 / 128 = 27
2222 / 2 = 1111
.
Parce que moi j’ai tendance à croire que c’est plus facile de travailler sur des nombres impairs. Comprendre que 27**2 * 128**2 = 3456**2 donc au lieu de se faire chier à calculer le carré de 3456 on fait celui de 27 puis on décale les bits à gauche pour se faciliter la vie. Et pour calculer le carré de 27 c’est assez simple:
.
27 = 14² – 13²
14/2 = 7
(7² * 2 – 7) * 8 + 1 = 729
.
On pourrait aller plus loin mais pour l’illustrer le mieux c’est de partir de 1111:
.
1111 = 556² – 555²
556 / 2 = 278
.
278/2 = 139
.
139 = 70² – 69²
70 / 2 = 35
.
35 = 18² – 17²
18/2 = 9
.
Et comme 9² on peut le calculer de tête, je propose qu’on reconstruise le carré.
.
(9**2 * 2 – 9) * 8 + 1 = 35²
(35**2 * 2 – 35) * 8 + 1 = 139²
139**2 * 4 = 278²
(278**2 * 2 – 278) * 8 + 1 = 1111²
.
Et donc là on a fait aucune multiplication à proprement parler, on s’est contenté de faire quelques additions et de décaler des bits vers la gauche donc intuitivement j’ai le sentiment que c’est pas complètement con d’en passer par là. Je veux bien croire que dans le détail, avec vos histoires de complexité algorithmique, on puisse en arriver à la conclusion que c’est pas idéal au regard de ce qu’on sait faire, ou même de l’algorithme qui débouchera sur la version plus complexe évoquée plus tôt, mais ça c’est une autre histoire. Je veux dire que de mon point de vue on peut encore optimiser la bêtise de façon élégante même si je n’ai pas encore eu le temps de me prendre assez la tête sur le sujet pour que ça vaille la peine d’en parler.
.
Bref, c’est pas la peine de psychoter ou d’être sur la défensive, je veux bien te traiter de cons quand tu prétends m’expliquer des choses qui te dépassent mais là c’est moi que ça dépasse donc tu peux voir ce thread comme ton safespace.

[I.G.Y]

« je veux bien te traiter de con » : oh je ne voudrais surtout pas te forcer.

« tu peux voir ce thread comme ton safespace » : partant sur ces bases de dérision je veux bien répondre (bases dont tu pourrais faire un très bon usage avec d’autres membres du forum plutôt que de les insulter, je t’y invite chaleureusement). Quant à ma psychose, je nage au contraire dans un océan de calme.
.
Il se trouve que j’avais déjà des réponses avant de voir la vidéo mais j’en ai encore plus après, elle est très bien faite. Le truc est justement que « [nos] histoires de complexité algorithmique » (quoique ça ne soit pas tant les miennes, je ne travaille pas là dessus) sont la clé pour ton interrogation. En gros : il est tout à fait possible que l’algorithme que tu mets en place ici puisse être plus performant pour des nombres de très petite taille que par exemple l’algo de Karatsuba (je n’en sais rien, il faudrait le poser théoriquement puis calculer), mais très très vite ça ne sera plus le cas (peut-être même que dès les nombres à 3-4 chiffres ça ne l’est plus). Une raison supplémentaire est que le cas précis que tu cites, 1234 x 5678, est en plus un peu particulier puisque comme tu l’as remarqué, par chance 3456 est divisible directement par une (un peu grande) puissance de 2. D’autre part ton algorithme met implicitement en place des techniques de factorisation, qui faites de tête paraissent simple mais dont la complexité algorithmique même optimisée peut être très grande sur les grands nombres (et la factorisation, c’est le genre de problème que les matheux les plus aguerris regardent de très très près depuis longtemps, tout aussi bien des étatistes que des anti-étatistes d’ailleurs, puisque c’est crucial en cryptographie/sécurité). On pourrait aussi parler des cas où tu tomberais sur des facteurs premiers assez grands, ou pire encore, sur des nombres premiers (tu ne pourrais donc diviser par rien du tout). D’autre part les opérations de décalage de bit sont effectivement très utiles (et massivement utilisées, à ma connaissance elles sont généralement implémentées par défaut dans les compilateurs) mais bien souvent ne réduisent pas la classe de complexité, c’est-à-dire le nombre d’opérations quand les nombres deviennent grands (je donnerai un exemple à la fin).
.
Bref, une illustration très concrète de pourquoi des algos non-optimaux voire même les plus naïfs possibles peuvent, pour des petits nombres, être plus rapides que les algos plus sophistiqués voire mathématiquement prodigieux t’es donnée dans ta vidéo. A 15min44, tu vois qu’il y a des points sur la gauche du graphe (donc nombres de petite taille) pour lesquels pour lesquels la courbe violette est au-dessus de la jaune, c’est-à-dire que l’algorithme le plus stupide (mais implémenté avec bit-shifting, il le dit) est plus rapide que l’algo beaucoup plus malin de Karatsuba et qui fait référence (implémenté aussi avec bit-shifting dès que possible). C’est d’ailleurs pourquoi il montre après que les implémentations par défaut de la multiplication dans des langages de programmation peuvent utiliser des algos différents selon la taille des nombres à multiplier (pour les petits nombres, Karatsuba n’est pas utilisé dans python, c’est ce qu’il montre graphique à l’appui). Ce qu’il dit aussi à la fin sur la constante multiplicative qui rend l’algo de Hoeven (papier que tu as cité plus haut) possiblement inutile avant des tailles de nombre proprement délirantes suit les mêmes principes.
.
Pour être encore plus concret sur la complexité, imaginons que tu découvres un algo très malin qui, partant de deux nombres de longueur n à multiplier, arrive à réduire la même multiplication à deux nombres dont la taille est divisée par 10 (on pourrait se dire que c’est déjà balèze comme réduction). Faisons aussi l’hypothèse (fausse, mais c’est fait exprès pour insister) que toutes les techniques que tu as utilisées pour faire cette réduction (factorisation etc…) sont si parfaites qu’elle sont même meilleures que le décalage de bits : imaginons qu’elles coûtent zéro. A la fin des fins, tu as épuisé toutes tes opérations magiques et le nombre d’opération (je vais assimiler complexité et nombre d’opérations, donc j’omets la constante multiplicative/la notation O(x^y), ça ne change pas la discussion), le nombre d’opérations donc qu’il te reste est (n/10)*(n/10)=n^2/100. Réduction impressionnante d’un facteur 100. Imaginons maintenant qu’on prend le fameux algo malin qui fait n^1.55 opérations pour faire la même chose. Si tu traces sur un graphique n^2/100 et n^1.55 en fonction de n, tu verras que ton algo fera mieux que l’algo ultra-optimisé jusqu’à environ n=30000, au-delà il se fera démolir. Or 30000, ça paraît énorme mais ça ne l’est pas tant (surtout si l’on parle de tableaux de nombres). Tout ça vient du fait que, pour parler vite, la classe de complexité de n^2/100 est en fait… la même que n^2, qui est moins bonne que n^1.55. Tout ça parce que mathématiquement O(n^2/100)=O(n^2) : la constate multiplicative 1/100, ou même 1/100000 ne change rien quand les nombres sont grands, elle ne change rien « asymptotiquement ».
.
En définitive, il n’est pas entièrement impossible que pour un tout petit nombre du genre 3 chiffres, un algo comme celui que tu décris batte Karatsuba qui est fait pour les grands nombres (les factorisations me laissent très dubitatifs sur ce point, mais après tout je ne sais pas). Néanmoins c’est en effet certain (et d’ailleurs il le dit dans la vidéo) que python fait un usage massif des décalages de bit parmi autres astuces pour atteindre cette performance dans les nombres de petite taille. Aucun doute par ailleurs que le code source de la multiplication en python est disponible, il existe peut-être des gens qui en vulgarisent le fonctionnement, je ne sais pas, c’est très probable.

[BIOGRAPHIE]

« oh je ne voudrais surtout pas te forcer. »
.
C’est pourtant ce que tu fais hein puisqu’à l’arrivée à part m’indigner face à ta bêtise je ne vois vraiment ce que je peux faire.

[BIOGRAPHIE]

“Complexité totale : La complexité de votre méthode semble être dominée par les calculs des carrés et la division répétée. On peut donc dire qu’elle est approximativement de complexité O(log⁡ N) pour des entiers de taille n, ce qui est relativement efficace par rapport à la multiplication classique.”
.
Est ce qu’on peut faire confiance à ChatGPT? J’ai de gros doutes. Ceci dit même s’il a fallu que je m’énerve il a quand même fini par comprendre le principe de ma bêtise et je dirais bien que j’ai hâte de le voir contrôler le monde mais malheureusement je n’oublie pas que ChatGPT est comme Macron, prêt à dire tout et son contraire du moment que ça lui permet d’être aimé à la fin.

[I.G.Y]

« J’ai de gros doutes » : doutes tout à fait rationnels puisque si c’était O(log(n)) tu ferais mieux que le meilleur mathématicien mondial sur le sujet qui fait O(n*log(n)) (celui de l’article dont tu as mis le lien, et dont il est aussi question à la fin de la vidéo). Comme quoi, chatGPT, à prendre avec de grosses pincettes. La comparaison avec Macron est plutôt pertinente (à ceci près que malgré ses fautes régulièrement très grossières, en matière de maths je lui poserais plus des questions à lui qu’à Macron)

[BIOGRAPHIE]

I.G.Y: « D’autre part ton algorithme met implicitement en place des techniques de factorisation, qui faites de tête paraissent simple mais dont la complexité algorithmique même optimisée peut être très grande sur les grands nombres (et la factorisation, c’est le genre de problème que les matheux les plus aguerris regardent de très très près depuis longtemps, tout aussi bien des étatistes que des anti-étatistes d’ailleurs, puisque c’est crucial en cryptographie/sécurité). On pourrait aussi parler des cas où tu tomberais sur des facteurs premiers assez grands, ou pire encore, sur des nombres premiers (tu ne pourrais donc diviser par rien du tout). »
.
Depuis quand prétendre que 81 = 1 x 81 signifie avoir factorisé 81?

[I.G.Y]

Je n’avais pas tout à fait compris l’algorithme que tu utilisais pour décomposer 27 car tu ne l’as pas explicité (j’ai cru que c’était une méthode proche de celle que tu mettais en avant au départ, qui aurait plutôt d’ailleurs donné 27=6^2-3^2 et qui aurait requis la factorisation 3*9=27, donc ça m’a étonné et je suis passé à autre chose, je réponds sur mon temps de travail donc je ne peux pas tout faire). En effet je comprends mieux maintenant pourquoi tu t’es placé dans le cas particulier du nombre impair, puisque pour ce type de nombre on peut bel et bien faire la décomposition que tu dis.
.
Mon intuition est que dans ton algo ce qui va dépendre de la taille n du nombre (et donc influencer la complexité algorithmique finale) est par exemple la taille et la structure en binaire du nombre qui équivaut à ton 3456 (et que tu divises par 128 pour trouver 27). En l’occurrence ton algo sera plus rapide si le nombre binaire contient peu de 1 (idéalement un seul, une puissance de deux parfaite genre 256) et sera beaucoup plus lent en cas d’une structure merdique comme 338=101010010. Pour 63=111111 on peut toujours faire 64-1, mais il faut toujours garder en mémoire que tous ses tests, ces opérations supplémentaires, ont un coût). Et il ne faut pas oublier que la décomposition du nombre en binaire qui a lieu au départ avant même d’exécuter la suite de ton algo peut elle-même être avoir un coût (mais asymptotiquement il est en O(log(n)), donc ça ne sera pas ce qui va plomber ton algo asymptotiquement). Bref tout ça va influencer le nombre de carrés élémentaires que tu dois calculer dans ta dernière étape (qui démarre à 9^2). Cette étape elle même en comporte plusieurs sous-étapes de « remontée » que tu as écrites, en l’occurrence 4 dans ton cas particulier, et ce nombre est dépendant lui-même de la taille initiale des nombres que tu multiplies. Je note d’ailleurs que 4 est pile poil… la taille n des deux nombres que tu multiplies au départ). Donc je pressens que pour calculer la complexité théorique finale il faut avant tout s’intéresser au nombre de fois où tu devras arriver à cette étape du 9^2 dans le cas général, et ensuite aux nombres d’étapes nécessaires pour « remonter » par reconstruction à ce qui équivaut dans ton cas particulier à 1111.

Bref, quoiqu’il arrive on ne pourrait juger du nombre d’opération qu’implique ta manière de faire qu’en posant théoriquement l’algorithme générique pour une multiplication de deux nombres N et M quelconques, pas sur des cas particulier. Je n’ai pas la réponse exacte a priori sur ce qui plombe (nécessairement) la complexité finale de ton algo par rapport à un algo optimisé car on ne peut l’avoir qu’une fois l’algorithme écrit dans le cas général, sans cela donner une réponse est impossible. Sauf à poser la question à un informaticien ou un mathématicien habitué à ces questions, il aura peut-être une réponse immédiate car il saura déjà à l’avance pourquoi ton algorithme va exploser car il en connaît déjà la formulation générique (parce que je pense que la réponse est connue des algorithmiciens professionnels. Je peux te suggérer de poser la question sur le forum les-mathematiques.net où traînent des spécialistes d’un peu toutes les branches des maths, je suis sûr et certain qu’il y a une section « complexité »).
.
Mais encore une fois et pour répéter ce que j’ai dit plus haut, je n’ai à aucun moment affirmé que ton algorithme était moins rapide sur des petits nombres que par exemple le meilleur algorithme de la terre de Hoeven, algorithmes qui sont fondamentalement faits pour des grands nombres (l’article que tu as posté s’intéresse à la complexité, qui est par définition même de la discipline affaire de grands nombres, d’où le fait que je réponde en premier lieu sur ce terrain, un terrain que tu as installé par l’article même que tu as posté). On peut même répondre avec quasi-certitude pour le cas de Hoeven : même une fois posé ton algorithme dans le cas générique je suis prêt à parier 50 balles qu’il sera plus rapide le Hoeven puisque cet algo n’atteint a priori son régime de supériorité que pour des nombres extraordinairement grands, c’est rappelé dans ta vidéo à la fin. Il est même quasiment certain que pour des nombres de petite taille l’algorithme « écolier » naïf de base en complexité O(n^2) fasse mieux, puisque celui-ci fait même mieux que le Karatsuba optimisé (ce qui est prouvé en pratique dans ta vidéo, ce que j’avais souligné plus haut dans ma réponse).
.
Il y a un grand avantage de ce genre de questions très concrètes : si tu veux avoir la réponse sur la performance de ta méthode par rapport à disons Karatsuba pour des petits nombre de taille 4, tu peux la coder et mesurer (et quand je dis « la coder », je veux bien sûr dire « pour une multiplication de nombres quelconques ». Ceci dit tu peux aussi coder le cas particulier, pour le fun)

[BIOGRAPHIE]

« Mais encore une fois et pour répéter ce que j’ai dit plus haut, je n’ai à aucun moment affirmé que ton algorithme était moins rapide sur des petits nombres que par exemple le meilleur algorithme de la terre de Hoeven »
.
Parce que je t’ai reproché d’avoir soutenu une chose pareille du haut de ma prétention à croire que je ne fais même pas aussi bien que l’algorithme de Karatsuba? Non moi ce que je te reproche c’est juste d’être incapable de t’en tenir à ce que je raconte et de ne pas être foutu de t’arrêter deux minutes sur ma bêtise pour la comprendre. C’est tout. Ceci dit c’est déjà pas mal car c’est quand même drôlement la honte de me faire des grandes leçons du haut de ton impuissance à comprendre ce que tu lis.
.
« En l’occurrence ton algo sera plus rapide si le nombre binaire contient peu de 1 (idéalement un seul, une puissance de deux parfaite genre 256) »
.
11 = 3
3 = 2² – 1²
.
111 = 5
5 = 4² – 3²
.
1111 = 15
15 = 8² – 7²
.
11111 = 31
31 = 16² – 15²
.
A chaque fois je propose de prendre le nombre pair pour le diviser par 2 donc le cas idéal c’est celui on a des 1 partout puisqu’on aura toujours une puisse de 2 quand on décompose les nombre sous forme de différence entre deux carrés. Par conséquent ne vient pas me dire que tu comprends ce que je raconte, c’est rigoureusement faux.
.
« donc ça m’a étonné et je suis passé à autre chose, je réponds sur mon temps de travail donc je ne peux pas tout faire »
.
A quel moment le fait que tu sois au travail te donne le droit de me tartiner toutes ces conneries sans même prendre la peine de comprendre ce que je raconte? C’est tout pété comme excuse. Tu ne comprends pas, tu le dis, je pars du principe que je me suis mal expliqué et je recommence puis si t’as pas le temps de répondre parce que t’es au travail et qu’il faudrait que tu prennes cinq minutes pour te concentrer pleinement sur la bêtise alors tu te contentes de dire que t’as pas le temps et que tu repasseras plus tard
.
Ou pas. Parce que c’est pas la peine de perdre ton temps à répondre si t’es pas foutu de prendre un peu de recul pour mesurer le problème avec ton comportement et, au besoin, de perdre 5 minutes à faire l’effort de comprendre ce que je dis.

[I.G.Y]

« il faudrait que tu prennes cinq minutes » : ce doit être une plaisanterie.
.
Pour le reste, le temps considérable que j’y passe (que tu ne vois pas et dont tu n’as rien à faire, mais ça m’est égal) est lié à deux choses : en effet il faut démêler l’implicite de ton algorithme puisque tu pars d’un cas particulier ce qui rend beaucoup plus difficile de répondre directement puisque ta procédure générique n’est pas posée (donc on ne peut pas calculer la complexité telle quelle, ce qui est le sujet de la conversation que tu as démarrée), et deuxièmement je cherche donc au fil de l’eau et de ce que tu écris, sur un sujet dont j’ai déjà dit au départ que je ne le connaissais pas (je joue le jeu, c’est peu de le dire). De plus se mêlent ici des opérations en décimal et des considérations sur le décalage de bit en binaire : or puisqu’il s’agit de trouver la faille, il faut tout déplier, trouver le loup. Pour démêler il faudrait à chaque fois soit prendre en compte à chaque étape le coût de conversion décimal/binaire quand il y a lieu, soit réécrire tout ce que tu écris uniquement en binaire pour bien faire apparaître le coût des opérations.

L’enjeu du problème que tu poses et par delà ton mépris complètement surfait qui me prête je ne sais quelle supériorité ou impuissance ridicule (sans parler le fait de me prêter un désintérêt de ce que tu écris) est le suivant : tu démarres la discussion par un article qui traite de complexité asymptotique (+ une vidéo sur le même sujet) et tu te demandes pourquoi ils n’utilisent pas ta méthode qui te paraît mieux, il s’agit donc de trouver « où se trouve le souci de complexité » dans ton algo puisqu’il y en a nécessairement un. Le trouver est une question intéressante et pas triviale a priori. Donc ça au moins c’est clair.
.
La réflexion que j’ai tentée tout en cherchant m’a amenée à pointer dans mon post précédent que dans l’algorithme même que tu écris et ne serait-ce que sur ton cas particulier, il y a un nombre d’étape qui dépend très probablement de la taille n de ton nombre de départ (en l’occurrence qui dépend le la taille de 1111, qui lui-même dépend de la taille de ton nombre de départ), et selon toute probabilité la puissance de n sera non négligeable (car la complexité de ton algo final ne peut pas être simplement O(n), puisque ce serait meilleur que Hoeven). A chaque étape où tu reconstruis tes carrés par décalages de bits et additions (« je propose qu’on reconstruise le carré ») se cachent des opérations : si tu as K étapes avec un décalage de bits seulement tu fais K fois un décalage de bit (en supposant qu’il se fait en temps constant O(1), cas idéal), tu auras donc O(K). Pour un peu que d’autres opérations se mêlent à ça, ta puissance de K va augmenter. Et puisque K dépend de la taille de ton nombre de départ, on a un indice sur « le loup ». Ce que je dis là semble aussi valable dans la phase « descendante » de ton algorithme qui est juste avant, qui à chaque fois qu’il tombe sur un nombre impair le décompose en différences de carré puis poursuit. Ceci répond donc bien directement à ta remarque de départ « on s’est contenté de faire quelques additions et de décaler des bits vers la gauche » (sous-entendu : « du coup ça semble a première vue plus rapide »). Exemple : si ton algo se retrouve à faire (n^2)/10 décalages de bits vers la gauche et aucune multiplication, certes tu n’auras fait que décaler et additionner mais ta complexité sera la même que l’algorithme de multiplication « naïf » qui est en n^2, c’est ça le point essentiel. Et qui répondait très directement à ton interrogation.
.
Pour le cas spécifique du nombre avec que des 1 en binaire j’ai dit explicitement que ça n’était nécessairement le plus défavorable. Et à vrai dire même le cas avec un seul 1 n’est peut-être pas si favorable, puisque ton algo continue de diviser étape par étape par 2 jusqu’à tomber sur un impair, et ensuite il fait l’astuce de décomposition en différence de carrés puis recommence à diviser etc… (il me semble d’ailleurs, je l’avais écrit plus haut, que si tu tombes sur un nombre premier un peu grand au moment de ton (K+1)^2-K^2, ça devient un facteur limitant, l’algo se stoppe et se retrouve à calculer un carré élementaire irréductible potentiellement grand : exemple, si tu arrives à 133 = 67^2−66^2, 67 est premier, tu te retrouves donc à devoir remonter/reconstruire les carrés à partir de 67**2 si je suis bien ton algo (à moins que tu ne rajoutes une procédure spéciale de décomposition de 67, ce qui rajouterait encore des étapes et des coûts). Or la taille de ce nombre premier peut être arbitrairement grande, donc tu as le coût possiblement très important de ce calcul de carré, puis de toutes les étapes de reconstruction).

[BIOGRAPHIE]

133 = 67² – 66²
66 / 2 = 33
(33² * 2 + 33 ) * 8 + 1 = 133²
.
Autant dire qu’on s’en fout que 67 soit un nombre premier et qu’encore une fois tu démontres que tu n’as pas compris la logique de la démarche.
.
Bref, je propose qu’on s’arrête là puisqu’on tourne rond et que la question à la base c’était de savoir si t’avais connaissance d’une approche qui impliquerait d’en passer par une version de la multiplication sous forme de différence entre deux carrés et que la réponse est non.

[I.G.Y]

Et je profite d’une insomnie dont j’espère qu’elle ne révèle pas un début de grippe pour retirer la phrase « à vrai dire même le cas [binaire] avec un seul 1 n’est peut-être pas si favorable » (on ne tombe évidemment jamais sur un nombre impair en divisant par deux successivement une puissance de deux, sauf à la fin). Phrase fatiguée.

Quant au nombre binaire plein de 1, qui est impair, il est bien sûr potentiellement tout à fait défavorable à l’algorithme selon les cas (selon les nombres qui apparaissent dans sa décomposition en différence de carrés).

Aussi, une manière en fait assez simple de mesurer le nombre d’opérations à réaliser entre chaque étape de décomposition en différence de carrés est, concernant le nombre de départ, le nombre de zéros avant le premier 1 en partant de la droite qu’il contient (puisque division par deux=décalage de bit vers la droite). Pour 10101000000 il faut 6 décalages, donc 6 opérations, puis on décompose le nombre impair obtenu en différences de carrés (ce qui coûte plusieurs opérations), puis on recommence. Jusqu’à tomber au moment de la décomposition en différences de carrés sur un nombre de gauche qui est premier (ou d’ailleurs impair, le cas se produit par exemple avec la décomposition de 129), auquel cas il faut soit faire autre chose soit il n’y a rien à faire.

[I.G.Y]

« tu n’as pas compris la logique de la démarche » : jamais dans aucun de tes exemples tu n’as divisé par deux le nombre de droite par deux. Puisque tu ne donnes aucune procédure explicite générique, je ne peux que m’adapter à ce que tu écris.
.
Et concernant la réponse à la question de départ, cette question n’était pas « est-ce que connais une méthode qui passe par la différence de deux carrés », mais « pourquoi il n’est jamais question de chercher à en passer par une différence entre deux carrés » (je cite), c’est complètement différent. La réponse à la question 1 est bien sûr non.
.
Donc il me semble qu’on a assez bien déblayé l’intérêt de cette question

[I.G.Y]

(L’intérêt de la question 2)

[BIOGRAPHIE]

I.G.Y:
21 = 11² – 10²
.
(11²-1) / 4 = 30
30 = 2+4+6+8+10
.
11 = 5+6
5×6 = 30
.
10² / 4 = 25
25 = 1+3+5+7+9
.
10 = 5+5
5×5 = 25
.
21 = 4 x (-1+2-3+4-5+6-7+8-9+10) + 1
.
1+2+3+4+5+6+7+8+9+10 = 30+25 = 5²+5+5² = 2×5²+5 = 55
55 x 4 + 1 = 221 = 11² + 10²
55 x 8 + 1 = 441 = 21²
.
« La réponse à la question 1 est bien sûr non. »
.
Je ne suis pas sûr que les deux questions soient vraiment différentes, je veux dire que je ne vois pas comment tu peux répondre à la question que je pose si tu n’as pas connaissance de méthodes construites autour de cette différence entre deux carrés. Parce que des méthodes j’en vois plusieurs pour ma part.
.
3×7 = 21
13×17 = 221
23×27 = 621
33×37 = 1221
43×47 = 2021
53×57 = 3021
.
Ca se réécrit sous forme de différence entre deux carrés:
5² – 2²
15² – 2²
25² – 2²
35² – 2²
45² – 2²
55² – 2²
.
Et les carrés des nombres qui se terminent par 5 se construisent à l’aide de quelques additions et d’un copier/coller de 25.
.
0 = 0 + « 25 » = 25
0+2 = 2 + »25″ = 225
0+2+4 = 6 + « 25 » = 625
0+2+4+6 = 12 + « 25 » = 1225
0+2+4+6+8 = 20 + »25″ = 2025
0+2+4+6+8+10 = 30 + « 25 » = 3025
.
Là dessus t’enlèves 4 partout et t’es bon. Après comment on exploite cette bêtise de façon plus générale pour travailler directement la différence entre 2 carrés? J’en sais rien mais je suis sûr que ça se fait même si je ne vois pas de façon simple dans l’immédiat de t’en convaincre. D’autant plus qu’en l’état il est surtout question de jouer à factoriser des nombres puisque j’ai peut être tort mais quand je vois ça:
.
3 = 2² – 1²
7 = 4² – 3²
.
(2×4 + 1×3)² – (2×3 + 1×4)² = (8 + 3)² – (6 + 4)² = 11² – 10² = 1 x 21 = 21
(2×4 – 1×3)² – (2×3 – 1×4)² = (8 – 3)² – (6 – 4)² = 5² – 2² = 3 x 7 = 21
.
Je me dis qu’il existe forcément une méthode simple et élégante de factoriser les nombres.
.
Bref, tu peux me reprocher de ne pas être clair, mais moi je n’y suis pour rien si à aucun moment tu ne prends la peine de me faire remarquer que tu ne comprends pas et que tu as besoin que je t’explique comment ça se tient. Parce que je suis désolé mais je ne peux pas deviner que tu ne comprends pas que c’est le nombre pair qu’il faut diviser par 2.

[I.G.Y.]

« Je ne suis pas sûr que les deux questions soient vraiment différentes » : elles sont très radicalement différentes, et je ne dis pas « radicalement » pour la cuistrerie. La question 1 est une question fermée, faisant appel à l’état de mes connaissances sur des manipulations algébriques très spécifiques. La question 2 est une question ouverte qui appelle un problème sur lequel réfléchir : partant d’une esquisse de procédure, pourquoi une procédure « de ce genre » n’est semble-t-il pas utilisée dans les bons algos de calculs de multiplication efficaces (puisque le sujet des gens que tu cites est l’efficacité algorithmique des grandes multiplications)? Pourquoi cette élégance là de ces petites astuces algébriques ne suffit pas pour résoudre le problème avec une complexité algorithmique satisfaisante? Pourquoi faut-il en passer par d’autres élégances plus complexes? Voilà la question 2. Qui est intéressante et pas triviale/immédiate.
.
Pour la question 1, je crois savoir qu’il existe des bouquins entiers d’algèbre qui sur des pages et des pages égrènent avec aridité des techniques de manipulations de nombre dont même les médaille Fields ne connaissent pas par cœur le 50è (j’ai un bouquin équivalent sur les calculs d’intégrale : 1200 pages, que des intégrales génériques différentes, accessible ici gratuitement pour le fun, c’est atroce même pour un habitué des intégrales). Sur la factorisation par exemple ça mobilise les meilleurs mathématiciens du monde en théorie des nombres donc il doit y avoir (sauf que très rapidement les techniques mises en oeuvre deviennent bien sûr hors de portée). Pour télécharger des bouquins énormes et hyper chers illégalement tu peux essayer sci-hub, ou le site ligben.li . Je n’ai pas de référence précise à fournir.
.
 » je n’y suis pour rien si à aucun moment tu ne prends la peine de me faire remarquer que tu ne comprends pas » : j’ai dit plusieurs fois que faute de procédure définie génériquement c’est très difficile de répondre clairement, c’est synonyme et plus précis.
.
 » je ne peux pas deviner que tu ne comprends pas que c’est le nombre pair qu’il faut diviser par 2″ : point simple qui rejoint d’ailleurs directement le précédent. A aucun moment une procédure, une fonction, un algorithme, n’implique que lorsqu’on fait des divisions par deux on choisisse dans la liste des membres de l’équation obtenue le membre pair. Je pourrais citer mille exemple dans lesquels ça ne fonctionne pas comme ça, parce que si on fait ça la procédure ne donne pas le résultat souhaité (et c’est donc exactement pour ça qu’une procédure générique est nécessaire pour en juger). Par exemple, on peut parfaitement, parmi les 10000 astuces algébriques de transformation, imaginer une qui ressemble à :

Soit un nombre (K+1)^2 – K^2 avec K un entier

— si (K+1) impair alors ajouter 1, diviser (K+1+1) par deux et faire [une procédure X] sur le résultat.

— si (K+1) est pair, diviser (K+1) par deux et faire [une procédure Y autre que X] sur le résultat.

Le principe est que dès lors qu’on entre dans le territoire des astuces de manipulation algébriques, tout est possible (au sens où la variété des manipulations/formules est grand, au même titre que la variété des formules d’intégrales). Donc présumer au vu de tes exemples qui montrent tous une division par deux du membre de gauche, que c’est en fait le membre pair (qu’il soit à gauche ou à droite) avec lequel il faut faire « ceci ou cela » serait en toute généralité une faute, une extrapolation totalement indue. Les distinctions « membre de gauche » et « membre de droite » sont très fréquentes dans les procédures.

[BIOGRAPHIE]

« Je n’avais pas tout à fait compris l’algorithme que tu utilisais pour décomposer 27 car tu ne l’as pas explicité (j’ai cru que c’était une méthode proche de celle que tu mettais en avant au départ, qui aurait plutôt d’ailleurs donné 27=6^2-3^2 et qui aurait requis la factorisation 3*9=27, donc ça m’a étonné et je suis passé à autre chose, je réponds sur mon temps de travail donc je ne peux pas tout faire) »
.
Tu n’avais pas compris mais il n’était pas question de faire remarquer que ça te dépassait, il était juste question de prendre tout droit et de me prendre pour un con. Tu n’avais pas compris et ton excuse c’était le fait d’être au travail mais à côté de ça même si t’es au travail t’es quand même en mesure de me chier des pavés pour brasser de l’air autour de la question de la complexité algorithmique dont on se fout. E

[I.G.Y]

« la question de la complexité algorithmique dont on se fout » : oui j’ai bien compris qu’en fait tu te fous de la réponse à ta propre question de départ.

Bonne suite

[BIOGRAPHIE]

I.G.Y: On calculera la complexité de mon algorithme le jour où j’aurais pris le temps de réfléchir sérieusement le problème de la multiplication et on attendra ce jour là car ce jour là ça aura son sens. Pour le moment par contre ça n’a aucun sens puisque moi tout ce que je me borne à prétendre c’est qu’il y a la forme naive de la multiplication qui sert de base à la copie qui partagée en premier lien puis il y a un autre chemin, un chemin qui implique de construire autour d’une différence entre deux carrés. Est ce que t’es déjà allé au bout de ce chemin? Est ce que t’as déjà pris la peine de t’interroger sérieusement sur ce que permet cette façon de représenter les nombres? Jamais. Donc ferme un peu ta gueule car à l’arrivée t’as juste démontré que tu n’es pas fait pour penser mais pour répéter connement ce que les gens de mon genre peuvent foutre sur la table.

[Auteur]

Messages