Re: Skybuck presents alternative division method, to be benchmarked ;)

The search is easily optimized if leading zero count instruction is 
available:

vBiggerDivisor := 1 shl 32-LeadingZeroCount;
v****fter := 1 shl 32-LeadingZeroCount;
vAnder := $FFFFFFFF shr LeadingZeroCount;

No more while vTemp > 0 loop necessary.

Interesting.

Now I go look for a leading zero count replacement for my AMD X2 3800+ 
(it 
doesn't have the instruction :))

Then I am gonna give it another benchmark try ;) :)

Bye,
  Skybuck.


"Skybuck Flying" <BloodyShame@[EMAIL PROTECTED]
> wrote in message 
news:230c6$480f33a2$541983fa$18551@[EMAIL PROTECTED]
>I suspected the algorithm was general.
>
> To prove it's general, here is a general version which works with any 
> divisor.
>
> I didn't bother optimizing it though.
>
> Just a proof of concept ;)
>
> No do***entation is provided for the algorithm by me... that's the fun 
> part for you... try to figure out how it works :) LOL.
>
> If you really interested in it, and can't figure it out... let me know I

> might tell you LOL.
>
> // Quickly written and quickly tested, not thoroughly tested.
>
> // general version just out of curiosity...
> function SimulatedDivGeneral( Content : longword; Divisor : longword ) :

> longword;
> var
> vTemp : longword;
> vDivisions : longword;
> vBiggerDivisor : longword;
> v****fter : byte;
> vAnder : longword;
> vDivisorDifference : longword;
> begin
> result := 0;  // latency 1

this piece not necessary anymore and can be replaced by the 4 (?) 
instructions above. Very nice.

> // search for bigger binary/****ft divisor the the current divisor
> vBiggerDivisor := 1;
> v****fter := 0;
> vAnder := 0;
>
> vTemp := Divisor;
>
> while vTemp > 0 do
> begin
>  vBiggerDivisor := vBiggerDivisor shl 1;
>  v****fter := v****fter + 1;
>  vAnder := vAnder shl 1 + 1;
>  vTemp := vTemp shr 1;
> end;



>
> vDivisorDifference := vBiggerDivisor - Divisor;
>
> // main algorithm
> while Content > vBiggerDivisor do // latency 1 + latency 1 = latency 2
> begin
>  vDivisions := (Content shr v****fter); // latency 1 + latency 1 =
latency 
> 2
>  Content := (Content and vAnder) + vDivisions * vDivisorDifference; // 
> latency 1 + latency 1 = latency 2
>  result := result + vDivisions; // latency 1
> end;
>
> // single loop latency: 2 + 2 + 2 + 1 = 7
> if Content >= Divisor then // latency 1 + latency 1 = latency 2
> begin
>  result := result + 1; // latency 1
> end;
>
> // best case latency: 1 + 7 + 3 = 11
> // worst case latency (max loops 11 for 32 bit longwords): 1 + 7 * 11 +
3 
> = 81
>
> // very close to div 7, though this routine is probably directpath
mostly 
> and not vector path
> // so maybe it's faster... but then again still some calling overhead.. 
> let's see what happens
> // when it's inlined ;)
> // yup inlining works real nice.
>
> // time for a benchmark :)
>
> // tested on amd x2 3800+
> // for content values ranging from say 1000 to even a million this
routine 
> appears
> // to be faster than the div... kinda nice.
>
> // general routine is slower... didn't bother to optimize it or so ;)
> end;

Bye,
  Skybuck.