Inscription / Connexion Nouveau Sujet
Niveau logiciels
Partager :

Manipuler de très grands nombres ?

Posté par
Epsilon
26-06-14 à 20:15

Bonjour, je recherche un moyen de composer des algorithmes sur ordinateur manipulant de très grands entiers sans les arrondir (du style 10^300 et +), comprenant seulement des opérations relativement simples (multiplication, addition, élévation au carré... rien de bien méchant).
Une idée ? Je me rends bien compte que de tels nombres vont faire que les opérations seront très longues...
Jadis j'avais utilisé CodeBlocks et Matlab mais je n'ai pas été satisfait, je me souviens plus trop pourquoi... soit les résultats n'étaient pas les bons pour deux mêmes algorithmes (erreurs d'arrondi car limite de chiffres atteinte ?) ou alors ils n'acceptaient pas des nombres trop gros
Une idée ?
Merci

Posté par
Glapion Moderateur
re : Manipuler de très grands nombres ? 26-06-14 à 22:39

Bonjour, voilà toujours un url d'un site qui fait des opérations sur de très grand entiers :

Posté par
Arowbaz
re : Manipuler de très grands nombres ? 26-06-14 à 23:59

bonsoir, perso je le fais en java après beaucoup vont critiquer mais ça me convient, tu peux utiliser la classe BigInteger dont l'entier max peut potentiellement être :

2^{32^{2^{31}}}\sim2^{64^{31}}\sim10^{19^{31}}\sim10^{589} (si je ne commets pas d'erreur)

les nombres sont stockés dans des tableaux d'entiers, sur 32 bits, ce qui explique la formule. Tu as surtout beaucoup, beaucoup de matière (+,-,/,*,^,%,gcd,lcm,modPow ...)

Posté par
amateur
re : Manipuler de très grands nombres ? 27-06-14 à 21:44

Bonjour,


Voici pour les longues soirées d'hiver ...
<par ex calcul de 300! (625 chiffres)>



CONST Faux = (0 = 1)
CONST Vrai = NOT (Faux)

const LenNb=1000 ' à modifier selon le nb chiffres à utiliser

TYPE nombre
len AS INTEGER
str AS STRING * LenNb
END TYPE


DIM a AS nombre
CALL Init
call Factorielle (a AS nombre, 300)
print ValNb$(a)
END
'-----------------------------------------------------
SUB Init
SCREEN 0: WIDTH 150, 40: _FONT 16
CLS
END SUB


SUB Pause
y$ = INKEY$
if len(y$)>0 then
  end
end if
END SUB
'------------------------------------------------
SUB SqrNb (rep AS nombre, p AS nombre)
DIM a AS nombre, b AS nombre, c AS nombre
   CALL LongToNb(a,0)
   CALL LongToNb(b,1)
   CALL LongToNb(c,0)
do while LENb%(a,p)
CALL AddNb(a, a, b)
CALL AddLongNb(b, b, 2)
CALL IncNb(c)
loop
call DecNb(c)
    CALL CopyNb(rep, c)
end sub
'------------------------------------------------
FUNCTION GetChif% (p AS nombre, p1 AS INTEGER)
GetChif% = VAL(MID$(p.str, p1, 1))
END FUNCTION

SUB PutChif (p AS nombre, p1 AS INTEGER, p2 AS INTEGER)
MID$(p.str, p1, 1) = CHR$(p2 + 48)
END SUB

SUB ConcateStrNb (dst AS nombre, a AS nombre, b AS STRING)
DIM s1 AS STRING, s AS STRING, n1 AS INTEGER, i AS INTEGER
s1 = LTRIM$(RTRIM$(b)): n1 = LEN(s1)
s = ""
FOR i = 1 TO n1
    s = MID$(s1, n1 - i + 1, 1) + s
NEXT i
s = s + a.str
dst.len = LEN(s)
dst.str = LEFT$(s + STRING$(LenNb, "0"), LenNb)
END SUB

SUB ConcateNb (dst AS nombre, a AS nombre, b AS nombre)
DIM k AS LONG, i AS LONG, s AS STRING
dst.len = a.len + b.len
dst.str = LEFT$(LTRIM$(MID$(b.str, 1, b.len)) + LTRIM$(MID$(a.str, 1, a.len)) + STRING$(LenNb, "0"), LenNb)
END SUB

SUB ZeroNb (p AS nombre)
p.len = 0
p.str = STRING$(LenNb, "0")
END SUB

FUNCTION UnNb% (n1 AS nombre)
DIM ret AS INTEGER
ret = Faux
IF n1.len = 1 AND LEFT$(n1.str, 1) = "1" THEN ret = Vrai
UnNb% = ret
END FUNCTION

SUB LongToNb (p AS nombre, p1 AS LONG)
CALL StrToNb(p, LTRIM$(STR$(p1)))
END SUB

SUB StrToNb (p AS nombre, p1 AS STRING)
DIM s AS STRING, i AS INTEGER, n AS INTEGER
CALL ZeroNb(p)
s = LTRIM$(RTRIM$(p1))
n = LEN(s)
p.len = n
FOR i = 1 TO n: MID$(p.str, i, 1) = MID$(s, n - i + 1, 1): NEXT i
END SUB

SUB CopyNb (dst AS nombre, src AS nombre)
dst.len = src.len
dst.str = src.str
END SUB

FUNCTION ValNb$ (n AS nombre)
DIM f AS STRING, i AS INTEGER, j AS INTEGER
IF n.len = 0 THEN
    f = "0"
ELSE
    j = n.len: f = "": FOR i = 1 TO j: f = MID$(n.str, i, 1) + f: NEXT i
END IF
ValNb$ = f
END FUNCTION

SUB ErrNb (n AS INTEGER)
IF n > LenNb THEN
    PRINT "Erreur: nombre trop long"
    END
END IF
END SUB

SUB Tranche (p1 AS nombre, p2 AS nombre, p3 AS nombre, p4 AS nombre)
DIM k AS LONG, n AS LONG
k = p4.len
CALL debNb(p1, p3, k)
IF LTNb%(p1, p4) THEN
    k = k + 1
    CALL debNb(p1, p3, k)
END IF
CALL finNb(p2, p3, p3.len - k)
END SUB

SUB ShiftNb (p1 AS nombre, p2 AS nombre)
IF ZNb%(p1) THEN
    p1.str = MID$(p2.str, p2.len, 1)
    p1.len = 1
ELSE
    p1.str = MID$(p2.str, p2.len, 1) + p1.str
    p1.len = p1.len + 1
END IF
p2.len = p2.len - 1
END SUB

SUB Mul10Nb (p1 AS nombre)
p1.str = "0" + p1.str
p1.len = p1.len + 1
END SUB
'-----------------------------------------------
SUB IncNb (p AS nombre)
DIM i AS INTEGER, n AS INTEGER, r AS INTEGER, c AS INTEGER
r = 1
n = 0
WHILE r > 0
    n = n + 1
    CALL ErrNb(n)
    c = VAL(MID$(p.str, n, 1)) + r
    r = INT(c / 10)
    c = c MOD 10
    MID$(p.str, n, 1) = CHR$(48 + c)
WEND
IF n > p.len THEN
    p.len = n
END IF
END SUB

SUB DecNb (p AS nombre)
'il faut que p>0
DIM i AS INTEGER, n AS INTEGER, r AS INTEGER, c AS INTEGER
r = 1
n = 0
DO WHILE r > 0
    n = n + 1
    CALL ErrNb(n)
    c = VAL(MID$(p.str, n, 1)) - r
    IF c < 0 THEN
        c = c + 10
    ELSE
        r = 0
    END IF
    MID$(p.str, n, 1) = CHR$(48 + c)
LOOP
IF MID$(p.str, p.len, 1) = "0" THEN
    p.len = p.len - 1
END IF
END SUB
'-----------------------------------------------
SUB AddNb (dst AS nombre, a AS nombre, b AS nombre)
DIM x AS nombre
DIM i AS INTEGER, r AS INTEGER, k AS INTEGER, n AS INTEGER
n = a.len
IF b.len > n THEN n = b.len
r = 0
FOR i = 1 TO n
    k = VAL(MID$(a.str, i, 1)) + VAL(MID$(b.str, i, 1)) + r
    r = INT(k / 10)
    k = k MOD 10
    MID$(x.str, i, 1) = CHR$(48 + k)
NEXT i
WHILE r <> 0
    n = n + 1
    CALL ErrNb(n)
    k = r MOD 10
    r = INT(r / 10)
    MID$(x.str, n, 1) = CHR$(48 + k)
WEND
x.len = n
CALL CopyNb(dst, x)
END SUB

SUB SubNb (c AS nombre, a AS nombre, b AS nombre)
' a>=b !!!!!!!!!!!!!
DIM i AS INTEGER, r AS INTEGER, k AS INTEGER, n AS INTEGER
n = a.len
r = 0
FOR i = 1 TO n
    k = VAL(MID$(a.str, i, 1)) - VAL(MID$(b.str, i, 1)) - r
    r = 0
    IF k < 0 THEN
        k = k + 10
        r = 1
    END IF
    MID$(c.str, i, 1) = CHR$(48 + k)
NEXT i
  
DO WHILE MID$(c.str, n, 1) = "0"
    n = n - 1
    IF n < 1 THEN
        n = 0
        EXIT DO
    END IF
LOOP
c.len = n
END SUB
'-----------------------------------------------
SUB MulNb (c AS nombre, a AS nombre, b AS nombre)
DIM x1 AS nombre, T AS nombre
DIM X AS INTEGER, r AS INTEGER, i AS INTEGER, j AS INTEGER, k AS INTEGER
CALL LongToNb(x1, 0)
X = 0
r = 0
k = 0
FOR i = 1 TO a.len
    FOR j = 1 TO b.len
        X = GetChif%(a, i) * GetChif%(b, j) + GetChif%(x1, i + j - 1) + r
        CALL PutChif(x1, i + j - 1, X MOD 10)
        r = INT(X / 10)
    NEXT j
    k = i + b.len - 1
    WHILE r > 0
        k = k + 1
        X = GetChif%(x1, k) + r MOD 10
        CALL PutChif(x1, k, X)
        r = INT(r / 10)
    WEND
NEXT i
x1.len = k
CALL CopyNb(c, x1)
END SUB

SUB AddLongNb (dst AS nombre, a AS nombre, p AS LONG)
DIM x AS nombre, b AS nombre
DIM i AS INTEGER, r AS INTEGER, k AS INTEGER, n AS INTEGER
CALL LongToNb(b, p)
n = a.len
IF b.len > n THEN n = b.len
r = 0
FOR i = 1 TO n
    k = VAL(MID$(a.str, i, 1)) + VAL(MID$(b.str, i, 1)) + r
    r = INT(k / 10)
    k = k MOD 10
    MID$(x.str, i, 1) = CHR$(48 + k)
NEXT i
WHILE r <> 0
    n = n + 1
    CALL ErrNb(n)
    k = r MOD 10
    r = INT(r / 10)
    MID$(x.str, n, 1) = CHR$(48 + k)
WEND
x.len = n
CALL CopyNb(dst, x)
END SUB

SUB SubLongNb (dst AS nombre, a AS nombre, p AS LONG)
DIM s AS nombre
CALL LongToNb(s, p)
CALL SubNb(dst, a, s)
END SUB

SUB MulLongNb (d AS nombre, s AS nombre, X AS LONG)
' d=s*x
DIM i AS INTEGER, n AS INTEGER, r AS INTEGER, c AS INTEGER
IF X = 0 THEN
    d.len = 0
    d.str = STRING$(LenNb, "0")
ELSE
    CALL CopyNb(d, s)
    r = 0
    n = d.len
    FOR i = 1 TO n
        c = VAL(MID$(d.str, i, 1)) * X + r
        r = INT(c / 10)
        c = c MOD 10
        MID$(d.str, i, 1) = CHR$(48 + c)
    NEXT i
    WHILE r <> 0
        n = n + 1
        CALL ErrNb(n)
        c = r MOD 10
        MID$(d.str, n, 1) = CHR$(48 + c)
        r = INT(r / 10)
    WEND
    d.len = n
END IF
END SUB

SUB ModNb (dst AS nombre, a AS nombre, b AS nombre)
DIM q AS nombre, r AS nombre
CALL Div0(q, r, a, b)
CALL CopyNb(dst, r)
END SUB

SUB DivNb (dst AS nombre, a AS nombre, b AS nombre)
DIM q AS nombre, r AS nombre
CALL Div0(q, r, a, b)
CALL CopyNb(dst, q)
END SUB

SUB pgcdNb (p AS nombre, p1 AS nombre, p2 AS nombre)
DIM a AS nombre, b AS nombre, q AS nombre, r AS nombre
CALL CopyNb(a, p1)
CALL CopyNb(b, p2)
CALL ModNb(r, a, b)
DO WHILE NOT (ZNb%(r))
    CALL CopyNb(a, b)
    CALL CopyNb(b, r)
    CALL ModNb(r, a, b)
LOOP
CALL CopyNb(p, b)
END SUB

SUB ppcmNb (p AS nombre, p1 AS nombre, p2 AS nombre)
DIM pg AS nombre, x1 AS nombre, k1 AS nombre, k2 AS nombre
CALL pgcdNb(pg, p1, p2)
CALL DivNb(k2, p2, pg)
CALL MulNb(p, p1, k2)
END SUB

SUB Div0 (quotient AS nombre, reste AS nombre, a AS nombre, b AS nombre)
DIM X AS nombre, M AS nombre, M1 AS nombre
DIM q AS nombre, T2 AS nombre
DIM k AS LONG, n AS LONG

CALL LongToNb(q, 0)
CALL CopyNb(X, a)
IF GENb%(a, b) THEN
    CALL Tranche(X, T2, a, b)
    n = Div1&(X, b)
    CALL LongToNb(q, n)
    CALL LongToNb(M, n)
    CALL MulNb(M1, b, M)
    CALL SubNb(X, X, M1)
    DO
        IF T2.len = 0 THEN EXIT DO
        CALL ShiftNb(X, T2)
        n = Div1&(X, b)
        IF n = 0 THEN
            CALL Mul10Nb(q)
        ELSE
            CALL LongToNb(M, n)
            CALL ConcateNb(q, q, M)
            CALL MulLongNb(M, b, n)
            CALL SubNb(X, X, M)
        END IF
    LOOP
END IF
CALL CopyNb(quotient, q)
CALL CopyNb(reste, X)
END SUB

FUNCTION Div1& (n1 AS nombre, n2 AS nombre)
DIM q AS nombre, i AS LONG
CALL CopyNb(q, n2)
CALL Pause
i = 1
DO WHILE LENb%(q, n1)
    i = i + 1
    CALL AddNb(q, q, n2)
LOOP
Div1& = i - 1
END FUNCTION


SUB PuisNb (p AS nombre, p1 AS nombre, p2 AS nombre)
' calcul rapide de a^b
' y=a;z= 1
'Tant que k >0 faire :
' Si k impair : z=z*y
' k=int(k/2)
' Si k >0 ; y=y*y
' Si k = 0 , on sort de la boucle
' fin tant que
' le résultat est dans z
DIM x AS nombre,y as nombre,z as nombre,k as nombre,deux as nombre
  call LongToNb (deux, 2)
  CALL CopyNb( k,p2)
  CALL CopyNb( y,p1)
  CALL LongToNb(z, 1)
  do while GT0Nb% (k)
if IsImPairNb% (k) then call MulNb (z, z, y)
call DivNb (k, k, deux)
    if ZNb%(k) then exit do
    if GT0Nb%(k) then  call MulNb (y, y, y)
  loop
  CALL CopyNb( p,z)
end sub

FUNCTION Somme& (p AS nombre)
DIM ret AS LONG, i AS LONG
ret = 0
for i=1 to p.len
ret=ret+GetChif%(p,i)
next i
Somme& = ret
END FUNCTION


SUB Factorielle (p AS nombre, p1 AS LONG)
DIM ret AS nombre, T AS nombre, i AS LONG
CALL LongToNb(ret, 1)
FOR i = 2 TO p1
locate 40,1 i
    CALL LongToNb(T, i)
    CALL MulNb(ret, ret, T)
NEXT i
CALL CopyNb(p, ret)
END SUB


SUB debNb (dst AS nombre, src AS nombre, p1 AS LONG)
DIM s AS STRING, i AS INTEGER, n AS INTEGER
dst.len = p1
dst.str = STRING$(LenNb, "0")
n = src.len - p1
FOR i = 1 TO p1: MID$(dst.str, i, 1) = MID$(src.str, n + i, 1): NEXT i
END SUB

SUB finNb (dst AS nombre, src AS nombre, p1 AS LONG)
DIM s AS STRING, i AS INTEGER
dst.len = p1
dst.str = STRING$(LenNb, "0")
FOR i = 1 TO p1: MID$(dst.str, i, 1) = MID$(src.str, i, 1): NEXT i
END SUB
'-----------------------------------------------
FUNCTION GT0Nb% (n1 AS nombre)
dim z as nombre
  call ZeroNb(z)
  GT0Nb%=GTNb% (n1,z)
END FUNCTION


FUNCTION IsPairNb% (n1 AS nombre)
dim ret as integer
ret=Vrai
if GetChif% (n1,1) mod 2=1 then ret=Faux
IsPairNb%=ret
END FUNCTION


FUNCTION IsImPairNb% (n1 AS nombre)
IsImPairNb%=not(IsPairNb%(n1))
END FUNCTION

FUNCTION ZNb% (n1 AS nombre)
DIM ret AS INTEGER, i AS INTEGER
ret = Vrai
FOR i = 1 TO n1.len
    IF NOT (MID$(n1.str, i, 1) = "0") THEN
        ret = Faux
        EXIT FOR
    END IF
NEXT i
ZNb% = ret
END FUNCTION

FUNCTION LTNb% (a AS nombre, b AS nombre)
DIM ret AS INTEGER, i AS INTEGER
ret = Faux
SELECT CASE a.len
    CASE IS < b.len
        ret = Vrai
    CASE IS > b.len
        ret = Faux
    CASE IS = b.len
        FOR i = a.len TO 1 STEP -1
            IF VAL(MID$(a.str, i, 1)) > VAL(MID$(b.str, i, 1)) THEN
                ret = Faux
                EXIT FOR
            ELSE
                IF VAL(MID$(a.str, i, 1)) < VAL(MID$(b.str, i, 1)) THEN
                    ret = Vrai
                    EXIT FOR
                END IF
            END IF
        NEXT i
END SELECT
LTNb% = ret
END FUNCTION

FUNCTION EQNb% (n1 AS nombre, n2 AS nombre)
DIM ret AS INTEGER, i AS INTEGER
ret = Faux
IF n1.len = n2.len THEN
    ret = Vrai
    FOR i = n1.len TO 1 STEP -1
        IF VAL(MID$(n1.str, i, 1)) <> VAL(MID$(n2.str, i, 1)) THEN
            ret = Faux
            EXIT FOR
        END IF
    NEXT i
END IF
EQNb% = ret
END FUNCTION

FUNCTION LENb% (n1 AS nombre, n2 AS nombre)
DIM ret AS INTEGER
ret = Faux
IF LTNb%(n1, n2) THEN
ret = Vrai
else
  IF EQNb% (n1, n2) then
   ret=Vrai
  end if
end if
LENb% = ret
END FUNCTION

FUNCTION NEQNb% (n1 AS nombre, n2 AS nombre)
NEQNb% = NOT (EQNb%(n1, n2))
END FUNCTION

FUNCTION GENb% (n1 AS nombre, n2 AS nombre)
DIM ret AS INTEGER
ret = Vrai
IF LTNb%(n1, n2) THEN ret = Faux
GENb% = ret
END FUNCTION

FUNCTION GTNb% (n1 AS nombre, n2 AS nombre)
DIM ret AS INTEGER
ret = Vrai
IF LENb%(n1, n2) THEN ret = Faux
GTNb% = ret
END FUNCTION

Posté par
Arowbaz
re : Manipuler de très grands nombres ? 28-06-14 à 21:17

Mais en java (je défend mon langage :p) c'est juste ^^ :

Citation :
public static void main(String[] args) {
BigInteger bi = new BigInteger("1");
for (int i = 2; i < 300; i++)
bi = bi.multiply(new BigInteger(Integer.toString(i)));
System.out.println(bi);
}


et on obtient en moins d'une seconde :

1020191707388135453451234870990895431295296013911923331389255804198255110589056224885050971408258577833130492962339087896214213025863
3438474228097596899151994707515897675731820133600407192541739228475198845230116892957508810729875476645506819214961012963658464782987
5145351075326925507090274145879816373376226225122768570764560647883318820166055483409238833395058848823113370742011576574688777752861
1689567167232647229501179173791849700963754690523849434274283126508788600484117443856454940778122664181980317589402026874109374624612
936056832000000000000000000000000000000000000000000000000000000000000000000000000

(exactement 613 chiffres ^^, à vérifier cependant ...)

édit Océane

Posté par
amateur
re : Manipuler de très grands nombres ? 30-06-14 à 21:28

Bonjour Arowbaz,

Mon but était de répondre à la question :

Citation :
je recherche un moyen de composer des algorithmes sur ordinateur manipulant de très grands entiers sans les arrondir
et non de plébisciter tel ou tel langage.

Afin d'améliorer et de passer à une version dynamique des nombres,
comment est gérée l'allocation mémoire en java des BigInteger ?
Y a t-il une limite ou le programme se place comme en Haskell en indiquant un out of memory?

Posté par
weierstrass
re : Manipuler de très grands nombres ? 01-07-14 à 06:57

Bonjour,
Je ne connais rien à se sujet, mais voila un topic qui traitait un peu du même sujet.
Méthodes de calculs sur des grands nombres

Posté par
verdurin
re : Manipuler de très grands nombres ? 02-07-14 à 21:34

Bonsoir,
je crois que le code de GIAC (Xcas) est libre.
Il doit être possible de demander des renseignement à Bernard Parisse ici

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !