Jaollisuus
klo 17:52 | 23.3.2008
Nyt ei pikaisella silmäyksellä löytynyt logiikan ja lukuteorian kirjasta, mutta onko olemassa algoritmejä, joilla mielivaltaisen suuren kokonaisluvun voisi osoittaa olevan jaollinen 3:lla? Luku on siis todella niin suuri, että sen numeroiden summan määrittäminen vie äärimmäisen pitkän ajan.
Vähennä siitä 3*10exp(x), missä x mahdollsimman suuri luku.
Toista edellinen tarpeellisen monta kertaa.
Lopulta jäljelle jäävän luvun on oltava kolmella jaollinen.
(esim. 333622-> vähennä 300000.
33622 -> vähennä 30000.
3622 -> vähennä 3000.
622 -> vähennä 300.
322 -> vähennä 300.
22 -> ei jaollinen.)
War doesn't determine who's right but who's left.
There is no such thing as an atheist in a foxhole.
Kiitän tästä. Pahoittelen noita muita topicceja, jotenkin mystisesti onnistuin kämmäämään aiheen lähettämisen.
Laske luvun numerot yhteen. Jos tulos on kolmella jaollinen, niin niin on alkuperäinen lukukin
esim.
3436776 --> 3+4+3+6+7+7+6 = 36
36 on kolmella jaollinen ja niin on alkuperäinen lukukin
P.S: Kyllähän tuossa aiemmin sanottiin jo yksi ratkaisutapa, mutta ajattelin pistää tämänkin
Egen esittämä klassinen tapa taitaa olla nopeampi (useampaan kertaan sovellettuna) kuin kuninkaan vähennyslaskumenetelmä.
Pitäisi tietää, millä tavalla tietokoneen muistissa sitten on talletettuna tämä suuri kokonaisluku ja millä tavalla on ohjelmoitu näitä valtavan pitkiä lukuja koskevat laskutoimitukset? Onko luku talletettu binäärisenä vai 10-järjestelmän lukuna? Jos binäärisenä niin mikä silloin on jaollisuusssääntö? Olisiko sama kuin 11:n jaollisuussääntö kymmenjärjestelmässä?
Salausalgoritmeissa käytetyissä luvuissa samoinkuin maailmankaikkeuden hiukkasten lukumäärässä on 'vain' kymmeniä numeroita ja suurimmissa tunnetuissa alkuluvuissa on miljoonia numeroita. Onko nyt kyseessä vielä suuremmat luvut?
Kaikki on tietokoneessa bitteinä.
Joko ihmisen kehittämä algoritmi tietylle jakajalle tai sitten vain kokeillaan, koska tietokoneissa tuota laskentakapasiteettia ja mielenkiintoa tehdä se riittää enemmän kuin ihmisessä
Kaikki on tietenkin bitteinä, ja tietokone osaa laskea vain 1+1 = 0 ja 1 muistiin
Luku voidaan kuitenkin tallettaa monella tavalla bitteinä. Esimerkiksi tallennetaan luku 13 bittijonona 1101 tai siten, että 1 (0001) on yhdessä muistipaikassa ja 3 (0011) toisessa muistipaikassa. Jälkimmäistä tapaa tarvitaan esimerkiksi, kun pitää tulostaa '13'.
Tällöin on kyseessä koneen bittimäärän ylitys, eli käytetään kahta muistipaikkaa tallentamaan suuri luku. Tämä ei kuitenkaan vaikuta siihen, että tietokone tallentaa kaikki luvut bitteinä.
Noin pikaisesti kokeillen numeroiden summasääntö toimii heksadesimaaliluvuillakin. Lukuteoriassa ehkä on jotain korkampitasoisia sääntöjä, mutta kyllä tuo summasääntö toimii käytännössä. Jos luku mahtuu nykyaikaisen tietokoneen muistiin, kone pystyy laskemaan sen numeroiden summan verraten nopeasti.
Ilmeisesti tuo on laajennettavissa pidemmillekin luvuille, ainakin 256-kantaan. Jos luku on binäärinen, prosessorin kykyjä hyödyntänee tehokkaimmin summaamalla 32 bittisiä sanoja. Summalle riittää 96 bittiä aivan varmasti, vaikka koneessasi olisi kiinni kaikki koskaan valmistetut kovalevyt ja puolijohdemuistit.