Näherung an Wurzeln mit Euklids Algorithmus?



  • Ich habe folgendes Programm:
    http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfCALC.html

    Zur Bestimmung von Näherungen der Wurzel aus 412 zu Rate gezogen.

    Wie kriege ich das Programmiert? Dass ich z.B. aus der ursprünglichen Gleichung
    die Variablen 61 und 3 kriege und die dann beliebig genauer werden lassen kann.

    This CF ends with  a repeating pattern: 
    20,  then 3, 2, 1, 3, 1, 4, 3, 2, 13, 10, 13, 2, 3, 4, 1, 3, 1, 2, 3, 40 repeating for ever
    Convergents:
     20: 20 = 20
      3: 61/3 = 20.333333333333332
      2: 142/7 = 20.285714285714285
      1: 203/10 = 20.3
      3: 751/37 = 20.2972972972973
      1: 954/47 = 20.29787234042553
      4: 4567/225 = 20.297777777777778
      3: 14655/722 = 20.297783933518005
      2: 33877/1669 = 20.297783103654883
     13: 455056/22419 = 20.29778313038048
     10: 4584437/225859 = 20.29778313018299
     13: 60052737/2958586 = 20.297783130184488
      2: 124689911/6143031 = 20.29778313018443
      3: 434122470/21387679 = 20.29778313018444
    ...
    

    Ich brauche das, um die Pell's Gleichung damit zu lösen.
    Und es ist auch so nützlich.

    Soweit ich das mitbekammen habe, hat es mit "Continued Fractions" zu tun und dem advanced algorithmus vom Euklid 😃

    Vielen Dank schonmal! :xmas1:



  • vielleicht hilft dieser Beitrag über Kettenbruchzerlegung erstmal weiter. Wenn man den Integertyp in boost::rational<> durch ein geeignetes 'BigInt' ersetzt, kann man auch die Genauigkeit über die von int hinaus steigern.

    :xmas2: Werner

    PS.: geht es um Problem 66?



  • Werner_logoff schrieb:

    PS.: geht es um Problem 66?

    Jap


Log in to reply