Bonjour,
Si on vous pose la question:
"2^(15) = 32768 et la somme de ses chiffres vaut 3 + 2 + 7 + 6 + 8 = 26.
Que vaut la somme des chiffres composant le nombre 2^(2222)?" (ça vient d'ici si jamais)
Comment vous en sortiriez vous avec l'overflow qui découle du calcul de la puissance?
Bonjour,
Avec la classe BigInteger de Java.....mais j'imagine qu'il existe quelque chose de "plus classe"
Dans le même ordre d'idée il y aurait gmp.h qu'on pourrait rajouter par un "include" (je travaille en c) il me semble...le problème c'est que, d'une part je n'ai pas ce .h et, d'autre part, je ne sais pas comment l'utiliser...
Il y a sans doute quelque chose de "plus classe" qu'un calcul explicite mais je sèche aussi sur cet aspect
Du coup je suis un peu coincé
Tu peux bosser avec des chiffres sous forme de tableau/liste d'entier et coder une méthode de multiplication spécifique à cette représentation.....c'est bourrin mais ca passe aussi
C'est affaire de contexte : si la question est posée dans le cadre d'un cours de maths, il y a certainement une astuce plus futée que de faire explicitement de calcul.
Si c'est un cours d'informatique, le but est peut-être justement d'écrire un algorithme de calcul multiprécision, et sans utiliser de librairie externe.
Le contexte c'est : les Défi Turing, des petits problèmes de math-info....un peu à cheval entre les deux contextes que tu proposes. Mais ils sont rarement résolubles à la main, donc je penche vers le calcul fait maison.
Si c'est un exercice de dextérité en programmation, avec la méthode bourrin, c'est l'affaire de 15 min de programmation et d'une dizaine de lignes de code en C.
A vos marques
En effet, une petite trentaine de lignes pour la multiplication par tableau...et dire qu'on ne peut pas renvoyer les tableaux en C ^^
Merci pour le conseil!
Passage en base 2?Envoyé par Curuxa
facile en base 2, une bonne méthode de conversion en base 10 ?
Utiliser les propriétés de la base 2, en particulier s'arranger pour ne pas avoir besoin de faire de multiplication. Pour cela on peut se baser sur le fait que 10 en base dix s'écrit 1010 en base 2, c'est-à-dire que multiplier un nombre binaire par 10 (en base dix) revient à ajouter (le même nombre auquel on ajoute trois zéros) à (le même nombre auquel on ajoute un zéro).
Pseudocode matlab:
function [resultat]=mycat(n)
% cette fonction calcule la somme des chiffres qui composent en base 10 le nombre 2^n
%% partie 1: calculer des vecteurs binaires équivalents aux puissances de 10 nécessaires
% nb: possible de le précalculer si la fonction sert souvent%% partie 2: calculer les chiffres en soustrayant les puissances de 10 à la cible en base 2
pdix(1)=[1010];
for i=2:ceil(n/4) % nb: 4 est sous-optimal, et on s'en foutpdix(i)=additionbinaire([pdix(i-1) 000],[pdix(i-1) 0]) % codage additionbinaire laissé en exerciceend
%initialisation cible et vecteur de chiffres en base 10endfunction
cible=[1]
for j=1:ncible=[cible 0]end
leschiffres(1:i)=0 % i vaut encore ceil(n/4)
%suite de soustraction
cp=0;
while cible>0if cible<pdix(i)endwhilei=i-1elsecible=soustractionbinaire(cibl e,pdix(i)) % guess what?endif
leschiffres(i)=leschiffres(i)+ 1
resultat=sum(leschiffres)
(EDIT: quelques petites erreurs à corriger)
La prochaine fois, utilise la balise Code au lieu de t'em..... avec des Indent.
Rien ne sert de penser, il faut réfléchir avant - Pierre Dac
en additionnant chaque chiffre
solution en vba
Code:Function somme3() x = 4096 ' 2^11 ch = "D:\MSVCNT\pianoVB\s3.txt" Open ch For Output As 1 Dim sh As String Dim s As String sh = x For I = 12 To 2222 s = "" r = 0 l = Len(sh) For j = l To 1 Step -1 v = val(mid$(sh, j, 1)) v = v + v + r If v > 9 And j > 1 Then v = v - 10 r = 1 Else r = 0 End If s = v & s Next j sh = s ' Print #1, I & ";" & s Next I v = 0 For I = 1 To Len(sh) v = v + val(mid(sh, I, 1)) Next I Print #1, "2^222;" & v Print #1, "2^222=" & sh Close #1 End Function résultat 2^2222 somme des chiffres = 2861 2^2222=1547677115575624254184382658235472791535161070408873830145349351090233328667804512422364275853900423503804899033346453512945679559567877542316042737764552713696141588418716140204086886650704273090100000221069479368440937854505143709045727517022393446877125821218380306429338134144203579243084344210850302269530215109407560072324692005026605768092823237574654293098337394602159836095545039545573518646912646772320356966790214406643154096565703738411295282926621396484834625765839133052942652813596720020035882962048175038381501748932494043384109354925516435358062977019881896258708661941266166556024148330076067880092291689258956662226351413716582839875206326801932484608
Il y a une erreur dans x = 4096 ' 2^11
4096 c'est 2^12
ce qui fait que c'est 2^2223 qui a été calculé
pour accélérer, on peut prendre au début x=2^15=32768
et modifier la boucle
For I = 16 To 2222
on trouve 2830 comme somme
La prochaine fois faudra aussi que je regarde le temps demandé... moins d'1 minute, aucune chance que mon programme fasse cela
Jamais utilisé. Pourrais-tu STP expliciter ce que font les lignes de code ci-dessous?
v = val(mid$(sh, j, 1))
v = v + val(mid(sh, I, 1))
On est amené à calculer les multiplications en base dix comme on l'appris à l'école primaire ! (les bambins apprennent encore ?)
Plutôt que manipuler des bits pour faire des multiplications de chiffres , utilisez les fonctionnalités de votre processeur et de votre langage pour multiplier; et tant qu'à faire, faites les calculs en base 100, 1000, 10000 etc selon les nombres entiers que gère votre configuration. Il est ensuite facile de convertir en base dix.
Je me place d'un point de vue pratique.
À toutes fins utiles, je rappelle qu'il n'est pas nécessaire de faire 2222 multiplications, il existe un algorithme d'exponentiation rapide pour calculer une puissance n-ième avec environ log2 (n) multiplications !
Avec tout ça il me semble que vous n'aurez pas besoin de recourir aux techniques de multiplication par FFT etc !
P.S:Sans aller jusqu'aux méthodes par transformée de Fourier rapide (FFT), il existe des méthodes de multiplication relativement rapide plus simples conceptuellement qui permettent d'améliorer les choses .
J'en avait vu une qui reposait sur l'identité x^2-y^2 = (x+y)(x-y).
sh étant une chaine de caractère, en vba pour parcourir les caractères d'une chaine il faut utiliser Mid(la chaine,début,nombre de caractère)
val converti une chaine numérique en entier
équivalence en c : atoi(sh[I]);
@Schrodies-cat : Mon programme ne fait que des additions, pas de multiplications
Combien ?
La puissance des microprocessurs actuels permet le gaspillage des ressources de calcul, mais si vous vous intéressez à 2^222222 ou 2^22222222, considérez les méthodes que je suggère.
Choisir le bon langage peut aider
Pour aller plus loin, il faudra faire des maths.Code:Python 2.7.3 (default, Feb 27 2014, 20:00:17) [GCC 4.6.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> 2**2222 773838557787812127092191329117736395767580535204436915072674675545116664333902256211182137926950211751902449516673226756472839779783938771158021368882276356848070794209358070102043443325352136545050000110534739684220468927252571854522863758511196723438562910609190153214669067072101789621542172105425151134765107554703780036162346002513302884046411618787327146549168697301079918047772519772786759323456323386160178483395107203321577048282851869205647641463310698242417312882919566526471326406798360010017941481024087519190750874466247021692054677462758217679031488509940948129354330970633083278012074165038033940046145844629478331113175706858291419937603163400966242304L >>> sum( int(d) for d in str(2**2222)) # somme des chiffres 2830 >>> sum( int(d) for d in str(2**222222)) # celui-là prend une demi seconde 300610
pour 2^n il fait n-12 addition plus le nombre de chiffre à additionner à la fin (669 pour n=2222 il met moins d'1 seconde à le calculer en VBA)
impressionnant ce python, c'est concis et rapideChoisir le bon langage peut aider
Code:>>> sum( int(d) for d in str(2**222222)) # celui-là prend une demi seconde 300610
J'ai essayé 222222 avec mon programme mais j'ai arrêté la tache au bout de 5 minutes il n'en était qu'à 27000
Le temps est exponentiel, je pense, donc au bout d'un moment ça pête!
Ben... pas vraiment puisque tu n'as pas essayé de coder ces idées pour vrai. Si tu le fais, je crains que tu ne sois déçu
Ok merci. Et à la ligne "s = v & s"? v est un nombre, s une chaine de caractère, comment vba interprète la commande & dans ce cas?
Dans ce cas c'est de la tricheChoisir le bon langage peut aider
si c'était + il ferait l'addition (d’ailleurs j’aurai pu supprimer val dans v = v + val(mid(sh, I, 1)) )
& est justement fait pour les chaines de caractère donc il convertie le numérique en caractère.
normalement avec des additions c'est linéaire mais il y a l'allocation mémoire des 2 chaines de caractères qui grossissent à chaque itération
Peux-tu donner un ou deux exemples de ce que fait la commande &?
v=43
s="123456"
v & s = "43123456"
v = 1
r = 0
v & r = "10"
J'ai fait le test de 222222 addition ça prend moins d'un seconde
MerciBon maintenant que je le comprend c'est conceptuellement similaire, en mieux codé.
Donc quadratique (autour de 0.5 n^2), alors que toute solution passant par des multiplications devrait nécessiter entre n^3 (méthode "naïve") et n^2.log(n).log(log(n)) (méthode Schönhage–Strassen l'enfer est pavé de Schönhage–Strassen) opérations... je crois que c'était bien cela le but de l'exercice: montrer qu'on peut aller plus vite que la méthode générale si on reconnait et exploite une propriété mathématique particulière (ici le fait que c'est un nombre de la famille des puissances de 2 plutôt qu'une puissance quelconque).
Autour d'une minute avec matlab même avec une bête de compétition... pas le meilleur choix de programme pour jouer avec des strings
Je me suis trompé car il y a 2 boucles imbriquées avec une augmentation de l'indice fin de la 2emme (la longueur de la chaine) dans laquelle est l'addition.Merci
Donc quadratique (autour de 0.5 n^2), alors que toute solution passant par des multiplications devrait nécessiter entre n^3 (méthode "naïve") et n^2.log(n).log(log(n)) (méthode Schönhage–Strassen l'enfer est pavé de Schönhage–Strassen) opérations... je crois que c'était bien cela le but de l'exercice: montrer qu'on peut aller plus vite que la méthode générale si on reconnait et exploite une propriété mathématique particulière (ici le fait que c'est un nombre de la famille des puissances de 2 plutôt qu'une puissance quelconque).
Autour d'une minute avec matlab même avec une bête de compétition... pas le meilleur choix de programme pour jouer avec des strings
en faisant le test ça donne le même résultat, il met trop de temps
Code:Function testsomme() v = 1 r = 0 l = 5 t1 = Time For I = 16 To 222222 v = 0 For j = 1 To l v = v + l + r Next j l = l + 1 Next I t2 = Time End Function
