flat assembler
Message board for the users of flat assembler.
Index
> Assembly > Division by multiplication  revisited Goto page Previous 1, 2 
Author 

Furs 10 Mar 2018, 16:31
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
A related question. What's the best (fastest, in general) way to check if a number is divisible by a constant? Sure, I can use the division here, and see if the result multiplied with the divisor is equal to the original value... but that's 2 muls. So I found this here: https://math.stackexchange.com/questions/1251327/isthereafastdivisibilitycheckforafixeddivisor 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 (compiletime) 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 34 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 compiletime, 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: Code: test al, 1 jnz .no imul eax, eax, 0xAAAAAAAB cmp eax, 0x55555555 ja .no 

10 Mar 2018, 16:31 

l4m2 24 Jan 2019, 02:24
Tomasz Grysztar wrote:
Code: imul ecx,edx,19h 

24 Jan 2019, 02:24 

Tomasz Grysztar 24 Jan 2019, 07:29
l4m2 wrote:


24 Jan 2019, 07:29 

bitRAKE 25 Jan 2019, 05:03
Furs wrote: A related question. What's the best (fastest, in general) way to check if a number is divisible by a constant? Sure, I can use the division here, and see if the result multiplied with the divisor is equal to the original value... but that's 2 muls. So I found this here: https://math.stackexchange.com/questions/1251327/isthereafastdivisibilitycheckforafixeddivisor Code: MACRO DisplayNumber in LOCAL number number = in scale 0 IF number < 0 DISPLAY '' number = number END IF REPEAT 1, n:number DISPLAY `n END REPEAT END MACRO virtual at 0 HexDigits:: db '0123456789ABCDEF' end virtual macro DisplayHex val*,bytes:0 local chars if bytes chars = 2*bytes else chars = 2 + 2*((bsr (val))/8) end if repeat chars load digit:byte from HexDigits: ((val) shr ((%%%) shl 2)) and 0Fh display digit end repeat end macro struc egcd: a,b local t if a = 0 .gcd = b .x = 0 .y = 1 else . egcd (b mod a),a t := .x .x = (.y  (b / a) * .x) .y = t end if end struc macro fast_div d*,w* local m,j, _d,t m = 1 shl w j = bsf d _d = d shr j if j > 0 display 'n << ' DisplayNumber wj display ' == 0',13,10 end if if _d > 1 t egcd _d,m display 'n * ' DisplayHex t.x mod m, w shr 3 display ' <= ' DisplayHex m / _d, w shr 3 display 13,10 end if end macro fast_div 76,64 https://www.youtube.com/watch?v=yisTTpLxY _________________ ¯\(°_o)/¯ “languages are not safe  uses can be” Bjarne Stroustrup 

25 Jan 2019, 05:03 

Furs 29 Jan 2019, 12:46
bitRAKE thank you for that, really helpful.


29 Jan 2019, 12:46 

Tomasz Grysztar 07 Feb 2019, 09:27
I'm adding a link to the other thread, where I discuss 2adic approach in detail. It nicely complements this one.


07 Feb 2019, 09:27 

Tomasz Grysztar 04 Jun 2020, 16:34
Furs wrote: A related question. What's the best (fastest, in general) way to check if a number is divisible by a constant? Sure, I can use the division here, and see if the result multiplied with the divisor is equal to the original value... but that's 2 muls. So I found this here: https://math.stackexchange.com/questions/1251327/isthereafastdivisibilitycheckforafixeddivisor And today I found a publication about an even better method of divisibility checking: https://lemire.me/blog/2019/02/08/fasterremainderswhenthedivisorisaconstantbeatingcompilersandlibdivide/ The "lkk_divisible" method from the paper works for even divisors as well as for the odd ones. 

04 Jun 2020, 16:34 

revolution 05 Jun 2020, 00:05
Tomasz Grysztar wrote: And today I found a publication about an even better method of divisibility checking: I don't understand why this: Code: return n * c <= c  1; Code: return n * c < c; 

05 Jun 2020, 00:05 

tthsqe 05 Jun 2020, 13:39
revolution, transforming n * c <= c  1 to n*c < c has problems when c = 0. Apparently the code is supposed to work in the very important case of testing divisibility by 1
In seriousness, if c a compile time constant, compilers can figure out the validity of the transformation and apply it. 

05 Jun 2020, 13:39 

revolution 05 Jun 2020, 13:49
tthsqe wrote: revolution, transforming n * c <= c  1 to n*c < c has problems when c = 0. Apparently the code is supposed to work in the very important case of testing divisibility by 1 let c = 0 then n * 0 <= 0  1 > false and n * 0 < 0 > false And the only way c = 0 is if 0xFFF...FFF/d = 0. So d is larger than the maximum integer. If d = 1 then c = 0xFFF....FFF 

05 Jun 2020, 13:49 

tthsqe 05 Jun 2020, 13:53
Keep in mind that the types are unsigned. Everything is mod 2^64 or 2^32. When d = 1, the addition wraps around to give c = 0, and now everything is <= c  1 because this is the max uint.


05 Jun 2020, 13:53 

Goto page Previous 1, 2 < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.