eGospodarka.pl
bezpłatny program PIT 2019

eGospodarka.plGrupypl.comp.programmingJak najszybciej obliczyć wieloskładnikową sumę potęg? › Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
  • X-Received: by 2002:ac8:1194:: with SMTP id d20mr1479290qtj.243.1581411871055; Tue,
    11 Feb 2020 01:04:31 -0800 (PST)
    X-Received: by 2002:ac8:1194:: with SMTP id d20mr1479290qtj.243.1581411871055; Tue,
    11 Feb 2020 01:04:31 -0800 (PST)
    Path: news-archive.icm.edu.pl!news.icm.edu.pl!fu-berlin.de!news-out.google.com!nntp.g
    oogle.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Tue, 11 Feb 2020 01:04:30 -0800 (PST)
    In-Reply-To: <8...@g...com>
    Complaints-To: g...@g...com
    Injection-Info: google-groups.googlegroups.com; posting-host=213.192.68.153;
    posting-account=f7iIKQoAAAAkDKpUafc-4IXhmRAzdB5r
    NNTP-Posting-Host: 213.192.68.153
    References: <e...@g...com>
    <8...@g...com>
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <a...@g...com>
    Subject: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    From: g...@g...com
    Injection-Date: Tue, 11 Feb 2020 09:04:31 +0000
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: quoted-printable
    Xref: news-archive.icm.edu.pl pl.comp.programming:214747
    [ ukryj nagłówki ]

    W dniu wtorek, 11 lutego 2020 08:01:34 UTC+1 użytkownik Wojciech Muła napisał:
    > On Friday, February 7, 2020 at 1:48:31 PM UTC+1, osobliwy nick wrote:
    > > Mam do wykonania pewną procedurę i zastanawiam się jak skonstruować algorytm,
    który wykonałby to najszybciej. Weźmy pewną liczbę zapisaną binarnie. Docelowo mają
    to być liczby 128-bitowe, ale w tym przykładzie weźmy liczbę 1011011 =
    64+32*0+16+8+4*0+2+1. Interesują nas tylko bity, które mają wartość niezerową:
    64+16+8+2+1. Dla tych bitów musimy policzyć następujące współczynniki:
    > >
    > > x1=64/2^(y-1) * 1
    > > x2=16/2^(y-1) * 2
    > > x3=8/2^(y-1) * 3
    > > x4=2/2^(y-1) * 4
    > > x5=1/2^(y-1) * 8
    > >
    > > Współczynników będzie tyle samo, co jedynek w zapisie binarnym naszej liczby. y
    to liczba jedynek w zapisie binarnym naszej liczby, w naszym przykładzie wynosi 5.
    Gdy mamy te współczynniki:
    > >
    > > x1=4
    > > x2=2
    > > x3=2
    > > x4=1
    > > x5=1
    > >
    > > Obliczamy liczbę:
    > >
    > > L = (a^0*x1+a^1*x2+a^2*x3+a^3*x4+a^4*x5)*2^(y-1)
    > >
    > > "a" może by równe jakiejś liczbie całkowitej podzielonej przez 2, na przykład:
    0.5, 1.5, 2.5, -3.5 itd. Zastanawiam się jak to najszybciej wykonać. Jeśli liczba ma
    mieć wiele bitów np. 128, to ostatnia potęga również wynosić aż 127. Stąd niezbędny
    jest algorytm szybkiego potęgowania. Jednak nawet wówczas może zajść potrzeba
    wykonania aż 128 potęgowań.
    > >
    > > Czy da się te potęgowania wykonać jakoś symultanicznie? Algorytm nie musi czekać
    na obliczenie np. a^10, żeby móc zacząć liczyć a^11. Mógłby liczyć wszystkie potęgi
    na raz. Liczenie tego po kolei zajmie t1+t2+t3+...tn czasu, gdzie "ti" to czasy
    potęgowania kolejnych a^i. A gdyby algorytm liczył symultanicznie, to zajmie mu to co
    najwyżej tyle czasu ile potrzebuje dla najwyższej, ostatniej potęgi. Czy coś takiego
    jest możliwe? Ma to jakąś nazwę w branży?
    >
    > Policzenie całkowitej potęgi x^128 wymaga tylko log_2(128) = 7 mnożeń:
    >
    > x = wejście
    > x2 = x*x // x^2
    > x4 = x2*x2 // x^4
    > x8 = x4*x4 // x^8
    > x16 = x8*x8 // x^16
    > x32 = x16*x16 // x^32
    > x64 = x32*x32 // x^64
    > x128 = x64*x64 // x^128
    >
    > Jak już masz te czynniki policzone, to łatwo z nich dostać dowolne potęgi.
    > Np. x^73 = x^{64 + 8 + 1} = x * x8 * x64; albo x^55 = x^{32 + 16 + 4 + 2 + 1} = x *
    x2 * x4 * x16 * x32.
    >

    Nawet ten właśnie przykład jest jednym z przykładów dydaktycznych w najlepszej
    książce programistycznej ewer:

    https://mitpress.mit.edu/sites/default/files/sicp/fu
    ll-text/book/book-Z-H-11.html#%_sec_1.2.4

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki
bezpłatny program PIT 2019

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: