• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 319
  • Last Modified:

Permutations, factorials and bitwise comparison

Hi,

I'm coding a function in order to test every calculations possible between x numbers.

I found over the net a pretty good algorithm which helped me a lot but it has its
limits... The prb with this code is that at some point it manage a bitwise comparison
(with AND operator) between 2 values, but when it reach very high numbers, it fails with
an overflow error due to the AND bitwise comparison which is limited to long values (32 bits)
in VB.

A simple example of the prb can be viewed just by typing following statement in the
debug/immediate window:  ?  2^32 AND 2^32

So 1st question : how can i use double variables (64 bits) with the AND-bitwise-comparison ?

Or 2nd question : any better idea for achieving my goal ?

As far as i know, bitwise comparison is fast. However, with my current code, checking all possible
calculations for eg 20 amounts gives 1.048.555 possible calculations (((2 ^ (20)) - 1) - 20).
And computing all these calculations already takes a little more than 30 minutes on my PC.

I found an interesting thread on the subject in this site here :
http://www.experts-exchange.com/Programming/Programming_Languages/Visual_Basic/Q_10042260.html

...but could not find out how to apply this for my prb :(

I also found a free dll (Binary Function Library 2.00) which seems very interesting, but as i'm not an
expert with bits, i couldn't sort this out myself either. The library can be found here :
  http://www.windowsmarketplace.com/results.aspx?bCatID=63&av=14-190969

Thanks for the help,

Fiorah.
0
FioraH
Asked:
FioraH
  • 6
  • 6
1 Solution
 
Mark_FreeSoftwareCommented:

to use that library, put it in the same folder as your app (or the system32 dir)

you are interested in this declaration:

Declare Sub AndQ Lib "BinaryLib" (ByRef ArPattern As Any, ByRef Amount As Any, Optional ByVal ArPatternSize As Long = 8)



to use it with your example:

Private Sub Command1_Click()
Dim dblRet As Double
dblRet = 2 ^ 32
AndQ dblRet, 2 ^ 32
Debug.Print "the operation 2 ^ 32 AND 2 ^ 32 equals " & CStr(dblRet)
End Sub
0
 
FioraHAuthor Commented:
ok, i understand your statement and it woks with my original example. (thanks for that)

however, can you tell me why coding the call of AndQ through this function...

Function MyAnd(Nb1, Nb2)

    AndQ Nb1, Nb2
   
    MyAnd = Nb1

End Function

...returns eg 2 when i type MyAnd (2,4)

but typing ? (2 and 4) in the debug window returns 0

At the end, my goal is to have a similar way of working than with the original AND-bitwise comparison.

not sure i'm very clear....

Thanks again for your help

Fiorah.
0
 
FioraHAuthor Commented:
and also note that i still got the same result if i declare my variables and the function itself as doubles :

Function MyAnd(Nb1 As Double, Nb2 As Double) As Double
   
    AndQ Nb1, Nb2
   
    MyAnd = Nb1
     
End Function
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
Mark_FreeSoftwareCommented:


the error is in the dll,

try this one, it works:

Private Function MyAnd(Nb1 As Double, Nb2 As Double) As Double
    AndQ Nb1, CLng(Nb2)       'converting to long does the trick
    MyAnd = Nb1
End Function
0
 
Mark_FreeSoftwareCommented:

i think your best bet is to write a dll yourself, or to split a double in two Longs

see this question for the double longs:

http://www.experts-exchange.com/Programming/Programming_Languages/Visual_Basic/Q_10619541.html?query=%22and%22+double&topics=93

(especially the accepted answer)
0
 
FioraHAuthor Commented:
do you mean that if i split my 2 doubles into 4 longs, i should then use the AND-bitwise
operator with my 4 numbers (instead of 2) ?

eg:

instead of : if (x and y) then ...my statements
i could have : if (x1 and x2 and y1 and Y2) then ...my statements

???

and could you also elaborate on how to split a double in two longs ? i read the thread
but did not get how a 1.1 double is derived into 2 longs (-1717986918 and 1072798105) ?!!?

forgive me if my questions seems dumb, but as you can guess, i'm new to binaries.....

Thanks,

Fiorah.
0
 
FioraHAuthor Commented:
and btw, the dll must be really buggy (??), because even when converting the 2nd operand
to long as you suggested, it still doesn't work with every case !

check with MyAnd(3,2) which results into 0 instead of 2 !

i tried mailing the author of the dll, but got no answer so far :(

or are we both missing something ????
0
 
Mark_FreeSoftwareCommented:
>>or are we both missing something ????

i don't think, cause i know pretty good how the "and" operation works


what i mean by splitting is this:


take the ("Big") hexadecimal value FD and the value AB

now both split them and perform an bitwise and:

F    D
A    B

F and A = A
D and B = 9


now join the 2 parts:

A9


and voila, your "Big" number

0
 
FioraHAuthor Commented:
i got an answer from dll's author who told me that the prb was not with his dll but with the way VB stores doubles variables. He explained me that a work-around to have is dll working was to split my doubles variables into arrays of two longs (just like you suggested).

But i'm really lost with hexs.... (!) i got your above example, but how am i suppose to split, very big values,
say 2^40 or 2^64, into two longs ? or into hexs ?

i'm not familiar with hex/binary notations... i think hexs has to be left-padded with zeroes to reach
16 chars, that's it ? But how do you represent 2^65 in hex ? or bigger : 2^150 ???

btw, strangely vb returns 1,84467440737096E+19 (18 446 744 073 709 600 000) for 2^64 when it should be
18 446 744 073 709 55 616, isn't it ? Do you know why ?

Thanks again for your answers.
0
 
Mark_FreeSoftwareCommented:

just to let you know i didnt left this Q:
i'm a little short on time now, i'll get back here as soon as possible (i think friday)
0
 
FioraHAuthor Commented:
Thanks again, if it can give you more ideas, here is how i use the AndQ function (i had to find a MyHex
function as the internal VB's Hex function is also limited to longs)

Function MyHex(ByVal Number)
Const HexChars = "0123456789ABCDEF"

    Number = CDbl(Number)
 
    If Number = 0 Then
        MyHex = "&H00000000&H00000000"
        Exit Function
    End If
 
    While Number > 0
        MyHex = Mid(HexChars, 1 + (Number - 16 * Fix(Number / 16)), 1) & MyHex
        Number = Fix(Number / 16)
    Wend
 
    MyHex = "&H" & String(16 - Len(MyHex), "0") & MyHex
    MyHex = Left(MyHex, 10) & "&H" & Right(MyHex, 8)
 
End Function

Then, i also created a MyAnd function, in order to reproduce, through the dll's AndQ function,
the internal VB's And function behavior :

Function MyAnd(ByVal Res As Double, ByVal var2 As Double) as Boolean
'An array of two Longs (1st operand)
Dim strtmp As String

    strtmp = MyHex(Res)

Dim lArray(1 To 2) As Long
lArray(2) = Left(strtmp, 10)
lArray(1) = Right(strtmp, 10)

    strtmp = MyHex(var2)

'An array of two Longs (2nd operand)
Dim l2ndOperand(1 To 2) As Long
l2ndOperand(2) = Left(strtmp, 10)
l2ndOperand(1) = Right(strtmp, 10)

    AndQ lArray(1), l2ndOperand(1)

   ' MyAnd will be true only if the result of the bitwise comparison is not 0 (&H0)
    MyAnd = ("&H" & Hex(lArray(2)) & Hex(lArray(1))) <> &H0

End Function

But these 2 calls (MyHex+MyAnd) considerably slows down the running time of my code (apparently
10 times slower than the VB's And)
In addition, i'm not sure the MyHex function can handle very large numbers (eg > 2^64, >2^100...)

And i won't copy my whole code which computes any possible calculations, but below is the main part
including how the And (or MyAnd) is used (i have commented the 2 lines used for MyAnd) :
(note that T() is an Array which stores all the amounts to be tested)

y = 2 ^ (intNb - 1) ' intNb is the number of amounts to be tested
For i = 1 To (2 ^ (intNb)) - 1
  z = y
  j = 0: intN = intNb: strCombi = "" ' j stores number of amounts in current operation
        While z > 0
            ' ******** VBs AND Bitwise comparison Method => limited to Longs :((
            ' strcombi stores the current amount in order to produce (at the end) our operation to be tested
            If (i And z) Then j = j + 1:strCombi = strCombi & T(intN) & "+"
            z = z \ 2: intN = intN - 1 ' backslash used for integer division -> limited to longs
            ' ******** ANDq comparison Method => not limited :))
'            If MyAnd(i, z) Then j = j + 1:strCombi = strCombi & T(intN) & "+"
'            z = Int(z / 2): intN = intN - 1
        Wend
        ' As our goal is to check sums between at least 2 amounts, no need to bother when there's only 1 !
        If j > 1 Then
            ' Let's remove the last '+' from our final operation to be tested
            strCombi = Left(strCombi, Len(strCombi) - 1)
            ' Now let's check operation's result
            ' !!! Warning : the Replace Function is used here when decimal separator in Regional Settings is a comma (,)
            ' !!! Remove the Replace if your decimal separator is the dot (.)
            If Eval(Replace(strCombi, ",", ".")) = 0 Then
               debug.print strcombi
            intNb = 0: intN = 0: i = 0: j = 0: y = 0: z = 0
            strCombi = ""
            End If
        End If
Next
   
Note that i also implemented an exit of the for-next loop as soon as 1 combination=0 is found. This
way i can re-launch the process with less number of amounts for the next pass (thus will reduce next
number of possibilities, thus running time)

Thanks for your help.


0
 
Mark_FreeSoftwareCommented:


ok, i haven't forgot about you, here are some functions that you might need:

'-----------------------------------start cutting here-------------------------------------------
Private Sub DblToArr(lHugeNumber As Double, ByRef tmpArr() As Long)
Dim tmpVal As Long, tmpVal2 As Double, n As Long
   'what this sub does, is breaking the value in pieces of 6 hexadecimal digits,
   'so &HFFFFFFF becomes &HF and &HFFFFFF
   Erase tmpArr   'make sure it is empty
   tmpVal2 = lHugeNumber \ 16777216         '&H1000000
   tmpVal = lHugeNumber - tmpVal2 * 16777216
   ReDim tmpArr(0)
   tmpArr(0) = tmpVal
   lHugeNumber = tmpVal2
   n = 1
   While tmpVal2 <> 0
      'tmpVal = CInt(tmpVal2 And andVal)
      tmpVal2 = lHugeNumber \ 16777216
      tmpVal = lHugeNumber - tmpVal2 * 16777216
      ReDim Preserve tmpArr(0 To n)
      tmpArr(n) = tmpVal
      lHugeNumber = tmpVal2
      n = n + 1
   Wend
End Sub


Private Sub ArrToDbl(tmpArr() As Long, ByRef lHugeNumber As Double)
Dim n As Long
   'this sub does exactly the reverse
lHugeNumber = 0         'clear the var
For n = UBound(tmpArr) To LBound(tmpArr) Step -1
   lHugeNumber = lHugeNumber * 16777216 + tmpArr(n)
Next
End Sub
'-----------------------------------stop cutting here-------------------------------------------



example usage:

'-----------------------------------start cutting here-------------------------------------------
Private Sub Command1_Click()
Dim tmp() As Long, dValue As Double
   DblToArr CDbl(268435455), tmp()           '&HFFFFFFF
   ArrToDbl tmp, dValue
      MsgBox CStr(268435455) & " became: " & vbCrLf & dValue
   DblToArr CDbl(268435456), tmp()           '&H10000000
   ArrToDbl tmp, dValue
      MsgBox CStr(268435456) & " became: " & vbCrLf & dValue
End Sub

'-----------------------------------stop cutting here-------------------------------------------

when you perform and operations, be careful:

the "smallest" part, eg the 6 most right hexadecimal digits are in the first part

0

Featured Post

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

  • 6
  • 6
Tackle projects and never again get stuck behind a technical roadblock.
Join Now