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
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 :
(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 ...)
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
Mais en java (je défend mon langage :p) c'est juste ^^ :
Bonjour Arowbaz,
Mon but était de répondre à la question :
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
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :