Ооочень длинное целое

    Накатал небольшую библиотечку для арифметических операций над натуральными числами любой длины. Поскольку писалось на Visual Basic for Applications (VBA), встроенном в Excel, переопределить операции + — * / не получилось, и все решается через вызов функций с 2-мя аргументами вида

    Function LongADD(s1 As String, s2 As String) As String

    Зато можно вызывать функции (или их комбинации) прямо из ячеек экселовского листа – все наглядно и понятно. И да, натуральные числа передаются как строки. Максимальная длина строки в VBA равна примерно 231 = 2 147 483 648 (посчитано моей функцией LongPower(«2», 31)), так что на поиграться с разными штуками хватит вполне.

    Для примера – умножение двух простых чисел из эпохальной статьи Ривеста, Шамира и Алдемана, откуда пошла вся современная криптография (в коде это константы RSA1, RSA2)



    Под катом – код на VBA, его можно просто вставить в модуль Excel-овского файла с поддержкой макросов (типа *.xlsm).

    P.S. не пробуйте использовать код для всяких конкурсов по разложению на простые множители. Он хоть и понимает числа с двумя миллиардами значащих цифр, но безумно медленный для таких задач.
    P.P.S. если все же что-то получится, 10% выигрыша – мне
    P.P.P.S. нет, лучше 15%


    ' Это 2 простых числа Ривеста, Шамира и Адлемана
    Public Const RSA1 = "3490529510847650949147849619903898133417764638493387843990820577"
    Public Const RSA2 = "32769132993266709549961988190834461413177642967992942539798288533"

    ' Функция выполняет длинное сложение
    Public Function LongAdd(s1 As String, s2 As String) As String

    ' Это перенос в следующий разряд и текущие цифры
    Dim Carry As Byte, Digit1 As Byte, Digit2 As Byte
    Dim Result As String

    Carry = 0
    Result = ""

    ' Более короткую строку дополняем слева нулями
    If Len(s1) > Len(s2) Then
    s2 = String(Len(s1) - Len(s2), "0") & s2
    Else
    s1 = String(Len(s2) - Len(s1), "0") & s1
    End If

    ' Складываем
    For i = Len(s1) To 1 Step -1
    Digit1 = CByte(Mid(s1, i, 1))
    Digit2 = CByte(Mid(s2, i, 1))

    Result = ((Carry + Digit1 + Digit2) Mod 10) & Result
    Carry = (Carry + Digit1 + Digit2) \ 10
    Next

    If Carry > 0 Then Result = Carry & Result

    LongAdd = Result

    End Function

    ' Функция выполняет длинное умножение
    Public Function LongMultiply(ByVal s1 As String, ByVal s2 As String) As String

    Dim Result As String, s As String
    Result = "0"

    ' Меняем местами строки, чтобы первая была всегда более длинной
    If Len(s1) < Len(s2) Then
    s = s1
    s1 = s2
    s2 = s
    End If

    ' Более короткую строку дополняем слева нулями
    s2 = String(Len(s1) - Len(s2), "0") & s2

    ' Умножаем
    For i = Len(s2) To 1 Step -1
    Result = LongAdd(Result, LongMultiplyDigit(s1, Mid(s2, i, 1)) & String(Len(s2) - i, "0"))
    Next

    LongMultiply = Result

    End Function

    ' Функция выполняет длинное умножение числа на одноразрядное число
    Public Function LongMultiplyDigit(s1 As String, s2 As String) As String

    ' Это перенос в следующий разряд и текущая цифра
    Dim Carry As Byte, Digit1 As Byte, Digit2 As Byte
    Dim Result As String

    Carry = 0
    Result = ""
    Digit2 = CByte(Left(s2, 1))

    If Digit2 = 0 Then
    LongMultiplyDigit = "0"
    Exit Function
    End If

    For i = Len(s1) To 1 Step -1
    Digit1 = CByte(Mid(s1, i, 1))

    Result = ((Carry + Digit1 * Digit2) Mod 10) & Result
    Carry = (Carry + Digit1 * Digit2) \ 10
    Next

    If Carry > 0 Then Result = Carry & Result
    LongMultiplyDigit = Result

    End Function

    ' Функция выполняет длинное вычитание
    Public Function LongSubstract(ByVal s1 As String, ByVal s2 As String) As String

    ' Это перенос в следующий разряд и текущая цифра
    Dim Carry As Byte, Digit1 As Byte, Digit2 As Byte
    Dim Result As String

    Carry = 0
    Result = ""

    If LongCompare(s1, s2) Then
    For i = Len(s1) To 1 Step -1

    Digit1 = CByte(Mid(s1, i, 1))

    If i - (Len(s1) - Len(s2)) < 1 Then
    Digit2 = 0
    Else
    Digit2 = Mid(s2, i - (Len(s1) - Len(s2)), 1)
    End If

    If Digit1 >= Digit2 + Carry Then
    Result = CStr(Digit1 - Carry - Digit2) & Result
    Carry = 0
    Else
    Result = CStr(10 + Digit1 - Carry - Digit2) & Result
    Carry = 1
    End If
    Next

    LongSubstract = LongTrim(Result)
    Else
    LongSubstract = "0"
    End If

    End Function

    ' Функция выполняет длинное деление
    Public Function LongDivide(ByVal s1 As String, ByVal s2 As String) As String

    ' Это делимое, частное и текущая цифра
    Dim Dividend As String, Residue As String, Quotient As String, Digit As Byte

    ' Отсекаем вариант, когда делитель больше делимого
    If Not LongCompare(s1, s2) Then
    LongDivide = "0"
    Exit Function
    End If

    Dividend = ""
    Residue = s1
    Quotient = ""

    While Len(Residue) > 0

    Dividend = LongTrim(Dividend & Left(Residue, 1))
    Residue = Right(Residue, Len(Residue) - 1)

    If LongCompare(Dividend, s2) Then
    For Digit = 1 To 9
    If Not LongCompare(Dividend, LongMultiplyDigit(s2, CStr(Digit))) Then Exit For
    Next

    Quotient = Quotient & CStr(Digit - 1)
    Dividend = LongSubstract(Dividend, LongMultiplyDigit(s2, CStr(Digit - 1)))
    Else
    Quotient = Quotient & "0"
    End If

    Wend

    LongDivide = LongTrim(Quotient)

    End Function

    ' Подсчет длинного факториала. 0! = 1
    Public Function LongFactor(N As Long) As String

    Dim Fact As String, i As Long

    Fact = "1"
    For i = 2 To N
    Fact = LongMultiply(Fact, CStr(i))
    Next
    LongFactor = Fact

    End Function

    ' Функция выполняет длинное возведение в степень.
    ' Основание всегда длинное (строка), степень - просто целое число
    Public Function LongPower(s As String, p As Long) As String

    Dim Power As String

    Power = s

    For i = 2 To p
    Power = LongMultiply(Power, s)
    Next

    LongPower = Power

    End Function

    ' Функция выполняет длинное сравнение двух строк - чисел
    ' Возвращается TRUE если первая строка больше либо равна второй
    Public Function LongCompare(s1 As String, s2 As String) As Boolean

    If Len(s1) <> Len(s2) Then
    LongCompare = (Len(s1) > Len(s2))
    Else
    For i = 1 To Len(s1)
    If CByte(Mid(s1, i, 1)) <> CByte(Mid(s2, i, 1)) Then
    LongCompare = CByte(Mid(s1, i, 1)) >= CByte(Mid(s2, i, 1))
    Exit Function
    Else
    LongCompare = True
    End If
    Next
    End If

    End Function

    ' Функция удаляет все нули слева от строки-числа
    Function LongTrim(s As String) As String

    Dim TrimString As String
    TrimString = s

    While (Left(TrimString, 1) = "0") And (Len(TrimString) > 1)
    TrimString = Right(TrimString, Len(TrimString) - 1)
    Wend

    LongTrim = TrimString

    End Function

    ' Группировка цифр по три
    Public Function GroupDigits(s As String) As String

    Dim d As String
    d = ""

    While Len(s) > 0
    d = " " & Right(s, 3) & d
    s = Left(s, Len(s) - 3)

    Wend

    GroupDigits = d

    End Function
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 6

      0
      Производительность с библиотечными реализациями сравнивали? Кроме арифметики что-то делать пробовали? Синусы там, корни?
        0
        Нет, не думаю, что что-то выдающееся))
        Другие функции — нет. Тут работа только с натуральными числами.
          +4
          Числа как строки, 10-чная система счисления (а могла бы быть как минимум 10^9-чная), умножение за квадратичную сложность, сама реализация на VBA…
          Поверьте, нет никакой необходимости оценивать производительность этого.
          +1
          Есть же всякие GMP, MPIR, MPFR… там вроде все реализовано (правда на Си, и я до сих пор не пойму чего они все три не объединятся в одну, ну да ладно).
            +8
            Не, ну вы серьёзно умножаете числа по основанию 10 в столбик? Да еще и на вба? Использовать большое основание не пробовали? А ффт для умножения?

            Хабр не торт :-/
              0
              UBASIC by Yuji Kida

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое