Joined: 16 Jun 2003
Location: Kraków, Poland
I'm a bit confused. So I need to iterate all shift values, but how can I check if the condition holds if I don't know the value of N? Should I assume the highest value possible for it that it can have? I mean, N is a runtime value, only the divisor is at compile time.
Yes, you can consider just the highest possible value of N, if inequality holds for it, then it holds for all the smaller values too.
For example if P = 1 then is true as long as . If P = 2 then to have we need , the allowed range of input becomes smaller.
And also if I divide 2^32 by 641, the remainder is 640, not 1, so how come it works?
EDIT: I'm guessing P is not the remainder, but rather D-remainder, am I right? I looked before at your example with 10, and you said P = 4, which fits just as well as on 641. (i.e. 10-6 = 4, and 641-640 = 1)
Oh, you're right, I confused the terminology, P is the complement of the remainder, P = D - R. In that post above where I gave all the formulas it is explained correctly.
Ok, the thing I gathered together works great (with all that I got from here, including your first method if the 0xFFFF...FF value is possible, I bet nobody else uses it ). Now I can feel at peace knowing the stupid thing can spit out the most optimal constants/method. Thanks
For odd divisors it's fantastic, one mul and one cmp, literally. But it needs two branches if the divisor is even, which sucks (or a lot of extra overhead code/registers usage, unless you can find a better way, problem is the ZF can't be used except with cmov, no adc/sbb tricks). Any better way for even divisors? (I'm not a math guru so I don't really understand how it works, lol)
I did implement them both in C++ with constexpr (compile-time) forcing, and it works fine, but it'd be nice to have a better way for even divisors. (by "better way" I mean in the resulting asm of course, not having two branches is a good win unless I need 3-4 extra instructions, then it's not so good)
(well I have them in C++ so far for HLL usage, which I just use it to compile a simple function if I want the constants for asm usage by looking at the output... like what I was originally doing, except GCC's optimizer sucks, though it's a bit ugly since I had to use internal constexpr functions to force it at compile-time, GCC is too dumb with loops otherwise; I don't know if anyone is interested in my C++ code with them)
For example, let's say checking if number is divisible by 6. So far my code spits this out:
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You can download files in this forum