Processing math: 100%
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 13 years ago

Menny gravatar image

Via the reference within this page: http://www.numbertheory.org/php/surd.html

I found a more elegant algorithm than the one sketched above:

Algorithm for finding the period of a quadratic irrational

  1. Input: (a,b,c)Z×N×Z and b not a perfect square. This triple represents a+bc.

  2. If c does not divide ba2 then multiply everything by |c||c| , and get new triple that we call (a,b,c)

  3. Set P0=a , Q0=c, d=c.

  4. For k0 set

(a) αk=Pk+dQk

(b) ak=αk

(c) Pk+1=akQkPk

(d) Qk+1=dP2k+1Qk

  1. Then α0=a+bc=[a0,a1,a2,...]

  2. Let k<l be the first pair of integers which satisfy that (Pk,Qk)=(Pl,Ql) then the period of α0 is (ak,,al1) .

Hopefully this will help implementing it...