Pienin yhteinen nimittäjä
Juha.Lyytik...@kolumbus.fi
Millaisia algoritmej� on ratkaista suurien lukujen (alle 10 kpl) PYJ?
Risto Kauppila
> Moi,
>
> Millaisia algoritmej� on ratkaista suurien lukujen (alle 10 kpl) PYJ?
>
>
Palautuu suurimman yhteisen tekij�n (SYT) laskemiseen, sill�
PYJ(n_1,n_2,...,n_r) = |n_1*n_2*...*n_r|/SYT(n_1,n_2,...,n_r).
SYT voidaan laskea Eukleideen algoritmilla.
http://fi.wikipedia.org/wiki/Eukleideen_algoritmi
Ohman
<risto.kauppi...@NOSPAM.saunalahti.fi.invalid> wrote:
> Juha.Lyytikainen-sa...@kolumbus.fi kirjoitti:
>
> > Moi,
>
> > Millaisia algoritmejä on ratkaista suurien lukujen (alle 10 kpl) PYJ?
>
> Palautuu suurimman yhteisen tekijän (SYT) laskemiseen, sillä
> PYJ(n_1,n_2,...,n_r) = |n_1*n_2*...*n_r|/SYT(n_1,n_2,...,n_r).
> SYT voidaan laskea Eukleideen algoritmilla.http://fi.wikipedia.org/wiki/Eukleideen_algoritmi
Olkoot luvut 2,4,6.SYT(2,4,6) = 2 ja PYJ(2,4,6) = 12. 2 x 4 x 6 = 48,
mutta 48 / 2 = 24 eikä suinkaan 12..
Tuolla kaavan nimittäjänä ei saa olla lukujen n_1, n_2, ...,n_r SYT
vaan sen pitää olla lukujen
n_1,n_2,..n_(k-1),n_(k+1)...n_r SYT. Nämä luvut ovat siis
alkuperäisten lukujen tulot, joista aina yksi luku (n_k) vuorollaan
puuttuu, siis n_1 puuttuu, sitten n_2 j.n.e.
Äskeisessä esimerkissäni nämä luvut ovat 4x6=24, 2x6=12 ja 2x4=8.
Lukujen 24,12 ja 8 SYT on 4 ja PYJ(2,4,6) oli tuo 12 ja 12 =
(2x4x6) / 4 .
Ohman
Ohman
Kirjoitusvirhe: kyseessä on siis lukujen n_1 x n_2 x...n_(k-1) x n(k
+1)...n_r (siis tuollaisten tulojen) SYT. Sanon kyllä tämän oikein
jatkossa
Ohman
Ohman
<Juha.Lyytikainen-sa...@kolumbus.fi> wrote:
> Moi,
>
> Millaisia algoritmejä on ratkaista suurien lukujen (alle 10 kpl) PYJ?
En kyllä tiedä,onko jotain " mukavaa" algoritmiä tähän tarkoitukseen,
tuo aiemmin esittämäni korjaus Kauppilan kirjoittamaan kaavaan antaa
lausekkeen,jota ei ole kovin helppo laskea,jos luvut ovat suuria.
Jos käytössä on ohjelma,joka jakaa lukuja alkutekijöihinsä, helpompi
voisi olla laskea vanhalla kunnon "koulukaavalla".Sehän menee näin:
Olkoot luvut n1,n2,...,nr
Jaetaan kukin luku ni alkutekijöihin.
Muodostetaan tulo, jossa jokainen näin saatu alkutekijä on mukana ja
esiintyy korkeimmassa potenssissa, missä se on jonkin luvun ni
alkulukuesityksessä. Tämä tulo on noiden lukujen PYJ.
Esimerkkejä:
Luvut ovat 2,4,6. 2=2, 4=2x2,6=2x3; PYJ = 2x2x3 = 12.
Luvut ovat 2,4,5,9,10,15.
2=2,4=2x2,5=5,9=3x3,10=2x5,15=3x5; PYJ = 2x2x3x3x5 = 180.
Luvut ovat 2,6,8,15.PYJ = 2x2x2x3x5 = 120.
Luvut ovat 5,6,16. PYJ = 2^4 x 3x5 = 16x15=240.
Varmaan tämän laskutavan tunsitkin ja etsit jotain vielä helpompaa
mutta liekö sellaista?
Ohman
Heikki Kaskelma
> Palautuu suurimman yhteisen tekij�n (SYT) laskemiseen, sill�
> PYJ(n_1,n_2,...,n_r) = |n_1*n_2*...*n_r|/SYT(n_1,n_2,...,n_r).
> SYT voidaan laskea Eukleideen algoritmilla.
> http://fi.wikipedia.org/wiki/Eukleideen_algoritmi
PYJ(n_1, n_2, ..., n_r) = | n_1 * n_2 * ... * n_r | / SYT(n_1, n_2, ..., n_r)^(r - 1).
Ohman
wrote:
> Risto Kauppila:
>
> > Palautuu suurimman yhteisen tekijän (SYT) laskemiseen, sillä
> > PYJ(n_1,n_2,...,n_r) = |n_1*n_2*...*n_r|/SYT(n_1,n_2,...,n_r).
> > SYT voidaan laskea Eukleideen algoritmilla.
> >http://fi.wikipedia.org/wiki/Eukleideen_algoritmi
>
> PYJ(n_1, n_2, ..., n_r) = | n_1 * n_2 * ... * n_r | / SYT(n_1, n_2, ..., n_r)^(r - 1).
Kukkua! Esim.5,6,16. 5x6x16 = 480. SYT(5,6,16) = 1. 1^(3-1) = 1.
Joten PYJ olisi 480. Mutta se on 240.
Ohman
Heikki Kaskelma
Heikki Kaskelma:
>> PYJ(n_1, n_2, ..., n_r) = | n_1 * n_2 * ... * n_r | / SYT(n_1, n_2, ...,
n_r)^(r - 1).
>Kukkua! Esim.5,6,16. 5x6x16 = 480. SYT(5,6,16) = 1. 1^(3-1) = 1.
>Joten PYJ olisi 480. Mutta se on 240.
Niinp�s onkin. Ajattelin huonosti - jos ollenkaan.
Risto Kauppila
> On 1 marras, 20:38, "Juha.Lyytikainen-sa...@kolumbus.fi"
> <Juha.Lyytikainen-sa...@kolumbus.fi> wrote:
>> Moi,
>>
>
> En kyll� tied�,onko jotain " mukavaa" algoritmi� t�h�n tarkoitukseen,
> tuo aiemmin esitt�m�ni korjaus Kauppilan kirjoittamaan kaavaan antaa
> lausekkeen,jota ei ole kovin helppo laskea,jos luvut ovat suuria.
>
> voisi olla laskea vanhalla kunnon "koulukaavalla".Seh�n menee n�in:
>
> Olkoot luvut n1,n2,...,nr
>
> Jaetaan kukin luku ni alkutekij�ihin.
>
> Muodostetaan tulo, jossa jokainen n�in saatu alkutekij� on mukana ja
> esiintyy korkeimmassa potenssissa, miss� se on jonkin luvun ni
> alkulukuesityksess�. T�m� tulo on noiden lukujen PYJ.
>
> Esimerkkej�:
>
> Luvut ovat 2,4,6. 2=2, 4=2x2,6=2x3; PYJ = 2x2x3 = 12.
>
> Luvut ovat 2,4,5,9,10,15.
>
> 2=2,4=2x2,5=5,9=3x3,10=2x5,15=3x5; PYJ = 2x2x3x3x5 = 180.
>
> Luvut ovat 2,6,8,15.PYJ = 2x2x2x3x5 = 120.
>
> Luvut ovat 5,6,16. PYJ = 2^4 x 3x5 = 16x15=240.
>
> mutta liek� sellaista?
>
> Ohman
Onkohan meill� eroa m��ritelmiss�. Minun PYJ on teoksessa Tom M
Apostol. An Introduction to Analytic Number Theory, Teht�v�ss� 1.21
m��ritelty.PyJ ei k�sitt��kseni ole lukuteoriassa kovin t�rke� k�site,
p�invastoin kuin syt.
Jussi Piitulainen
> On 1 marras, 20:38, "Juha.Lyytikainen-sa...@kolumbus.fi"
> <Juha.Lyytikainen-sa...@kolumbus.fi> wrote:
> >
> > Millaisia algoritmejä on ratkaista suurien lukujen (alle 10 kpl)
> > PYJ?
>
> En kyllä tiedä,onko jotain " mukavaa" algoritmiä tähän
> tarkoitukseen, tuo aiemmin esittämäni korjaus Kauppilan
> kirjoittamaan kaavaan antaa lausekkeen,jota ei ole kovin helppo
> laskea,jos luvut ovat suuria.
On tämmöinen: annetun lukujonon pienimpiin lukuihin lisätään
toistuvasti vastaava alkuperäinen luku kunnes jonon alkiot ovat yhtä
suuret, jolloin jono on alkuperäisen jonon (pyj, pyj, ..., pyj).
Wikipediassa (Least Common Multiple) oli selitys ja linkki.
Tiedostossa pyj.py:
def pyj(x0):
xm = x0
while min(xm) < max(xm):
xm = [ xmk if xmk > min(xm) else xmk + x0k
for (x0k,xmk) in zip(x0,xm) ]
return xm
Python-sessiossa sitten import pyj ja testitapaukset alla.
> Esimerkkejä:
>
> Luvut ovat 2,4,6. 2=2, 4=2x2,6=2x3; PYJ = 2x2x3 = 12.
>>> pyj.pyj([2,4,6])
[2, 4, 6]
[4, 4, 6]
[6, 8, 6]
[8, 8, 12]
[10, 12, 12]
[12, 12, 12]
(Tässä vaiheessa silmukassa oli käsky tulostaa xm.)
> Luvut ovat 2,4,5,9,10,15.
>
> 2=2,4=2x2,5=5,9=3x3,10=2x5,15=3x5; PYJ = 2x2x3x3x5 = 180.
>>> pyj.pyj([2,4,5,9,10,15])
[2, 4, 5, 9, 10, 15]
[4, 4, 5, 9, 10, 15]
[6, 8, 5, 9, 10, 15]
[6, 8, 10, 9, 10, 15]
... liki sata askelta ...
[176, 176, 175, 180, 180, 180]
[176, 176, 180, 180, 180, 180]
[178, 180, 180, 180, 180, 180]
[180, 180, 180, 180, 180, 180]
> Luvut ovat 2,6,8,15.PYJ = 2x2x2x3x5 = 120.
>>> pyj.pyj([2,6,8,15])
[120, 120, 120, 120]
(Nyt sitä tulostuskäskyä ei enää ole.)
> Luvut ovat 5,6,16. PYJ = 2^4 x 3x5 = 16x15=240.
>>> pyj.pyj([5,6,16])
[240, 240, 240]
En sitten tiedä, kuinka tämä käyttäytyy, kun luvut ovat niin suuria,
että niiden jakaminen tekijöihin on vaikeaa.
Ohman
<risto.kauppi...@NOSPAM.saunalahti.fi.invalid> wrote:
> Ohman kirjoitti:
>
>
>
>
>
> > On 1 marras, 20:38, "Juha.Lyytikainen-sa...@kolumbus.fi"
> > <Juha.Lyytikainen-sa...@kolumbus.fi> wrote:
> >> Moi,
>
>
> > En kyllä tiedä,onko jotain " mukavaa" algoritmiä tähän tarkoitukseen,
> > lausekkeen,jota ei ole kovin helppo laskea,jos luvut ovat suuria.
>
> > voisi olla laskea vanhalla kunnon "koulukaavalla".Sehän menee näin:
>
> > Olkoot luvut n1,n2,...,nr
>
> > Jaetaan kukin luku ni alkutekijöihin.
>
> > esiintyy korkeimmassa potenssissa, missä se on jonkin luvun ni
> > alkulukuesityksessä. Tämä tulo on noiden lukujen PYJ.
>
> > Esimerkkejä:
>
> > Luvut ovat 2,4,6. 2=2, 4=2x2,6=2x3; PYJ = 2x2x3 = 12.
>
> > Luvut ovat 2,4,5,9,10,15.
>
> > 2=2,4=2x2,5=5,9=3x3,10=2x5,15=3x5; PYJ = 2x2x3x3x5 = 180.
>
> > Luvut ovat 2,6,8,15.PYJ = 2x2x2x3x5 = 120.
>
> > Luvut ovat 5,6,16. PYJ = 2^4 x 3x5 = 16x15=240.
>
> > mutta liekö sellaista?
>
> > Ohman
>
> Apostol. An Introduction to Analytic Number Theory, Tehtävässä 1.21
> määritelty.PyJ ei käsittääkseni ole lukuteoriassa kovin tärkeä käsite,
> päinvastoin kuin syt.- Piilota siteerattu teksti -
>
> - Näytä siteerattu teksti -
Ei tässä PYJ:ssä mitään epäselvyyttä ole.Lukujen a(i), 1<= i <=n PYJ
on pienin sellainen luku, joka on jaollinen jokaisella luvulla a(i).
Esitin kaksi oikeata tapaa laskea tämän. Ensimmäinen löytyy mistä
tahansa hyvästä algebran kirjasta,jos otetaan suomalainen, niin
F.Nevanlinna:Johdatus lukuteoriaan ja algebraan. Toinen opetetaan jo
esikoulussa. Näytin myös esimerkeillä, kuinka lasketaan.
Kai nyt huomasit,että kaavasi johti heti virheelliseen tulokseen. PYJ
(2,4,6) = 12 eikä 2*4*6 / 2 = 24.
Tämä riittää minun osaltani tästä asiasta.
Ohman
Risto Kauppila
Turussa on tuota lukuteoriaa enemmän harrastettu, toivottavsti joku
heistä kommentoii tätä säiettä. Olet näköjään Python kavereita,
itse testaan matikkajuttuni Perlilä. Aika merkillistä olisi jos tuossa
Apostolin teoksessa olisi virhe.
Juha.Lyytik...@kolumbus.fi
>
> On tämmöinen: annetun lukujonon pienimpiin lukuihin lisätään
> toistuvasti vastaava alkuperäinen luku kunnes jonon alkiot ovat yhtä
> suuret, jolloin jono on alkuperäisen jonon (pyj, pyj, ..., pyj).
>
> Wikipediassa (Least Common Multiple) oli selitys ja linkki.
>
> Tiedostossa pyj.py:
>
> def pyj(x0):
> xm = x0
> while min(xm) < max(xm):
> xm = [ xmk if xmk > min(xm) else xmk + x0k
> for (x0k,xmk) in zip(x0,xm) ]
> return xm
>
Tuohan on kätevää. Samalla selviää kerroin osoittajalle kun luvut halutaan laventaa samannimisiksi.
Pohdin tässä piin arvon laskemista käyttäen laskutoimituksissa pelkästään kokonaislukuja.
Ohman
wrote:
Vaikka lupasinkin jo olla puuttumatta enää tähän tehtävään, en näy
malttavan olla esittämättä vielä erästä huomiota.Olkoot luvut a(i),
1<= i <= r
Tuo esittämäsi tapa johtaa sellaisiin lukuihin n(1),....,n(r), että n
(1) a(1) = n(2) a(2) = ...=n(r) a(r)
Ohman
>
> - Näytä siteerattu teksti -
Jatketaan,klikkasin vahingossa lähetä-kenttää ennen aikojaan!
Olkoon n(i)a(i) = D. on selvää, että D on jaollinen jokaisella luvulla
a(i).Se on ensimmäinen tällainen luku, joka menetelmällä
löytyy,laskenta pysäytetään siihen.
Minun esittämässäni 1. tavassa muodostetaan luvut
b(1) = a(2) a(3)...a(r)
b(2) = a(1) a(3)...a(r)
.
.
b(i) = a(1)a(2)...a(i-1)a(i+1)...a/r)
.
.
b(r) = a(1)....a(r-1)
Siis yksi luvuista a(i) vuorollaan puuttuu noista tuloista.Olkoon
kaikkien a(i)-lukujen tulo T. Tällöin a(1) b(1) = a(2) b(2) =...=a(r)
b(r) = T.
Jokainen luvuista a(i) tietenkin jakaa T:n ja T on siis niiden
yhteinen jaettava.Se ei kuitenkaan välttämättä ole pienin yhteinen
jaettava, sillä jos d = lukujen b(i) SYT ja merkitään
n(i) = b(i) / d,on n(1) a(1) = n(2) a(2)=...n(r) a(r) = D = T / d ja
jokainen a(i) jakaa luvun D.Tämä pätee tietenkin myös silloin kun d =
1.
Nämä luvut n(i) = b(i) / d ovat juuri ne samat n(i) - luvut,jotka
löytyvät tuolla sinun esittämälläsi algoritmillä.Ja D on tuo a(i)-
lukujen PYJ ja sama D joka löytyi esittämälläsi algoritmillä.
Niin että ihan samoista asioista näissä on kyse!
Ohman
Juha.Lyytik...@kolumbus.fi
> Jussi Piitulainen kirjoitti:
>>
>> On tämmöinen: annetun lukujonon pienimpiin lukuihin lisätään
>> toistuvasti vastaava alkuperäinen luku kunnes jonon alkiot ovat yhtä
>> suuret, jolloin jono on alkuperäisen jonon (pyj, pyj, ..., pyj).
>>
>> Wikipediassa (Least Common Multiple) oli selitys ja linkki.
>>
>> Tiedostossa pyj.py:
>>
>> def pyj(x0):
>> xm = x0
>> while min(xm) < max(xm):
>> xm = [ xmk if xmk > min(xm) else xmk + x0k
>> for (x0k,xmk) in zip(x0,xm) ]
>> return xm
>>
>
> Tuohan on kätevää. Samalla selviää kerroin osoittajalle kun luvut
> halutaan laventaa samannimisiksi.
Murtoluvussa osoittajat voivat olla samanlaisessa vektorissa ja niitä voi summata samassa loopissa kuin nimittäjiä. Jos siis tavoitteena on samalla nimittäjällä olevat murtoluvut.
Timo Korvola
> Wikipediassa (Least Common Multiple) oli selitys ja linkki.
>
> Tiedostossa pyj.py:
>
> def pyj(x0):
> xm = x0
> while min(xm) < max(xm):
> xm = [ xmk if xmk > min(xm) else xmk + x0k
> for (x0k,xmk) in zip(x0,xm) ]
> return xm
Voi isoilla luvuilla hieman kest��, koska tuo tekee jokaista i kohti
pyj(x0) / x0[i] yhteenlaskua.
Useamman luvun tapauksen voi palauttaa kahteen lukuun, sill�
pyj(x1, x2, ..., xn) = pyj(x1, pyj(x2, ..., xn)).
Kahden luvun tapauksen voi rouskuttaa Eukleideen algoritmilla:
pyj(x1, x2) = x1 x2 / syt(x1, x2).
--
Timo Korvola <URL:http://www.iki.fi/tkorvola>
Juha.Lyytik...@kolumbus.fi
> Jussi Piitulainen <jpii...@ling.helsinki.fi> writes:
>> Wikipediassa (Least Common Multiple) oli selitys ja linkki.
>>
>> Tiedostossa pyj.py:
>>
>> def pyj(x0):
>> xm = x0
>> while min(xm) < max(xm):
>> xm = [ xmk if xmk > min(xm) else xmk + x0k
>> for (x0k,xmk) in zip(x0,xm) ]
>> return xm
>
> Voi isoilla luvuilla hieman kest��, koska tuo tekee jokaista i kohti
> pyj(x0) / x0[i] yhteenlaskua.
Luulisi ett� bin��rimuotoinen yhteenlasku on koneelle nopea toimitus. Luuppi on koneelle vain yksi hyppyk�sky.
Suurien lukujen vertailun nopeudesta en tied�. P��asia ett� luvut s�ilyv�t yhdess� muuttujassa jota ei sijoitella uudelleen. Kokonaislukujen k�yt�ll� pyrit��n eroon jakolaskusta.
Jussi Piitulainen
> Timo Korvola kirjoitti:
> > Jussi Piitulainen <jpii...@ling.helsinki.fi> writes:
> >> Wikipediassa (Least Common Multiple) oli selitys ja linkki.
> >>
> >> Tiedostossa pyj.py:
> >>
> >> def pyj(x0):
> >> xm = x0
> >> while min(xm) < max(xm):
> >> xm = [ xmk if xmk > min(xm) else xmk + x0k
> >> for (x0k,xmk) in zip(x0,xm) ]
> >> return xm
> > kohti pyj(x0) / x0[i] yhteenlaskua.
>
> toimitus. Luuppi on koneelle vain yksi hyppykäsky. Suurien lukujen
> vertailun nopeudesta en tiedä. Pääasia että luvut säilyvät yhdessä
> muuttujassa jota ei sijoitella uudelleen. Kokonaislukujen käytöllä
> pyritään eroon jakolaskusta.
Huomio on osuva: yhteenlaskujen lukumäärä kasvaa suhteessa lukujen
tuloon.
Jos haet pyj:tä neljälle nelinumeroiselle alkuluvulle - ei yhteisiä
tekijöitä - niin yhteenlaskujen määrän ilmoittaa 12-numeroinen luku,
tai sinne päin, kun pyj on 16-numeroinen.
Jos haet neljälle kahdeksannumeroiselle alkuluvulle, yhteenlaskujen
määrä on 24-numeroinen. Kahdeksalle nelinumeroiselle 28-numeroinen.
Kahdeksalle kahdeksannumeroiselle pyj on 64-numeroinen ja
yhteenlaskujen määrä 56-numeroinen. Siis luokkaa 10 potenssiin 56
yhteenlaskua, karkeasti.
Jos tehdään sekunnissa 10**12 yhteenlaskua, niin ensimmäinen tapaus
vie sen sekunnin, ja viimeinen vie 10**44 sekuntia. Vuodessa on kai
luokkaa 10**7 sekuntia. (** tässä potenssin merkkinä)
Pää on kyllä flunssasta pahasti sekaisin. Kirjoitin ylle ensin ihan
hölynpölyä ja sitten kokonaan uudelleen.
Jossain sanottiin, että syt:n laskenta-aika on suhteessa lukujen
numeroiden määrään. Silloin nelinumeroisista kahdeksannumeroisiin
siirtyminen vain kaksinkertaistaa laskenta-ajan, ei 100-kertaista tai
10000-kertaista. Näin ajatellen niitä mn/syt(m,n)-pohjaisia laskuja
kannattaa varmasti vielä tutkia. Siinähän on vain yksi jakolasku, ja
sekin menee aina tasan.
Jussi Piitulainen
> Jussi Piitulainen <jpii...@ling.helsinki.fi> writes:
> > Wikipediassa (Least Common Multiple) oli selitys ja linkki.
> >
> > Tiedostossa pyj.py:
> >
> > def pyj(x0):
> > xm = x0
> > while min(xm) < max(xm):
> > xm = [ xmk if xmk > min(xm) else xmk + x0k
> > for (x0k,xmk) in zip(x0,xm) ]
> > return xm
>
> pyj(x0) / x0[i] yhteenlaskua.
>
> pyj(x1, x2, ..., xn) = pyj(x1, pyj(x2, ..., xn)).
> Kahden luvun tapauksen voi rouskuttaa Eukleideen algoritmilla:
> pyj(x1, x2) = x1 x2 / syt(x1, x2).
Kirjoittelin tuossa pari versiota lisää ja kokeilin satunnaisilla
luvuilla. Näin niiden kävi:
xs = [1219, 1835, 1451]
pyj_rem(xs) = 3245691115 in 1.59740447998e-05 seconds
pyj_sub(xs) = 3245691115 in 4.98294830322e-05 seconds
pyj_add(xs) = 3245691115 in 15.2581701279 seconds
xs = [1239, 1244, 1399, 1224]
pyj_rem(xs) = 219942710568 in 5.79357147217e-05 seconds
pyj_sub(xs) = 219942710568 in 0.569249868393 seconds
pyj_add(xs) = 219942710568 in 2026.36223602 seconds
Selvästi paras on pyj_rem, joka käyttää Eukleideen algoritmin
jakojäännös-versiota, ja selvästi toiseksi paras on pyj_sub, joka
käyttää sitä vähennys-versiota, joka on kai alkuperäinen Eukleideen
algoritmi. Tuo Wikipediasta poimimani pyj_add räjähtää käsiin: neljän
pienen luvun pyj:n laskeminen vie siltä yli puoli tuntia, kun muut
laskevat sen sekunnin murto-osissa. Tulos on sentään oikea.
Kilpailuun osallistuneet Python-pätkät:
# pyj(pyj(x,y),z) = pyj(x,y) z / syt(pyj(x,y),z),
# Eukleideen algoritmissa jakojäännös
def pyj_rem(xs):
p = 1
for x in xs:
p *= x // syt_rem(p,x)
return p
def syt_rem(x,y):
while y > 0:
x, y = y, x % y
return x
# sama,
# Eukleideen algoritmissa vähennyslasku
def pyj_sub(xs):
p = 1
for x in xs:
p *= x // syt_sub(p,x)
return p
def syt_sub(x,y):
while y > 0:
if x > y:
x = x - y
else:
y = y - x
return x
# Wikipediasta,
# liian hidas
def pyj_add(x0):
xm = x0
minxm = min(xm)
while minxm < max(xm):
xm = [ xmk + x0k if xmk == minxm else xmk
for (x0k,xmk) in zip(x0,xm) ]
minxm = min(xm)
return xm[0]
Heikki Kaskelma
> # liian hidas
>
> def pyj_add(x0):
> xm = x0
> minxm = min(xm)
> while minxm < max(xm):
> xm = [ xmk + x0k if xmk == minxm else xmk
Eikö tässä pitäisi olla xmk < max(xm) ?
Jussi Piitulainen
Taidat olla oikeassa. Tehdyt lisäykset pysyvät kaikkiaan samoina,
mutta samalla kierroksella tedään useampia.
Laskenta-aika näyttää yleensä putoavan puoleen tai jopa kolmasosaan
entisestä. (Kymmenkunta koetta kolmella tai neljällä luvulla väliltä
100 - 200.)
def pyj_adx(x0):
xm = x0
maxxm = max(xm)
while min(xm) < maxxm:
xm = [ xmk + x0k if xmk < maxxm else xmk
for (x0k,xmk) in zip(x0,xm) ]
maxxm = max(xm)
return xm[0]
Heikki Kaskelma
> def pyj_adx(x0):
> xm = x0
> maxxm = max(xm)
> while min(xm) < maxxm:
> xm = [ xmk + x0k if xmk < maxxm else xmk
> for (x0k,xmk) in zip(x0,xm) ]
> maxxm = max(xm)
> return xm[0]
Vähän lisää nopeutta saataneen vielä, jos lisätään
kerralla xm niin, että kaikki alkiot ovat vähintään
max(xm) (siis edellinen max(xm)):
xm = [xmk + ceil((maxxm-xmk)/x0k)*x0k for (x0k,xmk) in zip(x0,xm)].
Juha.Lyytik...@kolumbus.fi
Alkuperäisessä ongelmassa (piin laskeminen) on kysymys tästä kaavasta
http://upload.wikimedia.org/math/a/1/e/a1e9cdd753103629a0dcea20304df9a0.png
siinä laskettavien lukujen nimittäjät ovat 8i+1, 8i+4, 8i+5 ja 8i+6 ja i juoksee kohti ääretöntä. Voisi kenties tehdä oletuksen millä luvulla nimittäjät vähintään pitää kertoa että PYJ saadaan kun tiedetään i?
Juha.Lyytik...@kolumbus.fi
Alkuperäisessä ongelmassa (piin laskeminen) on kysymys tästä kaavasta
Timo Korvola
<Juha.Lyytik...@kolumbus.fi> writes:
> Voisi kenties tehd� oletuksen mill� luvulla nimitt�j�t v�hint��n
> pit�� kertoa ett� PYJ saadaan kun tiedet��n i?
Tee symbolisesti. Esim. Maximalla:
(%i1) ratsimp(4/(8*i+1) - 2/(8*i+4) - 1/(8*i+5) - 1/(8*i+6));
2
120 i + 151 i + 47
(%o1) --------------------------------------
4 3 2
512 i + 1024 i + 712 i + 194 i + 15
Tuosta eteenp�in p�rj�� liukuluvuillakin, kun summaa termit lopusta
alkaen.