Groups | Search | Server Info | Login | Register

Groups > comp.arch.arithmetic > #78

Re: New appromixation for integer division by 63 or 127

Show all headers | View raw

nikolaos.kavvadias@gmail.com wrote:
> Dear all,
>
> I believe I have invented a new approximation for quotient
> calculation that works for x/63 and x/127.
>
> The formula is as follows and it is divisionless and multiplierless:
>
> y = (((x>>n)+x+((1<<n)+1))>>n)-1;
>
> Use n=6 for 63, and n=7 for 127. 1<<n is the strength-reduced form
> for calculating 2^n.

Nothing new here.:-)

Instead of dividing by 63 you are multiplying by 65, and since 
(x+1)(x-1) = x^2 - 1, the error is manageable.

Effectively you are doing reciprocal mul with a multiplier with very few 
significant bits.

This also means that your formula only works for a limited range of 
inputs (i.e. number of bits in x), and it fails badly when (for a 32-bit 
number) x is so close to 2^32 that adding x/64 to it causes a carry.

BTW, I use a similar trick in my data calculations, when I need to 
divide a small range of inputs by 100 in order to convert a year number 
to century:

   //  y100 = y / 100;  // Reciprocal mul
   y100 = y * 41 >> 12;  // Faster version with very short reciprocal

The multiplier has just three bits set (101001) so it can be calculated 
with a pair of LEAs:

   lea ebx, [eax+eax*4]     ;; y*5
   lea ebx, [eax+ebx*8]	;; y*41
   shr ebx,12

The result is exact for all possible inputs in the 0..400 range which is 
what I need at this point.

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Back to comp.arch.arithmetic | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

New appromixation for integer division by 63 or 127 nikolaos.kavvadias@gmail.com - 2014-10-11 00:19 -0700
  Re: New appromixation for integer division by 63 or 127 nikolaos.kavvadias@gmail.com - 2014-10-11 06:05 -0700
  Re: New appromixation for integer division by 63 or 127 Terje Mathisen <terje.mathisen@tmsw.no> - 2014-10-13 10:20 +0200
    Re: New appromixation for integer division by 63 or 127 nikolaos.kavvadias@gmail.com - 2014-10-15 01:09 -0700

csiph-web