6,258 matches
-
mediu de pași necesar atunci când "a" și "b" sunt ambele alese aleator (cu distribuție uniformă) între 1 și "n" Înlocuind formula aproximativă pentru "T"("a") în această ecuație rezultă o estimare a lui "Y"("n") La fiecare pas "k" al algoritmului lui Euclid, se calculează câtul "q" și restul "r" pentru o pereche dată de întregi "r" și "r" Costul computațional al fiecărui pas este asociat cu găsirea lui "q", întrucât restul "r" poate fi calculat rapid din "r", "r", and
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
pas este asociat cu găsirea lui "q", întrucât restul "r" poate fi calculat rapid din "r", "r", and "q" Costul computațional al împărțirii numerelor pe "h" biți scalează ca "O"("h"("ℓ"+1)), unde "ℓ" este lungimea câtului. Pentru comparație, algoritmul original al lui Euclid bazat pe scăderi poate fi mult mai lent. O singura împărțire de întregi este echivalentă cu "q" scăderi ("q" este câtul împărțirii). Dacă raportul "a" supra "b" este foarte mare, și câtul este mare și este
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
probabilitatea ca la împărțire să rezulte câtul 1, 2, 3, sau 4 este aproximativ 41,5%, 17,0%, 9,3%, respectiv 5,9%. Întrucât operația de scădere este mai rapidă decât cea de împărțire, mai ales în cazul numerelor mari, algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri. Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid. Combinarea numărului estimat de pași cu calculul computațional estimat al fiecărui pas arată că algoritmul lui Euclid
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
5,9%. Întrucât operația de scădere este mai rapidă decât cea de împărțire, mai ales în cazul numerelor mari, algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri. Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid. Combinarea numărului estimat de pași cu calculul computațional estimat al fiecărui pas arată că algoritmul lui Euclid are o creștere pătratică ("h") în funcție de numărul de cifre "h" al celor două numere inițiale "a" și "b". Fie "h", "h
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numerelor mari, algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri. Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid. Combinarea numărului estimat de pași cu calculul computațional estimat al fiecărui pas arată că algoritmul lui Euclid are o creștere pătratică ("h") în funcție de numărul de cifre "h" al celor două numere inițiale "a" și "b". Fie "h", "h", ..., "h" numărul de cifre ale resturilor succesive "r", "r", ..., "r". Cum numărul de pași "N" crește liniar
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numărul de cifre "h" al celor două numere inițiale "a" și "b". Fie "h", "h", ..., "h" numărul de cifre ale resturilor succesive "r", "r", ..., "r". Cum numărul de pași "N" crește liniar cu "h", timpul de execuție este limitat de Algoritmul lui Euclid este folosit pe scară largă în practică, mai ales pentru numere mici, datorită simplității sale. Pentru comparație, se poate determina eficiența unor alternative la algoritmul lui Euclid. O abordare ineficientă a găsirii CMMDC a două numere naturale "a
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
de pași "N" crește liniar cu "h", timpul de execuție este limitat de Algoritmul lui Euclid este folosit pe scară largă în practică, mai ales pentru numere mici, datorită simplității sale. Pentru comparație, se poate determina eficiența unor alternative la algoritmul lui Euclid. O abordare ineficientă a găsirii CMMDC a două numere naturale "a" și "b" este de a le calcula toți divizorii comuni; CMMDC este, atunci, cel mai mare dintre aceștia. Divizorii comuni se pot găsi împărțind succesiv ambele numere
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ambelor numere. Așa cum se arată mai sus, CMMDC este egal cu produsul factorilor primi comuni ai celor două numere "a" și "b". Metodele actuale de factorizare sunt și ele ineficiente; multe alte sisteme criptografice se bazează tocmai pe această ineficiență. Algoritmul CMMDC binar este o alternativă eficientă care înlocuiește împărțirea cu operații mai rapide, exploatând reprezentările binare utilizate de calculatoare. Această alternativă, însă, scalează și ea ca "O"("h"²). Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
binar este o alternativă eficientă care înlocuiește împărțirea cu operații mai rapide, exploatând reprezentările binare utilizate de calculatoare. Această alternativă, însă, scalează și ea ca "O"("h"²). Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel ca algoritmul lui Euclid. Eficiența se poate îmbunătăți examinând doar primele cifre ale numerelor "a" și "b". Algoritmul binar poate fi extins la alte baze (algoritmi k-ari), cu creșteri ale vitezei de până la cinci ori. O abordare recursivă pentru numere întregi foarte
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
de calculatoare. Această alternativă, însă, scalează și ea ca "O"("h"²). Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel ca algoritmul lui Euclid. Eficiența se poate îmbunătăți examinând doar primele cifre ale numerelor "a" și "b". Algoritmul binar poate fi extins la alte baze (algoritmi k-ari), cu creșteri ale vitezei de până la cinci ori. O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici, cum ar fi cel
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ca "O"("h"²). Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel ca algoritmul lui Euclid. Eficiența se poate îmbunătăți examinând doar primele cifre ale numerelor "a" și "b". Algoritmul binar poate fi extins la alte baze (algoritmi k-ari), cu creșteri ale vitezei de până la cinci ori. O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici, cum ar fi cel al lui Schönhage și cel al lui Stehlé
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cifre ale numerelor "a" și "b". Algoritmul binar poate fi extins la alte baze (algoritmi k-ari), cu creșteri ale vitezei de până la cinci ori. O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici, cum ar fi cel al lui Schönhage și cel al lui Stehlé și Zimmermann. Acești algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată mai sus. Aceste metode subcuadratice scalează în general ca După cum s-a
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ale vitezei de până la cinci ori. O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici, cum ar fi cel al lui Schönhage și cel al lui Stehlé și Zimmermann. Acești algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată mai sus. Aceste metode subcuadratice scalează în general ca După cum s-a descris mai sus, algoritmul lui Euclid este folosit pentru a găsi cel mai mare divizor comun a două
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici, cum ar fi cel al lui Schönhage și cel al lui Stehlé și Zimmermann. Acești algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată mai sus. Aceste metode subcuadratice scalează în general ca După cum s-a descris mai sus, algoritmul lui Euclid este folosit pentru a găsi cel mai mare divizor comun a două numere naturale (numere întregi pozitive). Acesta poate
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ar fi cel al lui Schönhage și cel al lui Stehlé și Zimmermann. Acești algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată mai sus. Aceste metode subcuadratice scalează în general ca După cum s-a descris mai sus, algoritmul lui Euclid este folosit pentru a găsi cel mai mare divizor comun a două numere naturale (numere întregi pozitive). Acesta poate fi, însă, generalizat la numere reale, și la sisteme de numere mai exotice, cum ar fi polinoamele, întregii cuadratici
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cel mai mare divizor comun a două numere naturale (numere întregi pozitive). Acesta poate fi, însă, generalizat la numere reale, și la sisteme de numere mai exotice, cum ar fi polinoamele, întregii cuadratici și cuaternionii Hurwitz. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esențială în multe demonstrații din
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esențială în multe demonstrații din teoria numerelor. Algoritmul lui Euclid se poate aplica și numerelor reale, așa cum arată Euclid în Cartea 10 din "Elementele". Scopul algoritmului este identificarea unui număr real "g" astfel încât două numere reale, "a" și "b", sunt multipli întregi ai acestuia: "a" = "mg" și "b
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esențială în multe demonstrații din teoria numerelor. Algoritmul lui Euclid se poate aplica și numerelor reale, așa cum arată Euclid în Cartea 10 din "Elementele". Scopul algoritmului este identificarea unui număr real "g" astfel încât două numere reale, "a" și "b", sunt multipli întregi ai acestuia: "a" = "mg" și "b" = "ng", unde "m" și "n" sunt întregi. Această identificare este echivalentă cu găsirea unei relații întregi între două
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
și "b" = "ng", unde "m" și "n" sunt întregi. Această identificare este echivalentă cu găsirea unei relații întregi între două numere reale "a" și "b"; adică, ea determină întregii "s" și "t" astfel întât "sa" + "tb" = 0. Euclid folosește acest algoritm pentru a trata chestiunea lungimilor incomensurabile. Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile "r" sunt numere reale, deși câturile "q" sunt, ca și mai înainte, întregi. Al doilea este
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
sunt întregi. Această identificare este echivalentă cu găsirea unei relații întregi între două numere reale "a" și "b"; adică, ea determină întregii "s" și "t" astfel întât "sa" + "tb" = 0. Euclid folosește acest algoritm pentru a trata chestiunea lungimilor incomensurabile. Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile "r" sunt numere reale, deși câturile "q" sunt, ca și mai înainte, întregi. Al doilea este că algoritmul nu este garantat că se
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
a trata chestiunea lungimilor incomensurabile. Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile "r" sunt numere reale, deși câturile "q" sunt, ca și mai înainte, întregi. Al doilea este că algoritmul nu este garantat că se termină într-un număr finit "N" de pași. Dacă se termină, atunci fracția "a"/"b" este un număr rațional, adică este raportul a două numere întregi și poate fi scris ca fracție continuă finită ["q
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
se termină într-un număr finit "N" de pași. Dacă se termină, atunci fracția "a"/"b" este un număr rațional, adică este raportul a două numere întregi și poate fi scris ca fracție continuă finită ["q"; "q", "q", ..., "q"]. Dacă algoritmul nu se oprește, atunci fracția "a"/"b" este un număr irațional și poate fi descris de o fracție continuă infinită ["q"; "q", "q", ...]. Exemple de fracții continue infinite sunt raportul de aur "φ" = [1; 1, 1, ...] și rădăcina pătrată a
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
un număr irațional și poate fi descris de o fracție continuă infinită ["q"; "q", "q", ...]. Exemple de fracții continue infinite sunt raportul de aur "φ" = [1; 1, 1, ...] și rădăcina pătrată a lui 2, √2 = [1; 2, 2, ...]. În general, algoritmul nu se oprește, întrucât aproape toate rapoartele "a"/"b" de două numere reale sunt iraționale. O fracție continuă infinită poate fi trunchiată la un pas "k" ["q"; "q", "q", ..., "q"] pentru a da o aproximație a raportului "a"/"b", aproximație
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
și descompune în polinoame ireductibile, structuri analoage numerelor prime din mulțimea numerelor întregi. Cel mai mare divizor comun "g"("x") al două polinoame "a"("x") și "b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q"("x") și un polinom rest "r"("x") care satisfac ecuația recursivă unde "r"("x") = "a"("x") și "r
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cu termenul dominant al lui "r"("x"); aceasta asigură că gradul fiecărui rest este mai mic decât gradul predecesorului său grad["r"("x")] < grad["r"("x")]. Întrucât gradul este un număr întreg nenegativ, și întrucât el scade la fiecare pas, algoritmul lui Euclid se încheie într-un număr finit de pași. Ultimul rest nenul este cel mai mare divizor comun al celor două polinoame inițiale, "a"("x") și "b"("x"). De exemplu, fie următoarele polinoame de gradul patru, care fiecare se
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]