Tarttisin jonkunlaista algoritmia, millä saisi laskettua kahden liukuluvun jakolaskun. Liukuluku on muotoa 0.mantissa*10^eksponentti. Koodaan javalla ja liukuluvun mantissa on tallennettuna int-tyyppiseen taulukkoon, jonka alkiot ovat mantissan numeroita. Eksponentti on tyyppiä int. Lisäksi liukuluvulla on boolean-tyyppinen tieto siitä, onko luku negatiivinen vai ei. Millasella algoritmilla pystyis jakolaskun suorittamaan?
a = 0.x * 10^A b = 0.y * 10^B c = a / b = 0.z * 10^C, missä z = x/y ja C = A-B jos z < 0.1 z = z * 10 C = C-1 Ja jos jompikumpi on negatiivinen, niin sitten tulos on negatiivinen. Jos molemmat tai ei kumpikaan negatiivisia, tulos positiivinen.
Meniköhän oikein...
Olisit voinut jatkaa siihen edelliseen aiheeseen. Siellä antamani menetelmä toimii hyvin helposti jakolaskullakin.
// (a * 10^A) / (b * 10^B) = (c * 10^C)
// a / b * 10^(A-B) = (c * 10^C)
c = a / b;
C = A - B;
if (c >= 1) { // (c >= 1) <=> (a >= b)
c = c / 10;
C = C + 1;
}Jos ongelmasi on itse taulukoiden "jakamisessa", suosittelen esimerkiksi jakokulma-algoritmin kehittämistä - sen parempaa ratkaisua on turha kehitelläkään.
Ongelma on juuri siinä taulukoiden jakamisessa. Joku sellainen algoritmi mikä käsittelee taulukoiden alkioita ja antaa vastauksena esim. uuden taulukon missä on jakolaskun vastauksen mantissa. Antakaa vinkkejä... vaikka sellaisen jakokulma-algoritmin laatimisessa... pseudokoodikin on avuksi!
No tässä yksi toteutus jakokulmalle:
KANTA = 10; // Käytämme kymmenjärjestelmää.
// Lasketaan valmiiksi taulukko jakajan moninkerroista
jakajat[0] = 0;
for (i = 1; i < KANTA; ++i) {
jakajat[i] = jakajat[i - 1] + jakaja;
}
tarkkuus = 0; // laskettuja desimaaleja
while (tarkkuus < haluttu_tarkkuus) {
// Mikä moninkerroista on liian suuri?
// Silmukan voisi korvata myös tehokkaammalla haulla
for (i = 1; i < KANTA; ++i) {
if (jakajat[i] > jaettava) {
break;
}
}
// Suurta edellinen tietenkin on sopiva.
i = i - 1;
// Tästä saatiin seuraava desimaali
tulos[tarkkuus] = i;
++tarkkuus;
// Vähennetään ja kerrotaan kymmenellä (ts. siirretään numeroita)
jaettava = KANTA * (jaettava - jakajat[i]);
if (jaettava == 0) {
break; // Jako meni tasan
}
}Jakolasku on siis mahdollista toteuttaa vertailujen, vähennyslaskun ja 10:llä (tai muulla järjestelmän kantaluvulla) kertomisen avulla.
kiitos! perehdyn tuohon lähiaikoina..
Samaan tapaan pitäisi nyt toteuttaa kertolaskualgoritmi. Joku sellainen mikä laskisi kertolaskun esim. "allekkain". Välitulokset ei saisi olla niin pitkiä, ettei ne mahdu int-muuttujaan, tai muuten pitää tallettaa ne johonkin toisen tyyppiseen muuttujaan. Vinkkejä algoritmiin?
Kertolasku on helppoa: nollalla kerrottaessa saadaan nolla ja ykkösellä kerrottaessa kopioidaan toinen tulon tekijä: esim.
100010101 000000110 --------- 000000000 100010101 100010101 ------------ 1100111111
Hmm. Sisennys ei näemmä toimikaan kunnolla.
Mod. lisäsi kooditagit
Tarkotus ois kertoa lukuja keskenään, missä on kaikkia numeroita eikä vaan nollia ja ykkösiä. Se vois onnistua jotenkin niin, että jakais sen kertolaskun useampaan pienempään kertolaskuun, joiden tulokset sitten summaisi.
Palvy kirjoitti:
Tarkotus ois kertoa lukuja keskenään, missä on kaikkia numeroita eikä vaan nollia ja ykkösiä.
Entä jos luvun muuttaa binäärimuotoon?
Binäärimuotoon muuttaminen kuulostaa muuten hyvältä, mutta kun kymmenkantainen luku muutetaan binäärimuotoon, se on binäärimuodossa huomattavasti pidempi (kasvaa eksponentiaalisesti?). Ja luvut on tarkoitus esittää siten, että luvun mantissa on int-tyyppisen taulukon alkioina ja int-tyyppiseen taulukkoon mahtuu muistaakseni jotain miljoona tai 10 miljoonaa alkiota, joka olisi siis binääriluvun pituuden yläraja. Tällöin ainakin luvun pituuden yläraja olisi huomattavasti alempi, jos käytetään binäärilukuja, kuin että jos käytettäisiin ihan normaaleja 10-kantaisia lukuja. Olenko oikeassa?
Ehkä joku "allekkainlaskualgoritmi" olisi kätevä tässä kertolaskussa?
Divide and conquer - algoritmille toteutusta haeskelen. Ehdotuksia?
Nyt taidat olla vähän hukassa. Ei se ole mikään spesifinen algoritmi.
Mikä ongelma sen allekkain laskun tekemisessä nyt on? Osaatko ollenkaan itse ohjelmoida? Ohjelma toimii aivan samalla tavalla kuin paperialgoritmi.
Jos luku muutetaan kymmenjärjestelmästä kaksijärjestelmään, sen numeroiden määrä ei kasva "eksponentiaalisesti" vaan noin kolminkertaistuu. Tämän näkee siitä, että jos kymmenjärjestelmän luvussa on n numeroa, sen suuruus on suunnilleen 10n, ja tämän luvun voi esittää kaksijärjestelmässä suunnilleen log2(10n) eli n*log2(10) numerolla.
Mitähän tarkoitat tuolla "hajota ja hallitse" -algoritmilla? Jos luvuissa on kovin monta numeroa, kertolaskun voi toteuttaa alakoulumenetelmää nopeammin jakamalla kertolaskun sopivasti pienemmiksi kertolaskuiksi, jotka lasketaan rekursiivisesti. Mutta minä ehkä ainakin ensin tekisin kertolaskun ihan tavalliseen tapaan ja tutkisin, onko helppo toteutus riittävän nopea.
Teetkö muuten tätä ohjelmaa omaksi huviksesi vai onko tämä koulutehtävä tai vastaava? Jälkimmäisessä tapauksessa onko jossain nähtävillä tehtävänantoa?
No tällä hetkellä pohdin et mikä vois olla tehokkaampi algoritmi kuin perinteinen allekkainlaskualgoritmi, jossa jokainen luku joudutaan kertomaan jokaisella luvulla, esim. tossa toi ylin tapa http://fi.wikipedia.org/wiki/Kertolasku Suoritusaika kasvaa aika pahasti kun luvut pitenevät.
Sitten löysin tämmösen: http://en.wikipedia.org/wiki/Schönhage-Strassen_algorithm
Tuosta en vaan tajua "Convolutions" -otsikon alla kohtaa: "you just perform the carrying (for example, in the rightmost column, you'd keep the 8 and add the 1 to the column containing 27)".
Ja tossa tehtävänanto: http://www.cs.hut.fi/Opinnot/T-106.1223/k2008/suunnittelutehtava/tehtava.shtml
nojjoo.. ehkä mä teen eka ton perinteisen allekkainlaskun :)
Ole tarkkana! Schönhagen-Strassen toimii kokonaisluvuilla, mutta tehtävässä tarvitaan ilmeisesti myös desimaaliluvuille mielivaltaista tarkkuutta. Pelkkä Schönhagen-Strassen ei käsittääkseni ota kantaa siihen, mihin kohtaa desimaalipilkku tulee tuloksessa laittaa. Tämä ei varmaankaan ole vaikeaa lisätä algoritmiin, en tiedä, sillä en ole algoritmiin tutustunut.
Tuo "you just perform the carrying (for example, in the rightmost column, you'd keep the 8 and add the 1 to the column containing 27)." tarkoittaa, että kun tulos on muodossa (4, 13, 28, 27, 18), 18 muutetaan 8:ksi ja ykkönen lisätään lukuun 27. Tulokseksi tulee (4, 13, 28, 28, 8).
No mutta desimaaliluvuthan voi muuttaa kokonaisluvuiksi ja kymmenpotensseiksi:
1,234 * 5,6789 = 1234 * 10^(-3) * 56789 * 10^(-4) = 1234 * 56789 * 10^(-7) = 70077626 * 10^(-7) = 7,0077626
Luultavasti tämä on muutenkin järkevin ilmaisumuoto, ettei tarvitse pilkun kanssa tapella.
Metabolix kirjoitti:
No mutta desimaaliluvuthan voi muuttaa kokonaisluvuiksi ja kymmenpotensseiksi:
Ei voi aina. Tehtävässä edellytettiin mielivaltaisen tarkkuuden laskinta, joten esimerkiksi lukua pii ei voi esittää muodossa n*10^m, missä n ja m ovat kokonaislukuja. Tuota muotoa olevat luvut ovat aina piin likiarvoja.
Jaska kirjoitti:
Metabolix kirjoitti:
No mutta desimaaliluvuthan voi muuttaa kokonaisluvuiksi ja kymmenpotensseiksi:
Ei voi aina. Tehtävässä edellytettiin mielivaltaisen tarkkuuden laskinta, joten esimerkiksi lukua pii ei voi esittää muodossa n*10^m, missä n ja m ovat kokonaislukuja. Tuota muotoa olevat luvut ovat aina piin likiarvoja.
Eivätkös desimaaliluvut ole aina likiarvoja? Pii on tarkka-arvo, mutta kaikki sen desimaaliesitykset ovat likiarvoja. Et voi kirjoittaa paperille äärettömän montaa desimaalia.
Gaxx kirjoitti:
Eivätkös desimaaliluvut ole aina likiarvoja? Pii on tarkka-arvo, mutta kaikki sen desimaaliesitykset ovat likiarvoja. Et voi kirjoittaa paperille äärettömän montaa desimaalia.
3.0 on luvun 3 tarkka arvo. Mietiskelin vaan, että kun tarkkuus tulee olla mielivaltainen, tarkoittaako se sitä, että ohjelman tulisi osata muokata symbolisesti lausekkeita.
Jos tarkkuuden pitää olla mielivaltainen, niin esim.
e * 1,234 * pi^3 * e * 5,6789 = 1234 * 10^(-3) * 56789 * 10^(-4) * e^2 * pi^3 = 1234 * 56789 * 10^(-7) * e^2 * pi^3 = 70077626 * 10^(-7) * e^2 * pi^3 = 7,0077626 * e^2 * pi^3
Mistä eteenpäin sitä ei enää oikein voi viedä, jos tarkkuus halutaan pitää täydellisenä.
Vastaavasti murtoluvut voivat myös olla sellaisia, että niiden tarkkaa arvoa ei voi antaa desimaaliesityksenä, esim. 1/3.
Jaska kirjoitti:
Gaxx kirjoitti:
Eivätkös desimaaliluvut ole aina likiarvoja? Pii on tarkka-arvo, mutta kaikki sen desimaaliesitykset ovat likiarvoja. Et voi kirjoittaa paperille äärettömän montaa desimaalia.
3.0 on luvun 3 tarkka arvo. Mietiskelin vaan, että kun tarkkuus tulee olla mielivaltainen, tarkoittaako se sitä, että ohjelman tulisi osata muokata symbolisesti lausekkeita.
Mielivaltaisella tarkkuudella tarkoitettaneen tässä sitä, että mantissataulukon koko on vapaasti valittavissa, eli tarkkuus on mielivaltainen muistin rajallisuuteen saakka.
hunajavohveli kirjoitti:
Mielivaltaisella tarkkuudella tarkoitettaneen tässä sitä, että mantissataulukon koko on vapaasti valittavissa, eli tarkkuus on mielivaltainen muistin rajallisuuteen saakka.
Itse taas epäilin, että käytettävissä on Turingin kone, jolle algoritmit ja tietorakenteet tulee suunnitella. Tällöin luvuista voitaisiin ilmoittaa numeroituvasti äärettömän monta desimaalia.
mä ymmärsin tän tehtävän mielivaltaisen tarkkuuden juuri noin kun hunajatohveli kirjoitti. Eli maksimitarkkuus on int-tyyppisen taulukon alkioiden maksimilukumäärä. Se taitaa olla jotain miljoona tai 10 miljoonaa alkiota, mitä semmoiseen taulukkoon mahtuu, eli miten paljon kys. taulukko pystyy muistia varaamaan.
Metabolix: Kokeilin jakokulma-algoritmiasi laskemalla 263/14. Haluttu_tarkkuus olkoon 5. Tulostaulukkoon kaksi ensimmäistä alkiota tulee oikein, mutta tulostaulukkoon indeksillä 2 i:n arvoksi tulee 8, eikä 7 niinkuin pitäisi, sillä 263/14 = 18,786. Luultavasti myös kaikki loput alkiot tulee saamaan algoritmillasi arvon 8, koska muuttujan jaettava arvo on niin iso, että se ei ole ikinä enään pienempi kuin jakajat[i], ja näin ollen i saa aina arvon i - 1 = 8. Vai saakohan se itseasiassa arvoa ollenkaan koska break ei toteudu jaettavan ollessa niin iso...
Eiku sori kyl toi taitaa toimia oikein..
...ainakin jos jakajassa on vähintään yhtä monta numeroa kuin jaettavassa :) muulloin tulokseksi tulee jotain 999999..
No eikös niiden lukujen pitänyt jo olla muodossa 0,x ja 0,y? Sillä perusolettamuksella tuo on tehty.
Juu, ja mantissassa voi olla kyllä eri määrät numeroita. Mutta ei siinä muutakun lisää vaan nollia jakajan perään jos se on lyhyempi kuin jaettava. Sitten vaan sille eksponentin määräytymiselle pitää keksiä joku logiikka.
Tähän voi käyttää tällaista iterraatiota:
C = A / B = 1/B * A, tarvitsee siis laskea 1/B
C_(n+1) = C_n * (2 - B*C_n), kaava tulee Newtonin menetelmästä
Kun C_n on tarpeeksi lähellä (C_(n+1) - C_n < epsilon), on tulos C = C_n * A
10k desimaalia laskulle 13/131 tulee alle 100 millisekunnissa (luvun tulostaminen kestää). Luvut tosin tallennetaan 10^9 muodossa, niin voidaan laskea isompia paloja kerralla. 100k rupesi kestämään aika kauan.
Aihe on jo aika vanha, joten et voi enää vastata siihen.