Carré ou pas ?

Tu calcules sa racine carrée entière (integer square root) ?

L'algorithme (à la potence, par tranche de deux chiffres) de calcul de racine carrée d'un nombre de taille (nombre de chiffres) $\tau$ est polynomial en $\tau$, en $O(\tau^2)$ je dirais. Tout à fait raisonnable, donc.

Hello,
Dans ma vieille note, je dis qu'il faut choisir $a_0$ tel que $a_0^2 \ge a$, avec $a_0$ le plus petit possible. Je ne me souviens plus comment on peut le faire intelligemment (sans utiliser la racine carrée entière évidemment). Dans mon premier post, j'ai pris $a_0 = a$. Là, je recommence (avec la même donnée) en trichant un tantinet pour partir d'un $a_0$ moindre, noté $x$ ci-dessous.

[color=#000000]
> a := NextPrime(10^70) * NextPrime(10^100) * NextPrime(10^120) ;
> F := func < x | (x + a div x) div 2 > ;
> x := 2^((Ilog(2,a) + 1) div 2) ;  // CQ, gros tricheur
> x^2 ge a ;
true
> count := 0 ;
> time while true do                                             
time|while> y := F(x) ;
time|while> if y ge x then break ; end if ;
time|while> x := y ; count := count + 1 ;
time|while> end while ;
Time: 0.000
> count ;
8
> x^2 le a and a lt (x+1)^2 ;
true
[/color]

C'est juste pour montrer la sensibilité par rapport au point de départ $a_0$.

L'algorithme "à la potence" en découpant en paquets de deux chiffres ne se débrouille pas mal. En Sage :

def racent(n) :
    L=n.digits(100)
    a=0
    r=0
    while L != [] :
        p=L.pop()
        r=100*r+p
        t=0
        while (20*a+t+1)*(t+1)<=r :
            t+=1
        r=r-(20*a+t)*t
        a=10*a+t
    if r==0 : print n,"est un carré et sa racine carrée est", a
    else : print n,"n'est pas un carré et la partie entière de sa racine carrée est",a

Un essai avec un non carré :

n = next_prime(10^70) * next_prime(10^100) * next_prime(10^120)
%time racent(n)

100000000000000000000000000000000000000000000000000000000000000000000330000000000000000000000000002670000000000000000007900000000000000000000000000000000000000000000008811000000000000000026070000000000000000000000000210930000000000000000000000000000000000000000000000000000000000000000696069 n'est pas un carré et la partie entière de sa racine carrée est 10000000000000000000000000000000000000000000000000000000000000000000016500000000000000000000000000133500000000000000000394999999999999999986387500
CPU times: user 1.31 ms, sys: 0 ns, total: 1.31 ms
Wall time: 874 µs

et un essai avec un carré :

n=next_prime(ZZ(17*range(10),10))^2*next_prime(ZZ(17*range(9),10))^2
%time racent(n)

7494740442802098708819262955323943219619028627667319904288348303186392067854111534452995987780416681434232973286043022374187866927619733001745655425367439406561176034422328567272389892769129178705810126398012626836920021207613178837196440179239864631186420667989001390663755734664384556071466536746583687349340421049741559489948004401797128440910758881241500049653188958640585308462313669045151357371867591139748440718423428004845596674709260244183750979745992199529695986351801821057064556456851795087241809447022148069663249203782599597568992218174010791546084133203382168990054595919749654136755494699793265419164314346341699613517052129670249 est un carré et sa racine carrée est 86572168985200426875063252664049535242948163500838026326627012609205911237463801100289590086572168985200426875063252664049535242948163500838026326627069905349798090535253301356812486926085405483012697338705426524274699442831626734687319463872888736791445664083301356812486926085405483012697338705426524274699442831626915693
CPU times: user 4.23 ms, sys: 11 µs, total: 4.24 ms
Wall time: 3.22 ms

@reuns : tu décris l'algorithme "à la potence" bien connu que j'ai codé (as-tu lu le code ?), sauf que dans cet algorithme bien connu on a calculé $r=n-a^2$, et qu'on essaie $t$ jusqu'à ce que $(2ab+t+1)(t+1)>b^2r+m$. On remplace ensuite $a$ par $ab+t$ et $r$ par $b^2r+m-(2ab+t)t$.

Je signale également, en ce Mercredi 8 Mai 2019, un critère qu'il est pas mal : un nombre entier $N$ est un carré si et seulement si il existe un nombre entier $c$ tel que $N^2 - 4 = (c-2)(c + 2)$. POUF-POUF (suite à GBZM) Bien sûr, je voulais dire $N - 4 = (c-2)(c+ 2)$

@GBZM : vu (et corrigé). Et si ce n'était pas de l'humour ?

Bonjour à tous

Une réponse à la question de nodgim:

$a(:=7441)$ est premier avec $10$ et la congruence $x^2=a$ modulo $10^4$ a une solution $x_1 (:=2729)$.

Elle a donc exactement huit solutions: elle équivaut au système ( $x^2=a$ modulo $2^4$ ET $x^2=a$ modulo $5^4$), la première congruence ayant exactement quatre solutions et la seconde deux.

$x_1$ étant solution, quatre des huit solutions sont $ \pm x_1, \pm (x_1+5000)$.

Une cinquième $(:=x_5)$ s'obtient en résolvant $(x_1+ \epsilon 1250)^2=a$ modulo $10^4$, soit $\epsilon x_1+625=0$ modulo $4$, ou encore, vu que $625=1$ modulo $4$ et que $x_1:=2729=1$ modulo $4$, $\epsilon=-1$ et donc $x_5=x_1-1250$.

Les quatre autres solutions sont donc $ \pm x_5, \pm (x_5+5000)$.

Cordialement

Paul