Discussion:
A démontrer
(trop ancien pour répondre)
ast
2018-03-02 17:26:14 UTC
Permalink
Bonjour

Soient a, x deux entiers avec x > a

Soient

y = (x + a/x)/2
z = (x + a//x)//2

où // désigne la division entière

On a de façon évidente z <= y

mais sauriez-vous montrer que y-1 < z <= y ?


J'en ai besoin pour établir le critère d'arrêt
d'un algorithme de calcul de racine carrée entière
(fonction isqrt) avec la méthode de Héron.

A priori c'est vrai car j'ai fais de nombreux tests,
mais j'aimerais une preuve

cldt
ast
2018-03-02 17:28:21 UTC
Permalink
Post by ast
Bonjour
Soient a, x deux entiers avec x > a
erreur: x > sqrt(a)
Post by ast
Soient
y = (x + a/x)/2
z = (x + a//x)//2
où // désigne la division entière
On a de façon évidente z <= y
mais sauriez-vous montrer que y-1 < z <= y ?
J'en ai besoin pour établir le critère d'arrêt
d'un algorithme de calcul de racine carrée entière
(fonction isqrt) avec la méthode de Héron.
A priori c'est vrai car j'ai fais de nombreux tests,
mais j'aimerais une preuve
cldt
Samuel DEVULDER
2018-03-02 20:48:17 UTC
Permalink
Post by ast
y = (x + a/x)/2
z = (x + a//x)//2
où // désigne la division entière
donc a//x = int(a/x)
Post by ast
On a de façon évidente z <= y
mais sauriez-vous montrer que y-1 < z <= y ?
ben y-z = (a/x - int(a/x))/2

Pour tout réel t, 0<=t-int(t)<1, donc y-z<1/2 or 1/2 < 1, donc y-z < 1,
soit y-1<z.

Où est la difficulté? J'ai loupé un truc?

sam.
ast
2018-03-03 07:12:29 UTC
Permalink
Post by Samuel DEVULDER
Post by ast
y = (x + a/x)/2
z = (x + a//x)//2
où // désigne la division entière
donc a//x = int(a/x)
Post by ast
On a de façon évidente z <= y
mais sauriez-vous montrer que y-1 < z <= y ?
ben y-z = (a/x - int(a/x))/2
Je ne vois pas d'où sort cette formule, je crois
même qu'elle est fausse

Mais ce n'est pas très difficile effectivement

si x + a//x est pair:
(x + a//x)//2 = x/2 + (a//x)/2
y-z = x/2 + (a/x)/2 - x/2 - (a//x)/2 = 1/2 (a/x -a//x) < 1/2 < 1
ok

si x + a//x est impair:
(x + a//x)//2 = x/2 + (a//x)/2 - 1/2
y-z = x/2 + (a/x)/2 - x/2 -(a//x)/2 + 1/2 = 1/2 (a/x - a//x) + 1/2 < 1
ok
Samuel DEVULDER
2018-03-03 09:11:35 UTC
Permalink
Post by ast
Post by Samuel DEVULDER
Post by ast
y = (x + a/x)/2
formule (1)
Post by ast
Post by Samuel DEVULDER
Post by ast
z = (x + a//x)//2
formule (2)
Post by ast
Post by Samuel DEVULDER
Post by ast
où // désigne la division entière
donc a//x = int(a/x)
formule (3)
Post by ast
Post by Samuel DEVULDER
Post by ast
On a de façon évidente z <= y
mais sauriez-vous montrer que y-1 < z <= y ?
ben y-z = (a/x - int(a/x))/2
Je ne vois pas d'où sort cette formule, je crois
(1) - (2) donne y-z = (a/x - a//x)/2
formule (3) dit a//x=int(a/x) donc y-z = (a/x - int(a/x))/2
Post by ast
même qu'elle est fausse
Impossible! sauf si ce que tu appelle division entière n'est pas la
formule (3).

sam.
Olivier Miakinen
2018-03-03 10:23:15 UTC
Permalink
Bonjour,

Je n'ai pas lu tout en détail, mais...
Post by Samuel DEVULDER
Post by ast
Post by Samuel DEVULDER
Post by ast
y = (x + a/x)/2
formule (1)
Post by ast
Post by Samuel DEVULDER
Post by ast
z = (x + a//x)//2
formule (2)
As-tu remarqué qu'il y a, non pas une, mais deux divisions
entières dans cette formule ?
Post by Samuel DEVULDER
Post by ast
Post by Samuel DEVULDER
Post by ast
où // désigne la division entière
donc a//x = int(a/x)
formule (3)
Oui.

Et donc z = int((x + int(a/x))/2)
Post by Samuel DEVULDER
Post by ast
Post by Samuel DEVULDER
Post by ast
On a de façon évidente z <= y
mais sauriez-vous montrer que y-1 < z <= y ?
ben y-z = (a/x - int(a/x))/2
Non, du fait qu'il y avait une division entière par 2 dans
la formule (2) et non une division réelle (ou rationnelle).
Post by Samuel DEVULDER
Post by ast
Je ne vois pas d'où sort cette formule, je crois
(1) - (2) donne y-z = (a/x - a//x)/2
formule (3) dit a//x=int(a/x) donc y-z = (a/x - int(a/x))/2
Post by ast
même qu'elle est fausse
Impossible! sauf si ce que tu appelle division entière n'est pas la
formule (3).
Cf. supra.
--
Olivier Miakinen
Samuel DEVULDER
2018-03-03 14:29:50 UTC
Permalink
Post by Olivier Miakinen
Bonjour,
Je n'ai pas lu tout en détail, mais...
Post by Samuel DEVULDER
Post by ast
z = (x + a//x)//2
formule (2)
As-tu remarqué qu'il y a, non pas une, mais deux divisions
entières dans cette formule ?
oh punaise, non je suis complètement passé à coté. Ca change tout en effet.

Merci de m'avoir pointé sur le truc important que je loupais.

a+

sam.
Thomas Alexandre
2018-03-04 07:42:42 UTC
Permalink
Post by ast
Bonjour
Soient a, x deux entiers avec x > a
Soient
y = (x + a/x)/2 z = (x + a//x)//2
où // désigne la division entière
On a de façon évidente z <= y
mais sauriez-vous montrer que y-1 < z <= y ?
(1) y = (x + a/x)/2
(2) z = (x + a//x)//2

De (2) il vient :
2z = x + a//x - (x+a//x)%2
2z = x + E(a/x) - r (r=0 ou r=1)

où E(.) désigne la partie entière.

De (1) il vient :
2y = x + a/x

On a donc
2y-2z = a/x - E(a/x) + r
2y-2z = D(a/x) + r

où D(.) désigne la partie décimale.

Or par définition
0 <= D(a/x) < 1
et
0 <= r <= 1

donc
0 <= D(a,x) + r < 2
0 <= 2y-2z < 2
0 <= y-z < 1
-y <= -z < 1-y
y-1 < z <= y


... si j'ai les yeux en face des trous, évidemment.
--
Les nouvelles aventures incroyablement extraordinaires
de Don Rémy del κρυπτoλoγoς : http://zywn.free.fr/remy/
Thomas Alexandre
2018-03-04 08:08:05 UTC
Permalink
Post by Thomas Alexandre
(2) z = (x + a//x)//2
2z = x + a//x - (x+a//x)%2
Ce n'est pas forcément très clair.

Si l'on considère la division euclidienne de n par d, on a :
n = qd + r

Par définition
n//d = q
donc
(n//d)*d = qd
(n//d)*d = n-r

Et donc
z = X//2 => 2z = X - X%2
--
Les nouvelles aventures incroyablement extraordinaires
de Don Rémy del κρυπτoλoγoς : http://zywn.free.fr/remy/
Benoit RIVET
2018-03-10 21:04:07 UTC
Permalink
Post by ast
y = (x + a/x)/2
z = (x + a//x)//2
Si x est entier, x+a/x est compris entre deux entiers pairs consécutifs
:

2p <= x+a/x < 2p+2

La partie entière est x+a//x et elle vérifie alors :

2p <= x+a//x <2p+2

En divisant par 2 :

p <= (x+a//x)/2 < p+1

La partie entière est alors z=p et on a donc :

z <= y < z+1

Ainsi :

y-1 < z <= y

Un algorithme de calcul de racine carrée entière peut ainsi s'écrire (en
utilisant le langage Python) :

def isqrt(n):
"""
Paramètre
---------
n entier naturel

Résultat
--------
v racine carrée entière de n
"""
u=2**((n.bit_length()+1)//2)
v=(u+n//u)//2
while u>v:
u,v=v,(v+n//v)//2
return v
ast
2018-03-22 06:28:54 UTC
Permalink
Post by Benoit RIVET
Post by ast
y = (x + a/x)/2
z = (x + a//x)//2
Si x est entier, x+a/x est compris entre deux entiers pairs consécutifs
2p <= x+a/x < 2p+2
2p <= x+a//x <2p+2
p <= (x+a//x)/2 < p+1
z <= y < z+1
y-1 < z <= y
Un algorithme de calcul de racine carrée entière peut ainsi s'écrire (en
"""
Paramètre
---------
n entier naturel
Résultat
--------
v racine carrée entière de n
"""
u=2**((n.bit_length()+1)//2)
v=(u+n//u)//2
u,v=v,(v+n//v)//2
return v
Oui, je suis 100% d'accord avec ce code.
On trouve sur le net des programmes avec des critères
d'arrêt inutilement compliqués, par exemple ici:
http://python.jpvweb.com/python/mesrecettespython/doku.php?id=racine_entiere
Peut être parce que l'auteur démarre avec une valeur
initiale qui peut être inférieure ou supérieure
à sqrt(n)

Une application amusante: Calculer les décimales
de sqrt(2) (ou d'un autre entier)
Post by Benoit RIVET
Post by ast
isqrt(2*100**100)
14142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727
ast
2018-03-22 10:38:00 UTC
Permalink
Post by Benoit RIVET
Un algorithme de calcul de racine carrée entière peut ainsi s'écrire (en
"""
Paramètre
---------
n entier naturel
Résultat
--------
v racine carrée entière de n
"""
u=2**((n.bit_length()+1)//2)
v=(u+n//u)//2
u,v=v,(v+n//v)//2
return v
return u

sinon ne marche pas toujours, par exemple isqrt(3) -> 2

Loading...