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

#1

Van "elemi" osztás müvelet. Legalábbis x86-on tuti: [link]

Kérdezö:

Esetleg tudsz olyanokkal trükközni, hogy ha tudod pl hogy mindíg csak kettes hatványokkal osztasz, akkor osztás helyett jó a right shift, maradékképzéshez meg csak maskolni kell.

Vagy ha floatokkal is dolgozol és az osztód mindíg konstans, akkor csinálhatsz olyat, hogy kiszámolod compile-time az osztó reciprokát és akkor azzal szorozhatsz. A szorzás meg gyorsabb lesz, mint ha osztanál.

Lényeg a lényeg, ha csak nem tudod valahogy leszükíteni az osztók-osztandók lehetséges értékeit, akkor valószínüleg nem fogsz tudni gyorsabb algoritmust írni, mint az x86 beépített osztó utasítása.

Érdemes lehet még elolvasni az ide vágó wiki cikket:

[link]

1. Olyan, hogy maradékos osztás, nincs. Nem létezik. Osztási maradék-képzés van csak.

2. Azt nem tudni, hogy milyen tipusú változókon szeretnéd elvégeztetni a műveletet. Integer, valós?

Ha történetesen integer, nem nagyobb a gépi szó hosszánál, és az osztó is integer, emellett a kettő valamely hatványa (netán maga a hatványalap), akkor lehet biteltolást alkalmazni, ami gyorsabb a natív osztásnál.

Az egyes azt írja, hogy nincs elemi osztás a processzorokban. Ez téves infó, a mai, PC-be való processzorokban már vannak szorzó- és osztóművek.

A kis teljesítményűekben viszont gyakori, hogy még ma sincs. Ennek az az oka, hogy nem éri meg, mert sokkal drágábbá tenné a processzort és úgy lenne bennük a szorzó és osztómű, hogy a legtöbb esetben nem lennének (ki)használva.

De, mivel a kis teljesítményű processzorokat jellemzően képzett programozók programozzák, így a szorzás/osztás/kivonás műveleteket meg tudják valósítani más úton (addíció, komplemens képzés, stb.) is.

Abban már abszolút igaza van az első válaszolónak, hogy a legtöbb mai fordítóprogram nagyon okos és úgy negyed százaléknyi esetet kivéve, lehetetlen a modern, korszerű fordítókénál jobb, gyorsabb megoldást kreálni.

"Olyan, hogy maradékos osztás, nincs." -> De létezik. Pl. az Intel processzorokban is létező fogalom. "divide with remainder" néven szerepel a legtöbb dokumentációban, és arra utal, hogy egy műveletben megkapjuk a hányadost és a maradékot is. Az utasítást az utasításkészletben a DIV r/m64 fejezetben érdemes keresni.

És úgy működik, hogy a hányadost az RAX és a maradékot az RDX regiszterben adja vissza.

Igazán azt látni kéne, hozzá, hogy milyen processzorod van, és milyen környezetben kell az osztást elvégezni.

Általában ha a prociban van egész osztás és beleférsz a szóhosszba, meg abba a tartományban amibe a proci megengedi az osztást akkor a leggyorsabb az szokott lenni ha a procira bízod.

Ha nincs osztás a prociban (ami elég sok prociban nincs, még azok közül is, amelyek amúgy pl. szorozni tudnak), vagy olyan a számok nagyságrendje, hogy nem tud vele a proci mit kezdeni akkor van több osztási algoritmus. Ilyenkor fel kell ezeket túrni és meg kell nézni, hogy a Te környezetedben (proci, op.rendszer, számok nagyságrendje, szóhosszak stb.) melyik lesz a nyerő megoldás. Egészen sok időt el lehet szúrni azzal, mire az ember eljut odáig, hogy jó osztó programja legyen.