Processzor: osztás, maradékos osztás milyen bitműveletekre cserélhető le gyorsítási céllal?

7, oké, de ez sztem a sima osztás, ami szolgáltatja az eredményt és a maradékot.

Én viszont a MOD utasításra gondoltam, azt szokás manapság maradékos osztásnak becézni, de hát, az nem osztás - az eredményt nem kapjuk meg, csak a maradékot. Na de, ez is a művelet célja.

Ha az osztandó mindíg elég kicsi(mondjuk belefér 16 bitbe) és az osztó mindíg konstans(azt írtad, hogy 10) és van pár száz szabad kB memóriád, akkor kiszámolhatod elöre compile-time az osztás eredményét, maradékát.

Kipróbáltam, az én gépemen(intel core, linux) 2.3x gyorsabb egy nagy precalculated táblából kinézni az eredményt, mint végrehajtani az osztást.

Öszintén szólva nagyobb gyorsulásra számítottam. Nem nagyon szoktam ilyen performance dolgokat mérni, ha esetleg valaki jobban ért hozzá, nézzen rá, mit rontok el:

[link]

Nem tudom mennyire segithet ha megpróbalsz osztasi szabályt találni, így elmeletileg is találhatsz nagy számra hatékony szamolást.. (?)

Osztási szabály keresése: "a" alap "b"vel osztása:

a^n = k*b +/- 1 alakban érdemes

De 2 és 10-el ez nem működik, viszont 10=2*5, nezzük 5-tel:

5 osztja 2^4-1 et. ill. barmely 2^(4n)-1 -et is.

Tehát 4(*n)-esével csoportosítva a 2es számrendszerbeli szám szamjegyeit elég, majd azokat összeadva kell vizsgálni az oszthatósagot:

10'1010'1111'0101 = [10]*16^3 +[1010]*16^2 + [1111]*16 + [0101] csoporosítás érdemes mert: [....]16^n= (3*5+1)^n= binomialis tétel=[....]*(k*3*5 + 1) melynej 5 osztási maradéka éppen [....], ógy csak a maradékokkal kell számolni.

Igen ám de 2 db 4 bites szám összedás túlcsordulhat, nem hogy k db-é. Ahelyett hogy k db-ot adunk összes és ujra csoportosítani kellene négyesével 2 db összeadása után a túlcsordulásos eredményt bontjuk 2 db 4bitesre, s kvázi a túlcsordulást még hozzáadjuk az eredményhez, ami már nem okozhat másodjára túlcsordulást, hisz a max érték 2*(2^n -1)+1 =2*(n+1) -1 < 2^(n+1)

5 és 2 maradékából pedig egy kis tablazat segitsegével kikeressük 10 maradékát. pl. 7 maradéknál 5tel 2, 2 vel 1, a maradék.

Ezt kombinálhatod az előző hozzaszóló ötletével hogy előre kiszámolt értekeid vannak 2^(4n) számokig 5tel való osztásukkal, azok egész és maradék értékeivel, s nem kell közben ( nem elég nagy) felső korlátot szabni az inputnak.

A matematikai hátterét tekintve :)

Tehát a példámban a 10'1010'1111'0101 szám maradéka 5-tel annyi mint 2+10+15+5 maradéka 5-tel, ami 2 és ezt még én is kiszámoltam fejben. 2-vel való maradéka 1 így 10-el osztva 7 maradékot ad, mert /10-/5-/2 maradék-alakban:

0-0-0, 1-1-1, 2-2-0, 3-3-1, 4-4-0, 5-0-1, 6-1-0, -->((!7!-2-1)), 8-3-0, 9-4-1

Egész rész:

(szumma([....](16^n-1+1)) -maradék)/5

=szumma([....](16^n-1)/5) + szumma([....]-maradék)/5

=szumma([....]*3*szumma(16^(n-1))) + szumma([....]-maradék)/5

azaz 10'1010'1111'0101 esetén:

2*3*(16^2+16+1) + 10*3*(16+1) + 15*3*(1) +((2+10+15+5)-2)/5 = 2199

(2199-1)/2=1099 lesz az egész rész 10-el osztva, vagyis:

10'1010'1111'0101 = 1099*10 + 7 = 10997 (pipa)

Itt egy program-nyelv, és annak interpretere. Tíz perc alatt megtanulható!

[link]

Mindössze négy kulcs-szó és három operátor az egész.

Maga az interpreter 123 sornyi kód, pedig véletlenszám-generátor és trace opció is van benne.

A forrás végén, illetve az alatt vannak példaprogramok is, amik segítik a megértést.

Itt meg egy feladat.

Írj egy scriptet ami ezt: 6 * 3 + (5 - 1) / 2

ki tudja számolni.

Előzőhöz:

A '=' az értékadás operátora. Pl. B = 12

A '+' az matematikai operátorként összeadás. Pl. B = B + 2

A '+' logikai kifejezésekben viszont a '>' (NAGYOBB MINT) operátor. pl. IF B + 10 azt jelenti IF B > 10.

A '!' negálja az előtte levő változó értékét. Pl. B ! a B egyes komplemensét állítja elő.

A '!' logikai operátorként a '<>' (NEM EGYENLŐ) jelentéssel bír. Pl. IF B ! 10 JMP .END azt jelenti, hogy IF B <> 10 JMP .END

A B = B + 1 lerövidíthető erre: B +

Ez főleg ciklusok építésénél jöhet jól. Így könnyebb, gyorsabb a ciklusváltozót inkrementálni.

A nyelv zárójelezést nem ismer és a scriptek soraiban, soronként csak egy logikai és egy matematikai operátor lehet.

Az 'ASCII demo' script kimenete:

A B C D E F G H

I J K L M N O P

Q R S T U V W X

Y Z [ \ ] ^ _ `

a b c d e f g h

i j k l m n o p

q r s t u v w x

y z { | } ~

----------- (403 lines done) Code:

1 B = 1

2 M = 127

3 U = 65

4 S = 32

5 T = 10

6 JMP .LOOP

7 .SUB

8 B = 0

9 PRN T

10 RET

11 .LOOP

12 PRN U

13 PRN S

14 IF B + 7 JMP .SUB

15 U = U + 1

16 B = B + 1

17 IF M + U JMP .LOOP

18 JMP .SUB

----------- Variables (B..R, S..Z):

M 127

R 99

S 32

T 10

U 127

Ez valahogy lemaradt:

Az 'R' változó speciális. Véletlenszámokat szolgáltat. A változó írásával lehet a véletlenszámok felső értékét beállítani. Pl. az R = 340 azt jelenti, hogy az olvasáskor (pl. PRN R vagy B = R) egy 0 és 340 közötti számot fog az R változó szolgáltatni.

Az R utáni (S..Z) változók értékei a PRN utasítással használva ASCII kódok gyanánt működnek, azaz a tárolt értéküknek megfelelő ASCII karakter kerül a kimenetre (feltéve, ha nyomtatható). Ilyen módon lehet szöveget írni a kimenetre. Példa:

S = 65

PRN S

Ennek a két sornak az eredménye egy A karakter lesz a kimeneten.

S = 65

.loop

PRN S

S +

IF 67 + S JMP .LOOP

Ennek az öt sornak az eredménye meg ez: ABC

Javasolt az

S = 32 (mint space)

T = 10 (mint new line)

beállítása.

A bitsy scriptekben a ';' karakter utáni rész már komment, de csak az aktuális sor végéig. A kommenteket az interpreter nem veszi figyelembe, nem is dolgozza fel. A scriptek tartalma kis- nagybetűre nem érzékeny, minden sor kapitalizálódik, még a futtatás előtt.

Ennyi ..