From: Gik <patatai aol.com>
Subject: Re: Liczby pseudolosowe dowolnej =?ISO-8859-2?Q?d=B3ugo=B6ci?=
Borneq napisał:
> Funkcja random w Delphi jest bardzo szybka - zaledwie jedno mnożenie, a
> drugie gdy chcemy dopasować wynik do przedziału; mimo prostoty ma
> całkiem zadowalająca "losowość".
> Ale ma jedną wadę - otrzymujemy liczbę 32 bitową, a żeby otrzymać
> większą np 128 bitową nie wystarczy 4 razy wygenerować po 32 bity, bo to
> nie będzie prawdziwa 32 bitowa.
hm, 4 bajty(32 b) można połączyć w 128 bity, ale .... nie w Delphi.
Do obliczeń na 128 bitach potrzeba odpowiednich bibliotek.
> Gdzie można znaleźć algorytmy generowania wielkich liczb pseudolosowych
> i testy na ich zachowanie losowe?
Algorytmy generowania i testy dużych liczb losowych nie różnią sie od
tych dla małych liczb ( tylko obliczenia są na liczbach wielobajtowych a
czas generowania/testowania się zwiększa)
--
Gik
From: "Radosław Hofman" <radekh teycom.pl>
Subject: Re: LICZENIE EKSTREMUM FUNKCJI
> Moje pytanie tyczy się określenia czy jest to wartość maksymalna czy
> minimalna
> ====================================
> W tym celu należy policzyć 2gą pochodną dla f/2 i sprawdzić czy jest
> większa
> czy mniejsza od zera (większa - minimum; mniejsza - maksimum)
Użycie drugiej pochodnej to jedna z metod, ale nie jedyna. Pochodna, to nic
innego jak tangens kąta pod jakim przechodziłaby styczna do funkcji w
punkcie x. Wartość wynosi zero, jeżeli styczna byłaby równoległa do osi X,
czyli mielibyśmy ekstremum.
Wystarczy zbadać wartości pierwszej pochodnej wokół ekstremum - po lewej
stronie jest +, a po prawej -, to mamy doczynienia z maksimum, a jeżeli z
lewej -, a z prawej + to minimum... Wersja z II pochodną na mojej maturze
była w zadaniu na celujący :), a funkcja wyglądała tak, że obliczenie tej II
pochodnej było wyjątkowo siermiężne.
Pozdr
Radek Hofman
From: =?iso-8859-2?Q?=A3ukasz?= Kalbarczyk <lukaszusun topocztowy.net>
Subject: Re: Re: Re: Matematyka klasa 5 podstawowka
Dnia Tue, 9 Oct 2007 04:41:02 CST, flower napisał(a):
> Użytkownik "Antek Laczkowski" <antekL1 nospam.onet.pl> napisał w wiadomości
>> Dnia 05-10-2007 o 11:03:52 flower <flower19737 wp.pl> napisał(a):
>>>> A jeżeli chodzi o intuicję, to bardzo, bardzo wiele osób łapałem ( i
>>>> sam
>>> też
>>> się dałem złapać) na to: w dwóch sklepach był taki sam towar w tej samej
>>> cenie. W jednym ze sklepów zdrożał o 20%, a potem staniał o 10%, a w
>>> drugim
>>> tak samo tylko odwrotnie: najpierw potaniał o 10%, a potem zdrożał o
> 20%.
>>> W którym kosztuje więcej po tych zmianach? Odpowiesz natychmiast?
>> Nie liczę, tylko z intuicji: 10% z dużego przyrostu to więcej, niż 20% z
>> mniejszego.
>> (te liczby, 10, 20 są podobne)
>> PIERWSZY sklep jest droższy. Złapałem się?
> Ano. W jednym cena została pomnożona przez 1.2 a potem przez 0.9, a w drugim
> w odwrotnej kolejności.
> Proste, nie? W której klasie jest mnożenie i procenty? :-)))
> P.S. Ja złapałem się na to na V bodajże roku matematyki.
Bo to jest bardzo podobne do sformułowania problemu
,,wzrosła o 10% a potem spadła o 10%''
i mózg musi przynajmniej moment się zawahać,
po czym popaść w wielką niepewność :)
--
ŁK (09.10.2007 17:02:11)
From: Krzysztof Nowak <ksnowak priv.onet.pl>
Subject: Re: Liczby pseudolosowe dowolnej =?ISO-8859-2?Q?d=B3ugo=B6ci?=
Nie widze problemu, wystarczy miec dobry generator ciagow
zero-jednykowych i mozesz sobie wtedy brac liczby losowe jakie tylko chcesz.
KN
Borneq pisze:
> Funkcja random w Delphi jest bardzo szybka - zaledwie jedno mnożenie, a
> drugie gdy chcemy dopasować wynik do przedziału; mimo prostoty ma
> całkiem zadowalająca "losowość".
> Ale ma jedną wadę - otrzymujemy liczbę 32 bitową, a żeby otrzymać
> większą np 128 bitową nie wystarczy 4 razy wygenerować po 32 bity, bo to
> nie będzie prawdziwa 32 bitowa.
> Duże liczby pseudolosowe mogą być potrzebne na przykłąd gdy chcemy
> sprawdzić czy liczba jest pierwsza używając algorytmu probabilistycznego
> Gdzie można znaleźć algorytmy generowania wielkich liczb pseudolosowych
> i testy na ich zachowanie losowe?
======================================= Nota moderatora:
Prosimy odpowiadac pod cytowanym postem.
From: Krzysztof Nowak <ksnowak priv.onet.pl>
Subject: Re: Slepy problem komiwojazera
Witam, a dlugosci jakich dokladnie sciezek zna slepy komiwojazer?
Jak na razie to albo problem jest trywialny, albo nie ma rozwiązania.
KN
bim-bom pisze:
> Czesc wszystkim!
> Problem komiwojazera to: jest n miast, kazde polozone w jakies
> odleglosci od kazdego z innych. Majac dane odleglosci miedzy miastami,
> trzeba znalezc najkrotsza droge przejscia z miasta x do miasta x
> przechodzac przez wszystkie miasta dokladnie jeden raz.
> Slepy problem komiwojazera to taki, w ktorym nie mamy na wejsciu
> odleglosci miedzy miastami, ale majac dana sciezke przejscia przez
> miasta, mozemy okreslic jej calkowita dlugosc.
> Moj problem jest taki - jak szybko mozna zmienic slepy problem
> komiwojazera w "zwykly" problem komiwojazera, tzn. okreslic macierz
> odleglosci miedzy wszystkimi miastami? Bardzo prosty algorytm bedzie
> dzialal w czasie O(n^5) albo O(n^6), ale pewnie sa lepsze. Macie jakies
> dobre propozycje?
>
> Z gory dzieki.
======================================= Nota moderatora:
Prosimy odpowiadac pod cytowanym postem.
From: Przemyslaw Kwiatkowski <micha micha.waw.pl>
Subject: Re: Matematyka klasa 5 podstawowka
Łukasz Kalbarczyk wrote:
>>> PIERWSZY sklep jest droższy. Złapałem się?
>> Ano. W jednym cena została pomnożona przez 1.2 a potem przez 0.9, a w drugim
>> w odwrotnej kolejności.
>> Proste, nie? W której klasie jest mnożenie i procenty? :-)))
>> P.S. Ja złapałem się na to na V bodajże roku matematyki.
>
> Bo to jest bardzo podobne do sformułowania problemu
> ,,wzrosła o 10% a potem spadła o 10%''
> i mózg musi przynajmniej moment się zawahać,
> po czym popaść w wielką niepewność :)
No, ale tu jest mnożenie 0,9*1,1. No i o ile jeszcze rozumiem, że można
"od razu" nie widzieć, czy jest to więcej czy mniej niż 1, to chyba
jednak od razu widać, że to nie jest 1...
--
MiCHA
From: "zdumiony" <zdumiony jestem.pl>
Subject: =?iso-8859-2?Q?Ca=B3kowanie_na_kole?=
Całkujemy numerycznie funkcję dwóch zmiennych na obszarze koła o środku
(0,0) i promieniu 1. Niech funkcja ta będzie ograniczona i ma ograniczone
pochodne.
Działamy tak, że całkujemy Y od -1 do 1. Wartościami dla y będzie całka
jednej scanlinii czyli poziomego przedziału od -sqrt(1-y^2) do sqrt(1-y^2)
Można zauważyć, że nawet gdy użyjemy dobrej metody całkowania jak metodą
Romberga, to jednak nie będzie dobrej zbieżności; spowodowane jest to tym,
że dla Y = -1 lub Y = 1 bardzo szybko maleje długość scanlinii i na końcach
ich pochodna dąży do (minus, plus)nieskończoności
Problem sprowadza się do całkowania funkcji jednej zmiennej, która na
krańcach przedziału wykazuje osobliwość pochodnej.
Mamy scałkować g(x)*sqrt(1-x^2) na przedziale -1,1;
g(x) - funkcja określona na przedziale dowolnie skomplikowanym wzorem czy
nawet stablicowana i interpolowana; ma warunek aby była ograniczona na
przedziale i miała ograniczone pochodne.
Waga sqrt(1-x^2) powoduje jednak że całkowanie wykazuje małą zbieżność,
ponieważ na krańcach przedziału sqrt(1-x^2) ma nieograniczone pochodne więc
i g(x)*sqrt(1-x^2) ma nieograniczone pochodne.
Musimy coś zrobić z pochodną na krańcach;
Aby to zrobić transformujemy os X rozciągając i zwężając poziomo, aby
otrzymać funkcję, która będzie miała ograniczone pochodne w całym
przedziale; jeden pomysł to funkcja 1-t na przedziale <0;1) i 1+t na
przedziale (-1;0) Jednak oprócz tego że wymagane są dwie funkcje na dwóch
podprzedziałach, nieograniczenie zwężamy os X w punkcie zero, co spowoduje
problemy przy całkowaniu.
Szukamy takiej funkcji, która ma wartość 1 w zerze i w obie strony
jednostajnie się zwęża, ale ma dodatkowy warunek - w zerze ma pochodną równą
zero i w pobliżu zera jej pochodna nie jest nieograniczenie większa od
pochodnej sqrt(1-x^2)
Taki warunek spełnia funkcja 1-t^2 (gdzie t jest osią x po transformacji)
Rozwiązujemy sqrt(1-x^2) = 1-t^2
Rozwiązania według t dla x są
-sqrt(2-t^2)*abs(t) lub sqrt(2-t^2)*abs(t) dla t należącego do (-1,1)
Dla t dodatniego x musi być dodatnie a dla t ujemnego x musi być ujemne
czyli transformacja T(t) = sqrt(2-t^2)*t
Rozwiązania według x dla t są
-sqrt(1-sqrt(1-x^2)) lub t=sqrt(1-sqrt(1-x^2))
Czyli odwrotna transformacja R(x) = -sqrt(1-sqrt(1-x^2)) dla x<0
i sqrt(1-sqrt(1-x^2)) dla x>=0
Jako przykład weźmiemy g(x) = x^2, czyli całkujemy x^2*sqrt(1-x^2)
Na przedziale (-1;1) ma wartość Pi/8 = 0.39269908169872
Na przedziale (1/2;1) ma wartość Pi/24+sqrt(3)/64 = 0.15796298776783
Skorzystajmy z całkowania metodą Romberga na przedziale (a,b), w Delphi:
function Romberg(a,b: double;r:integer):real;
const
rmax = 31;//max for signed int64
var
h0,h,h2,x: real;
Iarr: array[0..1,0..rmax-1] of real;
temp_sum: real;
i,j,j_1: integer;
exp_2: integer;
exp_4,exp_4_1: int64;
begin
result := 0;
if r>rmax then raise exception.Create('Romberg: r parameter too big');
exp_2 := 1;
exp_4 := 1;
h0 := b-a;
h := h0;
Iarr[0,0] := h*(f(a)+f(b))/2.0;
for i:=1 to r-1 do
begin
temp_sum := 0.0;
exp_2 := exp_2 shl 1;
h := h0/exp_2;
h2 := h+h;
j := 1;
x := a+h;
while j<exp_2 do
begin
temp_sum := temp_sum + f({a+j*h)}x);
x := x+h2;
inc(j,2)
end;
Iarr[0,i] := Iarr[0,i-1] * 0.5 + temp_sum * h;
end;
for j:=1 to r-1 do
begin
exp_4 := exp_4 shl 2;
exp_4_1 := exp_4-1;
j_1 := j-1;
for i:=0 to r-j-1 do
begin
Iarr[j mod 2,i] := (exp_4*Iarr[j_1 mod 2,i+1]
- Iarr[j_1 mod 2,i])/(exp_4_1);
result := Iarr[j mod 2,i]
end;
end;
end;
Najpierw liczymy bez transformacji; wtedy f będzie postaci:
function f(x:real):real;
begin
result:=x*x*sqrt(1-x*x);
end;
Teraz uwzględnijmy transformację - procedura Romberg podaje nam t, z tego
obliczamy x
za pomocą transformacji T(t) = sqrt(2-t^2)*t; mając x możemy obliczyć naszą
wartość
x*x*sqrt(1-x*x); transformacja spowodowała że przy krańcach przedziału
będzie zagęszczenie "słupków" całkowania, co powoduje że należy użyć
funkcji, która będzie zmniejszała ich wagę; jako wagi użyję pochodnej T(t)
T'(t) = sqrt(2-t*t)-t*t/sqrt(2-t*t) i pomnożę przez wynik
Ostatecznie mamy:
function f(t:real):real;
var
x: real;
w: real;
begin
x:=sqrt(2-t*t) * t;
result:=x*x*sqrt(1-x*x);
w:=sqrt(2-t*t)-t*t/sqrt(2-t*t);
result:=result*w;
end;
(uwaga: w celu optymalizacji można jednokrotnie wyliczyć wyrażenie
sqrt(2-t*t), które tu występuje trzykrotnie)
Wtedy rezultaty dla różnych r, liczonych z
for r:=1 to 10 do
writeln(r,' ',Romberg(-1,1,r)-Pi/8:15:15); //powyżej 15 miejsca błędy
zaokrągleń
a)bez transformacji:
1 -0.392699081698724
2 -0.392699081698724
3 -0.084778938130924
4 -0.026444296608318
5 -0.008915896820316
6 -0.003087651304315
7 -0.001081158639064
8 -0.000380469826902
9 -0.000134208797748
10 -0.000047396175662
b)z transformacją
1 -0.392699081698724
2 -0.392699081698724
3 0.136451180514194
4 -0.003331691698791
5 -0.000024669713825
6 -0.000000173015446
7 -0.000000000629977
8 -0.000000000000978
9 -0.000000000000001
10 0.000000000000000
Teraz liczymy na przedziale (1/2;1)
a) bez transformacji używając w pętli:
writeln(r,' ',Romberg(1/2,1,r)-(Pi/24+sqrt(3)/64):15:15);
1 -0.157962987767838
2 -0.015901199149510
3 -0.004634817410605
4 -0.001558172573518
5 -0.000541806511721
6 -0.000190341884640
7 -0.000067113794177
8 -0.000023698915767
9 -0.000008373882403
10 -0.000002959761215
b) z transformacją; tu uwaga - o ile przedtem przedział (-1;1) został
transformowany również na (-1;1) (tak samo bez zmian będzie (-1;0) i (0;1) )
tak teraz do obliczenia przedziału t należy użyć transformacji R
R(x) = -sqrt(1-sqrt(1-x^2)) dla x<0 i sqrt(1-sqrt(1-x^2)) dla x>=0
wtedy będziemy mieli przedział t od sqrt(3)/2-1/2 do 1
writeln(r,' ',Romberg(sqrt(3)/2-1/2,1,r)-(Pi/24+sqrt(3)/64):15:15);
1 -0.157962987767838
2 0.010028273525767
3 -0.000125429942587
4 -0.000000843440424
5 -0.000000002965530
6 -0.000000000005676
7 -0.000000000000005
8 0.000000000000000
9 -0.000000000000001
10 0.000000000000001
W ten sposób można całkować z niewygodną funkcją sqrt(1-x^2), co zwłaszcza
się przydaje gdy chcemy scałkować dwuwymiarowy obszar będący kołem.
From: =?iso-8859-2?Q?=A3ukasz?= Kalbarczyk <lukaszusun topocztowy.net>
Subject: Re: LICZENIE EKSTREMUM FUNKCJI
Dnia Tue, 9 Oct 2007 04:47:42 CST, Rafał Drobot napisał(a):
> Witam, mam takie zadanie
>
> podpunkt b)
>
> Zbadaj czy funkcja d(x) posiada ekstremum, a jesli tak czy jest to minimum,
> czy maksimum.
>
> d(x) = f(1 + (x/f-x) + (f-x/x)
> d(x) = f( (x/f-x) + (f/x) )
Czy maturzysta mógłby pisać te napisy tak, żeby miały sens :>?
Rozumiem, że f to stała, a nie funkcja -- ot tak, żeby było fajniej,
zatem d(x)=f*(x/f+f/x-x). Oczywiście stała f na początku jest
do niczego niepotrzebna i dla czytelności warto ją chwilowo pominąć
i zająć się x/f+f/x-x.
A może chodzi o f(1+x/(f-x)+(f-x)/x)?
Wtedy do zadanie można rozwiązać niemal w pamięci.
Kładąc y(x)=f/x-1 mamy oczywiście y'(x)=-f/x^2 i do zbadania
funkcję y(x)+1/y(x). Ekstremum może być tylko dla y(x)=+/-1,
bo pochodna y(x) jest stale ujemna, czyli tutaj dla x=f/2.
y(x) w otoczeniu 1/2 jest dodatnie, czy ujemne?
Czy więc jest to minimum, czy maksimum?
Jak to zależy od f?
> W celu obliczenia wartości ekstremalnej liczę pierwszą pochodną funkcji i
> przyrównuję ją do zera.
> d'(x) = f ( [f/(f-x)^2] - (f/x^2) )
> po rozwiązaniu d'(x)=0
> x=f/2
> ====================================
> Moje pytanie tyczy się określenia czy jest to wartość maksymalna czy
> minimalna
> ====================================
> W tym celu należy policzyć 2gą pochodną dla f/2 i sprawdzić czy jest większa
> czy mniejsza od zera (większa - minimum; mniejsza - maksimum)
> (teoretycznie powinno byc to minimum, gdyż jest to część zadania z fizyki, w
> którym jest jeszcze rysunek)
> Mój problem polega na tym, że nie wychodzi mi
> obliczenie 2giej pochodnej.
> (wychodzi dość skomplikowane równanie z (x^-4) między innymi) Mógłby tu ktoś
> napisać mi krok po kroku odpowiedź, abym mógł przeanalizować gdzie popełniam
> błąd?
NIe za bardzo widzę, jak do obliczenia drugiej pochodnej w f/2 trzeba
rozwiązać jakiekolwiek równanie.
--
ŁK (10.10.2007 10:52:09)
From: Gik <patatai aol.com>
Subject: Re: =?ISO-8859-2?Q?Ca=B3kowanie_na_kole?=
zdumiony napisał referat i udostępnił go publicznie.
Mniejsza o to jaki jest udział autora w tym opracowaniu. Istnieje wiele
opisów metod całkowania numerycznego, które rozwiązują efektywne jakieś
cząstkowe problemy. Jednym z przykładów jest opis dostarczony przez
'zdumionego'.
Niestety w opracowaniu tym jest wiele uproszczeń.
> Można zauważyć, że nawet gdy użyjemy dobrej metody całkowania jak metodą
> Romberga, to jednak nie będzie dobrej zbieżności; spowodowane jest to
> tym, że dla Y = -1 lub Y = 1 bardzo szybko maleje długość scanlinii i na
> końcach ich pochodna dąży do (minus, plus)nieskończoności
Metoda Romberga nie jest metodą całkowania numerycznego, tylko metodą
iteracyjnego zmniejszenia błędów obliczeń. Metoda zastosowania poniżej
to metoda trapezów z stałym krokiem całkowania z wykorzystaniem metody
Romberga do zmniejszenia błędów całkowania numerycznego
> Problem sprowadza się do całkowania funkcji jednej zmiennej, która na
> krańcach przedziału wykazuje osobliwość pochodnej.
> Mamy scałkować g(x)*sqrt(1-x^2) na przedziale -1,1;
No właśnie. To właśnie powoduje, że autor ( ten książkowy) przygotował
sobie 'chłopca do bicia'. Przykład właśnie wymaga zmiennego kroku
całkowania. Uprzedzę że dalsze rozważania o uzmnienieniu kroku
całkowania są OK
> Musimy coś zrobić z pochodną na krańcach;
> Aby to zrobić transformujemy os X rozciągając i zwężając poziomo, aby
> otrzymać funkcję, która będzie miała ograniczone pochodne w całym
> przedziale; jeden pomysł to funkcja 1-t na przedziale <0;1) i 1+t na
> przedziale (-1;0).......
Rozumowanie to( łącznie z tym co opuściłem) jest oczywiście poprawne. Ma
jednak jedna bardzo istotną wadą : dla każdej innej 'wagi' musimy na
nowo poszukiwać metody odpowiedniej dla naszej funkcji
> Jako przykład weźmiemy g(x) = x^2, czyli całkujemy x^2*sqrt(1-x^2)
> function Romberg(a,b: double;r:integer):real;
> function f(x:real):real;
> begin result:=x*x*sqrt(1-x*x); end;
> Teraz uwzględnijmy transformację - procedura Romberg podaje nam t, z
> Ostatecznie mamy: // dla transformacji funkcji
> function f(t:real):real;
> var x: real; w: real;
> begin x:=sqrt(2-t*t) * t; result:=x*x*sqrt(1-x*x);
> w:=sqrt(2-t*t)-t*t/sqrt(2-t*t); result:=result*w;
> end;
Widzimy tutaj znacznie więcej obliczeń, co dla komputera nie jest
problemem ale na pewno znalezienie tych relacji przez obliczającego jest
jednak czasochłonne
>
> Wtedy rezultaty dla różnych r, liczonych z
Wyniki, które zostały zamieszczone są oczywiście OK. Bo takie miały być.
Ale jaki stąd wniosek?. Czy jest to metoda uniwersalna czy też
szczególny przypadek?
Może więc zdumiony spróbuje nam przedstawić tą metodę dla bardzo
podobnej funkcji i obliczy wartość całki w przedziale od -1 do +1 z funkcji
x^2 / sqrt(1-x^2)
żeby nie było kłopotu z dokładną wartością tej całki od razu powiem, że
wartość tej całki wynosi Pi/2
Aha, dlaczego dla funkcji x^3 sqrt[1-x^2) uzyskujemy dokładną wartość
całki w przedziale -1,+1 bez potrzeby jakieś transformacji i to nawet
dla r=2 ;)
--
Gik