Author Topic: Division with magic multiplier  (Read 1677 times)

jj2007

  • Member
  • *****
  • Posts: 10557
  • Assembler is fun ;-)
    • MasmBasic
Division with magic multiplier
« on: August 27, 2018, 08:16:29 AM »
Using a magic multiplier used to be the trick to avoid slow division. It works fine, but my tests say that the advantage is small, especially if the numbers are small. DivBy10 is a macro that divides the argument passed by 10. The result is in edx.

Code: [Select]
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
450 ms for DivBy10, Rand(-1)
1108 ms for idiv

391 ms for DivBy10, Rand(2000000000)
553 ms for idiv

399 ms for DivBy10, Rand(20000)
469 ms for idiv

Siekmanski

  • Member
  • *****
  • Posts: 2331
Re: Division with magic multiplier
« Reply #1 on: August 27, 2018, 09:49:15 AM »
Code: [Select]
Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz
444 ms for DivBy10, Rand(-1)
1059 ms for idiv

350 ms for DivBy10, Rand(2000000000)
474 ms for idiv

390 ms for DivBy10, Rand(20000)
420 ms for idiv
[/code]
Creative coders use backward thinking techniques as a strategy.

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7553
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Division with magic multiplier
« Reply #2 on: August 27, 2018, 11:33:34 AM »
I don't know what is in the source as it is not MASM.

Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz
365 ms for DivBy10, Rand(-1)
1018 ms for idiv

295 ms for DivBy10, Rand(2000000000)
420 ms for idiv

300 ms for DivBy10, Rand(20000)
363 ms for idiv
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

LiaoMi

  • Member
  • ****
  • Posts: 698
Re: Division with magic multiplier
« Reply #3 on: August 27, 2018, 05:03:03 PM »
Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz
348 ms for DivBy10, Rand(-1)
986 ms for idiv

307 ms for DivBy10, Rand(2000000000)
427 ms for idiv

303 ms for DivBy10, Rand(20000)
388 ms for idiv

jj2007

  • Member
  • *****
  • Posts: 10557
  • Assembler is fun ;-)
    • MasmBasic
Re: Division with magic multiplier
« Reply #4 on: August 27, 2018, 05:43:30 PM »
I don't know what is in the source as it is not MASM.

Inter alia, there is a loop in the source (which opens fine in Wordpad btw):
Code: [Select]
  .Repeat
void Rand(randRange)
cdq
mov esi, 10
idiv esi
inc ecx
  .Until ecx>loops

Or did you mean "modern MASM" syntax, as in .Until ecx}loops?  ;)

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7553
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Division with magic multiplier
« Reply #5 on: August 27, 2018, 06:20:05 PM »
 :biggrin:

You have been flogging that one for a few years now. Now if you are so hostile to anything Microsoft, why are you using Windows and not Unix or Lunix variations ?
Quote
(which opens fine in Wordpad btw)
So now we have WordPad as the ultimate proogramming editor.  :P

Humerous how someone who hates Microsoft so desperately clings to a clone of the 1990 version of the Microsoft assembler. How would you handle FASM or GAS in a non Microsoft world, perhaps NASM if you wanted to go multi-port.

Just to make you laugh, I can open it in my RTF help file editor.

include \masm32\MasmBasic\MasmBasic.inc   ; download
DivBy10 MACRO arg
  ifdifi <arg>, <eax>
   mov eax, arg
  endif
  mov edx, 3435973837
  mul edx
  sar edx, 3
ENDM

  °B1Init
  PrintCpu 0
  xor ecx, ecx
  loops=100000000
  NanoTimer()
  .Repeat
   DivBy10 Rand(-1)
   inc ecx
  .Until ecx>loops
  PrintLine NanoTimer$(), " for DivBy10, Rand(-1)"
  xor ecx, ecx
  NanoTimer()
  .Repeat
   void Rand(-1)
   cdq
   mov esi, 10
   idiv esi
   inc ecx
  .Until ecx>loops
  PrintLine NanoTimer$(), " for idiv", CrLf$

  xor ecx, ecx
  NanoTimer()
  .Repeat
   DivBy10 Rand(2000000000)
   inc ecx
  .Until ecx>loops
  PrintLine NanoTimer$(), " for DivBy10, Rand(2000000000)"

  xor ecx, ecx
  NanoTimer()
  .Repeat
   void Rand(2000000000)
   cdq
   mov esi, 10
   idiv esi
   inc ecx
  .Until ecx>loops
  PrintLine NanoTimer$(), " for idiv", CrLf$

  xor ecx, ecx
  NanoTimer()
  .Repeat
   DivBy10 Rand(20000)
   inc ecx
  .Until ecx>loops
  PrintLine NanoTimer$(), " for DivBy10, Rand(20000)"

  xor ecx, ecx
  NanoTimer()
  .Repeat
   void Rand(20000)
   cdq
   mov esi, 10
   idiv esi
   inc ecx
  .Until ecx>loops
  Inkey NanoTimer$(), " for idiv", CrLf$
EndOfCode

°B5RichMasm: Press F6 to assemble & link


Bottom line is REAL MEN[tm] write their loop code in Intel mnemonics, not everyone wants a compiler writer to hold their hot little hand.  :biggrin:

Now the question is, where is your modern 64 bit /LARGEADDRESSAWARE code ?
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7553
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Division with magic multiplier
« Reply #6 on: August 28, 2018, 12:47:13 AM »
Psssssst, I should have mentioned, as the code you posted is 32 bit, have you confused 32 and 64 bit MASM ?

32 bit MASM (ML.EXE) runtime comparison operators.

Operator Meaning

== Equal
!= Not equal
>  Greater than
>= Greater than or equal to
<  Less than
<= Less than or equal to
&  Bit test (format: expression & bitnumber)
!  Logical NOT
&& Logical AND
|| Logical OR

CARRY? Carry bit set
OVERFLOW? Overflow bit set
PARITY? Parity bit set
SIGN? Sign bit set
ZERO? Zero bit set
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

AW

  • Member
  • *****
  • Posts: 2583
  • Let's Make ASM Great Again!
Re: Division with magic multiplier
« Reply #7 on: August 28, 2018, 01:03:12 AM »
Is this the daily portion of Spam Basic?

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7553
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Division with magic multiplier
« Reply #8 on: August 28, 2018, 02:20:34 AM »
I have a very pragmatic view about using Microsoft's tool set. Every time I buy a new retail OS version it costs me a small fortune and while most of their apps are crap, the tool set works OK and I have used versions of them since the DOS days so I make sure I get what I pay for by using their tool set on an OS that I have paid for.

Now while I have nothing against anyone using anything they like, OCR of granite inscriptions are OK by me, I don't intend to have anyone else's view imposed on me as I choose to use what I pay for. The "Open Sauce" guys are fine doing their own thing and while most of it ends up as a pile of sh*t dumped to die somewhere, they are all big kids now.

What I don't grasp is anyone who so desperately hates Microsoft buying Windows when they can get their own copy of an "Open Sauce" OS for free. GAS is a great assembler if you use the Intel rather than AT&T notation you could almost look like MASM.  :P
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy:

jj2007

  • Member
  • *****
  • Posts: 10557
  • Assembler is fun ;-)
    • MasmBasic
Re: Division with magic multiplier
« Reply #9 on: August 28, 2018, 02:25:53 AM »
Is this the daily portion of Spam Basic?

No, it's the daily portion of "nobody holds your hot little hand" 8)

What I don't grasp is anyone who so desperately hates Microsoft buying Windows

Linux is worse. Which doesn't stop me from solemnly declaring that .if eax}edx causes eye cancer :badgrin:

hutch--

  • Administrator
  • Member
  • ******
  • Posts: 7553
  • Mnemonic Driven API Grinder
    • The MASM32 SDK
Re: Division with magic multiplier
« Reply #10 on: August 28, 2018, 02:28:46 AM »
> Linux is worse. Which doesn't stop me from solemnly declaring that .if eax}edx causes eye cancer

If that is all that is stopping you from writing 64 bit, do it like REAL MEN[tm] with mnemonics.

    cmp rax, rdx
    je label
hutch at movsd dot com
http://www.masm32.com    :biggrin:  :skrewy: