Quote:
> Please excuse the accidental b in numeric.
> I am trying to create an RSA fuction.
> I can only use ASP code no libs (public server)
> Can math be done on string vars?
> Maybe not kilobyte and megabyte. (I may have over estimated but
> one of my smaller numbers will be 4096 bits (bringing me into quadrillions)
> Does this help at all?
My arbitrary-precision arithmetic code can do addition, subtraction, and
multiplication well enough, but only original-Pentium-quality division.
(The multiplication code uses the plain old O(n*m) algorithm, instead
of a potentially faster Fourier-based method, and the division code uses
a half-assed Newton iteration.) There's no modulo yet, either. Do you
need the sign bit, or will you only need large "unsigned" numbers? If
you need to, maybe you can store a sign bit in the leftmost bit of one
of the array elements. Yes, this code is buggy and really intended for
arbitrary-precision floating-point arithmetic, but maybe it'll do:
----cut here----
Option Base 0
Option Compare Binary
Option Explicit: DefObj A-Z
Private Const Base = 1000000000
Public Type Diggler
Mantissa() As Long
Negative As Boolean
End Type
Function Factorial(ByRef N As Variant) As String
Dim DN As Diggler: DN = DiggVal(Format$(N, "0"))
Dim One As Diggler: One = DiggVal("1")
Dim Temp As Diggler: Temp = One
While DiggComp(DN, One) > 0
Temp = DiggMul(Temp, DN)
DN = DiggSub(DN, One)
Wend
Factorial = DiggStr(Temp)
End Function
Function DecFact(ByRef N As Variant) As Variant
Dim DN As Variant: DN = CDec(N)
Dim Temp As Variant: Temp = CDec(1)
While DN > 1
Temp = Temp * DN
DN = DN - 1
Wend
DecFact = Temp
End Function
Public Sub DiggNormalize(ByRef Diggler As Diggler)
Dim LB As Long: LB = LBound(Diggler.Mantissa)
Dim UB As Long: UB = UBound(Diggler.Mantissa)
Debug.Assert LB <= UB
If LB = UB Then
Debug.Assert Diggler.Mantissa(LB) >= 0 And Diggler.Mantissa(LB) < Base
If Diggler.Mantissa(LB) <> 0 Then Exit Sub
' it's zero
Diggler.Negative = False
If LB <> 0 Then ReDim Diggler.Mantissa(0 To 0)
Exit Sub
ElseIf Diggler.Mantissa(LB) <> 0 And Diggler.Mantissa(UB) <> 0 Then
Debug.Assert Diggler.Mantissa(LB) >= 0 And Diggler.Mantissa(LB) < Base
Debug.Assert Diggler.Mantissa(UB) >= 0 And Diggler.Mantissa(UB) < Base
Exit Sub
End If
Dim i As Long
For i = UB To LB Step -1
Debug.Assert Diggler.Mantissa(i) >= 0 And Diggler.Mantissa(i) < Base
If Diggler.Mantissa(i) <> 0 Then Exit For
Next
If i < LB Then
' it's zero
Diggler.Negative = False
ReDim Diggler.Mantissa(0 To 0)
Exit Sub
ElseIf i < UB Then
UB = i
ReDim Preserve Diggler.Mantissa(LB To UB)
End If
End Sub
Public Function DiggAdd(ByRef Term1 As Diggler, ByRef Term2 As Diggler) As Diggler
If (Term1.Negative = False) = (Term2.Negative = False) Then
UAdd DiggAdd, Term1, Term2
DiggAdd.Negative = Term1.Negative
Else
Select Case UComp(Term1, Term2)
Case Is > 0
USub DiggAdd, Term1, Term2
DiggAdd.Negative = Term1.Negative
Case Is < 0
USub DiggAdd, Term2, Term1
DiggAdd.Negative = Term2.Negative
Case Else
ReDim DiggAdd.Mantissa(0 To 0)
End Select
End If
End Function
Public Function DiggSub(ByRef Term1 As Diggler, ByRef Term2 As Diggler) As Diggler
If (Term1.Negative = False) = (Term2.Negative = False) Then
Select Case UComp(Term1, Term2)
Case Is > 0
USub DiggSub, Term1, Term2
DiggSub.Negative = Term1.Negative
Case Is < 0
USub DiggSub, Term2, Term1
DiggSub.Negative = (Term1.Negative = False)
Case Else
ReDim DiggSub.Mantissa(0 To 0)
End Select
Else
UAdd DiggSub, Term1, Term2
DiggSub.Negative = Term1.Negative
End If
End Function
Public Function DiggComp(ByRef Number1 As Diggler, ByRef Number2 As Diggler) As Integer
If Number1.Negative Then
If Number2.Negative Then
DiggComp = UComp(Number2, Number1)
Else
DiggComp = -1
End If
Else
If Number2.Negative Then
DiggComp = 1
Else
DiggComp = UComp(Number1, Number2)
End If
End If
End Function
Private Function UComp(ByRef Term1 As Diggler, ByRef Term2 As Diggler) As Integer
Dim LB1 As Long: LB1 = LBound(Term1.Mantissa)
Dim UB1 As Long: UB1 = UBound(Term1.Mantissa)
Dim LB2 As Long: LB2 = LBound(Term2.Mantissa)
Dim UB2 As Long: UB2 = UBound(Term2.Mantissa)
While UB1 > LB1 And Term1.Mantissa(UB1) = 0: UB1 = UB1 - 1: Wend
While LB1 < UB1 And Term1.Mantissa(LB1) = 0: LB1 = LB1 + 1: Wend
While UB2 > LB2 And Term2.Mantissa(UB2) = 0: UB2 = UB2 - 1: Wend
While LB2 < UB2 And Term2.Mantissa(LB2) = 0: LB2 = LB2 + 1: Wend
Dim i As Long, j As Long, k As Long
For i = Max(UB1, UB2) To Min(LB1, LB2) Step -1
If LB1 <= i And i <= UB1 Then j = Term1.Mantissa(i) Else j = 0
If LB2 <= i And i <= UB2 Then k = Term2.Mantissa(i) Else k = 0
If j < k Then UComp = -1: Exit Function
If j > k Then UComp = 1: Exit Function
Next
End Function
Private Function Min(ByVal X As Long, ByVal Y As Long) As Long
If X < Y Then Min = X Else Min = Y
End Function
Private Function Max(ByVal X As Long, ByVal Y As Long) As Long
If X > Y Then Max = X Else Max = Y
End Function
Private Sub UAdd(ByRef Result As Diggler, ByRef Term1 As Diggler, ByRef Term2 As Diggler)
Dim LB1 As Long: LB1 = LBound(Term1.Mantissa)
Dim UB1 As Long: UB1 = UBound(Term1.Mantissa)
Dim LB2 As Long: LB2 = LBound(Term2.Mantissa)
Dim UB2 As Long: UB2 = UBound(Term2.Mantissa)
While LB1 < UB1 And Term1.Mantissa(LB1) = 0: LB1 = LB1 + 1: Wend
While UB1 > LB1 And Term1.Mantissa(UB1) = 0: UB1 = UB1 - 1: Wend
While LB2 < UB2 And Term2.Mantissa(LB2) = 0: LB2 = LB2 + 1: Wend
While UB2 > LB2 And Term2.Mantissa(UB2) = 0: UB2 = UB2 - 1: Wend
Dim LBR As Long, UBR As Long
LBR = Min(LB1, LB2)
UBR = Max(UB1, UB2)
Debug.Assert LBR <= UBR
ReDim Result.Mantissa(LBR To UBR + 1)
Dim i As Long, Carry As Long
For i = LBR To UBR + 1
If LB1 <= i And i <= UB1 Then Carry = Carry + Term1.Mantissa(i)
If LB2 <= i And i <= UB2 Then Carry = Carry + Term2.Mantissa(i)
If Carry >= Base Then
Result.Mantissa(i) = Carry - Base
Carry = 1
ElseIf Carry > 0 Then
Result.Mantissa(i) = Carry
Carry = 0
End If
Debug.Assert Result.Mantissa(i) >= 0 And Result.Mantissa(i) < Base
Next
Debug.Assert Carry = 0
End Sub
Private Sub USub(ByRef Result As Diggler, ByRef Upper As Diggler, ByRef Lower As Diggler)
Dim LBU As Long: LBU = LBound(Upper.Mantissa)
Dim UBU As Long: UBU = UBound(Upper.Mantissa)
Dim LBL As Long: LBL = LBound(Lower.Mantissa)
Dim UBL As Long: UBL = UBound(Lower.Mantissa)
While LBU < UBU And Upper.Mantissa(LBU) = 0: LBU = LBU + 1: Wend
While UBU > LBU And Upper.Mantissa(UBU) = 0: UBU = UBU - 1: Wend
While LBL < UBL And Lower.Mantissa(LBL) = 0: LBL = LBL + 1: Wend
While UBL > LBL And Lower.Mantissa(UBL) = 0: UBL = UBL - 1: Wend
Dim LBR As Long, UBR As Long
LBR = Min(LBU, LBL)
UBR = Max(UBU, UBL)
Debug.Assert LBR <= UBR
ReDim Result.Mantissa(LBR To UBR)
Dim i As Long, Carry As Long
For i = LBR To UBR
If LBU <= i And i <= UBU Then Carry = Carry + Upper.Mantissa(i)
If LBL <= i And i <= UBL Then Carry = Carry - Lower.Mantissa(i)
If Carry < 0 Then
Result.Mantissa(i) = Carry + Base
Carry = -1
ElseIf Carry > 0 Then
Result.Mantissa(i) = Carry
Carry = 0
End If
Debug.Assert Result.Mantissa(i) >= 0 And Result.Mantissa(i) < Base
Next
Debug.Assert Carry = 0
End Sub
Public Function DiggMul(ByRef Multiplier As Diggler, ByRef Multiplicand As Diggler) As Diggler
Dim LB1 As Long: LB1 = LBound(Multiplier.Mantissa)
Dim UB1 As Long: UB1 = UBound(Multiplier.Mantissa)
Dim LB2 As Long: LB2 = LBound(Multiplicand.Mantissa)
Dim UB2 As Long: UB2 = UBound(Multiplicand.Mantissa)
While UB1 > LB1 And Multiplier.Mantissa(UB1) = 0: UB1 = UB1 - 1: Wend
While LB1 < UB1 And Multiplier.Mantissa(LB1) = 0: LB1 = LB1 + 1: Wend
While UB2 > LB2 And Multiplicand.Mantissa(UB2) = 0: UB2 = UB2 - 1: Wend
While LB2 < UB2 And Multiplicand.Mantissa(LB2) = 0: LB2 = LB2 + 1: Wend
Dim LBR As Long: LBR = LB1 + LB2
Dim UBR As Long: UBR = UB1 + UB2 + 2
Debug.Assert LBR <= UBR
ReDim DiggMul.Mantissa(LBR To UBR)
Dim i As Long, j As Long
For i = LB1 To UB1
For j = LB2 To UB2
Dim A As Long, B As Long, C As Long, D As Long, E As Long, F As Long
A = Multiplier.Mantissa(i) \ 1000000
B = (Multiplier.Mantissa(i) \ 1000) Mod 1000
C = Multiplier.Mantissa(i) Mod 1000
D = Multiplicand.Mantissa(j) \ 1000000
E = (Multiplicand.Mantissa(j) \ 1000) Mod 1000
F = Multiplicand.Mantissa(j) Mod 1000
Dim R0 As Long, R1 As Long
R1 = A * D * 1000 + A * E + B * D
R0 = A * F + B * E + C * D
R1 = R1 + R0 \ 1000
R0 = (R0 Mod 1000) * 1000 + B * F + C * E
R1 = R1 + R0 \ 1000000
R0 = (R0 Mod 1000000) * 1000 + C * F
Debug.Assert R1 < Base
Debug.Assert R0 < 2 * Base
DiggMul.Mantissa(i + j + 2) = DiggMul.Mantissa(i + j + 2) + (DiggMul.Mantissa(i + j + 1) + R1) \ Base
DiggMul.Mantissa(i + j + 1) = (DiggMul.Mantissa(i + j + 1) + R1) Mod Base + (DiggMul.Mantissa(i + j) + R0) \ Base
DiggMul.Mantissa(i + j) = (DiggMul.Mantissa(i + j) + R0) Mod Base
' Dim T0 As Variant
' T0 = CDec(Multiplier.Mantissa(i)) * CDec(Multiplicand.Mantissa(j)) _
' + CDec(DiggMul.Mantissa(i + j + 1)) * Base + CDec(DiggMul.Mantissa(i + j))
' DiggMul.Mantissa(i + j) = T0 - Int(T0 / Base) * Base
' T0 = Int(T0 / Base)
' DiggMul.Mantissa(i + j + 1) = T0 - Int(T0 / Base) * Base
' DiggMul.Mantissa(i + j + 2) = DiggMul.Mantissa(i + j + 2) + Int(T0 / Base)
Next
Next
For i = LBR To UBR - 1
'If DiggMul.Mantissa(i) >= Base Then
...