flat assembler
Message board for the users of flat assembler.

 Index > Assembly > Division by multiplication - revisited Goto page Previous  1, 2
Author
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 7960
Location: Kraków, Poland
Tomasz Grysztar
Furs wrote:
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.

Furs wrote:
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.
28 Feb 2018, 23:56
Furs

Joined: 04 Mar 2016
Posts: 1657
Furs
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/is-there-a-fast-divisibility-check-for-a-fixed-divisor

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:
Code:
```test al, 1
jnz .no
imul eax, eax, 0xAAAAAAAB
cmp eax, 0x55555555
ja .no    ```
10 Mar 2018, 16:31
l4m2

Joined: 15 Jan 2015
Posts: 666
l4m2
Tomasz Grysztar wrote:
Code:
```        imul    edx,19h
mov     ecx,edx
mov     edx,09999999Ah    ```
Why give edx the value and move to ecx rather than
Code:
`imul ecx,edx,19h    `
?
24 Jan 2019, 02:24
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 7960
Location: Kraków, Poland
Tomasz Grysztar
l4m2 wrote:
Tomasz Grysztar wrote:
Code:
```        imul    edx,19h
mov     ecx,edx
mov     edx,09999999Ah    ```
Why give edx the value and move to ecx rather than
Code:
`imul ecx,edx,19h    `
?
I may have not optimized that routine perfectly, but I ended up using the next variant (the one with only three multiplications) anyway.
24 Jan 2019, 07:29
bitRAKE

Joined: 21 Jul 2003
Posts: 3307
Location: vpcmipstrm
bitRAKE
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/is-there-a-fast-divisibility-check-for-a-fixed-divisor
In fasmg syntax:
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 w-j
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    ```
And a topic related video...

_________________
25 Jan 2019, 05:03
Furs

Joined: 04 Mar 2016
Posts: 1657
Furs
bitRAKE thank you for that, really helpful.
29 Jan 2019, 12:46
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 7960
Location: Kraków, Poland
Tomasz Grysztar
07 Feb 2019, 09:27
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 7960
Location: Kraków, Poland
Tomasz Grysztar
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/is-there-a-fast-divisibility-check-for-a-fixed-divisor
In the aforementioned thread about 2-adic approach I showed a trick that uses just a single multiplication. It seems to be equivalent to the one you found, even though I derived it using a different method. While it only works so nicely for odd numbers, it has an additional perk that when the number is exactly divisible, you get the result of the division for free.

And today I found a publication about an even better method of divisibility checking:
https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/
The "lkk_divisible" method from the paper works for even divisors as well as for the odd ones.
04 Jun 2020, 16:34
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18266
revolution
Tomasz Grysztar wrote:
And today I found a publication about an even better method of divisibility checking:
https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/
The "lkk_divisible" method from the paper works for even divisors as well as for the odd ones.
That is good.

I don't understand why this:
Code:
`return n * c <= c - 1;    `
Isn't more simply this:
Code:
`return n * c < c;    `
05 Jun 2020, 00:05
tthsqe

Joined: 20 May 2009
Posts: 733
tthsqe
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18266
revolution
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
In seriousness, if c a compile time constant, compilers can figure out the validity of the transformation and apply it.
I still don't see it.

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

Joined: 20 May 2009
Posts: 733
tthsqe
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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum