2^2222

[Curuxa]

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?
-----

[Arzhur]

Bonjour,


Avec la classe BigInteger de Java.....mais j'imagine qu'il existe quelque chose de "plus classe"

[Curuxa]

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é

[Arzhur]

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

[A voir en vidéo sur Futura]

[WizardOfLinn]

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.

[Arzhur]

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.

[WizardOfLinn]

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

[Curuxa]

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!

[invite73192618]

Comment vous en sortiriez vous avec l'overflow qui découle du calcul de la puissance?

Passage en base 2?

[Schrodies-cat]

facile en base 2, une bonne méthode de conversion en base 10 ?

[invite73192618]

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

pdix(1)=[1010];
for i=2:ceil(n/4) % nb: 4 est sous-optimal, et on s'en fout

pdix(i)=additionbinaire([pdix(i-1) 000],[pdix(i-1) 0]) % codage additionbinaire laissé en exercice

end

%% partie 2: calculer les chiffres en soustrayant les puissances de 10 à la cible en base 2

%initialisation cible et vecteur de chiffres en base 10

cible=[1]
for j=1:n

cible=[cible 0]

end
leschiffres(1:i)=0 % i vaut encore ceil(n/4)

%suite de soustraction
cp=0;
while cible>0

if cible<pdix(i)

i=i-1

else

cible=soustractionbinaire(cibl e,pdix(i)) % guess what?
leschiffres(i)=leschiffres(i)+ 1

endif

endwhile
resultat=sum(leschiffres)

endfunction

(EDIT: quelques petites erreurs à corriger )

[JPL]

La prochaine fois, utilise la balise Code au lieu de t'em..... avec des Indent.

[EauPure]

en additionnant chaque chiffre
solution en vba

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

[EauPure]

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

[invite73192618]

La prochaine fois, utilise la balise Code au lieu de t'em..... avec des Indent.

La prochaine fois faudra aussi que je regarde le temps demandé... moins d'1 minute, aucune chance que mon programme fasse cela

solution en vba

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))

[Schrodies-cat]

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).
(...)

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 !

[Schrodies-cat]

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).

[EauPure]

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))

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

[Schrodies-cat]

(...)
@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.

[bobflux]

Choisir le bon langage peut aider

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 aller plus loin, il faudra faire des maths.

[EauPure]

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.

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)

[EauPure]

Choisir le bon langage peut aider

>>> sum( int(d) for d in str(2**222222)) # celui-là prend une demi seconde
300610

impressionnant ce python, c'est concis et rapide
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

[bobflux]

Le temps est exponentiel, je pense, donc au bout d'un moment ça pête!

[invite73192618]

Je me place d'un point de vue pratique.

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

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

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?

Choisir le bon langage peut aider

Dans ce cas c'est de la triche

[EauPure]

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?

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.

[EauPure]

Le temps est exponentiel, je pense, donc au bout d'un moment ça pête!

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

[invite73192618]

convertie le numérique en caractère.

Peux-tu donner un ou deux exemples de ce que fait la commande &?

[EauPure]

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

[invite73192618]

v=43
s="123456"
v & s = "43123456"

Merci Bon maintenant que je le comprend c'est conceptuellement similaire, en mieux codé.

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

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).

J'ai fait le test de 222222 addition ça prend moins d'un seconde

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

[EauPure]

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

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.
en faisant le test ça donne le même résultat, il met trop de temps

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