flat assembler
Message board for the users of flat assembler.
Index
> Main > Compute 10^n/10 using only 1 register with 2 instructions Goto page Previous 1, 2, 3 
Author 

Furs
Amazing thread, should be made a sticky, I don't want it lost. Maybe in some useful tricks section or so
Maybe we should have a thread with such code tricks, possibly in more languages (I have in constexpr C++ also, computing the constant itself fully at compiletime, zero overhead there). Then we can link this thread and others from there so it's not lost, and only that thread be made sticky. Tomasz Grysztar wrote: Well, except that B needs to be odd, but if it's even you can start with shifting both A and B right in parallel until B becomes odd 

29 Jan 2019, 12:40 

Tomasz Grysztar
Furs wrote: What if A is 1? Shifting it right would make it zero, so it's clearly wrong. 

29 Jan 2019, 13:06 

Tomasz Grysztar
For the purpose of playing with 2adic numbers using fasmg I made this macro that implements the same algorithm for division:
Code: struc div2adic? A, B, BITS:64 .a = A .b = B while .b and 1 = 0 assert .a and 1 = 0 .b = .b shr 1 .a = .a shr 1 end while . = 0 .product = 0 while .product xor .a .index = bsf (.product xor .a) if .index >= BITS break end if . = . or 1 shl .index .product = .product + .b shl .index end while end struc Code: i3 div2adic 1,3 dq i3 ; 0AAAAAAAAAAAAAAABh Code: i7 div2adic 1,7, 512 ddqq i7 ; 0B6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB6DB7h 

15 Oct 2019, 11:10 

Tomasz Grysztar
There is one more thing worth mentioning: even though 2adic reciprocals are only useful for division when you know that the number is divisible exactly, it is also quite easy to verify that it was the case (so you can have error handling).
For example, if we compute 32 lowest digits of A/B (let's call that 32bit value Q), then if we multiply it by B, we get 32 lowest digits of (A/B)*B = A. The only problem is that when A was not exactly divisible by B, then Q*B has some additional digits (above the 32) and it just happens to have the same low 32 digits as A. Therefore to test whether the number was exactly divisible, it is enough to check whether Q*B overflows out of 32 bits. For unsigned case this can be tested by comparing Q with (1 shl 32)/B. For example, to divide an unsigned number by 7 and signal an error when the number was not exactly divisible: Code: imul eax,0B6DB6DB7h cmp eax,(1 shl 32)/7 ja not_divisible Last edited by Tomasz Grysztar on 08 Nov 2019, 06:34; edited 1 time in total 

07 Nov 2019, 19:39 

revolution
Yes, makes sense.
But it fails for 0xfffffffc (0x24924924 * 7) 0xB6DB6DB7 * 0xfffffffc = 0x(...B6DB6DB4)24924924 (1 shl 32) / 7 = 0x24924924(.6DB6DB6DB...) So the JAE test is taken. 

08 Nov 2019, 05:49 

Tomasz Grysztar
Oh, right, this should be JA there. The divisor must be odd, so (1 shl 32)/B is never going to be exact (and it is rounded down). So when the numbers are equal, there is still no overflow.
In other words the condition for no overflow is Q <= (1 shl 32)/B < . 

08 Nov 2019, 06:21 

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

Copyright © 19992019, Tomasz Grysztar.
Powered by rwasa.