How to handle a number larger than biggest variable?

[Banana]

I have some numbers which I need to convert to binary format, and this is one off time, but I'm not sure how I would fit the numbers in to perform the necessary conversion.

The numbers has 256 significant digits (actually I only needed 78 digits to create a 256 digit long binary representation). AFAICT, there aren't anything online or freely available that allows me to do conversion with such precision.

The problem is that the algorithm to convert from base 10 to base 2 requires that I repeatedly divide the remaining integer by 2 as I move from leftmost digit to the last:

e.g.

Convert 118 from base 10 to base 2

118 ÷ 2 = 59	0
59 ÷ 2 = 29	1
29 ÷ 2 = 14	1
14 ÷ 2 = 7	0
7 ÷ 2 = 3	1
3 ÷ 2 = 1	1
1 ÷ 2 = 0	1

which becomes 1110110 (reading upward).

But the biggest number I can store is 4 million something. Because the numbers are fractional, it's quite important that I keep the significant digits so no fudging.

I would imagine in order to divide a large number, I'd need to hold a number of variable, split the large number into smaller number that variables can hold, then divide 2 with the first variable, and carry over the result into the second variable and so forth? Or maybe there's easier way?

 

[georgedwilkinson]

I seem to remember, long, long ago, using bit shift operations on VB strings (I think VB2 or 3), possibly one byte at a time. Those routines did not fail on subsequent upgrades to VB (up to VB5, I think).

So, if my memory serves right, you could create a 32 byte string and use operators like Hex(), Oct(), and multiply/divide by 2. You could also and bytes with powers of 2 to mask out a certain bit and get your "binary" representation. This might give the appearance of being a 32 byte number. If you use this technique, it won't be easy.

If you know C/C++ and can write a DLL to call functions from VBA it would be easiest.

 

[gemma-the-husky]

obviously there must be ways of dealing with long numbers, or they couldnt calculate pi to inordinate lengths, but it must be quite specialised stuff

 

[Banana]

Actually, I was delighted to find that Python was capable of dealing with such large number with no problem at all. If you happen to have an interpreter just drop in this function, and you're good to go:

# convert a decimal (denary, base 10) integer to a binary string (base 2)
# tested with Python24   vegaseat    6/1/2005

def Denary2Binary(n):
    '''convert denary integer n to binary string bStr'''
    bStr = ''
    if n < 0:  raise ValueError, "must be a positive integer"
    if n == 0: return '0'
    while n > 0:
        bStr = str(n % 2) + bStr
        n = n >> 1
    return bStr

def int2bin(n, count=24):
    """returns the binary of integer n, using count number of digits"""
    return "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])

# this test runs when used as a standalone program, but not as an imported module
# let's say you save this module as den2bin.py and use it in another program
# when you import den2bin the __name__ namespace would now be  den2bin  and the
# test would be ignored
if __name__ == '__main__':
    print Denary2Binary(255)  # 11111111
    
    # convert back to test it
    print int(Denary2Binary(255), 2)  # 255
    
    print
    
    # this version formats the binary
    print int2bin(255, 12)  # 000011111111
    # test it
    print int("000011111111", 2)  # 255
    
    print

    # check the exceptions
    print Denary2Binary(0)
    print Denary2Binary(-5)  # should give a ValueError

I'm working on a script to handle fractional part of decimal, but it's much easier than messing with multiple variables and carrying over the extra one to next variable.

 

[ByteMyzer]

If what you are looking for is a Base-converter for large numbers, the following code will take an input string of a number, the original base and the base to which the number is to be converted, and return the result as a string.

Example:

?basConv("80678533204755556875623860917935", 10, 2)

1111111010010011100110011010000100001001001111111001111010010111100011010010101000101110011101011010101111

Public Function basConv( _
    ByVal basInp As String, _
    ByVal basFrom As Integer, _
    ByVal basTo As Integer) _
    As String

Dim basLp As Integer        ' Miscellaneous Loop Counter
Dim basChr(35) As String    ' contains Digit Index Array
                            ' "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
Dim basVal(90) As Integer   ' ASCII Conversion Index -
                            ' Digit Character to Numeric Equivalent
Dim basIdx As Integer       ' Variable Conversion Array Index
Dim basCtr As Integer       ' Variable Conversion Array Index Counter


' Generate Index Data
For basLp = 0 To 9
    basChr(basLp) = Chr(basLp + 48)
    basVal(basLp + 48) = basLp
Next basLp
For basLp = 10 To 35
    basChr(basLp) = Chr(basLp + 55)
    basVal(basLp + 55) = basLp
Next basLp

' Initialize Conversion Array
basIdx = 1
ReDim basVar(1) As Integer

' Loop through Input String
For basLp = 1 To Len(basInp)
    ' Set Conversion Array Index Counter to Top of Array
    basCtr = 1
    basVar(0) = basVar(0) * basFrom _
    + basVal(Asc(Mid$(basInp, basLp, 1)))
    ' Multiply value in Bottom of Array
    ' by the original base factor and add the digit value
    While basCtr <= basIdx
        basVar(basCtr) = basVar(basCtr) * basFrom _
            + Int(basVar(basCtr - 1) / basTo)
        basVar(basCtr - 1) = basVar(basCtr - 1) Mod basTo
        If basCtr = basIdx And basVar(basCtr) > basTo - 1 Then
            ' If the product value is greater than the array value,
            ' increment the array index and inflate the array
            basIdx = basIdx + 1
            ReDim Preserve basVar(basIdx)
        End If
        basCtr = basCtr + 1
    Wend
Next basLp

' Loop through the array and create the result string
For basLp = basIdx To 0 Step -1
    basConv = basConv & basChr(basVar(basLp))
Next basLp

End Function

 

[Banana]

Now I need to create functions to perform binary additions on large numbers (256-bits) which I store as Byte arrays.

My original code was to loop the array backward, doing regular addition, and carrying over the excess of 255. I should raise the power of the next set, but that would require me to be able to contain 10^77 number. I decided it'd be a good idea to 2/carryover so I don't have to worry about number overflowing, while maintaining correct binary representation.

However, I'm not too confident if this is correct... Can someone give me a clue?

Private Function BinAdd(inByte1() As Byte, inByte2() As Byte) As Variant

Dim i As Integer
Dim j As Integer
Dim sum As Long
Dim carry As Long
Dim arSum() As Byte

j = UBound(inByte1())

If Not j = UBound(inByte2()) Then
    Exit Function
Else
    ReDim arSum(0 To j)
End If

For i = j To 0 Step -1
    If Not carry = 0 Then
        sum = CLng(inByte1(i)) + CLng(inByte2(i)) + (2 / carry)
    Else
        sum = CLng(inByte1(i)) + CLng(inByte2(i))
    End If
    If sum > 255 Then
        carry = sum - 255
        sum = 255
    Else
        carry = 0
    End If
    arSum(i) = CByte(sum)
Next i

End Function

 

[Banana]

Looking at it more carefully, I'm seeing how breaking it up in arrays can seriously trip up the additions.

Take this for example:

  11111111  '255
+ 11111111  '255
==========
 111111110  '510

Breaking this into two bytes, we get:

00000001 '1*(2^8)=256
11111110 '254

Therefore, when the sum goes over 255, I cannot just subtract 255 and carry over the remainder because this is not the case of 255+255, but rather 256+254.

So does that I will have to convert everything into binary to tell what remainder I should carry over, and what number to put in for this element, or is there a easier way?

Edit: Doing some more experiment, it looks like I want to subtract the sum from 256 and carry over the remainder, but not sure if this is still valid for all other numbers...

Edit 2: Switching between the bc and the VBA, it looks like this works...

Private Function BinAdd(inByte1() As Byte, inByte2() As Byte) As Variant

Dim i As Integer
Dim j As Integer
Dim sum As Long
Dim carry As Long
Dim arSum() As Byte

j = UBound(inByte1())

If Not j = UBound(inByte2()) Then
    Exit Function
Else
    ReDim arSum(0 To j)
End If

For i = 0 To j
    If Not carry = 0 Then
        sum = CLng(inByte1(i)) + CLng(inByte2(i)) + (carry)
    Else
        sum = CLng(inByte1(i)) + CLng(inByte2(i))
    End If
    If sum > 255 Then
        carry = 1
        sum = sum - 256
    Else
        carry = 0
    End If
    arSum(i) = CByte(sum)
Next i

BinAdd = arSum

End Function

Private Sub foo()

Dim whatever() As Byte
Dim i As Integer
Dim i256(3) As Byte
Dim i512(3) As Byte

i256(0) = 255
i256(1) = 255
i256(2) = 0
i256(3) = 0

i512(0) = 255
i512(1) = 1
i512(2) = 0
i512(3) = 0

whatever = BinAdd(i256(), i512())

For i = 0 To 3
    Debug.Print whatever(i)
Next i

End Sub

Output:

000000010000000111111110 or 66046

Can anyone else verify this will produce correct result for all set of numbers?