Sólin Sólin Rís 10:52 • sest 15:43 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 07:25 • Síðdegis: 19:43 í Reykjavík
Fjaran Fjara Árdegis: 01:09 • Síðdegis: 13:45 í Reykjavík
Sólin Sólin Rís 10:52 • sest 15:43 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 07:25 • Síðdegis: 19:43 í Reykjavík
Fjaran Fjara Árdegis: 01:09 • Síðdegis: 13:45 í Reykjavík
LeiðbeiningarTil baka

Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=
Forsíða Náttúruvísindi og verkfræði Tölvunarfræði Hvernig eru tölvur látnar velja sjálfar af hendingu milli nokkurra kosta?

Flokkun:

10.10.2000
Náttúruvísindi og verkfræði Tölvunarfræði

Hvernig eru tölvur látnar velja sjálfar af hendingu milli nokkurra kosta?

Hjálmtýr Hafsteinsson

Oftast eru notaðir svokallaðir slembitölugjafar (á ensku "random number generators"), en það eru forrit sem búa til röð talna sem lítur út eins og tölurnar hafi verið valdar af hendingu. Aðalatriðið er að ekki sé nein regla í talnaröðinni heldur að tölurnar séu nokkuð jafndreifðar á því bili sem leyfilegt er. Byrjað er með eitthvert upphafsgildi og það notað til að búa til næsta gildi í röðinni, sem síðan er notað til að búa til þarnæsta og svo koll af kolli. Röðin getur orðið mjög löng, en um leið og sama talan kemur aftur þá endurtekur öll röðin sig. Þannig má líta á slembitöluröðina sem hring og upphafsgildið segir hvar á að byrja í hringnum. Í nútíma slembitölugjöfum er lengd hringsins allt að 10300, sem er gríðarlega stór tala. Til samanburðar má nefna að talið er að fjöldi atóma í hinum þekkta alheimi sé um 1076.

Dæmi um slembitölugjafa er fall þar sem næsta slembitala er fundin með því að margfalda þá síðustu með 23, leggja 1 við og nota síðan aðeins tvo öftustu tölustafina, það er að segja afganginn þegar deilt er uppí töluna með 100. Stærðfræðilega má skrifa þetta fall sem xi+1 = (23*xi + 1) mod 100. Aðgerðin mod skilar afgangnum þegar seinna gildinu er deilt upp í það fyrra.

Ef upphafsgildi slembitölugjafans er 4 þá er næsta gildi: (23*4 + 1) mod 100 eða (92 + 1) mod 100, sem er 93. Næsta gildi er þá (23*93 + 1) mod 100, eða (2139 + 1) mod 100, sem er 40, gildið þar á eftir er (23*40 + 1) mod 100, eða 921 mod 100, sem er 21. Athugið að um leið og við fáum aftur töluna 4 þá verður næsta tala 93, síðan 40, og svo framvegis.

Þessi slembitölugjafi er ekki sérlega góður, því hann gefur okkur í mesta lagi 100 mismunandi tölur. Hægt er að bæta úr því með því að velja hærri stuðla í fallið. Til dæmis 439321 í stað 23 og 1000000 í stað 100. Þessi gerð slembitölugjafa kallast línuleg samleifaraðferð (á ensku "linear congruential method") og var mjög mikið notuð í tölvum á sínum tíma. Hún er einföld í útreikningi og virðist skila tölum sem eru nokkuð vel dreifðar. Við nánari rannsóknir kom hins vegar í ljós að hægt var að finna ákveðin mynstur í dreifingu talnanna, auk þess sem fallið var mjög viðkvæmt fyrir vali á stuðlinum sem x er margfaldað með (prófið til dæmis að nota stuðulinn 10 í stað 23 í fallinu hér að ofan). Nú er þessi aðferð yfirleitt ekki notuð, nema í gömlum forritum eða þar sem hraðinn skiptir meira máli en gæði slembitalnanna.

Þetta er allt gott og blessað. Við fáum röð handahófskenndra talna út frá gefnu upphafsgildi, en hvernig getum við valið upphafsgildið á slembinn hátt? Við þurfum eitthvert upphafsgildi til að ræsa slembitölugjafann. Fyrir sama upphafsgildi fáum við alltaf sömu röðina. Það getur hentað vel í sumum tilfellum, til dæmis þegar verið er að prófa hvort forrit virki rétt, en yfirleitt viljum við ekki að slembin forrit hegði sér alltaf eins.

Til að búa til slembið upphafsgildi þarf tölvan að hafa aðgang að raunverulega slembnum tölum. Ein leið væri að biðja notandann að kasta upp krónu nokkrum sinnum og slá inn niðurstöðurnar. Þetta þyrfti aðeins að gera í fyrsta sinn sem forritið er keyrt, því það gæti geymt hjá sér síðasta slembitölugildi og notað það í næstu keyrslu. Þetta er þó óþægilegt og tímafrekt fyrir notandann, þannig að ýmsar aðrar leiðir eru reyndar. Önnur svipuð leið er að biðja notandann að slá hundrað sinnum á einhverja lykla á lyklaborði tölvunnar og nota síðan bilið á milli ásláttanna til að búa til slembitölu. Tölvur geta mælt tíma uppá milljónustu hluta úr sekúndu, þannig að hægt er að nota milljónustu partanna úr tímanum milli lyklaborðsásláttar sem slembigildi. Það segir sig sjálft að notandi getur ekki slegið það jafnt á lyklanna að milljónustu hlutarnir séu þeir sömu. Hundruðustu hlutanir eru jafnvel ekki þeir sömu.

Ef við viljum losa notandann frá því að þurfa að gera eitthvað, þá eru til ýmsar leiðir þar sem hann þarf ekki að taka beinan þátt í smíði slembitalnanna. Það væri mögulegt að nota klukkuna í tölvunni. Þá er verið að nota sér að forritið sé keyrt upp á handahófskenndum tíma, að minnsta kosti er líklega handahófskennt á hvaða sekúndubroti innan núverandi sekúndu forritið er ræst. Aðalvandamálið við þessa aðferð er að ekki nást mjög stórar slembitölur, oft ekki nema 5-10 bitar sem hægt er að treysta að séu slembnir, en bestu slembitölugjafarnir í dag þurfa nokkur hundruð slembna bita sem upphafsgildi.

Það eru til ýmis tæki, sem hægt er að tengja við tölvuna, sem gefa slembitölur. Eitt slíkt er Geigerteljari, sem nemur geislavirkni í umhverfi tölvunnar. Það er lítil regla í þeim gögnum og henta þau því vel sem uppspretta raunverulegra slembigagna. Hægt er að kaupa Geigerteljara til að tengja við tölvu á um það bil 150 bandaríkjadali (www.aw-el.com). Ef hljóðnemi eða myndavél er tengd við tölvuna þá er jafnvel hægt að nýta sér bakgrunnssuð frá þeim tækjum sem slembigögn.

Að lokum má benda á að "raunverulega slembin gögn" er mjög loðið hugtak. Í fyrsta lagi þá hlýtur það að tengjast röð talna eða bita. Það er ekki hægt að segja að ein tala sé slembin (eða að hún sé ekki slembin!). Til dæmis ef ég á að velja tölu frá 1 til 100 af handahófi og nefni töluna 42. Er þessi tala slembin? Já og nei! Það er engin leið að vita hvort ég myndi alltaf nefna 42 eða hvort ég setti 100 gildi í pott og valdi eina tölu af þeim. Ef ég væri beðinn um að nefna fleiri tölur þá væru meiri möguleikar á að sjá hvort um raunverulegar slembitölur væri að ræða. Þó er ekki til nein örugg aðferð. Ef ég nefni tölurnar 42, 43, 44, 45, þá er ákveðin regla í þeim, en það er samt mögulegt að þær veldust á þennan hátt af handahófi úr potti. Ekki mjög líklegt, en samt mögulegt. Við myndum yfirleitt ekki telja þessa talnaröð slembna, jafnvel þó hún væri fengin á algerlega slembinn hátt, með því að draga gildin af handahófi úr potti. Það eina sem hægt er að gera er að reikna út líkurnar á því að þessi röð fengist við útdrátt úr potti, þar sem jafnar líkur eru á að sérhver tala sé valin (eins og á að vera í Lottó!). Ef líkurnar reynast mjög litlar, til dæmis minna en 1%, þá viðurkennum við ekki röðina sem slembna talnaröð.

Frekara lesefni:
  • "Biblían" um slembitölur er bók Donald Knuth, The Art of Programming: Seminumerical Algorithms 3. útgáfa. Hún inniheldur gríðarlega mikið af efni um fræðilega hlið slembitölugjafa og um tölfræðilegar prófanir á þeim.
  • Vefsíða með upplýsingum um slembitölugjafa: The pLab Project
  • Ýmislegt efni um slembitölur fyrir dulmálskóðun.

Frekara lesefni af Vísindavefnum:

Höfundur

Hjálmtýr Hafsteinsson

Hjálmtýr Hafsteinsson

dósent í tölvunarfræði við HÍ

Útgáfudagur

10.10.2000

Síðast uppfært

8.4.2019

Spyrjandi

N.N.

Efnisorð

Tilvísun

Hjálmtýr Hafsteinsson. „Hvernig eru tölvur látnar velja sjálfar af hendingu milli nokkurra kosta?“ Vísindavefurinn, 10. október 2000, sótt 3. desember 2024, https://visindavefur.is/svar.php?id=985.

Hjálmtýr Hafsteinsson. (2000, 10. október). Hvernig eru tölvur látnar velja sjálfar af hendingu milli nokkurra kosta? Vísindavefurinn. https://visindavefur.is/svar.php?id=985

Hjálmtýr Hafsteinsson. „Hvernig eru tölvur látnar velja sjálfar af hendingu milli nokkurra kosta?“ Vísindavefurinn. 10. okt. 2000. Vefsíða. 3. des. 2024. <https://visindavefur.is/svar.php?id=985>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki

Senda grein til vinar

=

Hvernig eru tölvur látnar velja sjálfar af hendingu milli nokkurra kosta?
Oftast eru notaðir svokallaðir slembitölugjafar (á ensku "random number generators"), en það eru forrit sem búa til röð talna sem lítur út eins og tölurnar hafi verið valdar af hendingu. Aðalatriðið er að ekki sé nein regla í talnaröðinni heldur að tölurnar séu nokkuð jafndreifðar á því bili sem leyfilegt er. Byrjað er með eitthvert upphafsgildi og það notað til að búa til næsta gildi í röðinni, sem síðan er notað til að búa til þarnæsta og svo koll af kolli. Röðin getur orðið mjög löng, en um leið og sama talan kemur aftur þá endurtekur öll röðin sig. Þannig má líta á slembitöluröðina sem hring og upphafsgildið segir hvar á að byrja í hringnum. Í nútíma slembitölugjöfum er lengd hringsins allt að 10300, sem er gríðarlega stór tala. Til samanburðar má nefna að talið er að fjöldi atóma í hinum þekkta alheimi sé um 1076.

Dæmi um slembitölugjafa er fall þar sem næsta slembitala er fundin með því að margfalda þá síðustu með 23, leggja 1 við og nota síðan aðeins tvo öftustu tölustafina, það er að segja afganginn þegar deilt er uppí töluna með 100. Stærðfræðilega má skrifa þetta fall sem xi+1 = (23*xi + 1) mod 100. Aðgerðin mod skilar afgangnum þegar seinna gildinu er deilt upp í það fyrra.

Ef upphafsgildi slembitölugjafans er 4 þá er næsta gildi: (23*4 + 1) mod 100 eða (92 + 1) mod 100, sem er 93. Næsta gildi er þá (23*93 + 1) mod 100, eða (2139 + 1) mod 100, sem er 40, gildið þar á eftir er (23*40 + 1) mod 100, eða 921 mod 100, sem er 21. Athugið að um leið og við fáum aftur töluna 4 þá verður næsta tala 93, síðan 40, og svo framvegis.

Þessi slembitölugjafi er ekki sérlega góður, því hann gefur okkur í mesta lagi 100 mismunandi tölur. Hægt er að bæta úr því með því að velja hærri stuðla í fallið. Til dæmis 439321 í stað 23 og 1000000 í stað 100. Þessi gerð slembitölugjafa kallast línuleg samleifaraðferð (á ensku "linear congruential method") og var mjög mikið notuð í tölvum á sínum tíma. Hún er einföld í útreikningi og virðist skila tölum sem eru nokkuð vel dreifðar. Við nánari rannsóknir kom hins vegar í ljós að hægt var að finna ákveðin mynstur í dreifingu talnanna, auk þess sem fallið var mjög viðkvæmt fyrir vali á stuðlinum sem x er margfaldað með (prófið til dæmis að nota stuðulinn 10 í stað 23 í fallinu hér að ofan). Nú er þessi aðferð yfirleitt ekki notuð, nema í gömlum forritum eða þar sem hraðinn skiptir meira máli en gæði slembitalnanna.

Þetta er allt gott og blessað. Við fáum röð handahófskenndra talna út frá gefnu upphafsgildi, en hvernig getum við valið upphafsgildið á slembinn hátt? Við þurfum eitthvert upphafsgildi til að ræsa slembitölugjafann. Fyrir sama upphafsgildi fáum við alltaf sömu röðina. Það getur hentað vel í sumum tilfellum, til dæmis þegar verið er að prófa hvort forrit virki rétt, en yfirleitt viljum við ekki að slembin forrit hegði sér alltaf eins.

Til að búa til slembið upphafsgildi þarf tölvan að hafa aðgang að raunverulega slembnum tölum. Ein leið væri að biðja notandann að kasta upp krónu nokkrum sinnum og slá inn niðurstöðurnar. Þetta þyrfti aðeins að gera í fyrsta sinn sem forritið er keyrt, því það gæti geymt hjá sér síðasta slembitölugildi og notað það í næstu keyrslu. Þetta er þó óþægilegt og tímafrekt fyrir notandann, þannig að ýmsar aðrar leiðir eru reyndar. Önnur svipuð leið er að biðja notandann að slá hundrað sinnum á einhverja lykla á lyklaborði tölvunnar og nota síðan bilið á milli ásláttanna til að búa til slembitölu. Tölvur geta mælt tíma uppá milljónustu hluta úr sekúndu, þannig að hægt er að nota milljónustu partanna úr tímanum milli lyklaborðsásláttar sem slembigildi. Það segir sig sjálft að notandi getur ekki slegið það jafnt á lyklanna að milljónustu hlutarnir séu þeir sömu. Hundruðustu hlutanir eru jafnvel ekki þeir sömu.

Ef við viljum losa notandann frá því að þurfa að gera eitthvað, þá eru til ýmsar leiðir þar sem hann þarf ekki að taka beinan þátt í smíði slembitalnanna. Það væri mögulegt að nota klukkuna í tölvunni. Þá er verið að nota sér að forritið sé keyrt upp á handahófskenndum tíma, að minnsta kosti er líklega handahófskennt á hvaða sekúndubroti innan núverandi sekúndu forritið er ræst. Aðalvandamálið við þessa aðferð er að ekki nást mjög stórar slembitölur, oft ekki nema 5-10 bitar sem hægt er að treysta að séu slembnir, en bestu slembitölugjafarnir í dag þurfa nokkur hundruð slembna bita sem upphafsgildi.

Það eru til ýmis tæki, sem hægt er að tengja við tölvuna, sem gefa slembitölur. Eitt slíkt er Geigerteljari, sem nemur geislavirkni í umhverfi tölvunnar. Það er lítil regla í þeim gögnum og henta þau því vel sem uppspretta raunverulegra slembigagna. Hægt er að kaupa Geigerteljara til að tengja við tölvu á um það bil 150 bandaríkjadali (www.aw-el.com). Ef hljóðnemi eða myndavél er tengd við tölvuna þá er jafnvel hægt að nýta sér bakgrunnssuð frá þeim tækjum sem slembigögn.

Að lokum má benda á að "raunverulega slembin gögn" er mjög loðið hugtak. Í fyrsta lagi þá hlýtur það að tengjast röð talna eða bita. Það er ekki hægt að segja að ein tala sé slembin (eða að hún sé ekki slembin!). Til dæmis ef ég á að velja tölu frá 1 til 100 af handahófi og nefni töluna 42. Er þessi tala slembin? Já og nei! Það er engin leið að vita hvort ég myndi alltaf nefna 42 eða hvort ég setti 100 gildi í pott og valdi eina tölu af þeim. Ef ég væri beðinn um að nefna fleiri tölur þá væru meiri möguleikar á að sjá hvort um raunverulegar slembitölur væri að ræða. Þó er ekki til nein örugg aðferð. Ef ég nefni tölurnar 42, 43, 44, 45, þá er ákveðin regla í þeim, en það er samt mögulegt að þær veldust á þennan hátt af handahófi úr potti. Ekki mjög líklegt, en samt mögulegt. Við myndum yfirleitt ekki telja þessa talnaröð slembna, jafnvel þó hún væri fengin á algerlega slembinn hátt, með því að draga gildin af handahófi úr potti. Það eina sem hægt er að gera er að reikna út líkurnar á því að þessi röð fengist við útdrátt úr potti, þar sem jafnar líkur eru á að sérhver tala sé valin (eins og á að vera í Lottó!). Ef líkurnar reynast mjög litlar, til dæmis minna en 1%, þá viðurkennum við ekki röðina sem slembna talnaröð.

Frekara lesefni:
  • "Biblían" um slembitölur er bók Donald Knuth, The Art of Programming: Seminumerical Algorithms 3. útgáfa. Hún inniheldur gríðarlega mikið af efni um fræðilega hlið slembitölugjafa og um tölfræðilegar prófanir á þeim.
  • Vefsíða með upplýsingum um slembitölugjafa: The pLab Project
  • Ýmislegt efni um slembitölur fyrir dulmálskóðun.

Frekara lesefni af Vísindavefnum:...