Kezdőoldal » Tudományok » Alkalmazott tudományok » Egy számítógépes program 1...

Egy számítógépes program 1 milliárd hatványait (1. ,2. , stb) használja input paraméternek, és hosszú (előjel nélküli) egészként 32 bites szavakon ábrázolja. Folytatás? Van.

Figyelt kérdés

Mikor lesz először az input legfelső szavának legfelső bitje 1-es, hányadik számnál?


Köszi!



2013. okt. 16. 11:07
1 2
 1/14 BringaManó ***** válasza:
"Folytatás? Van." xD
2013. okt. 16. 12:01
Hasznos számodra ez a válasz?
 2/14 2xSü ***** válasza:

Nem biztos, hogy egészen értem a kérdést. Egy 32 bites előjel nélküli egész esetén az első bit akkor fordul át, mikor a szám nagyobb, vagy egyenlő, mint 2^31. 2^31 = 2 147 483 648. Így:

2 147 483 646 = 0b 0111 1111 1111 1111 1111 1111 1111 1110

2 147 483 647 = 0b 0111 1111 1111 1111 1111 1111 1111 1111

2 147 483 648 = 0b 1000 0000 0000 0000 0000 0000 0000 0000

2 147 483 649 = 0b 1000 0000 0000 0000 0000 0000 0000 0001


Magyarán, ha a szám nagyobb, vagy egyenlő 2 147 483 648-al, akkor az első bit 1-es. Ha kisebb, akkor meg 0-ás.


Ha a paraméter egyszerű szám, ami 1 milliárd valamelyik hatványa, akkor 1 millárd esetén még 0 az első bit. 1 millárd négyzete meg bele sem fél egy 32 bites egészbe. Tehát a paraméter vagy 0 vagy 1 milliárd (első hatványa) lehet csak.

2013. okt. 16. 14:32
Hasznos számodra ez a válasz?
 3/14 A kérdező kommentje:

Hosszú egész: 1 milliárd négyzete, köbe, stb. 64, 96, 128, ... biten ábrázolva, szükség szerint k*32 biten.

A (szükséges) legfelső 32 biten mikor lesz nagyobb, vagy egyenlő 2 147 483 648?

2013. okt. 16. 15:05
 4/14 A kérdező kommentje:
... 32 bites szó-füzéren ábrázolja.
2013. okt. 16. 15:23
 5/14 2xSü ***** válasza:

Tehát végülis van egy (10^9)^n kifejezésünk, és az a kérdés, hogy ennek a 2^32 számrendszerben felírt alakjának első számjegye mikor nagyobb vagy egyenlő, mint 2^31. Ez elég vicces kérdés így matematikailag megfogalmazva.


Ehhez azt kell tudni, hogy mondjuk van egy n számunk, ezt m számrendszerben felírva a számjegyek számát a log_m(n) adja meg. Az első számjegyet ennek a törtrésze fogja megadni. Tehát m ^ (log_m(n) - floor(log_m(n)). Ez az első számjegy.


Itt tehát a kérdés, hogy ha van egy számunk, ami 1 millárdnak az n-dik hatványa (ahol n egész), akkor mikor teljesül a következő:


2^32 ^ (log_{2^32}((10^9) ^ n) - ⌊log_{2^32}((10^9) ^ n)⌋) >= 2^31


Vicces feladat.

2013. okt. 16. 15:57
Hasznos számodra ez a válasz?
 6/14 A kérdező kommentje:

Szerintem nincs explicit formula a megoldásra, csak grafikusan és statisztikusan lehet megközelíteni.

Erre gondolok: log2(10^9)~29,89735 ebből köv. hogy n növelésével n*(32-29,89735)=n*2,10265-el távolodik 10^9 hatványának log2-je 2^32 hatványának log2-jétől.

Tehát 32/2,10265=15,219 többszöröseinek közelében esélyes, és P=1/2,10265=0,4756 eséllyel jó.

Vagyis, ahogy gondolható átlagosan minden 32. n-re igaz.

[link]

2013. okt. 16. 17:37
 7/14 anonim ***** válasza:

Megoldás:

32 bites szavak binárisan kiírva: [link]

32 bites szavak decimálisan kiírva: [link]

2013. okt. 16. 18:55
Hasznos számodra ez a válasz?
 8/14 A kérdező kommentje:

#7: Szép! Gratulálok! Számítógéppel megoldva a "számítógépes" kérdés.


Általánosan mely 10^(9n)-re igaz?

Legyen X=log2(2^32 / 10^9)=(log2(2^32 - log2(10^9))=(32-29,89735)= X = 2,10265

A legfelső szó log2-je rendre: 32-X, 32-2X, 32-3X,... majd amikor 0 alá menne +32-vel ugrik,

(10^9*es belefér, nem növekszik a szóhossz)

ami átlagosan Y = 32/X = 15,2189 -enként történik meg.

Jól látszik: [link] és [link]

Alkalmas n-ek: k*Y (k=1,2,3...) felfelé kerekített értékei LEHETNEK: 16,31,46,61,77,92,107...

de ezek közül csak azok jók melyekre (n*X) mod 32 a (0..1) intervallumba esik: 46,61,107,122,137,183...

Szerinted?

2013. okt. 17. 12:08
 9/14 anonim ***** válasza:

"#7: Szép! Gratulálok! Számítógéppel megoldva a "számítógépes" kérdés. "


Köszönöm.


"Legyen X=log2(2^32 / 10^9)=(log2(2^32 - log2(10^9))=(32-29,89735)= X = 2,10265"

Nem jól van zárójelezve, helyesen: "Legyen X=log2(2^32 / 10^9)=log2(2^32) - log2(10^9))=(32-29,89735)= X = 2,10265"


"A legfelső szó log2-je rendre: 32-X, 32-2X, 32-3X,... majd amikor 0 alá menne +32-vel ugrik,"


0 alá menés +32 vel való ugrás az nem más mint mod 32.

Amit te írsz az nem log2-je hanem log2-ének log2-je, dehát log2-je : 2^log2(32-(1*x) mod 32), 2^log2(32-(2*x) mod 32) ... ==> A legfelső szó trunc(2^(2^log2(32-(1*x) mod 32))), trunc(2^(2^log2(32-(2*x) mod 32))) ...


"ami átlagosan Y = 32/X = 15,2189 -enként történik meg. "


Korábban meg azt írtad hogy "átlagosan minden 32. n-re igaz".

Vettem a milliárdnak az első 10000 hatványát, ezek közül listába raktam azok sorszámát melyek a feltételnek megfelelnek: [link]

Ezekből 4754 db van, ekkor mondhatom azt hogy ezek közül átlagosan minden 2.103491796381994 -ik tagra igaz.

Viszont ha máshogy veszem az átlagot egész más jön ki. A [link] listát egy szigorúan monoton növekvő sorozatnak tekintem, ebből csinálok egy másik sorozatot mely egy a növekedés mértékét tartalmazza: [link]

Ennek veszem a számtani átlagát akkor 32.00673258994319-et kapok, tapasztalat szerint ez az átlag a sorozat hosszának növelésével 32-be tart.


"Jól látszik: [link] és [link]

Alkalmas n-ek: k*Y (k=1,2,3...) felfelé kerekített értékei LEHETNEK: 16,31,46,61,77,92,107...

de ezek közül csak azok jók melyekre (n*X) mod 32 a (0..1) intervallumba esik: 46,61,107,122,137,183... "


Pontosan.

2013. okt. 17. 20:40
Hasznos számodra ez a válasz?
 10/14 anonim ***** válasza:

"Vettem a milliárdnak az első 10000 hatványát"

Elírtam, nem a milliárdnak vettem az első 10000 hatványát, hanem 16,31,46,61,77,92,107... stb hatványai közül vettem az első 10000-et.

2013. okt. 17. 20:55
Hasznos számodra ez a válasz?
1 2

Kapcsolódó kérdések:





Minden jog fenntartva © 2023, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!