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

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

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

Зато можно вызывать функции (или их комбинации) прямо из ячеек экселовского листа – все наглядно и понятно. И да, натуральные числа передаются как строки. Максимальная длина строки в VBA равна примерно 2³¹ = 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