-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming,pl.sci.matematyka
Subject: Re: Liczby Fibonacciego rzędu N
Date: Mon, 16 May 2016 16:57:35 +0200
Organization: ATMAN - ATM S.A.
Lines: 94
Message-ID: <nhcn50$b8g$1@node2.news.atman.pl>
References: <nh4std$qlq$1@node2.news.atman.pl> <nh4t8e$qve$1@node2.news.atman.pl>
<a...@n...plus.net>
<nh8ku5$dci$1@node2.news.atman.pl> <nh8mir$f0n$1@node2.news.atman.pl>
<nh8mup$f5k$1@node2.news.atman.pl> <nh8nj2$flh$1@node2.news.atman.pl>
<nh9g0i$5fu$1@node2.news.atman.pl> <nha9ll$e24$1@node1.news.atman.pl>
<nhbs4t$g29$1@node2.news.atman.pl> <nhceq6$2n8$1@node2.news.atman.pl>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1463410657 11536 89.73.81.145 (16 May 2016 14:57:37 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Mon, 16 May 2016 14:57:37 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
Thunderbird/38.6.0
In-Reply-To: <nhceq6$2n8$1@node2.news.atman.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:209407 pl.sci.matematyka:153392
[ ukryj nagłówki ]On 16.05.2016 14:35, bartekltg wrote:
> On 16.05.2016 09:16, Borneq wrote:
>> W dniu 15.05.2016 o 18:55, bartekltg pisze:
>>> bieganie tego pierwiastka do 2 łatwo zrozumieć znów patrząc na
>>> wielomian.
>>>
>>> w0= q^k - q^(k-1) - q^2 - q - 1
>
> Wyciąłeś za dużo cytatu:
>
>
>>>
>>> (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.
>
>
>> Tak z grubsza w = 2-1/(2^k)
Można też to ciut porawić.
q^k (2 - q) == 1
(2 - q) == 1/q^k
// y = 2-q
y = 1/(2-y)^k = 1/2^k 1/(1-y/2)^k =~= 1/2^k (1+y k/2)
y = 1/2^k / (1-k/2^(k+1) )
q = 2 - 1/2^k / (1-k/2^(k+1) )
k, err_pierwszy wzor, err_drugi wzor
{2, 0.1, 0.05},
{3, 0.04, 0.007},
{4, 0.01, 0.001},
{5, 0.003, 0.0002},
{6, 0.0008, 0.00002},
{7, 0.0002, 4.*10^-6},
{8, 0.00006, 6.*10^-7},
{9, 0.00002, 9.*10^-8},
{10, 5.*10^-6, 1.*10^-8},
{11, 1.*10^-6, 2.*10^-9},
{12, 4.*10^-7, 3.*10^-10},
{13, 1.*10^-7, 4.*10^-11},
{14, 3.*10^-8, 6.*10^-12},
{15, 7.*10^-9, 9.*10^-13},
{16, 2.*10^-9, 1.*10^-13},
{17, 5.*10^-10, 2.*10^-14},
{18, 1.*10^-10, 2.*10^-15},
{19, 3.*10^-11, 3.*10^-16},
{20, 9.*10^-12, 5.*10^-17}
I to liniowa aproksymacja, i to liniowa aproksymacja, a parę cyfr
znaczacych się pojawia ;-)
BTW,
q <- 2 - 1/q^k
Jest (w okolicy q=2) przekształceniem zwężającym. Iterując je
w granicy dostaniemy oczekiwany wynik. W dodatku ma bardzo dobrą
stałą (~ 2^-k).
Jednak jest to zbieżność liniowa, więc matoda Newtona, mimo większej
komplikacji, jest lepsza. Obie wymagają jednokrotnego
policzenia q^k, co jest najbardziej kosztowną operacją.
pzdr
bartekltg
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=
- 2024-05-18 Łódź => Handlowiec - Systemy CRM <=
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=
- 2024-05-17 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=