Dear all, I believe I have invented a formula 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. It does not require any double-word arithmetic (like with multiplying by the 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 to this? Best regards Nikolaos Kavvadias http://www.nkavvadias.com http://github.com/nkkav/
Nikolaos Kavvadias wrote: > Use n=6 for 63, and n=7 for 127. > It does not seem to work for other dividers Have you tried n=5 for 31, n=4 for 15 and so on? I try to figure out if your formula works. (For native speakers: Is it 'Have you tried…' or 'Did you try…' in this case?)
Hi, >> It does not seem to work for other dividers > > Have you tried n=5 for 31, n=4 for 15 and so on? > I try to figure out if your formula works. Yes, it seems that it does not work with other dividers. There exist "one-off" errors. I might give it a shot for (hopefully branchless) fix/correction for all dividers of the 2^n-1 form. Not sure if this is possible. Best regards Nikolaos Kavvadias http://www.nkavvadias.com > (For native speakers: Is it 'Have you tried…' or 'Did you try…' in this > case?)
:
Edited by User
I just tried it, but I think I have to disappoint you. For example just try to divide 126 by 63 which is exactly 2. Your formula gives 2.01514 as result, which is 0.76% error. Dividing 126 by 64, which is much faster than the calculation of your formula, gives 1.96875 which is 1.56% error. I think either one needs a fast calculation, then he can divide by 64 and accept the error or he needs a exact calculation, then your formula is not accurate enough. For higher x-values, the error of dividing by 64 instead of 63 stays constant, but the error of your formula grows. Dividing 504(=8*63) gives an error of 1.79%. So one can say, your formula has better accuracy for smaller numbers, but since it only works for integers or fixed point arithmetics, the rounding-erros are much higher.
Hi > I just tried it, but I think I have to disappoint you. For example just > try to divide 126 by 63 which is exactly 2. Your formula gives 2.01514 > as result, which is 0.76% error. Dividing 126 by 64, which is much > faster than the calculation of your formula, gives 1.96875 which is > 1.56% error. there is nothing to be disappointed about. This is an intentional formula for software integer division, i.e. truncating division. So it does int->int mappings for the quotient. I am not targeting calculations where the fractional part plays a significant part. Best regards Nikolaos Kavvadias http://www.nkavvadias.com
I know, but dividing by 64 (and adding 1 for correct rounding) is still much faster and not less accurate.
>> I just tried it, but I think I have to disappoint you. For example just >> try to divide 126 by 63 which is exactly 2. Your formula gives 2.01514 >> as result, which is 0.76% error. I agree that there are unoptimized calculations such as this one but for truncated division, any calculation is correct for the 63 and 127 divisors. x=126 happens to be n<<1 for n=6=>k=2^n-1=63. x is anyway treated as the variable/unknown: only n is known and I what I want to do is calculate in a divisionless and multiplierless way. Was scavenging some old notes of mine and recovered this algo. Seems I can claim it as back as May 16, 2011.
Dussel wrote: > I know, but dividing by 64 (and adding 1 for correct rounding) is still > much faster and not less accurate. But only for x in the range from 63 to 8000. Without formal proof im am also skeptical about Nikolaos formala. At least he should provide a range for x values it has been testet.
Dear Lattice User wrote: > Without formal proof im am also skeptical about Nikolaos formala. At > least he should provide a range for x values it has been testet. Thank you for your skeptical view. Indeed my formula works only for dividends x that are: x <= (2^(2*n)) - 1. However, it seems to work for any divisor!!! I've tested all divisors from 2 to 8. E.g. for n = 6, the divisor is 2^n - 1 = 63. The formula will work for x <= 4095 = (2^(2*n)) - 1. It will produce one-off errors for certain x >= 4096. But it will be correct for the "small" x values. I had devised the hack via "algorithmic sketching". I mean that I had started from a basic formula with some "holes" in it. The holes where small constants or operators. There exist such techniques in academia, put more nicely; sometimes called algorithmic sketching, combinatorial sketching, etc. Essentially is about devising algorithmic sketches (incomplete algorithms with wildcards) and then use a mechanism to fill the gaps. I don't seem to find my step-by-step notes. My test program is here:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #include <math.h> |
4 | |
5 | /* main: |
6 | */ |
7 | int main(void) |
8 | {
|
9 | int qapprox, qexact; |
10 | int i, j, k; |
11 | |
12 | for (i = 2; i < 8; i++) {
|
13 | // for (j = 1; j < 4096; j++) {
|
14 | for (j = 1; j < ((1<<i)-1)*((1<<i)-1); j++) {
|
15 | k = (1<<i) - 1; |
16 | qapprox = (((j>>i)+j+((1<<i)+1))>>i)-1; |
17 | qexact = j / k; |
18 | if (qapprox != qexact) {
|
19 | fprintf(stderr, "qapprox = (%d/%d) = %d\tqexact = (%d/%d) = %d\n", |
20 | j, k, qapprox, j, k, qexact); |
21 | } |
22 | } |
23 | } |
24 | return 0; |
25 | } |
Best regards Nikolaos Kavvadias http://www.nkavvadias.com
I am sorry, please find attached correct version of the test program and correct range for x. Also, the range for x is [0,2^(2*n)-2], i.e. for n = 6, the range is 0:4094.
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #include <math.h> |
4 | |
5 | /* main: |
6 | */ |
7 | int main(void) |
8 | {
|
9 | int qapprox, qexact; |
10 | int i, j, k; |
11 | |
12 | for (i = 2; i < 8; i++) {
|
13 | for (j = 1; j < (1<<i)*(1<<i)-1; j++) {
|
14 | k = (1<<i) - 1; |
15 | qapprox = (((j>>i)+j+((1<<i)+1))>>i)-1; |
16 | qexact = j / k; |
17 | if (qapprox != qexact) {
|
18 | fprintf(stderr, "qapprox = (%d/%d) = %d\tqexact = (%d/%d) = %d\n", |
19 | j, k, qapprox, j, k, qexact); |
20 | } |
21 | } |
22 | } |
23 | return 0; |
24 | } |
Lattice User wrote: > Dussel wrote: >> I know, but dividing by 64 (and adding 1 for correct rounding) is still >> much faster and not less accurate. > > But only for x in the range from 63 to 8000. > BTW This is wrong, Dussels formula gives 2015 wrong results in the range 0 .. 4095
Lattice User wrote: > Dussels formula gives 2015 wrong results in the range > 0 .. 4095 You are right. I tested it. But I'll try to find a better solution ;-)
Did anybody notice that this is in C-language and has been posted in the
VHDL area?
Anyway I do not see any advantage in this equations especially not since
both dividers are close to a binary number and the given transformation
of a binary division is simple, like e.g.
x/127 = x/128 * 128/127 = x/128 + x/128/127 ....
= x/128 + x/16256 ....
= x/128 + x/128/128 + x/128/128/128
and so on, and so on
> I believe I have invented a formula for quotient calculation that works
Me too :-)
When I started computer game programming in 1980, I realized I did not
have any divider at all in my poor 6502 and also no time with the only
2MHz to perform divisions. Therefore I sat down and wrote a document
covering most of the required divisions for gaming (like 10,60,3600 for
times and 100,1000, for lengths and also some values for conversion of
american fahrenheit temperatures to german degrees. I even found a
simple definition for PI and the irrational relation of music note
distances of 185/196.
All worked with such sequences of adders and shift divisions.
They where found intuitively by try and error method, because I was 12
years of age and did not have enough maths in school so far. Later they
told me about Restklassen (modulo), Taylor Sequences and similar things.
Once you understood the story behind this, it is easy to find tons of
abstractions of division and indirect division, and with vhdl they are
sometimes incredibly fast.
:
Edited by User
Jürgen Schuhmacher wrote: > I even found a simple definition for PI and the irrational > relation of music note distances of 185/196. Can you tell more about this, please? Me I am searching for a simple way to create sine waves from y = (pi * 2 * w) with variable w ("omega").
Watch this topic
Disable multi-page viewPlease log in before posting. Registration is free and takes only a minute.
Existing account
Do you have a Google/GoogleMail account? No registration required!
Log in with Google account
Log in with Google account
No account? Register here.