Algorithmi nvmerici

Svmmarivm

Lectiones priores hvivs partis docvervnt circvitvs scribere et de eis cvm invariante et variante ratiocinari; haec lectio eam rationem ad qvattvor algorithmos nvmericos classicos adhibet, compvtatris antiqviores et adhvc in vsv. Examen primalitatis per divisiones tentativas, qvod ad $\sqrt{n}$ consistit ob cavsam qvae demonstratvr, et cvivs condicio sistendi exvndat si neglegenter scribitvr. Algorithmvs Evclidis ad maximvm commvnem divisorem, cvm svo invariante, sva terminatione, svis insidiis in nvmeris negativis et sva comparatione cvm std::gcd. Mvtatio basis per divisiones svccessivas et regvla Horneri, qvae nvmervm ex cifris svis restitvit et polynomivm eodem schemate aestimat. Et bisectio, qvae radicem approximat intervallvm in dvo secando, theoremate valoris intermedii firmata, cvm nvmero gyrorvm qvi ante compvtatvr. Qvisqve algorithmvs vt obiectvm mathematicvm proponitvr: cvm demonstratione evm facere qvod dicit, demonstratione evm desinere et prima nvmeratione gradvvm eivs.

Proposita discendi

Examen primalitatis per divisiones vsqve ad $\sqrt{n}$ implementare et explicare cvr satis sit ad $\sqrt{n}$ pervenire.
Algorithmvm Evclidis implementare, eivs invariantem envntiare (maximvs commvnis divisor non mvtatvr) et cvm std::gcd comparare.
Nvmervm in aliam basim per divisiones svccessivas convertere et repraesentationem positionalem, vel polynomivm, regvla Horneri aestimare.
Radicem bisectione vsqve ad tolerantiam approximare, et compvtare qvot iterationes postvlet.

Divisores et nvmeri primi

Divisiones tentativae

Integer $n \geq 2$ primvs est si soli eivs divisores positivi svnt 1 et $n$ ; si alivm habet, compositvs est; 0 et 1 neqve hoc neqve illvd svnt. Definitio statim algorithmvm svggerit: qvemqve candidatvm $d$ inter 2 et $n - 1$ temptare et nvmervm compositvm declarare simvl ac vnvs evm dividat. Est circvitvs minimi divisoris lectionis Circvitvs, et rectvs est. Atqvi pro primo decem cifrarvm fere centies milies centena milia divisionvm facit, et fere omnes invtiles svnt, ob cavsam seqventem.

PropositioSatis est vsqve ad

\sqrt{n}

temptare

Si $n \geq 2$ compositvs est, divisorem $d$ habet cvm $2 \leq d \leq \sqrt{n}$ .

Demonstratio

$n = a \cdot b, \quad 2 \leq a \leq b$
Si $n$ compositvs est, vt prodvctvm dvorvm factorvm scribitvr, qvorvm nevter 1 nec $n$ aeqvat. Minor dvorvm $a$ nominatvr.
$a^2 \leq a \cdot b = n$
Mvltiplicando $a \leq b$ per positivvm $a$ fit $a^2 \leq ab = n$ , vnde $a \leq \sqrt{n}$ : minor factor cvivsqve factorisationis a sinistra ipsivs $\sqrt{n}$ iacet.
$d \leq \sqrt{n} \iff \frac{n}{d} \geq \sqrt{n}$
Divisores igitvr in paribvs $(d, n/d)$ apparent, circa $\sqrt{n}$ reflexis: cvm $n = 36$ , paria svnt $(2, 18)$ , $(3, 12)$ , $(4, 9)$ et $(6, 6)$ . Si nvllvs candidatvs vsqve ad $\sqrt{n}$ ipsvm $n$ dividit, nec vllvs vltra dividit, qvia socivs eivs privs apparvisset.

Ex qvo seqvitvr nvmervm divisionvm ab circiter $n$ ad circiter $\sqrt{n}$ descendere: pro $n$ prope vicies milies centena milia, a vicies milies centenis milibvs ad qvadraginta sex milia. Programma formam vexilli lectionis Circvitvs rectos designare adhibet: isPrime initio vervm est et circvitvs id exstingvit si divisorem invenit.

Programma in C++

#include <iostream>#include <print>int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("{} primvs est", n);    } else {        std::println("{} primvs non est", n);    }}

Data programmati inserenda

2147483647

Exitvs

2147483647 primvs est

Tria consilia animadversionem merentvr. Vexillvm per n >= 2 initialisatvr, ita vt 0, 1 et nvmeri negativi non primi declarentvr sine ingressv in circvitvm: hvnc casvm oblivisci error typicvs est, qvia cvm $n = 1$ circvitvs nvllvm gyrvm facit et programma 1 primvm declararet. Condicio ipsivs for dvo membra habet: vexillvm, qvod circvitvm in primo divisore sistit, et limitem. Et limes scribitvr d <= n / d, qvod, pro integris positivis, aeqvivalet ipsi $d^2 \leq n$ (divisio integra trvncat, sed $d$ qvotientem trvncatvm non svperat prorsvs cvm $n/d$ non svperat, qvia $d$ integer est). Nvmervs introitvs, $2^{31} - 1$ , maximvs int est et primvs; programma id decernit $46\,339$ residvis, eis candidatorvm a 2 ad $46\,340$ .

Invarians circvitvs est: nvllvs integer a 2 ad $d - 1$ ipsvm $n$ dividit, dvm vexillvm vervm manet. Valet in ingressv, cvm intervallvm a 2 ad 1 vacvvm est; conservatvr, qvia si $d$ ipsvm $n$ non dividit, intervallvm nvmero crescit qvi evm non dividit; et in egressv cvm vexillo vero, invarians et condicio falsa, $d^2 > n$ , simvl dicvnt nvllvm candidatvm vsqve ad $\sqrt{n}$ ipsvm $n$ dividere, qvod propositio postvlat. Varians est nvmervs candidatorvm qvi temptandi restant, id est integrorvm inter $d$ et $\sqrt{n}$ : vno in qvoqve gyro decrescit nec infra nihil descendit.

Condicio qvae exvndat

Modvs natvralis limitem scribendi est d * d <= n, et error est. Cvm introitv priore circvitvs ad $d = 46\,341$ pervenit, et tvm prodvctvm $46\,341^2 = 2\,147\,488\,281$ maximvm int svperat.

Programma in C++

#include <iostream>#include <print>int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("Primvs? {}", isPrime);}

Data programmati inserenda

2147483647

Exitvs

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

Programma codice 1 finitvm est.

Detector modi agendi indefiniti programma in prodvcto sistit. Sine eo, exvndatio cvm signo modvs agendi indefinitvs est, et norma non dicit qvid accidat. Qvod cvm GCC in Linux observatvr, cvm optimizatione et sine ea, instrvctivvm est: prodvctvm circvmvertitvr et negativvm fit vel minvs qvam $n$ , et cvm nvllvs int maximvm svperet, condicio d * d <= n nvmqvam iam impleri desinit; circvitvs candidatos temptare pergit per circiter vicies milies centena milia gyrorvm, donec ad $d = n$ pervenit, qvod ipsvm $n$ dividit, et programma nvmervm primvm compositvm declarat. Error exvndationis non vt exvndatio se ostendit, sed vt responsvm falsvm. Forma d <= n / d exvndare non potest, qvia dividit pro mvltiplicando; lectio Bit et bibliotheca mathematica alivd effvgivm praebebat, limitem semel per std::sqrt compvtare, sed tvm accvratio limitis a rotvndatione virgvlae flvitantis pendet, et divisio integra eam difficvltatem non habet.

Lectio «Nvmeri primi et theorema fvndamentale arithmeticae», cvrsvs Algebra et Geometria I, demonstrat omnem integrvm maiorem qvam 1 prodvctvm primorvm vno tantvm modo esse; divisiones tentativae via directissima svnt id prodvctvm inveniendi, $n$ per qvemqve divisorem inventvm dividendo et cvm qvotiente pergendo.