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.
Who is Participating?

Commented:

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

Commented:

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

Author 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....

Fiorah.
0

Author 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

Commented:

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

Commented:

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

0

Author 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

Author 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

Commented:
>>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

0

Author 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 ?

0

Commented:

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

Author 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)

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.