Author Topic: idiv algorithm  (Read 226 times)

Mikl__

  • Member
  • *****
  • Posts: 1136
idiv algorithm
« on: November 24, 2021, 04:16:02 AM »
Hi, All!
It required to binary divide +117 by -13. If I divide +117 by +13, it is simple, I will used subtractions and shifts,

but how to binary divide 01110101b by 11110011b so that the result is 11110111 using elementary operations (shifts, addition, subtraction, logic AND, OR, XOR)?
I understand that you need to look for literature on intel8080 or microcontrollers and look there, but so far nothing is at hand...

nidud

  • Member
  • *****
  • Posts: 2311
    • https://github.com/nidud/asmc
Re: idiv algorithm
« Reply #1 on: November 24, 2021, 05:01:27 AM »
Well, you cant, so you divide 117 by 13 and use NEG.

mineiro

  • Member
  • ****
  • Posts: 810
Re: idiv algorithm
« Reply #2 on: November 24, 2021, 07:00:32 AM »
Two's complement (not + 1) (neg).
A computer never subtracts, only do additions. So, how to perform subtraction by doing addition?
The two-complement idea was in limbo for a long time until they found a use for it. (from eletronics point of view).

There is a one-complement as well, which uses only "not".
In both cases, exceptions should be handled.

In electronics they teach us "half adder" and "full adder". They don't teach us "subtraction".
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 8741
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: idiv algorithm
« Reply #3 on: November 24, 2021, 08:42:13 AM »
 I am driven by sheer laziness when I use SSE2 32 and 64 bit arithmetic, its easy, fast and reliable.  :biggrin:
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

mineiro

  • Member
  • ****
  • Posts: 810
Re: idiv algorithm
« Reply #4 on: November 24, 2021, 09:22:09 AM »
This code need a bit more refinement, with a bit more work can deal with big numbers.
Code: [Select]
;253/7, 253/-7        ;prime numbers
mov rdi,8000000000000000h       ;sign mask
mov rax,117 ;0      ;dividend
mov rbx,-13 ;0      ;divisor
xor rsi,rsi         ;quotient
                    ;remainder will be rax
test rbx,rdi        ;sign mask, if left most digit is 1 means negative number, if 0 means positive number
jz @F
neg rbx             ;two complement
@@:
.if rax < rbx       ;2/5, 0/1    ;quotient = 0, remainder = dividend
    jmp @F
.endif
.if rbx == 0        ;N/0        ;handle exception
    xor eax,eax
    div rsi         ;forced exception, division by 0
.endif
;--------------------
bsr rcx,rax         ;counting rotations
inc rcx
bsr rdx,rbx
inc rdx
sub rcx,rdx         ;rcx= final shift, magnitude        2/2 = 0, 3/2 = 0
shl rbx,cl          ;align numbers

.repeat
    shl rsi,1
    .if rax >= rbx
        sub rax,rbx         ;rax turns into remainder
        or rsi,1
    .endif
    shr rbx,1
    dec rcx
.until rcx == -1

@@:
;RESULT
;quotient = 36         ;rsi
;remainder = 1         ;rax
;36*7+1=253
I'd rather be this ambulant metamorphosis than to have that old opinion about everything

daydreamer

  • Member
  • *****
  • Posts: 1810
  • green elevator
Re: idiv algorithm
« Reply #5 on: November 24, 2021, 11:42:37 PM »
Look at old free computer magazines,there was multiply article, on 6502 but it's just shifts and adds?
Maybe search for 8bit embedded code?
@miniero
Maybe possible make subtract circuit thinking out of the box,like rcpss instruction uses 1024 LUT and gfx card pixel shader has 1cycle cosine and sine,probably builtin LUT
Neg xdelta and neg ydelta perfect for breakout game,just bounce ball inside square

SIMD fan and macro fan
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."

mineiro

  • Member
  • ****
  • Posts: 810
Re: idiv algorithm
« Reply #6 on: November 25, 2021, 04:29:05 AM »
... just shifts and adds?
@miniero
... probably builtin LUT

shifts are arithmetical adds or can be multiplications.
1+1=10 or (1b shl 1)
10+10=100 or (10b shl 1)
101+101=1010 or (101b shl 1) or (101*2)
...
Yes, a transform precalculated table (LUT) is an option, but will be more harder to be expanded (big data) because need more memory to hold results. Like perform a number factorial!.

I'd rather be this ambulant metamorphosis than to have that old opinion about everything

daydreamer

  • Member
  • *****
  • Posts: 1810
  • green elevator
Re: idiv algorithm
« Reply #7 on: November 25, 2021, 02:42:32 PM »
... just shifts and adds?
@miniero
... probably builtin LUT

shifts are arithmetical adds or can be multiplications.
1+1=10 or (1b shl 1)
10+10=100 or (10b shl 1)
101+101=1010 or (101b shl 1) or (101*2)
...
Yes, a transform precalculated table (LUT) is an option, but will be more harder to be expanded (big data) because need more memory to hold results. Like perform a number factorial!.
something like this
Code: [Select]
mov ecx,numberofbits
xor edx,edx ;zero result,ebx*eax
@@L1:sar ebx,1 ; check bits 0,1,2,3,4,5,6,7,8...in loop
jcc @@L2 ;if mul by zero jump over,else mul by 1
add edx,eax
@@L2:sal eax,1 ;now * 10,100,1000,10000,10000...
dec ecx
jne @@L1
with the clock cycles on modern cpus,probably circuits that tests many bits in parallel to achive so low number of cycles,probably
actually I have factorial LUTs for my trigo taylor series,for 3!,5!,7!,9! for sine,2!,4!,6!,8! for cosine,storing 99! in LUT is big gain vs doing lots of muls to calculate it
divide is more complex testing equal or less:subtract,last time I did it I ended up in some endless loop
still schools multiply table 0-100 easily fit into memory
SIMD fan and macro fan
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."

mikeburr

  • Member
  • **
  • Posts: 142
Re: idiv algorithm
« Reply #8 on: Today at 04:12:31 AM »
in 64 bit .. multiply by 4EC4EC4EC4EC4EC5 == divide by 13 ... but what are you going to do with the remainder ???
regards mike b