X-Received: by 10.236.119.67 with SMTP id m43mr1987758yhh.31.1413011944555; Sat, 11 Oct 2014 00:19:04 -0700 (PDT)
X-Received: by 10.140.38.177 with SMTP id t46mr2211qgt.21.1413011944475; Sat, 11 Oct 2014 00:19:04 -0700 (PDT)
Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!dc16no2005005qab.1!news-out.google.com!i10ni82qaf.0!nntp.google.com!dc16no2005004qab.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.arch.arithmetic
Date: Sat, 11 Oct 2014 00:19:04 -0700 (PDT)
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=5.55.57.237; posting-account=lD5X3AoAAAB2_KDReA0WuoP_A_fBgycC
NNTP-Posting-Host: 5.55.57.237
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <74d951ee-6fd2-43ad-8f0a-2852a031bd2c@googlegroups.com>
Subject: New appromixation for integer division by 63 or 127
From: nikolaos.kavvadias@gmail.com
Injection-Date: Sat, 11 Oct 2014 07:19:04 +0000
Content-Type: text/plain; charset=ISO-8859-1
Lines: 17
Xref: csiph.com comp.arch.arithmetic:76

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.

My formula does not require any double-word arithmetic (like with multiplying by multiplicative inverse and then performing adjustment steps). It does not seem to work for other dividers, but a systematic fix may be possible.

Are there any known references on this?

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