Type Zeckendorf
    As Integer dLen
    As Ulongint dVal

    Declare Constructor()
    Declare Constructor(x As String)
    Declare Sub a(n As Integer)
    Declare Sub b(Pos As Integer)
    Declare Sub c(Pos As Integer)
    Declare Sub inc()
    Declare Function suma(rhs As Zeckendorf) As Zeckendorf
    Declare Function resta(rhs As Zeckendorf) As Zeckendorf
    Declare Function producto(rhs As Zeckendorf) As Zeckendorf
    Declare Function toString() As String
End Type

Constructor Zeckendorf()
    This.dLen = 0
    This.dVal = 0
End Constructor

Constructor Zeckendorf(x As String)
    Dim As Ulongint q = 1
    Dim As Integer i = Len(x) - 1
    This.dLen = Int(i / 2)
    This.dVal = 0
    While i >= 0
        This.dVal += (Asc(Mid(x, i+1, 1)) - Asc("0")) * q
        q *= 2
        i -= 1
    Wend
End Constructor

Sub Zeckendorf.a(n As Integer)
    Dim As Integer i = n
    Do
        If This.dLen < i Then This.dLen = i
        Dim As Integer j = (This.dVal Shr (i * 2)) And 3
        If j = 0 Or j = 1 Then Exit Sub
        If j = 2 Then
            If ((This.dVal Shr ((i + 1) * 2)) And 1) <> 1 Then Exit Sub
            This.dVal += 1ULL Shl (i * 2 + 1)
            Exit Sub
        End If
        If j = 3 Then
            Dim As Ulongint temp = 3ULL Shl (i * 2)
            temp Xor= &HFFFFFFFFFFFFFFFFULL
            This.dVal And= temp
            This.b((i + 1) * 2)
        End If
        i += 1
    Loop
End Sub

Sub Zeckendorf.b(posic As Integer)
    If posic = 0 Then
        This.inc()
        Exit Sub
    End If
    If ((This.dVal Shr posic) And 1) = 0 Then
        This.dVal += 1ULL Shl posic
        This.a(Int(posic / 2))
        If posic > 1 Then This.a(Int(posic / 2) - 1)
    Else
        Dim As Ulongint temp = 1ULL Shl posic
        temp Xor= &HFFFFFFFFFFFFFFFFULL
        This.dVal And= temp
        This.b(posic + 1)
        This.b(posic - Iif(posic > 1, 2, 1))
    End If
End Sub

Sub Zeckendorf.c(posic As Integer)
    If ((This.dVal Shr posic) And 1) = 1 Then
        Dim As Ulongint temp = 1ULL Shl posic
        temp Xor= &HFFFFFFFFFFFFFFFFULL
        This.dVal And= temp
        Exit Sub
    End If
    This.c(posic + 1)
    If posic > 0 Then
        This.b(posic - 1)
    Else
        This.inc()
    End If
End Sub

Sub Zeckendorf.inc()
    This.dVal += 1
    This.a(0)
End Sub

Function Zeckendorf.suma(rhs As Zeckendorf) As Zeckendorf
    Dim As Zeckendorf copy = This
    Dim As Ulongint rhs_dVal = rhs.dVal
    Dim As Integer limit = (rhs.dLen + 1) * 2
    For gn As Integer = 0 To limit - 1
        If ((rhs_dVal Shr gn) And 1) = 1 Then copy.b(gn)
    Next
    Return copy
End Function

Function Zeckendorf.resta(rhs As Zeckendorf) As Zeckendorf
    Dim As Zeckendorf copy = This
    Dim As Ulongint rhs_dVal = rhs.dVal
    Dim As Integer limit = (rhs.dLen + 1) * 2
    For gn As Integer = 0 To limit - 1
        If ((rhs_dVal Shr gn) And 1) = 1 Then copy.c(gn)
    Next
    While (((copy.dVal Shr ((copy.dLen * 2) And 31)) And 3) = 0) Or (copy.dLen = 0)
        copy.dLen -= 1
    Wend
    Return copy
End Function

Function Zeckendorf.producto(rhs As Zeckendorf) As Zeckendorf
    Dim As Zeckendorf na = rhs, nb = rhs, nr
    Dim As Ulongint dVal = This.dVal
    For i As Integer = 0 To (This.dLen + 1) * 2 - 1
        If ((dVal Shr i) And 1) > 0 Then nr = nr.suma(nb)
        Dim As Zeckendorf nt = nb
        nb = nb.suma(na)
        na = nt
    Next
    Return nr
End Function

Function Zeckendorf.toString() As String
    Dim As String dig(2) = {"00", "01", "10"}
    Dim As String dig1(2) = {"", "1", "10"}

    If This.dVal = 0 Then Return "0"
    Dim As Integer idx = (This.dVal Shr ((This.dLen * 2) And 31)) And 3
    Dim As String sb = dig1(idx)
    For i As Integer = This.dLen - 1 To 0 Step -1
        idx = (This.dVal Shr (i * 2)) And 3
        sb &= dig(idx)
    Next
    Return sb
End Function

' Main
Print "Addition:"
Dim As Zeckendorf g = Zeckendorf("10")
g = g.suma(Zeckendorf("10"))
Print g.toString()
g = g.suma(Zeckendorf("10"))
Print g.toString()
g = g.suma(Zeckendorf("1001"))
Print g.toString()
g = g.suma(Zeckendorf("1000"))
Print g.toString()
g = g.suma(Zeckendorf("10101"))
Print g.toString()
Print

Print "Subtraction:"
g = Zeckendorf("1000")
g = g.resta(Zeckendorf("101"))
Print g.toString()
g = Zeckendorf("10101010")
g = g.resta(Zeckendorf("1010101"))
Print g.toString()
Print

Print "Multiplication:"
g = Zeckendorf("1001")
g = g.producto(Zeckendorf("101"))
Print g.toString()
g = Zeckendorf("101010")
g = g.suma(Zeckendorf("101"))
Print g.toString()

Sleep