Maradék képzés


Ez a program elosztja a-t b-vel, és a maradékot adja vissza eredményként. A helyet az eredmény számára a NewNumber függvényen keresztül foglalja le. Ha nincs elég memória, akkor a visszatérési értk NULL

Az osztás a szokásos algortimus alapján történik. A b-t addig toljuk nagyobb helyiértékek felé, amíg még éppen kisebb vagy egyenlő, mint a. Természetesen a feltolás a memóriában fizikailag nem történik meg, az aktuális eltolás értékét pow változóban tároljuk. Amikor a lehetséges maximális eltolást kiszámítottuk elkezdődik a levonás. Mivel a számrendszer alapja nem 2, hanem 256, ezért lehet, hogy b felshiftelt értékének multszorosát lehet levonni. mult értékét nem lehet gyorsan kiszámítani, csak biztonságos becslést adni. Amikor ez a becslés megvan, akkor kiszámítjuk a-mult*b*256pow értékét.

mult értékének a becslése úgy van megoldva, hogy ha téved, akkor mult túl kicsi, de soha sem túl nagy. Ezért ezt a lépést addig lehet ismételni, amíg b elshiftelt értéke kisebb vagy egyenlő, mint a. Precízebben megfogalmazva mult becslése vagy a helyes értéket, vagy ennél eggyel kisebbet ad, és mult értéke soha nem nulla. Ennek eredményeképpen a belcső ciklus maximum kétszer fut le minden egyes külső ciklusban.

A belső ciklus minden egyes lefutása után a külső ciklus lefelé tolja a b számot egészan addi, míg az vissza nem kerül eredeti pozíciójára. Más szavakkal pow értékét csökkenti a program, míg az nulla nem lesz.

Number Remainder(Number a, Number b){
 register int pow;
 register Number acc;
 register u8 mult;
Kiszámítjuk a maximális eltolási értéket. A kapott szám lehet, hogy eggyel nagyobb lesz, mint a maximális érték, ahol b*256pow még levonható, de ez nem okoz gondot.
 pow = Length(a) - Length(b);
Ha a rövidebb, mint b, vagy más szavakkal, ha pow negatív, akkor az eredmény maga az a.
 if( pow <0 )return dupnumber(a); 
Gyártunk egy másolatot a-ból. Erre acc mutat. Ezt használjuk a számítás során, és itt alakul ki az eredmény.
 acc = DupNumber(a);
 if( acc == NULL )return (Number)0;
A külső ciklus elvégzi a kivonást minden egyes lehetséges eltolási pozícióra.
 for( ; pow >= 0 ; pow-- ){
Ez a ciklus lehetne egy egyszerű if abban az esetben, ha mult értékét pontosan meg tudnánk becsülni. Ezzel a becsléssel is maximum kétszer fut le.
 while( powerCompare(acc,b,pow) >= 0 ){
A biztonságos becslést a következőképpen tesszük:

A legjobb becslés az lenne, ha mult értékét beállíthatnánk a legnagyobb, acc/(b*256pow) értékénél nem nagyobb egész értékre. Mivel azonban ezt nem tudjuk kiszámítani, ezért egy alsó becslést adunk. A fenti helyett egy olyan törtet készítünk, ahol a számláló nem nagyobb, mint acc és a nevező nem kisebb, mint b*256pow.

Ebben a törtben a számlálót acc értékéből kapjuk olyan módon, hogy a legnagyobb, vagy a két legnagyobb helyiértékű digitet kivéve minden helyiértékre nullát írunk.

A nevezőben az eredeti nevező legfelső digitjét tartjuk meg, és a kisebb helyértékű digitek minegyikébe 255-öt írunk. Az egyszerűbb kezelhetőség érdekében ehhez még hozzáadunk egyet, így az alsó digitek a nevezőben is csupa nullából fognak állni, és csak a legnagyobb helyiértékű digit, amelyet nem írtunk felül 255-tel növekszik eggyel.

A teljes biztonság érdekében a valóságban kettővel növeljük meg ezt a digitet, és ha a végső eredmény nem nulla, akkor levonunlk belőle egyet. Ha az így kapott eredmény nulla, akkor mult lehet 1, hiszen biztosan tudjuk a fenti while ciklus feltételéből, hogy acc nagyobb, mint b.

 if( acc->n > b->n+pow )
 /* Ha acc-nak több digitje van, mint az eltolt b-nek. */
 mult = (POW2_8*acc->digit[acc->n-1]+acc->digit[acc->n-2])
 /
 (b->digit[b->n-1]+2);
 else
 /* Ha acc és b ugyanannyi digittel rendelkeik. */
 mult = acc->digit[acc->n-1] / (b->digit[b->n-1]+2);
 if( mult )mult--; /* We should make an underestimation. */
 if( !mult )mult = 1;/* One trial we do at least, because we know that
 * b is smaller than acc. */
 powerSub(acc,b,pow,mult);
 }
 }
 return acc;
 }

toc