Fast MOD

Category: Math

Date: 03-28-2012

Return to Index


 
'Compilable Example:
#Compiler PBWin 9, PBWin 10
#Compile EXE
#Dim All
 
#Include "Win32API.inc"
%iLoopMax = 100000000
%Numerator = 80000
%Denominator = 200
Global hDlg As Dword
Global qFreq, qStart, qStop As QUAD, DeltaTime As Single
 
Function PBMain() As Long
   Dialog New Pixels, 0, "Test Code",300,300,200,300, %WS_OverlappedWindow To hDlg
   Control Add Button, hDlg, 100,"MOD", 50,10,100,20
   Control Add Button, hDlg, 200,"Equation", 50,40,100,20
   Control Add Button, hDlg, 300,"SubtractMany", 50,70,100,20
   Control Add Button, hDlg, 400,"ASM", 50,100,100,20
   Control Add Button, hDlg, 500,"Lookup", 50,130,100,20
   Control Add Button, hDlg, 600,"FPU", 50,160,100,20
   Control Add Button, hDlg, 700,"Multiply", 50,190,100,20
   Control Add Button, hDlg, 800,"Power of 2", 50,220,100,20
   QueryPerformanceFrequency qFreq
   Dialog Show Modal hDlg Call DlgProc
End Function
 
CallBack Function DlgProc() As Long
   If Cb.Msg = %WM_Command And Cb.Ctl = 100 Then MODNormal
   If Cb.Msg = %WM_Command And Cb.Ctl = 200 Then Equation
   If Cb.Msg = %WM_Command And Cb.Ctl = 300 Then SubtractMany
   If Cb.Msg = %WM_Command And Cb.Ctl = 400 Then ASM_Hutch
   If Cb.Msg = %WM_Command And Cb.Ctl = 500 Then Lookup_Boyd_Kurt
   If Cb.Msg = %WM_Command And Cb.Ctl = 600 Then FPU_Hutch
   If Cb.Msg = %WM_Command And Cb.Ctl = 700 Then Multiply_Paul
   If Cb.Msg = %WM_Command And Cb.Ctl = 800 Then PowerOf2
End Function
 
Sub MODNormal
   'GetTickCount - milliseconds since Windows started. accurate to about 15ms
   Local iLoop,i,j,n As Long
   QueryPerformanceCounter qStart
   For iLoop = 1 To %iLoopMax
      '------------------------------------
      i = %Numerator : n = %Denominator
      j = i Mod n
      '------------------------------------
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "MOD Normal  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(j)
End Sub
 
Sub Equation
   'GetTickCount - milliseconds since Windows started. accurate to about 15ms
   Local iLoop,n,i,j As Long
   QueryPerformanceCounter qStart
   For iLoop = 1 To %iLoopMax
      '------------------------------------
      i = %Numerator : n = %Denominator
      j = i - n * i\n
      '------------------------------------
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "Equivalent  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(j)
End Sub
 
Sub SubtractMany
   'GetTickCount - milliseconds since Windows started. accurate to about 15ms
   Register i As Long, n As Long
   Local iLoop As Long
   QueryPerformanceCounter qStart
   For iLoop = 1 To %iLoopMax
      '------------------------------------
      i = %Numerator : n = %Denominator
      While i >= n
         i = i - n
      Wend
      '------------------------------------
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "Subtract Many  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(i)
End Sub
 
Sub ASM_Hutch
   Register i As Long, n As Long
   Local iLoop As Long
   QueryPerformanceCounter qStart
   For iLoop = 0 To %iLoopMax
      '============================================================
      i = %Numerator : n = %Denominator
      ! mov eax, i
      ! xor edx, edx
      ! mov ecx, n
      ! div ecx
      ! mov i, edx             'i contains result
      '============================================================
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "ASM_Hutch  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(i)
End Sub
 
Sub Lookup_Boyd_Kurt
   Local i,n,j,iLoop As Long
   ReDim LookupTable200(80000) As Long
   QueryPerformanceCounter qStart
   For iLoop = 0 To %iLoopMax
      '============================================================
      i = %Numerator : n = %Denominator
      j = LookupTable200(i)
      '============================================================
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "Lookup_Boyd  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(j)
End Sub
 
Sub FPU_Hutch
   Local iLoop,x,j,i,n As Long    'x just is like poor-man Register None
   n = %Denominator
   QueryPerformanceCounter qStart
   For iLoop = 1 To %iLoopMax
      '------------------------------------
      i = %Numerator
      !fild n   'load n into the FPU
      !fild i   'load i into the FPU
      !fprem    'calculate the remainder of i/n
      !fistp j  'store result in j
      !fcomp    'pop FPU stack to clean it up
      '------------------------------------
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "FPU  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(j)
End Sub
 
Sub Multiply_Paul
   Local iLoop,x,i,j,n,ScaledOneOverN  As Long  'x just is like poor-man Register None
   QueryPerformanceCounter qStart
   n=%Denominator
   ScaledOneOverN = &h100000000/n +1      'must be calculated once before the loop
   For iLoop = 1 To %iLoopMax
      '------------------------------------
      i = %Numerator
      !mov eax,i                'get i
      !mul ScaledOneOverN       'multiply by the magic number to put integer into edx and remainder in eax
      !mul n                    'scale remainder in eax back to an integer in edx
      !mov j,edx                'save result
      '------------------------------------
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "Multiply  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(j)
End Sub
 
Sub PowerOf2
   Local i,n,j,iLoop, Power As Long
   ReDim LookupTable200(80000) As Long
   QueryPerformanceCounter qStart
   For iLoop = 0 To %iLoopMax
      '============================================================
      i = %Numerator : n = 256 : Power = 16
      j = i AND (32-1)
      '============================================================
   Next iLoop
   QueryPerformanceCounter qStop
   DeltaTime = (qStop-qStart)/qFreq
   ? "PowerOf2  " + Format$(DeltaTime,"0.###") & " seconds   " + "Result: " + Str$(j)
End Sub
 
'gbs_00996
'Date: 03-10-2012


created by gbSnippets
http://www.garybeene.com/sw/gbsnippets.htm