João da Rocha Labrego

Bem-vindo(a), João da Rocha Labrego!

Seu trabalho é importante. Sou colaborador da Wikipédia. Espero que também goste de colaborar com esta enciclopédia, que dá a qualquer pessoa a possibilidade de ter livre acesso ao somatório de todo o conhecimento humano. Ajude-nos a melhorar e acrescentar informações. Obrigado por suas contribuições. Espero que goste daqui e decida ficar.

Aqui estão algumas páginas que podem ajudar:

• Os cinco pilares da Wikipédia
• Tutorial
• Como editar uma página e Como melhorar um artigo
• Como criar o seu primeiro artigo
• Livro de estilo

Se precisar de ajuda, pergunte em minha página de discussão ou na página para tirar dúvidas. Pode também se inscrever no programa de tutoria e ser acompanhado(a) por um(a) editor(a) mais experiente. Por favor assine suas mensagens nas páginas de discussão usando quatro tiles (~~~~) ou o botão presente no alto da janela de edição; isso irá inserir automaticamente seu nome de usuário e a data. Guilherme Moura (discussão) 23h22min de 18 de fevereiro de 2015 (UTC)

Testes em Logaritmo

Boas vindas, e obrigado(a) por experimentar a Wikipédia. Seu teste na página Logaritmo funcionou, porém foi necessário revertê-lo ou excluí-lo. Motivo: o único local correto para testar as ferramentas de edição da Wikipédia é a página de testes. Por favor, consulte a página de boas-vindas para aprender mais a respeito de como contribuir com esta enciclopédia. Obrigado(a). Guilherme Moura (discussão) 23h22min de 18 de fevereiro de 2015 (UTC)

Algoritmos Aritméticos

Tenho notado na Internet uma grande procura por algoritmos aritméticos, principalmente para trabalhar-se com números muito grandes que não cabem no escopo dos tipos numéricos disponíveis nas linguagens.

Como possuo uma coleção de algoritmos desenvolvidos e/ou coletados por mim na Internet, em função de uma biblioteca que estou desenvolvendo em C++ para trabalhar com números gigantes, gostaria disponibilizar esses mesmos algoritmos para as pessoas que deles necessitam.

Antes de mais nada, devo alerta-los de que usei o VBA para testar esses algoritmos e, por isso, disponibilizarei para vocês o código VBA para testes no EXCEL.

Não me delongarei em explicações sobre o código-fonte pois o entendimento ficará por conta do programado.

Defini o tipo numérico como BigInteger e, por isso, vocês deverão abrir uma planilha EXCEL e no VBA criar um módulo de classe com o nome BigInteger onde vocês copiarão o código-fonte abaixo na íntegra.

À medida em que eu for acrescentando novas coisas ou melhorando o código-fonte já existente, eu irei postando aqui para que vocês os utilizem.

No momento, creio que os programadores VBA mais avançados já conseguirão fazer alguma coisa com o código-fonte que ora disponibilizo.

  Option Explicit
  Option Base 1
  
  Private sign As Integer
  Private data() As LongLong
  Private length As Long
  Private physicalLength As Long
  
  Private Sub Class_Initialize()
  
     ToZero
     
  End Sub
  
  Private Sub Class_Terminate()
     'MsgBox "Created by João da Rocha Labrego"
  End Sub
  
  Friend Property Get Signal() As Integer
  
     Signal = sign
     
  End Property
  
  Friend Property Let Signal(ByVal value As Integer)
  
     sign = value
     
  End Property
  
  Friend Property Get Digit(ByVal index As Long) As LongLong
  
     Digit = data(index)
     
  End Property
  
  Friend Property Let Digit(ByVal index As Long, ByVal value As LongLong)
  
     data(index) = value
     
  End Property
  
  Friend Property Get GetLength() As Long
  
     GetLength = length
     
  End Property
  
  Public Function Parse(ByVal value As String) As String
  
     Dim i As Long, char As String
     
     Parse = vbNullString
     For i = 1 To Len(value)
         char = Mid(value, i, 1)
         If Not (char < "0" Or char > "9") Then
            If Not (char = "0" And Parse = vbNullString) Then
               Parse = Parse + char
            End If
         ElseIf char = "-" And Parse = vbNullString Then
            Parse = char
         End If
     Next
     
  End Function
  
  Friend Sub Resize(ByVal size As Long, Optional ByVal clearDigits As Boolean = False)
  
     Dim i As Long
     
     If size > physicalLength Then
        physicalLength = size + 50
        ReDim Preserve data(physicalLength)
     End If
     For i = IIf(clearDigits, 1, length + 1) To size
         data(i) = 0
     Next
     length = size
     
  End Sub
  
  Friend Sub ShiftRight(Optional times As Long = 1)
  
     Dim i As Long, j As Long
     
     If Not IsZero Then
        For i = 1 To times
            Resize length + 1
            For j = length To 2 Step -1
                data(j) = data(j - 1)
            Next
            data(j) = 0
        Next
     End If
     
  End Sub
  
  Public Sub SetValue(ByVal value As String)
  
     value = Parse(value)
     Valorize value
     
  End Sub
  
  Public Sub Valorize(ByVal value As String)
  
     Dim i As Long, j As Long, digitsCount As Long
     
     If value = vbNullString Then
        value = K_ZERO
     End If
     If Left(value, 1) = "-" Then
        sign = K_NEGATIVE
        value = Mid(value, 2)
     Else
        sign = K_POSITIVE
     End If
     digitsCount = Int(Len(value) / K_DIGIT_LENGTH) + IIf(Len(value) Mod K_DIGIT_LENGTH = 0, 0, 1)
     Resize digitsCount
     j = 1
     Do While value <> vbNullString
         data(j) = Val(Right(value, K_DIGIT_LENGTH))
         If Len(value) > K_DIGIT_LENGTH Then
            value = Left(value, Len(value) - K_DIGIT_LENGTH)
         Else
            value = vbNullString
         End If
         j = j + 1
     Loop
     
  End Sub
  
  Public Function GetValue() As String
  
     Dim i As Long
     
     GetValue = vbNullString
     For i = 1 To length - 1
         GetValue = Right(String(K_DIGIT_LENGTH, "0") + CStr(data(i)), K_DIGIT_LENGTH) + GetValue
     Next
     GetValue = IIf(sign = K_NEGATIVE, "-", "") + CStr(data(i)) + GetValue
     
  End Function
   
  Friend Sub Copy(ByRef value As BigInteger, Optional ByVal startIndex As Long = 1, Optional ByVal endIndex As Long = -1)
  
     Dim i As Long
     
     If endIndex = -1 Then
        endIndex = value.GetLength
     End If
     Resize endIndex - startIndex + 1
     sign = value.Signal
     For i = startIndex To endIndex
         data(i - startIndex + 1) = value.Digit(i)
     Next
     
  End Sub
  
  Friend Sub Append(ByRef value As BigInteger)
     Dim lastLength As Long, i As Long, j As Long
     
     lastLength = length
     j = value.GetLength
     If IsZero Then
        Resize value.GetLength
        lastLength = 0
     Else
        ShiftRight value.GetLength
     End If
     For i = length - lastLength To 1 Step -1
         data(i) = value.Digit(j)
         j = j - 1
     Next
  
  End Sub
  
  Public Sub ToZero()
  
     Resize 1
     sign = K_POSITIVE
     data(1) = 0
     
  End Sub
  
  Public Sub ToOne()
  
     Resize 1
     sign = K_POSITIVE
     data(1) = 1
     
  End Sub
  
  Public Function ToBigInteger(ByVal value As LongLong) As BigInteger
     
     Dim result As New BigInteger
  
     sign = IIf(value < 0, K_NEGATIVE, K_POSITIVE)
     Do
        result.Digit(result.GetLength) = value Mod K_NUMERIC_BASE
        value = Int(value / K_NUMERIC_BASE)
        If value > 0 Then
           result.Resize result.GetLength + 1
        Else
           Exit Do
        End If
     Loop
     
     Set ToBigInteger = result
     
  End Function
  
  Public Function IsZero() As Boolean
  
     IsZero = length = 1 And data(1) = 0
        
  End Function
  
  Public Function IsOne() As Boolean
  
     IsOne = length = 1 And data(1) = 1 And sign = K_POSITIVE
     
  End Function
  
  Public Function IsMinusOne() As Boolean
  
     IsOne = length = 1 And data(1) = 1 And sign = K_NEGATIVE
     
  End Function
  
  Public Function IsNegative() As Boolean
  
     IsNegative = sign = K_NEGATIVE
     
  End Function
  
  Public Function IsPositive() As Boolean
  
     IsPositive = sign = K_POSITIVE
     
  End Function
  
  Public Function IsEven() As Boolean
  
     IsEven = data(1) Mod 2 = 0
     
  End Function
  
  Public Function IsOdd() As Boolean
  
     IsOdd = data(1) Mod 2 = 1
     
  End Function
  
  Public Function Opposite() As BigInteger
     
     Dim result As New BigInteger
     
     result.Copy Me
     result.Signal = -result.Signal
     Set Opposite = result
  
  End Function
  
  Public Function Absolute() As BigInteger
     
     Dim result As New BigInteger
     
     result.Copy Me
     result.Signal = K_POSITIVE
     Set Absolute = result
  
  End Function
  
  Friend Sub Normalize()
  
     Dim i As Long
     
     For i = length To 1 Step -1
         If data(i) <> 0 Then
            Exit For
         End If
     Next
     If i < length Then
        If i > 0 Then
           Resize i
        Else
           ToZero
        End If
     End If
     
  End Sub
  
  Public Function Compare(ByRef value As BigInteger) As Integer
  
     Dim i As Long
     
     Compare = K_EQUAL
     If length < value.GetLength Then
        Compare = K_MINOR
     ElseIf length > value.GetLength Then
        Compare = K_MAJOR
     Else
        For i = length To 1 Step -1
            If data(i) < value.Digit(i) Then
               Compare = K_MINOR
               Exit For
            ElseIf data(i) > value.Digit(i) Then
               Compare = K_MAJOR
               Exit For
            End If
        Next
     End If
     
  End Function
  
  Public Function CompareDigit(ByVal value As LongLong) As Integer
  
     Dim i As Long
     
     Compare = K_EQUAL
     If length = 1 Then
        If data(1) < value Then
           Compare = K_MINOR
        ElseIf data(1) > value Then
           Compare = K_MAJOR
        End If
     ElseIf length > 1 Then
        Compare = K_MAJOR
     Else
        Compare = K_MINOR
     End If
     
  End Function
  
  Public Function Add(ByRef value As BigInteger) As BigInteger
  
     Dim addend1 As BigInteger, addend2 As BigInteger, result As New BigInteger, sum As LongLong, i As Long
  
     If sign = value.Signal Then
        If IsZero Then
           result.Copy value
        ElseIf value.IsZero Then
           result.Copy Me
        Else
           If length < value.GetLength Then
              addend1 = value
              addend2 = Me
           Else
              Set addend1 = Me
              Set addend2 = value
           End If
           sum = 0
           result.Resize addend1.GetLength
           For i = 1 To addend2.GetLength
               sum = sum + addend1.Digit(i) + addend2.Digit(i)
               result.Digit(i) = sum Mod K_NUMERIC_BASE
               sum = Int(sum / K_NUMERIC_BASE)
           Next
           For i = i To addend1.GetLength
               sum = sum + addend1.Digit(i)
               result.Digit(i) = sum Mod K_NUMERIC_BASE
               sum = Int(sum / K_NUMERIC_BASE)
           Next
           If sum > 0 Then
              result.Resize result.GetLength + 1
              result.Digit(i) = sum
           End If
        End If
        result.Normalize
        result.Signal = sign
     Else
        Set result = Subtract(value.Opposite)
     End If
     Set Add = result
     
  End Function
  
  Public Sub Increment()
  
     Dim i As Long
     
     If sign = K_NEGATIVE Then
        Set Me = Absolute.Decrement
        sign = K_NEGATIVE
     Else
        For i = 1 To length
            If data(i) = K_NUMERIC_BASE - 1 Then
               data(i) = 0
            Else
               data(i) = data(i) + 1
               Exit For
            End If
        Next
        If i > length Then
           Resize length + 1
           data(i) = 1
        End If
     End If
  
  End Sub
  
  Public Function Subtract(ByRef value As BigInteger) As BigInteger
  
     Dim minuend As BigInteger, subtrahend As BigInteger, result As New BigInteger, difference As LongLong, i As Long
     
     If sign = value.Signal Then
        If IsZero Then
           result.Copy value
        ElseIf value.IsZero Then
           result.Copy Me
        ElseIf Compare(value) = K_EQUAL Then
           result.ToZero
        Else
           If Compare(value) = K_MINOR Then
              Set minuend = value
              Set subtrahend = Me
           Else
              Set minuend = Me
              Set subtrahend = value
           End If
           result.Resize minuend.GetLength, True
           difference = 0
           For i = 1 To subtrahend.GetLength
               difference = K_NUMERIC_BASE + minuend.Digit(i) - subtrahend.Digit(i) - difference
               result.Digit(i) = difference Mod K_NUMERIC_BASE
               difference = IIf(difference < K_NUMERIC_BASE, 1, 0)
           Next
           For i = i To minuend.GetLength
               difference = K_NUMERIC_BASE + minuend.Digit(i) - difference
               result.Digit(i) = difference Mod K_NUMERIC_BASE
               difference = IIf(difference < K_NUMERIC_BASE, 1, 0)
           Next
           result.Signal = minuend.Signal
           result.Normalize
        End If
     Else
        Set result = Add(value.Opposite)
     End If
     Set Subtract = result
        
  End Function
  
  Public Sub Decrement()
  
     Dim i As Long
     
     If sign = K_NEGATIVE Then
        Set Me = Absolute.Increment
        sign = K_NEGATIVE
     Else
        For i = 1 To length
            If data(i) = 0 Then
               data(i) = K_NUMERIC_BASE - 1
            Else
               data(i) = data(i) - 1
               Exit For
            End If
        Next
     End If
     
  End Sub
  
  Public Function Multiply(ByRef value As BigInteger) As BigInteger
  
     Dim i As Long, j As Long, k As Long, result As New BigInteger, product As LongLong
     
     If IsZero Or value.IsZero Then
        result.ToZero
     ElseIf IsOne Then
        result.Copy value
     ElseIf value.IsOne Then
        result.Copy Me
     Else
        result.Resize length + value.GetLength, True
        For i = 1 To length
            k = i
            product = 0
            For j = 1 To value.GetLength
                product = product + data(i) * value.Digit(j) + result.Digit(k)
                result.Digit(k) = product Mod K_NUMERIC_BASE
                product = Int(product / K_NUMERIC_BASE)
                k = k + 1
            Next
            result.Digit(k) = product
        Next
        result.Normalize
     End If
     result.Signal = sign * value.Signal
     Set Multiply = result
     
  End Function
  
  Public Function MultiplyByDigit(ByVal value As LongLong) As BigInteger
     
     Dim result As New BigInteger, product, i As Long
     
     If IsZero Or value = 0 Then
        result.ToZero
     ElseIf IsOne Then
        result = ToBigInteger(value)
     ElseIf value = 1 Then
        result.Copy Me
     Else
        value = value Mod K_NUMERIC_BASE
        result.Resize length + 1, True
        product = 0
        For i = 1 To length
            product = product + data(i) * value
            result.Digit(i) = product Mod K_NUMERIC_BASE
            product = Int(product / K_NUMERIC_BASE)
        Next
        If product > 0 Then
           result.Digit(result.GetLength) = product
        End If
        result.Normalize
     End If
     result.Signal = sign * IIf(value < 0, K_NEGATIVE, K_POSITIVE)
     Set MultiplyByDigit = result
     
  End Function
  
  Public Function Divide(ByRef value As BigInteger, Optional ByRef remainder As BigInteger = Nothing) As BigInteger
     Dim dividend As New BigInteger, product As New BigInteger, result As New BigInteger, minQuotient As LongLong, _
         maxQuotient As LongLong, quotient As LongLong, comparison As Integer, haveQuotient As Boolean, i As Long
     
     If value.IsZero Then
        Err.Raise 1000, Nothing, "Divisor is zero."
     End If
     Set remainder = New BigInteger
     If IsZero Then
        result.ToZero
        remainder.ToZero
     ElseIf value.IsOne Then
        result.Copy Me
        remainder.ToZero
     Else
        comparison = Compare(value)
        If comparison = K_MINOR Then
           result.ToZero
           remainder.Copy Me
        ElseIf comparison = K_EQUAL Then
           result.ToOne
           remainder.ToZero
        Else
           haveQuotient = False
           For i = length To 1 Step -1
               dividend.ShiftRight
               dividend.Digit(1) = data(i)
               comparison = dividend.Compare(value)
               If comparison = K_MINOR Then
                  If haveQuotient Then
                     result.ShiftRight
                  End If
               ElseIf comparison = K_EQUAL Then
                  result.ShiftRight
                  result.Digit(result.GetLength) = 1
                  haveQuotient = True
               Else
                  result.ShiftRight
                  minQuotient = 0
                  maxQuotient = CLng(K_NUMERIC_BASE) - 1
                  Do While minQuotient <= maxQuotient
                     quotient = Int((minQuotient + maxQuotient) / 2)
                     Set product = value.MultiplyByDigit(quotient)
                     comparison = product.Compare(dividend)
                     If comparison = K_EQUAL Then
                        maxQuotient = quotient
                        Exit For
                     End If
                     If comparison = K_MINOR Then
                        minQuotient = quotient + 1
                     Else
                        maxQuotient = quotient - 1
                     End If
                  Loop
                  If quotient <> maxQuotient Then
                     Set product = value.MultiplyByDigit(maxQuotient)
                  End If
                  result.Digit(1) = maxQuotient
                  Set dividend = dividend.Subtract(product)
                  haveQuotient = True
               End If
           Next
           result.Normalize
           remainder.Copy dividend
        End If
     End If
     result.Signal = sign * value.Signal
     Set Divide = result
     
  End Function
  
  Public Function DivideByDigit(ByVal value As LongLong, Optional ByRef remainder As BigInteger = Nothing) As BigInteger
  
     Dim result As New BigInteger, dividend As LongLong, quotient As LongLong, i As Long, j As Long, haveQuotient As Boolean
     
     If value = 0 Then
        Err.Raise 1000, Nothing, "Divisor is zero."
     End If
     Set remainder = New BigInteger
     If IsZero Then
        result.ToZero
        remainder.ToZero
     ElseIf value = 1 Then
        result.Copy Me
        remainder.ToZero
     Else
        comparison = CompareDigit(value)
        If comparison = K_MINOR Then
           result.ToZero
           remainder.Copy Me
        ElseIf comparison = K_EQUAL Then
           result.ToOne
           remainder.ToZero
        Else
           value = value Mod K_NUMERIC_BASE
           dividend = 0
           result.Resize length - IIf(value > data(length), 1, 0), True
           j = result.GetLength
           For i = length To 1 Step -1
               dividend = dividend * K_NUMERIC_BASE + data(i)
               If dividend >= value Then
                  quotient = Int(dividend / value)
                  result.Digit(j) = quotient
                  j = j - 1
                  dividend = dividend - quotient * value
                  haveQuotient = True
               ElseIf haveQuotient Then
                   result.Digit(j) = 0
                   j = j - 1
               End If
           Next
           remainder.Copy ToBigInteger(dividend)
           result.Normalize
        End If
     End If
     result.Signal = sign * IIf(value < 0, K_NEGATIVE, K_POSITIVE)
     Set DivideByDigit = result
     
  End Function
  
  Public Function Power(ByVal exponent As LongLong) As BigInteger
     Dim base As New BigInteger, result As New BigInteger
     
     exponent = Abs(exponent)
     If exponent = 0 Then
        result.ToOne
     ElseIf exponent = 1 Then
        result.Copy Me
     Else
        base.Copy Me
        result.ToOne
        If exponent > 0 Then
           Do While exponent > 1
              If exponent Mod 2 = 1 Then
                 Set result = result.Multiply(base)
                 If exponent = 1 Then
                    Exit Do
                 End If
              End If
              Set base = base.Multiply(base)
              exponent = Int(exponent / 2)
           Loop
           Set result = result.Multiply(base)
        End If
     End If
     result.Signal = IIf(exponent Mod 2 = 0, K_POSITIVE, Signal)
     Set Power = result
  End Function
  
  Public Function Root(ByVal degree As Long, Optional remainder As BigInteger = Nothing) As BigInteger
  
     Dim radicand As New BigInteger, potency As New BigInteger, result As New BigInteger, buffer As New BigInteger, _
         radix As LongLong, minRadix As LongLong, maxRadix As LongLong, groupLength As Long, i As Long, _
         comparison As Integer, coeficient As New BigInteger
            
     degree = Abs(degree)
     Set remainder = New BigInteger
     If degree = 0 Then
        Err.Raise 1000, Nothing, "Degree is zero."
     End If
     If degree Mod 2 = 0 And IsNegative Then
        Err.Raise 1000, Nothing, "Even degree with negative radicand."
     End If
     If degree = 1 Or IsOne Or IsZero Then
        result.Copy Me
        remainder.ToZero
     Else
        groupLength = length Mod degree
        groupLength = IIf(groupLength = 0, degree, groupLength)
        i = length
        minRadix = 1
        radix = 0
        coeficient.Valorize CStr(K_NUMERIC_BASE)
        Set coeficient = coeficient.Power(degree - 1)
        Set coeficient = coeficient.MultiplyByDigit(degree)
        maxRadix = data(1)
        remainder.ToZero
        Do While i > 1
           i = i - groupLength
           buffer.Copy Me, i + 1, i + groupLength
           radicand.Append buffer
           remainder.Append radicand
           groupLength = degree
           result.ShiftRight
           Do While minRadix <= maxRadix
              radix = Int((minRadix + maxRadix) / 2)
              result.Digit(1) = radix
              Set potency = result.Power(degree)
              comparison = potency.Compare(radicand)
              If comparison = K_EQUAL Then
                 maxRadix = radix
                 Exit Do
              End If
              If comparison = K_MINOR Then
                 minRadix = radix + 1
              Else
                 maxRadix = radix - 1
              End If
           Loop
           remainder.Copy Subtract(potency)
           result.Digit(1) = maxRadix
           minRadix = 0
        Loop
        result.Normalize
        If result.Digit(1) <> radix Then
           Set potency = result.Power(degree)
        End If
        remainder.Copy Subtract(potency)
     End If
     result.Signal = sign
     Set Root = result
     
  End Function

João da Rocha Labrego (discussão) 01h33min de 21 de fevereiro de 2015 (UTC)