Groups | Search | Server Info | Login | Register

Groups > comp.arch.arithmetic > #79

Re: New appromixation for integer division by 63 or 127

Show all headers | View raw

Hi Terje,

indeed, my formula:

- will actually work for any divisor of the form 2^n-1
- can be simplified to (x + (x>>n) + 1)>>n
- works for a limited range: x should be in the closed interval: [0, 2^(2n)-2] 

I understand this is not new, but it has never been properly documented.
I have spent quite some time tracking a textbook (or paper) on this. Implicitly, yes, it's there, it can be inferred; but no direct reference to it.

BTW pkhuong contributed a nice number-theoretical proof for the formula regarding a somewhat larger range here: 
http://www.reddit.com/r/programming/comments/2j18nt/multiplierless_hack_for_constant_division_by_2n1/

I also have a blog article on the topic:
- http://nkavvadias.com/blog/2014/10/11/multless-kdiv/

Further, it is useful and even more portable to have the formula working in any high-level language, I prefer it compared to x86 or ARM assembly trickery :). Your div-by-100 using leas for scaled multiplication is nice and you can do a similar thing with ARM's addressing modes.

I have written a tool for generating optimum code for ANSI C and "generic assembly". It is named kdiv and you can find it here: http://github.com/nkkav/kdiv 
It is based on Hacker's Delight' ideas and code for calculating the magic number (multiplicative inverse)

There is also kmul, its sister (or brother?) project here: http://github.com/nkkav/kmul . This is based on Preston Briggs' code for Bernstein's algorithm on multiplication by integer constants. 


Best regards
Nikolaos Kavvadias
http://www.nkavvadias.com





Τη Δευτέρα, 13 Οκτωβρίου 2014 11:20:38 π.μ. UTC+3, ο χρήστης Terje Mathisen έγραψε:
> 
> > 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 | 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