Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28582

Re: Liczby Fibonacciego rzędu N

Cross-posted to 2 groups.

Show all headers | View raw

On 15.05.2016 11:37, peter wrote:
> Borneq pisze:
>> W dniu 15.05.2016 o 04:29, Borneq pisze:
>>> W dniu 15.05.2016 o 04:23, Borneq pisze:
>>>> Jakie wzory uogólnionych ciągów inicjowanych jedynkami?
>>>
>>> To znaczy wzór nie na same ciągi, ale równanie dla x_{i+1}/x_i przy i
>>> dążącym do nieskończoności.
>>> Na przykład dla Fibonacciego : fib^2 = fib+1
>>
>> Chyba wiem:
>> dla Fibonacciego: a_n = a_{n-1}+a_{n-2}
>> jeśli przez r oznaczymy golden ratio, to
>> r^2 = r+1
>> dla innych będzie analogicznie:
>> r^3 = r^2+r+1
>
> OK. Tylko to nie jest już golden ratio
>
> r = 1/3 ( 1+(19-3sqrt[33])^(1/3) + (19+3sqrt[33])^(1/3) )
> r = 1.839286755
>
>> r^4 = r^3+r^2+r+1
>> r^5 = r^4+r^3+r^2+r+1
>> ...
>> Wystarczy teraz do tablicy Hornera i szukać metodą Newtona około
>> punktu x=2.
>>
> A to masz już gotowe
> {{2, 1.618033989}, {3, 1.839286755}, {4, 1.927561975}, {5,
>    1.965948237}, {6, 1.983582843}, {7, 1.991964197}, {8,
>    1.996031180}, {9, 1.998029470}, {10, 1.999018633}, {11,
>    1.999510402}, {12, 1.999755501}, {13, 1.999877833}, {14,
>    1.999938939}, {15, 1.999969475}, {16, 1.999984739}, {17,
>    1.999992370}, {18, 1.999996185}, {19, 1.999998093}, {20,
>    1.999999046}}

Nie ma co się ograniczać;-)

2: 
1.618033988749894848204586834365638117720309179805762862135448622705260462818902449707207204189391137
3: 
1.839286755214161132551852564653286600424178746097592246778758639404203222081966425738435419428307014
4: 
1.927561975482925304261905861736622168698554255163384727146647038009666062297815559149818253461890653
5: 
1.965948236645485337189937375934401396151327177456861393236934508442252712871886881734818665554630472
6: 
1.983582843424326330385629293391425752730080865568821753216359065656702278014172402986575070226899797
7: 
1.991964196605035021097741754584374963479318960053157995244782153400951980309622183563141577022719017
8: 
1.996031179735414589815317901755839774489379680945221927634853627284595269945627520379784497496677719
9: 
1.99802947026228669866233146697141889422394811200720817635007606418347246216418323113493506302640167
10: 
1.999018632710101138663409239129152861854310076062220826532008328824786927236540933057020104301232375
11: 
1.999510401978285491440043956861529326661081254266614810779837519236615390078719789044140796520274345
12: 
1.999755500937317536697426762400382912383323386504556323062753939321611287661284370644702025866990915
13: 
1.999877832711545540039946899212990477872263216888867413202466954233036366079897025359931465066825935
14: 
1.999938938749594648497845059170961691634186447969185808282677452968010724453480158889012554038686369
15: 
1.999969475434503292360189201418153043006796608216820644909453656234921657658569086286226322162157151
16: 
1.999984739347944107289059690853180523398789865045347828924870915759038438904118573567103314365400392
17: 
1.999992370110654554581262086662690173744461423887555531876842475084516571192165982892311479262694294
18: 
1.999996185171760268010734733416410670883028695620770951598826851042717888337484473992487986041191113
19: 
1.999998092616805432968528027719761428200428348135841577975196837806368081561631463543584620578204458
20: 
1.999999046316588514457316408446048445016706257736798957683555662453016630707735356535989845294224046

Kod w c++ (mathematica drogawa) na dole.


bieganie tego pierwiastka do 2 łatwo zrozumieć znów patrząc na
wielomian.

w0= q^k - q^(k-1) - q^2 - q - 1

Rozszerzemy go dla ułatwienia obliczeń o dodatkowy pierwiastek
mnożąc przez (q-1). NIe zmienia to pozostąłych pierwiastków.

w = w*(q-1) =  q^(k+1) - 2 q^k + 1

[Przy okazji, robiąc wykres pierwiastków widać, że układają sie
na okregu jednostkowym i dodatkowy pierwiastek siedzi w okolicy x=2.
Spodziewam się więc, że ten wielomian podobny jest do
(q^k -1) (q-2) =    q^(k+1) - 2 q^k - q -2 ]

0 = q^k (q-2) +1

(2-q)q^k = 1

(2-q)q^k ma pierwiastek w 0 i 2. W okolicy 2 bardzo szybko rośnie,
(bo praktycznie wygląda jak funkcja liniowa (2-q)*2^k) i trafia
w jedynkę. Skoro przyblizęnie q^k = 2^k wydaje się dobre i w okolicy 
rozwiązania
(2-q)q^k = 1
to je zastosujmy do rozwiązania:

(2-q) = 1/2^k.
q = 2 - 2^-k

{{15, 1.9999694824218750000},
  {16, 1.9999847412109375000},
  {17, 1.9999923706054687500},
  {18, 1.9999961853027343750},
  {19, 1.9999980926513671875},
  {20, 1.9999990463256835938}}

Bardzo ładnie współgra z dokładnymi wynikami.


pzdr
bartekltg



#include <iostream>
#include <mpreal.h>
#include <iomanip>
using namespace std;

// kompilować z biblotekami -lmpfr -lgmp

int main(){
     const int precyzja = 100;
     mpfr::mpreal::set_default_prec(precyzja*1.2*log(10)/log(2));
     mpfr::mpreal x ;

     for (int k=2; k<21;k++)  {
         x=2;
         while ( (x-2)* mpfr::pow(x,k) + 1 > pow(10,-precyzja) )
             x= (x *(2 + k *(-2 + x) - mpfr::pow(x,-k)))/(k* (-2 + x) + x) ;
         cout <<setprecision(precyzja)<< k<<": "<<  x << endl;
     }
     return 0;
}

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-13 17:46 +0200
  Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-13 17:52 +0200
    Re: Liczby Fibonacciego rzędu N Roman W <bloody_rabbitREMOVETHIS@gazeta.pl> - 2016-05-14 10:10 +0100
      Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-14 16:51 +0200
      Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 03:55 +0200
        Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:23 +0200
          Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:29 +0200
            Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:40 +0200
              Re: Liczby Fibonacciego rzędu N peter <ToJestTo@nic.nie.wiem> - 2016-05-15 11:37 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-15 18:55 +0200
                Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-16 09:00 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 14:42 +0200
                Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-16 09:16 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 14:35 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 16:57 +0200
          Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-15 14:26 +0200

csiph-web