Pythonin lukutarkkuus

[ilkant]

Tein yhtä matematiikkatehtävää ratkaistessani pienen python-ohjleman, joka laskee 100! arvon. Ja sen jälkeen toinen tehtävä, jossa lasektaan 1000! arvo. Hämmästyksekseni laskenta ei tuottanut ylivuotoa. Etsin sitten Googlella tietoa lukutarkkuudesta. Löytyi Wikipediasta tieto, että pyhtonilla tyypin int tarkkuus on rajoittamaton kokonaisluku.

Tuleeko kokonaisluvulle raja koneen keskusmuistin koosta? Vai osaako pyhton swapata levylle keskusmuistia suuremmat luvut?

[Jere Sumell]

On siitä jo aikaa, kun aloitin Ohjelmointiputkassa keskustelun "Rekursio vai iteraatio Kertomassa" -keskustelusäikeen, taisi olla siinä tulla vastaan, että nykyiselläänkin on rajallinen määrä rekursiota käytettäessä, mitä tietokone pystyy laskemaan niitä uudelleenkutsun arvoja.

Itseänikin tämä kiinnostaisi, kuinka Python onnistuu laskemaan noin suurien lukujen kertoman, olettaen, että käytät sen laskennassa rekursiota?

EDIT - 04.07.2022 23:36

Tuolla Ohjelmointiputkankin säikeessä keskustelukommenteissa tuli esiin, että tarpeeksi usean funktion itsensä uudelleenkutsun jälkeen lopulta ohjelman suoritus päättyy pinon ylivuodon tähden, ja sielläkin päädyttiin siihen, että jos mahdollista, kannattaa käyttää iterointia, eli toistorakennetta tässä kertoman tapauksessa.

Löysin Artturi Jallin kirjoittaman artikkelin tästä aiheesta, kuinka syvälle menevän rekursiokutsusarjan Python pystyy käsittelemään, ja oletuksena näköjään Pythonissa on Rekursiosyvyydelle 1000 kutsua. Lisäksi tuossa fyysikko Jallin artikkelissa on maininta, että kannattaa rekursion sijaan suosia iteraatiota.

Suora linkki tuohon Artturi Jallin "What Is the Maximum Recursion Depth in Python" -artikkeliin on
https://www.codingem.com/python-maximum-recursion-depth/

[ilkant]

Itseänikin tämä kiinnostaisi, kuinka Python onnistuu laskemaan noin suurien lukujen kertoman, olettaen, että käytät sen laskennassa rekursiota?

Käytin for-silmukkaa.

Koodia: [Valitse]

    a = 1
    for i in range(1, 101):
        a *= i

Ja sen jälkeen tein vielä 1000!, josta piti laskea vielä 250 viimeisen numeron summa. Nämä siis jonkun somekeskustleijan ideoita. Teki senkin niin nopeasti ja kaikki numerot olivat mukana, että mitään muuta tapaa ei ollut tarpeellista käyttää.

Kauan sitten (noin 30 vuotta sitten) lainasin kirjastosta kirjan, jossa kerrottiin laskennasta supertietokoneella. Siinä näytettiin monta tapaa fortranille, joilla vähän koodia muuntamalla saatiin huikeita aikasäästöjä suoritusajoissa. Saattoi olla myös muistin kulutuksessa. On ihan mielenkiintoista sekin tietotekniikan alue.

[Jere Sumell]

No tuo mitä olet ratkaissut tuon kertoman laskemisen ongelman iteratiivisesti, niin on totta, että iteratiivinen implementointitapa on muistin käyton kannalta tehokkaampaa, ja mitä tulee algoritmin aikakompleksisuuteen, niin iteraatio on selkeästi nopeampi, jos nyt vertaa esimerkiksi rekursiiviseen ratkaisutapaan.

Sama mikä ongelma on kyseessä, jos ongelma on rekursiivisesti ratkaistavissa, se on yleensä tottakai myos iteraativisesti ratkaistavissa, niin ei se ainoastaan tässä kertoman osalta ole niin, tuo resurssitehokkuus niin muistin käyton, kuin ajankin suhteen, että iteraatio on nopeampi, pätee joka tapaukseen.

Tuossa Aalto-yliopiston insinoorifyysikko Jallin artikkelissa, johon viittasin edellisessä kommentissani, niin Jalli päättänyt valita tuohon esimerkki-ongelmaksi yksinkertaisesta rekursiivisesti ratkeavasta ongelmasta tuo fibbonaccin lukusarjan, mutta se nyt on sama mikä se on, voihan se olla mikä tahansa.

Onhan 30 vuoden aikana nykyisten supertietokoneidenkin laskentateho ja muistikapasiteetit kasvaneet, mutta ei se ydinasia ole mihinkään kadonnut, tai ne ongelmat, joita tähän aihealueeseen liittyy. Algoritmin aikakompleksisuus, mitä on yksi, mitä täytyy miettiä algoritmiä implementoitaessa, niin vaikka olisi kuinka suuri laskentateho koneessa, niin jos algoritmi on laadittu huonosti, eli se on hidas, niin se on joka tapauksessa hidas. Eli tietokoneen laskentateholla, tai prosessorien nopeudella, jotka suorittavat lopulta sen laskennan, sillä ei ole mitään merkitystä lopulta, suoriutuuko algoritmi nopeammin vai hitaammin, eli se on ohjelmoijan ymmärrettävä laatia mahdollisimman resurssitehokkaasti se algoritmi tilanteen mukaan.

EDIT 05-07-2022 9:01

Lisäyksenä vielä vähän aikaperspektiivin laajentamiseen, että mitä kerroit lukeneesi 30-vuotta vanhaa tietokonekirjaa, niin voisi kuvitella varmasti, että jos ajatellaan, että C-kieli on julkaistu 1960-luvun lopussa, tai ainakin ollut kehitteillä, kun UNIX on julkaistu 1970-vuonna, niin sen aikaisissa tietojenkäsittelypiireissä ne ihmiset kohtasivat samat ongelmat, ja päätysivät sitten käsittelemmään ratkaisut niihin, eli ne on pysynyt sieltä asti ainakin lopulta samoina tämän aihepiirin alalla.

[ilkant]

On nämä laskenta-algoritmit edelleen tärkeitä. Käsitysteni mukaan tietokonelaskentaa käytetään nykyisin niin paljon kuin koneet mahdollistavat. Ja tämä kehitys ei pysähdy. Seurauksena saamme entistä ihmeellisempiä ja monipuolisempia simulaatioita tai ratkaisuja ja sitten edelleen parempia tuotteita kuten lääkkeitä, sääennusteita, avaruustutkimusta, bioinformaatiota, jne.

[Jere Sumell]

Olet oikeassa, arvon ilkant, näinhän se asia todellakin on omastanikin mielestä niin hyvässä kuin pahassa.

Onhan se totta, että koko ajan laskentatehojen noustessa saadaan yhä tarkempia esimerkiksi juuri sääennusteita ja pätee tosiaan muihinkin matemaattisiin malleihin pohjautuvissa laskelmissa ja simulaatioissa.

En tiedä sitten, kuinka paljon eri sovellusalojen sisällä ne matemaattiset mallit, joita sitten tietokoneen avulla lasketaan, kehittyvät, tai kuinka nopealla aikasyklillä, voi olla, että ei mitenkään kovin nopeaan tahtiin, voisi kuvitella.

Mitä ilmatieteen laitoksella opiskelijat perehtyvät niihin matematiisiin malleihin, joita säätilan ennustamiseen liittyy, niistä en tiedä se on vähän vieraampi ala, mutta lääkekehityksen osalta ja biolääketieteen kehityksen osalta juuri, että hyvässä mielessä saadaan koko ajan parempia lääkkeitä kehitettyä ihmiskunnan käyttoon ihmisten terveyden ylläpitämisen edistämiseksi, niin olen jonkin verran perehtynyt biolääketieteen lääkekehityksen sovellusalueen malleihin, mitä siellä tutkijat soveltavat, niin pintapuolisesti päätynyt evoluutioalgoritmeihin, voisi kuvitella, että ne nyt ainakin siellä on, mitä se yhteiso hyodyntää, ja se mielenkiinto kohdistuu niihin.

Ei varmaan yksistään tietokoneiden laskentatehon nousu, kun myos esimerkiksi avaruusteleskooppien optiikka, ja siihen teknologiaan liittyvä on avannut avaruustutkimuksessakin kokonaan uusia ovia ja mielenkiinnon kohteita, mutta sitten taas optiikkakin lienee juuritasolla matemaattisia malleja hyodyntävä sovellus, niin siinäkin sitten päädytään siihen, että tietokoneiden laskentatehon yhä noustessa, saadaan tarkempaa optiikkaa niihin kaukoputkiin, joilla avaruustutkimusta voi tehdä, vaikka tykkäisi vain harrastetasolla tähyillä tähtitaivasta halvemmalla jokamiehen käyttoon myytävällä kaukoputkella aukealla pellolla kaikessa rauhassa, nekin tosin kehittyneet tottakai, nuo isot avaruusteleskoopit on vain se kärkihännän huippu siellä, kyllähän se siellä meidän tavallisten kuluttajien tasollakin heijastuu se huippututkimuksen tulokset ilmenee tekniikan kehittymisenä jossain määrin.

[Jere Sumell]

Vielä haluan lisätä, että tieteenalalla, jolle tietojenkäsittelyä, tai matemaattista laskentaa koneellisesti sovelletaan, jos alalla käytetään jossain asiayhteydessä matemaattista mallia jonkin asian selvittämiseksi, niin on varmaan jo aika pitkäänkin ollut sovellukset joka mallille olemassa vähän tieteen sovellusalasta riippumatta, vaikea kuvitella, että ei olisi.

Esimerkiksi taloustieteissäkin käytetään paljonkin matemaattisia malleja, mutta kyllä niistä kaikista, jotka ovat tottakai yleisessä tiedossa, koska muita ei lopulta oikein olekaan sitten, niin kyllä niistäkin ollut jo pitkään sovellukset olemassa, en tiedä, kaikki ei ole kaupallisia, ja osalla niistä tietokonesovelluksista ei välttämättä edes ole mitään kaupallista potentiaalia, ja jos joskus sitten harvoin saattaa tulla jokin uusi malli, mikä ehkä tuo jotain uutta johonkin jo olemassaolevaan, malli kehittyy ikään kuin, niin kyllä aika pian sitten siitäkin ainakin akateemisissa piireissä siitä laaditaan tietokonesovellus.

Tästä näkökulmasta ajatellen, olisi saattanut olla järkevämpää ensin opiskella jonkin sellaisen tieteenalan tutkinto, josta on kiinnostunut, ja vasta sen jälkeen tietojenkäsittelyn tutkinto, olisi sitten ollut valmiina jokin sovellusala, paljonkin ihmisiä, ketkä opiskelleet kaksi tutkintoa juuri tässä järjestyksessä.

Siiinä mielessä nyt aivan kannata omiksi iloiksi lähteä tyhjästä ohjelmoimaan oikeastaan minkään spesifin sovellusalan matemaattisten laskennan automatisointiin pyrkivää algoritmiä, tai ohjelmisto, ellei sitten joku palkkaa tietokoneohjelmoijaksi siten, että se sovellusalan tuntemus ei nouse työn onnistuneen suorittamisen esteeksi ja siinä on sitten mahdollista ja työnantaja antaa aikaa myös perehtyä siihen sovellusalan kenttään siinä määrin, että kykenee vähän ymmärtämään sitä niin, että kykenee ohjelmoimaan sovelluksen.

EDIT: 06.07.2022 16:59

Lisäyksenä vielä, että mitä tämä laskenta ylipäätään ja luvuilla pelaaminen liittyy hyvin voimakkaasti kvantitatiivisiin tutkimusmenetelmiin, niin kysymykseen, jos vastaat itsellesi, että onko olemassa tieteen oppialaa, jossa käytetään kvantitatiivisia mentelemiä edes tukena, jossa laskentaa ei olisi koneellistettu, vaan se tehtäisiin yhä käsin 2022? Ei sellaista taida olla, vastaisin näin julkisesti.

Nämä esimerkkialat, mitä tässäkin ketjussa nyt ollut, ovat luonnontieteiden alalta, mutta ei oikein yhteiskuntatieteilijät ja humanistitkaan täysin voi välttyä jonkinlaiselta laskennalta. En tiedä, varmaan jonkin humanismin teoreettisen filosofian parissa toimivat eivät juuri harrasta kvantitatiivista tutkimusta, mutta tiedä ovatko hekään vapaita aivan kaikesta laskennasta. Logiikka-kurssikin vaatii jonkinlaista matemaattista päättelyä, mutta siihen ei nyt välttämättä tarvitse käyttää konetta apuna.

EDIT 06.07.2022

Logiikasta ja sen tietokonesovelluksista vielä, mitä humanismin flilosofian opiskelijat ensimmäinen kurssi taitaa olla se Logiikka -kurssi siellä ihan opintojen alettua, niin siitäkin olen nähnyt netissä tietokonesovelluksen. Siinä tietokonesovelluksessa, kun pistää sen ongelman kohteen logiikkalauseen syötteenä siihen lomakkeen sille varattuun kenttään kaikkineen, niin sitten tulosteena tulee se lopputulema.

EDIT 06.07.2022

Tuipa usea lisäys alkuperäiseen tähän vastaukseeni. Tietojenkäsittelyn termein, jos ongelma on algoritmisesti ratkeava, sama miltä alalta ongelma on, tai mikä se ongelma on, siitä on olemassa jo tietokonesovellus laadittuna. Ja mitä algoritmisesti ratkeamattomia ongelmia on paljon enemmän ihmisten maailmassa tällä hetkellä, kuin niitä algoritmisesti ratkeavia, niin ei ole poissuljettua, etteikö voisi jossain kohtaa, jos joku esittää pätevän ratkaisun johonkin algoritmisesti tällä hetkellä ratkeamattomaan ongelmaan, ja lopulta päädytään siihen, että todellakin se ratkaisee sen ongelman, joka sen on tarkoitettu ratkaistavaksi, niin sittenhän se siirtyy pois tuolta ratkeamattomien ongelmien listalta algoritmisesti ratkeavien joukkoon kuuluvaksi.

[Postimies]

Binääripuu on helppo esittää rekursiivisesti, Rekursion purkaminen tuosta paljon haastavampaa. Pythonia en tunne, mutta C:llä osoittimia käyttäen muistiin saa kyllä melko ison puun, josta tiedon haku melko nopeaa.

[Jere Sumell]

Mitä tuohon puurakenteen purkamiseen tulee, niin ainakin syvyys- ja leveyshaun osalta riittää ohjelmoida pino tai jono -algoritmi rekursiivisesti, mikäli ensin ne alkiot on järjestetty jollain lajittelualgorimtillä.

On ihan totta, että binääripuu on nopein läpikäytävä, mutta vaikka sitten puu ei olisikaan binääripuu, niin siinähän on kuitenkin se tietty järjestys, miten ne poikasolmut luetaan. Esimerkiksi hakemisto tai tiedostorakenne on käsittääkseni myös puu rakenteeltaan, eikä se käytännössä sekään ole binääripuu koskaan.

Ohjelmoi vaikka ajan kuluksi tietokoneen jonkin kiintolevyn hakemistopuuhun liittyvä algoritmi ja ratkaise ongelma rekursiota käyttäen. Siinäkin yhdenlaista pähkinää ja ajanvietettä, jos ei keksi mitään muuta tekemistä, ja haluaa jotain ohjelmoida.

Lisäys 11.08.2022 14:51

Jos joku on minun lisäkseni joskus miettinyt tuota, mitä noista puu-rakenteen solmuista viralliset termit ovat isä-poika -solmut tai -suhde, sitä, että mitä nuo ovat sidoksissa miessukupuolen edustajaan, että onko siinä mitään jompaa kumpaa sukupuolta epätasa-arvoistavaa, niin sen verran selvitin sitä asiaa, että sitä on tutkittu, ja lopulta ollaan päädytty siihen, että tuo termipari ei ole kumpaakaan sukupuolta epätasa-arvoistava, vaikka nuo on liitettävissäkin miessukupuolen edustajistoon.

[Postimies]

Ne on jo tehty. Fat-tiedostojärjestelmä käyttää listaa mikä on hidas. Muut tiedostojärjestelmät käyttävät puurakennetta. Tuohon löytyy paljon esimerkkejä netistä tai jostain tietorakenteita käsittelevästä kirjasta. Alkion lisäys ja haku hyvin yksinkertaista. Tasapainossa jos haluaa pitää tulee koodista pitempi kuin jokunen rivi. Muistaakseni Hanoin tornitkin ratkeaa rekursiivisesti helposti. Ohjelmointi olisi kiva harrastus, mutta aika ei riitä.

[Jere Sumell]

Varmaan tuo Hanoin Tornit lienee tunnetuin, tai yleisimmin esitetty noissa teoksissa, missä  käsitellään rekursiota, ainakin mitä itse olen selannut joitain sellaisia vähän järkevämpiä tiiliskiviä.

Oma kantani melkein on, että ohjelmointi kannattaa jättää harrastus-asteelle, niin siinä ole sillä tavalla sitten mitään stressiä pääse syntymään minkään deadlinejen kanssa, mielenterveyskin voi säästyä pidempään.

[nm]

Jos joku on minun lisäkseni joskus miettinyt tuota, mitä noista puu-rakenteen solmuista viralliset termit ovat isä-poika -solmut tai -suhde, sitä, että mitä nuo ovat sidoksissa miessukupuolen edustajaan, että onko siinä mitään jompaa kumpaa sukupuolta epätasa-arvoistavaa, niin sen verran selvitin sitä asiaa, että sitä on tutkittu, ja lopulta ollaan päädytty siihen, että tuo termipari ei ole kumpaakaan sukupuolta epätasa-arvoistava, vaikka nuo on liitettävissäkin miessukupuolen edustajistoon.

Minulle tutummat termit puun solmuille ovat vanhempi ja lapsi (sekä juuri ja lehti). Nämä myös vastaavat englanninkielisiä nimityksiä.

[Jere Sumell]

En tiedä sitten, kun itse olen nähnyt akateemisissakin lähteissä käytettävän isä-lapsi -terminologiaa.

Tuo vanhempi-lapsi olisi ehkä mielekkäämpi itsellänikin ottaa käyttöön, kun sehän on sitten jo sukupuolineutraali, mitä tykkään edistää tasa-arvon toteutumista tässä elämässäni.

En ole selvittänyt sitä, olen itse ja englannin kielisessä materiaalissa törmännyt parent-child -pariin, mutta kaikkihan nyt ei ole ihan yksi yhteen suomennettuna nyt yleensäkään muillakaan aloilla englanti-suomi -käännöksissä, ja tekniikan terminologia muutoinkin vaikuttaa vielä nykyään aika vajaavaiselta käsittääkseni.

Joku voi täsementää tähän ketjuun varmaan, jos on enemmän perillä virallisesta tekniikka-sanasto-käännöksistä, mitä suomen kielitoimisto ja muut tahot niitä virallisia määrityksiä ylläpitää, mitä nuo sitten on.

ostan tuon vanhempi-lapsi -käännöksen mielelläni omaan sanavarastooni, se on jotenkin tosiaan mielekkäämpi, kuin tuo isä-poika, johon itse olen törmännyt enemmän.