Page 3 sur 4

Re: [Défi math] Calculer rapidement une factorielle

Publié : jeu. 30/sept./2010 21:47
par PAPIPP
@ Dobro et @SPH
Puisque SPH arrive à faire afficher un nombre très grand...
Justement non pas pour l’instant. c’est l’objet de ma 2em remarque.

La structure type SPH ne fonctionne que sur des entiers positifs il faudrait une structure pour
Accepter les nombres réels avec signe et décimales.
Par exemple le premier poste en .w le premier bit serait réservé au signe puis les 15 autres bits au nombre de décimales 2^15=32768 décimales possibles
Ou autre exemple prendre les 2 premiers postes le premier bit pour le signe
Et le 31 bits qui suivent pour l’exposant soit en base 10 soit en base 2 2^31= 2 147 483 648.
Plus de 2 milliards de chiffres significatifs en base 10

Ensuite et seulement après cette définition proposer à SPH ou à d’autres de rechercher tous les opérateurs de base :

1) Sur une seule structure de type SPH :

ENTREE d’un grand nombre en format string et le convertir dans le structure type SPH
SORTIR à partir de la structure de SPH convertir le grand nombre en format string
CONVERSION Type .w .l .q .f .d en structure type SPH
CONVERSION Type SPH en . .w .l .q .f .d

2) Sur 2 structures de même type inventées par SPH :
ADDITION
SOUSTRACTION
MULTIPLICATION
DIVISION


3) Puis ensuite de passer aux opérateurs plus élaborés comme par exemple :
Log10
Logn
EXPO10
EXPO
COS
SIN
TANG
ARCSIN
ARCCOS
ARCTANG
COSH
SINH
TANGH
ARCOSH
ARCSINH
ARCTANGH
FACTORIELLE (non à partir d’un type .l mais d’une structure type SPH
COMBIN
ARRANG
BESSEL
GAMA
Etc…

Bon courage.
A+

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 1:03
par Backup
ou peut etre passer par les strings ...


pour en revenir a la fonction récursive , voici justement l'exemple typique
que l'utilisation de la récursivité , n'est pas forcement le meilleur choix :)
j'ai cogité un peu la dessus voici mes résultats

voici en premier la fonction recursive en action :


; ******* avec recursivité **********
debug "********* avec recursivité **********"
for i=1 to valeur_max
         debug factorielle(i)
next i
        
Procedure factorielle(n)
         If n = 1
                 ProcedureReturn 1
         EndIf
         ProcedureReturn n * factorielle(n - 1)
EndProcedure
; ***********************************


soit 9 lignes de code !!

la meme chose sans recursivité :D


; ****** sans recursivité ***********
debug "********* sans recursivité **********"
res=1
for i=1 to valeur_max
        res=i*(res)
         debug res
next i
; *******************************


5 ligne de code !! :D

comme quoi la récursivité c'est un style pas forcement un gain en terme de nombre de ligne de code ... en tout cas poiur cette exemple :)


apres naivement , je me suis dit si j'employais des strings , je ne serai pas limité par la taille
d'une variable , alors j'ai fais :


; ****** sans recursivité mais string***********
debug "********* sans recursivité mais string**********"
res2.s= "1"
for i=1 to valeur_max
        res2.s= str (i* valf (res2.s))
         debug res2.s
next i
; *******************************


mais voila , ça coince quand meme , ça aurai été trop simple :lol:
pourtant dans la pratique j'ecris le résultat du calcul dans un string, donc pas limité ... en principe , mais la limite se trouve ailleurs alors ...peut etre dans le
valf (res2.s)


dommage , mon idée avait de l'idée :lol:

code complet :

Code : Tout sélectionner


valeur_max=10

declare factorielle(n)
; ****** sans recursivité ***********
debug "********* sans recursivité **********"
res=1
for i=1 to valeur_max
  res=i*(res) 
  debug res
next i
; *******************************

; ****** sans recursivité  mais string***********
debug "********* sans recursivité  mais string**********"
res2.s="1"
for i=1 to valeur_max
  res2.s=str(i*valf(res2.s))
  debug res2.s
next i
; *******************************


; ******* avec recursivité **********
debug "********* avec recursivité **********"
for i=1 to valeur_max
  debug factorielle(i)
next i 
 Procedure factorielle(n)
  If n = 1
    ProcedureReturn 1
  EndIf
  ProcedureReturn n * factorielle(n - 1)
EndProcedure
; ***********************************





Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 1:14
par Frenchy Pilou
Il va falloir affiner car ton maximum 4 294 901 760 ! est encore bien petit :)

là ils en sont à (1.7976931349 × (10 puissance 308) ) !
et le résultat est
10 puissance (5.5336665775 × (10 puissance 310)) :mrgreen:

il est communément admit qu'il y a 10 puissance 80 atomes dans l'univers
donc on ne peut même écrire le résultat pour le lire, cela pousserait et pas qu'un peu les limites de l'univers :lol:

ah c'est des joyeux drilles les matheux :D
c'est déjà rassurant de savoir que le nombre d'après pour la prochaine multiplication sera
(10 puissance (5.5336665775 × (10 puissance 310))) + 1 :mrgreen:

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 6:34
par SPH
Frenchy Pilou a écrit :Il va falloir affiner car ton maximum 4 294 901 760 ! est encore bien petit :)
Heu, non non. J'ai bien dis factorielle de 4 294 901 760; ce qui fait un nombre de plusieurs millions de chiffres :mrgreen:

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 9:09
par PAPIPP
Bonjour à Tous
Réponse à Frenchy Pilou
Il va falloir affiner car ton maximum 4 294 901 760 ! est encore bien petit :)
Essayons de nous figurer le nombre représenté par pow(2,32)!
En zone .l 2^32=4294967296 zone non signée
Qu’elle est l’ordre de grandeur de 4294967296!
Ici on peut utiliser la formule log( n!) approchée d’une factorielle pour réaliser les calculs en machine
Car la formule Stirling atteint les limites de calcul en .d
Log( n!)~n*Log(n)-n
Nous obtenons :

Code : Tout sélectionner

; Calculons pow(2,32)! ; avec formule de Stirling on dépasse la capacité de calcul .d
n.q=Pow(2,32)
Debug Round(Sqr(2*#PI*n)*Pow((n/#E),n),#PB_Round_Nearest)
; avec la formule approchée du Log(n!)
; alors que Log(n!)~n*Log(n)-n
nd.d=n
ln.d=nd*Log(nd)-nd
Debug ln ; pour remonter au nombre n! ~ e^ln  pas facile à comprendre alors convertissons en LOG10(n!) ce qui nous donne 
;avec Log10(n!)=Log10(#E)*Log(n!)
L10n.d=Log10(#E)*ln
;Debug ln
Debug "log10("+Str(nd)+"!)="+StrD(L10n)
log10(4294967296!)=39507966971.1305470000

Or Log10(1000)=1E3 avec 4 chiffres pour 1000
Donc Log10( n!)= 39507966971.130547 donc plus de 39.507966971130547 10^9
ou 39 milliards de Chiffres pour le nombre 4294967296!
Le nombre 4294967296!=>10^39507966971.130547 (ou 10 puissance 39507966971.130547)
il est communément admit qu'il y a 10 puissance 80 atomes dans l'univers
Nombre qui dépasse l’entendement (alors toujours petit 4294967296! !!)

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 10:10
par SPH
PAPIPP, je vois que tu es fort en math et en ASM. On va bien s'entendre.

Pour les autres, oui, ma routine est une routine de multiplication entre un nombre de maximum 31 bits (32?) par un nombre d'autant de bit que vous voulez. Je crois qu'il ne faut pas demander a Fred de l'integrer dans PB. Ca ne servirait a rien. Nan, il faut se taper le bon code adapté a ses besoins.

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 11:40
par Backup
SPH a écrit : Je crois qu'il ne faut pas demander a Fred de l'intégrer dans PB. Ca ne servirait a rien. Nan, il faut se taper le bon code adapté a ses besoins.
bien une variable non limité en affichage , permettrai surtout au naze en math comme moi
de pouvoir manipuler des grands nombres, ( appliquer des formules toute faites )
sans avoir a se cogner un code en ass !! ;)

je sais pour l'avoir vu , qu'il y a moyen d'y arriver par le truchement des variables Strings !

car celle-ci ne sont pas limité en affichage ;)

on peut sortir un nombre de la taille de plusieurs Tomes en utilisant l'éditeur :D

ça permettrai de faire un prg de recherche de PI ou autre joyeusetés intellectuel du genre :)
(pour Pi un algo a deja ete donné ici qui utilise les strings en sorti ;) )

je reve d'une variable x.G (G comme Giga mega baleze :lol: )
avec les fonctions qui vont avec ... comme l'a suggéré PAPIPP

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 12:39
par Starwolf20
Que pensez vous de GMP ??? http://gmplib.org/

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 17:17
par SPH
C'est vrai que quand on y pense, on est vite overflow. Dans un calcul mathematique, il suffit d'une etape qui depasse pour avoir un faux calcul :|

Re: [Défi math] Calculer rapidement une factorielle

Publié : ven. 01/oct./2010 18:52
par Frenchy Pilou
J'ai l'impression que vous n'avez pas compris :lol:
C'est le nombre de départ de la factorielle qui est petit :roll:
Relisez mon post
la factorielle 4 294 901 760 ! c'est grosso modo factorielle 4 milliards

le nombre que je proposais avait déjà lui plus de 308 chiffres avant de le passer en factorielle ! :mrgreen:
4 milliards n'en a que 10 (de chiffres)
cela n'a donc aucune commune mesure :D
Quant au chiffre d'arrivée j'en parle même pas :wink:
C'est en cela qu'il y a encore du mouron à se faire :lol:

Re: [Défi math] Calculer rapidement une factorielle

Publié : sam. 02/oct./2010 7:12
par SPH
Frenchy Pilou a écrit :le nombre que je proposais avait déjà lui plus de 308 chiffres avant de le passer en factorielle ! :mrgreen:
Faudrait en avoir l'utilité. Mais, est-ce stockable??! :|

Re: [Défi math] Calculer rapidement une factorielle

Publié : sam. 02/oct./2010 10:02
par Frenchy Pilou
L'utilité de ces calembredaines à longues portées ne sert que pour de sombres histoires de sécurisations et pour faire avancer la recherche des techniques de codage pour manipuler des grands nombres :)

Re: [Défi math] Calculer rapidement une factorielle

Publié : sam. 02/oct./2010 10:50
par Backup
bon je me suis collé au probleme en utilisant les infos de SPH
SPH a écrit :On procede comme une multiplication sur le papier :
ABCDEFG
* X
=======


et en n'utilisant QUE le purebasic :)
SPH a écrit :Je viens d'essayer entièrement en PB mais impossible !! Et si je reussi, ca fera trop de détours pour trop de perte de temps de calcul...
si! si! c'est possible :)

voici le code que je viens de mettre au point , qui reprend le mécanisme d'une multiplication a la main (multiplication +addititon) , ce qui évite de manipuler des gros chiffres
mais peut obtenir de tres grand nombres !
pour se faire j'emploie les Strings ;) car elle sont illimitées ,on peut écrire 3 tomes de chiffres dedans.. pas de problèmes :)

le code si dessous utilise 2 procédures
une, qui multiplie , puis l'autre, qui est utilisée par la première , qui s'occupe de la longue addition
de cette multiplication...

tout a fait dans l'esprit de cette image :

TTTTTTTTT ; nombre a multiplier
RRRRRRRRRR ; nombre multiplicateur
=========
eeeeeeeeee addition
eeeeeeeeee addition
eeeeeeeeee addition
eeeeeeeeee addition
___________
Resultat

le code ci dessous calcul la factoriel de 200
mais surtout l'affiche !! :D

sinon un exemple d'utilisation de multiplication standard est proposé sous la forme


; *********** exemple d'utilisation de la multiplication **********
b.s= "92245" ; ce nombre va etre multiplié par
multiplicateur.s= "9229" ; celui ci ;o)
calldebugger
debug multiplication(multiplicateur.s,b.s) ; affiche le resultat : o)
; *****************************************************



Avantage , on est plus limité par la taille des nombres a multiplier :)



declare.s multiplication(multiplicateur.s,b.s)
declare.s addition_liste(long_maximale.q)

; ; *********** exemple d'utilisation de la multiplication **********²
b.s= "92233720369223372036" ; ce nombre va etre multiplié par
multiplicateur.s= "92233720369223372036" ; celui ci ;o)

debug multiplication(multiplicateur.s,b.s) ; affiche le resultat : o)
calldebugger
; ; *****************************************************


; ************** calcul de factoriel ******************
valeur_max=20
res.s= "1"
for i=1 to valeur_max
        i$= str (i)
        res.s=multiplication(res.s,i$)
next i
debug res.s
calldebugger
; *****************************************************


procedure.s multiplication(multiplicateur.s,b.s)
         ; By Dobro
         if len (multiplicateur.s)>len(b.s)
                buf.s=multiplicateur.s
                multiplicateur.s=b.s
                b.s= buf.s
         endif
         global newlist pile.s()
        
        multiplicateur.s= reversestring (multiplicateur.s)
        b.s= reversestring (b.s)
        long_multiplicateur.q= len (multiplicateur.s)
        long_b.q= len (b.s)
        
        i_multiplicateur.q=0
         while i_multiplicateur.q < long_multiplicateur.q
                i_multiplicateur.q =i_multiplicateur.q +1
                extrait_multiplicateur.q= val ( mid (multiplicateur.s,i_multiplicateur,1)) ; recup l'extrait du nombre multiplicateur
                i_b=0
                 while i_b < long_b
                        i_b=i_b+1
                        extrait_b= val ( mid (b.s,i_b,1)) ; ; recup l'extrait du nombre b
                         ; ************ multiplie *****************
                        resultat.s=resultat.S+ str (extrait_b*extrait_multiplicateur+retenue) :retenue=0
                        resultat.s= reversestring (resultat.s)
                         ; *************************************
                        retenue= val ( mid (resultat.s ,2,1)) : reste= val ( mid (resultat.s ,1,1))
                        resultat.s= ""
                        ligne_provisoire$=ligne_provisoire$+ str (reste)
                 wend
                
                
                 if retenue<>0 ; ya une retenue !
                        ligne_provisoire$=ligne_provisoire$+ str (retenue)
                         addelement (pile()) ; on pose la rangée en cours
                        pile()=ligne_provisoire$
                        retenue=0:reste=0
                         ;ligne_provisoire$=""
                 else ; pas de retenue
                         addelement (pile()) ; on pose la rangée en cours
                        pile()=ligne_provisoire$
                        retenue=0:reste=0
                 endif
                 if long_b.q<2 and long_multiplicateur.q<2 ; ressort le calcul simple tout de suite
                         addelement (pile())
                        pile()=ligne_provisoire$
                        resultat.s= reversestring (pile())
                        ligne_provisoire$= ""
                         ProcedureReturn resultat.s
                 else ; **********************************************************************
                         ;on passe a la rangée suivante
                         nextelement (pile())
                         ; ajout d'un zero
                        compt.q=compt.q+1
                        resultat.s = lset (resultat.s, compt.q, "0" )
                        ligne_provisoire$=resultat.s
                 endif
         wend
        
         if compt.q>0
                 lastelement (pile())
                long_maximale.q= len (pile())
                 resetlist (pile())
                total.s=addition_liste(long_maximale.q)
                total.s= reversestring (total.s)
                 ProcedureReturn total.s
         endif
endprocedure


procedure.s addition_liste(long_maximale.q)
         ; by dobro
        ligne_provisoire$= ""
        i.q=0
         while i.q<long_maximale.q
                i.q=i.q+1
                 ForEach pile()
                        extrait_bit= extrait_bit+ val ( mid (pile(), i,1))+retenue :retenue=0
                 next ; fin de l'addititon ligne
                ligne_provisoire$= ligne_provisoire$+ right ( str (extrait_bit),1)
                retenue= val ( left ( str (extrait_bit), len ( str (extrait_bit))-1))
                total.s=ligne_provisoire$
                extrait_bit=0
         wend
         ProcedureReturn total.s
endprocedure





:)

Re: [Défi math] Calculer rapidement une factorielle

Publié : sam. 02/oct./2010 11:46
par Backup
arg , a partir d'une certaine valkeur ça deconne

parceque j'ai encore des variables qui me bloque

( les boucles je pense... ) je regarde ça :)

Re: [Défi math] Calculer rapidement une factorielle

Publié : sam. 02/oct./2010 12:29
par Backup
for n'accepte pas les variables de type Quad !!

j'aimerai bien avoir une explication la dessus !!