W dniu czwartek, 24 lipca 2014 20:54:31 UTC+2 użytkownik feldmarszałek tusk napisał:
> dzi�ki, co� takiego obija�o mi si� po g�owie, ale nie mog�o si�
>
> wykrystalizowaďż˝ ;o)
>
>
>
> a czy Kto� tu zna jaki� algorytm podnoszenia 10 do pot�gi?

spoko, nie ma problemu (boz ale jestem glody, dwa dni na piwie kofeinie i prawie nic
do jedzenia - i jeszcze rece po cholernym kleszczu jak zwykle bola jak cholera)

co do pow to nei wiem bo nei wiem jaki to sprzet itp

do góry

On 24.07.2014 20:54, feldmarszałek tusk wrote:

>>
>> jesli rysujesz wykres y=f(x) w tej skali to robisz cos takkiego
>
>> for(float x = 0; x < 10; x += 10./width)
>> {
>> y = f( pow(10,x) );
>> Setpixel(x*width/10., y*height/maxy);
> >}

A na wafla tak? Ciag geometryczny tworzysz prościej.
Potęgowanie jest drogie (nie wiem, czy to nie logarytm
i exponent:) A przecież w każdym kolejnym kroku y jest
dokładnie 10^(1/width) raza większe, wystarczy jedno mnożenie
na pętlę.

for(float y = minimum; y < maximum; y *= iloraz_ciągu)
//czy jak tak wygodniej to na x, ale y*=; zawsze
{
Setpixel(x*width/10., y*height/maxy);
}


> dzięki, coś takiego obijało mi się po głowie, ale nie mogło się
> wykrystalizować ;o)

O, czyli wykrzywiona emotikonka pod postem o ciaghu geometrycznym
nie oznaczała 'ojej, jakie to proste' tylko 'nic nie rozumiem'? :/

> a czy Ktoś tu zna jakiś algorytm podnoszenia 10 do potęgi?

Gdyby nie to, zę masz niecałkowite wykładniki, dla niewielkich
potęg to może być szybsze.
http://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%
C4%99gowania

Ale tu w ogóle nie potrzebujesz potęgowania, tylko jedno
mnożenie w kroku.

pzdr
bartekltg

do góry

Użytkownik "feldmarszałek tusk" napisał w wiadomości grup
dyskusyjnych:lqrkpc$r7t$...@n...news.atman.pl...

>a czy Ktoś tu zna jakiś algorytm podnoszenia 10 do potęgi?

Dopisujesz zera do 1 w łańcuchu znaków i wywołujesz scanf. ;)

Poszukaj biblioteki CEPHES.

do góry

W dniu 2014-07-22 14:31, bartekltg pisze:
> Odpowiedź prosta, rozbić" liczbę na cechę/mantysę, choćby
> funkcją frexp (x) -> (y,n) : x = y*2^n, 0.5<=y<1

Jak zrobić funkcję frexp? Trzeba bitowo grzebać we floacie, gdzie już
jest rozbita na cechę i mantysę? Chyba się da, C++ to nie Java i można
robić takie konwersje


> całość:
> http://pastebin.com/WuYW6MTJ

chrono::high_resolution_clock::now()
to standardowa otoczka QueryPerformanceCounter ?

do góry

W dniu 2014-07-29 09:52, Borneq pisze:
>> całość:
>> http://pastebin.com/WuYW6MTJ

> x*(38.7609531719041669376926170246289866685554061249
47+
> x*(-245.85943859848429206309024729452081797918448383
011+
> x*(1305.02133731409794430037909996049017213519358597
46+
> x*(-5483.3897186528672757505743075974516855722609750
103+
> x*(18373.3692859474882123764452828071424328947070318
93+
> x*(-49720.330484326774507017799362836307490489909887
034+


Jest metoda szybsza niż Hornera, zwłaszcza dla wielomianów wysokiego
stopnia, mnoży od razu przez współczynnik kwadratowy.

>>>>
wklejam z .doc, który 10 lat temu napisałem, trochę tu będzie
nieczytelne, nie wiem jaką ma nazwę ten algorytm



Najpierw wielomian doprowadzamy do postaci, dla której współczynniki
przy dwóch najwyższych potęgach są równe jedności. Następnie rozkładamy
wielomian czynnikami kwadratowymi postaci y^2-a_i
Załóżmy, że wielomian pn(x) ma przy najwyższej potędze współczynnik
równy jedności, czyli jest postaci:
pn(x) = xn+an-1xn-1+an-2xn-2+...a1x+a0

po podstawieniu y = x + (an-1-1)/n ===> x = y - (an-1-1)/n
otrzymamy qn(y)

qn(y) = yn+yn-1+bn-2yn-2+...b1y+b0

Jeżeli zadany wielomian ma przy najwyższej potędze współczynnik różny od
jedności, czyli jest to wielomian wn(z) postaci:
wn(z) = cnzn+cn-1zn-1+cn-2zn-2+...c1z+c0
wtedy, aby otrzymać pn(x) należy albo podzielić cały wielomian przez cn
, albo podstawić
x = Sqrtn(cn)*z ===> z = x/ Sqrtn(cn)
zaleznie od tego, gdy chcemy przeskalować rezultat czy argument funkcji.


qn(y) = yn+yn-1+bn-2yn-2+...b1y+b0

dzieląc qn(y) przez y2-a1 otrzymujemy dla pewnego a1
qn(y) = (y2-a1)*( cn-2*yn-2+ cn-3*yn-3+cn-4*yn-4+...+c1*y+c0)+?1y+?1

Chcemy dobrać takie a1, aby po podzieleniu wielomianu przez (y2-a1)
otrzymać wielomian, który również będzie miał przy najwyższych dwóch
potęgach współczynniki równe jedności oraz reszta z dzielenia wielomianu
przez (y2-a1) była pojedyńczą liczbą.

qn(y) = (y2-a1)*(yn-2+yn-3+cn-4*yn-4+...+c1*y+c0)+?1

gdzie
cn-2=cn-3=1 oraz ?1=0

wzór rekurencyjny na cj ma postać:
cj=bj+2+a1*cj+2 (j=n-4,n-5,....-2)
przy czym c-1 = ?1, c-2 = ?1

Uwzględniając, że ?1 = 0 przedstawiamy ?1 jako wyrażenie zależne od a1 i bi
?1 = c-1 = b+a1*c1=b1+a1*(b3+a1*c3) =
b1+a1*b3+a12(b3+a1*c5) = b-1+a1*b3+a12*b5+...+anr-1*b2r-1+a1r
(2r = n-2 dla n parzystego lub n-1 dla n nieparzystego)
podstawiając ?1=0, otrzymamy dla a1 równanie
b1+a1*b3+a12*b5+...+anr-1*b2r-1+a1r = 0
Załóżmy, że ma pierwiastek rzeczywisty, niech a1 będzie pierwiastkiem
wtedy otrzymamy rozkład
qn(y)=(yn-a1)*(yn-2+yn-3+cm-4*ym-4+...c1*y+c0)+?1

dzieląc wielomian w nawiasach, jeżeli znowu znajdziemy pierwiastek,
otrzymamy
qn(y)=(y2-a1)*((y2-a2)*(yn-4+yn-5+dn-6*yn-6+...+a0)+
?2)+?1
a kiedy nie ma pierwiastka
qn(y) = (y2-a1)*(y*(yn-3+yn-4+....c1)+c0)+?1

Gdy za każdym razem mamy znaleziony pierwiastek ai, wtedy qn(y) ma rozkład:
qn(y) = (...(((?ny2+y+as)*(y2-as-1)+?s-1)*(y2-as-2)+?s-2)...
)*(y2-a1)+?1
(*)

?n = 1 dla n parzystych; 0 dla n nieparzystych
s = 1/2 *n dla n parzystych; 1/2 *(n+1) dla n nieparzystych

Algorytm obliczania pn(x)
albo x = x*Sqrtn(an) gdy najpierw przeskalowujemy argument funkcji
y = x+ (an-1-1)/n
z = y2
ws = ?n*z+y+as
wj = wj+1*(z-aj)+?j (j=s-1,s-2,...1)
pn(x) = w1
albo pn(x) = an*w1 gdy na końcu przeskalowujemy rezultat funkcji

przykład
p4(x) = x4+5x3+3x2+2
a3=5 => y = x+1 => x := y-1
q4(y)= y4+y3-6y2+5y+1 podstawiając ?1=0
0 = 5+a1
stąd a1 = -5
i
q4(y) = (y2+5)*(y2+y-11)+56
algorytm obliczania:
y := x+1
z := y*y
w := z+y-11
w ;= w*(z+5)+56


1.>
0.000204700z^7+0.001439274z^6+0.008328596z^5+0.04163
5012z^4+0.166667986z^3+0.500006347z^2+0.999999901z+0
.999999801
w przedziale <-1;1> maksymalna różnica wynosi około 2e-7

2. z:=x/0.297178123
otrzymamy

3. x^7 + 2.0895004648ox^6 + 3.5932515591ox^5
+ 5.3381571582ox^4 + 6.3504088014ox^3
+ 5.6616347459ox^2 + 3.3649849203ox + 0.999999801

x = y-(2.08950044541-1)/7
x = y-0.155642921


4.
y^7 + y^6 + 2.1506749053oy^5 + 3.1691354977oy^4
+ 3.7604523590oy^3 + 3.3533330221oy^2 + 1.9930983727oy
+ 0.5923035272
wyliczone:
5.x^5+x4+1.4184012627x3+2.4368618551x2+2.7217944997x
+1.5688833150
a: -0.732273642600117 (pierwiastek
x^3+2.1506749053x^2+3.760452359x+1.9930983727)
reszta: -0.5565483727

ten nie ma pierwiastka, ponieważ x^2+1.4184012627x+2.7217944997 nie ma
pierwiastków
i rozkłada się na
x^4+x3+1.4184012627x2+2.4368618551x+2.7217944997
i resztę 1.5688833150

rozkłada się na y^2-a dla a=-2.4368618551 (pierwiastek równania
x+2.4368618551)
i wielomian stopnia drugiego
x^2+x-1.0184605924
i resztę 5.2036422682

do góry

W dniu 2014-07-22 14:31, bartekltg pisze:
> całość:
> http://pastebin.com/WuYW6MTJ

A może by spróbować podzielić wielomian przez wielomian? Choć dzielenie
trwa znacznie dłużej niż mnożenie, to będzie tylko jedno.
Skąd wziąłeś te wzory? Czy podobnie daje się wyprowadzić na inne
funkcje? A jeśli chodzi o wolniejsze szeregi ale pozwalające wyliczyć z
dowolną dokładnością, to gdzie można natknąć się na zbiór takich wzorów?
Trochę jest na exp, sinus,czy cosinus w tablicach matematycznych.

do góry

już się pewnie obrazili... jak to w eu...

do góry

W dniu 2014-07-29 09:52, Borneq pisze:
> Jak zrobić funkcję frexp? Trzeba bitowo grzebać we floacie, gdzie już

To jest standardowa funkcja, ale dosyć długo liczona. Zajmuje prawie
połowę czasu liczenia logarytmów metoda Czebyszewa. A koprocesor od razu
ma cechę i mantysę. Poza tym może zrównoleglić Hornera, tak że najpierw
w logarytmicznym czasie wyliczy x,x^2,x^4,x^8,x^16.
Z przykładu widać że log2 jest znacznie szybciej wyliczany niż log czy
log10, więc wiedząc to można uniknąć liczeń log(x)/log(2)

do góry

On Tue, 29 Jul 2014 16:10:19 +0200, Borneq <b...@a...hidden.pl>
wrote:

>W dniu 2014-07-29 09:52, Borneq pisze:
>> Jak zrobić funkcję frexp? Trzeba bitowo grzebać we floacie, gdzie już
>
>To jest standardowa funkcja, ale dosyć długo liczona. Zajmuje prawie
>połowę czasu liczenia logarytmów metoda Czebyszewa. A koprocesor od razu
>ma cechę i mantysę. Poza tym może zrównoleglić Hornera, tak że najpierw
>w logarytmicznym czasie wyliczy x,x^2,x^4,x^8,x^16.
>Z przykładu widać że log2 jest znacznie szybciej wyliczany niż log czy
>log10, więc wiedząc to można uniknąć liczeń log(x)/log(2)


http://stackoverflow.com/questions/11376288/fast-com
puting-of-log2-for-64-bit-integers

A.L.

do góry

On 29.07.2014 09:52, Borneq wrote:
> W dniu 2014-07-22 14:31, bartekltg pisze:
>> Odpowiedź prosta, rozbić" liczbę na cechę/mantysę, choćby funkcją
>> frexp (x) -> (y,n) : x = y*2^n, 0.5<=y<1
>
> Jak zrobić funkcję frexp? Trzeba bitowo grzebać we floacie, gdzie już
> jest rozbita na cechę i mantysę? Chyba się da, C++ to nie Java i
> można robić takie konwersje

Użyć funkcji frexp z cmath.

A ona bawi się w bity. Działa tak samo, a ja nie muszę pamiętać
dokładnie specyfikacji ieee ileśtam. Nie można przesadzać z firowaniem;)

>> całość: http://pastebin.com/WuYW6MTJ
>
> chrono::high_resolution_clock::now() to standardowa otoczka
> QueryPerformanceCounter ?

Cholera wie. Pewnie "zależy od implementacji".
Najdokładniejszy zegar, jaki jest dostępny dla piszącego
bibliotekę na danej maszynie.
Pewnie można zapytać się zegara o precyzja, a przynajmniej
o rozdzielczość.

> A może by spróbować podzielić wielomian przez wielomian? Choć
> dzielenie trwa znacznie dłużej niż mnożenie, to będzie tylko jedno.

Przecież właśnie to robię. Mam wielomian w liczniku, wielomian
w mianowniku, liczone są oba, potem wyniki są dzielone.

> Skąd wziąłeś te wzory? Czy podobnie daje się wyprowadzić na inne
> funkcje?

Dla wielomianów masz kryterium Czebyszewa i algorytm Remeza.
http://en.wikipedia.org/wiki/Remez_algorithm

Dla wymiernych kryterium też działa (pewnie już nie na zasadzie
_najlepszej_ funkcji, a jedynie przyzwoitej, jak będę potrzebował,
wgryzę się głębiej. Na razie odpłynąłem w próbę zrozumienia,
dlaczego funkcje wymierne dają tak znacznie lepsze wyniki
niż wielomiany:).

Wyznaczenie też jest bardziej kłopotliwe.
Jakoś robi to boost
http://www.boost.org/doc/libs/1_36_0/libs/math/doc/s
f_and_dist/html/math_toolkit/backgrounders/remez.htm
l
I jakoś lepiej robi to mathematica
http://reference.wolfram.com/language/FunctionApprox
imations/ref/MiniMaxApproximation.html
[używa błędu względnego, chciałem +-bezwzględny,
dodałem do funkcji 100:)]

> A jeśli chodzi o wolniejsze szeregi ale pozwalające wyliczyć
> z dowolną dokładnością, to gdzie można natknąć się na zbiór takich
> wzorów? Trochę jest na exp, sinus,czy cosinus w tablicach
> matematycznych.

To, co powyżej nie było przybliżeniem Pada. Było funkcją wymierną
utworzoną aby na danym przedziale jak najlepiej (minimalny błąd
maksymalny) odtworzyć funkcję.

Różnica jest taka, jak między szeregiem taylora a najlepszym wielomianem
danego stopnia.

Takie funkcje na pewno są w pracach poświęconych wyznaczaniu
numerycznych przybliżeń. Kiedyś czytałem coś większego
o polilogarytmach, były tabelki;-)


Metody z kwadratowaniem na razie rozumiem, nie umiem znaleźć ;-)
Może jakbyś przepuścił przez tą maszynkę podane tam wielomiany.



pzdr
bartekltg

do góry