Computerised long division
For x / y Where y is smaller then x.Remainder = xshift = sizeof(y);cnum = y << (sizeof(x) - sizof(y));while(1) { if (cnum > remainder) { Cnum = Cnum >> Shift; if(!Cnum){break;} remainder = remainder - cnum; div++;}Div = Result of the divisionRemainder = Modulus.
This had problems. i'm leaving it here for entertainment value. (see if you can find out what went wrong).
//Simpler versionRemainder = xCnum = ywhile(1) {if (cnum > remainder) {Break;)remainder = remainder - cnum;div++;}
That works, but is very slow.
//A slightly faster (but maybe buggier) one.while(1) {Cnum = Cnum + yif (cnum > remainder) { x--; cnum = cnum - y; break;}x++;}Div = x;Remainder = cnum - remainder;
I'm pretty sure theres a faster one...
Remainder = x;max = [Insert biggest 32 bit number here];min = 1;while(1) {if ((max - min) < 1) {break;}Cdiv = (max + min) >> 1;cnum = y * cdiv;if ((cnum == remainder) { Break;}if (Cnum > reminder) { Max = Cdiv;} Else {Min = Cdiv;}}Div = Cdiv;Remainder = Cnum - Remainder;
Binary search for division. (and modulus at the same time) Nifty?
You just need a fast Multiply routine....
Does anybody have a fast mult routine they want to share?
From,
Nice coder
[Edited by - Nice Coder on January 29, 2005 5:06:46 PM]