Extension Math Functions

[rifter1818]

Edited For Clarity

What i would like to do is find a way to extend math for very large numbers, (much larger than int64.maxvalue) in fact up to millions of digits long (idealy) The two methods for storing these large numbers im thinking of are 1) as a string and 2) as an array of int64's ex say i(0) = 1 and i(1) = 11 then i = 11 000 000 001 or something like that. Which method would you advise?

 

The second Part of the question is how to run the math functions for these large numbers, the Methods i need are addition, Subtraction, Multiplication, Devision (and mod (not sure what the real name for this is)), and square roots.

Edited April 26, 2004 by rifter1818

[rifter1818]

After Looking it over ive decided to use Strings to hold the numbers. Addition and subtraction are easy enough for large numbers but how about multiplecation and devision, mod Only has to be boolean(Has or doesn't have a remainder)..

[Arch4ngel]

Does you number have to go negative ?

If not... you could take an Unsigned Integer of 64 bits.

 

What do you think ?

[rifter1818]

Number is not negative

 

However you cant use Uints as they have upper limits (strings have upper limites but its roughly 10 ^ 2 000 000 000 so that is sufficiantly large not to mention if you use a larger base (i think 122 is stable with strings) 122 ^ 2 000 000 000)) So far i have almost finished algorythyms for all the needed functions when im done ill post them here in hopes that others can use them / give me hints on optimizing them.

[rifter1818]

Current Math Functions, Note that the Square root is acurate to only +- 1 (which may be accurate enough for my needs but not for others. Decimals are not supported (again not needed for me).

   Public Function Add(ByVal Left As String, ByVal Right As String) As String
       Dim i As Integer
       Dim C, T As Byte
       Dim out As String = ""
       FillLength(Left, Right)
       For i = 0 To Left.Length - 1
           T = (CByte(Mid(Left, Left.Length - i, 1)) + CByte(Mid(Right, Right.Length - i, 1)) + C) Mod 10
           C = (CByte(Mid(Left, Left.Length - i, 1)) + CByte(Mid(Right, Right.Length - i, 1)) + C) \ 10
           out = T & out
       Next
       Return Fix(CStr(C) & out)
   End Function
   Public Function Subtract(ByVal Left As String, ByVal Right As String) As String
       Dim i As Integer
       Dim Out As String
       Dim C, T As Int16
       FillLength(Left, Right)
       For i = 0 To Left.Length - 1
           T = (CInt(Mid(Left, Left.Length - i, 1)) - CInt(Mid(Right, Right.Length - i, 1))) + C
           If T < 0 Then
               T += 10
               C = -1
           Else
               C = 0
           End If
           Out = T & Out
       Next
       Return Fix(Out)
   End Function
   Public Function Multiply(ByVal Left As String, ByVal Right As String) As String
       Dim I, TD As Integer
       Dim out, T As String
       out = "0"
       For I = 1 To Right.Length
           T = Left
           For TD = 1 To Right.Length - I
               T = T & "0"
           Next
           For TD = 1 To Mid(Right, I, 1)
               out = Add(out, T)
           Next
       Next
       Return Fix(out)
   End Function
   Public Function Fix(ByVal Number As String) As String
       Do Until Mid(Number, 1, 1) <> "0" Or Number.Length = 1
           Number = Mid(Number, 2)
       Loop
       Return Number
   End Function
   Public Function GT(ByVal Left As String, ByVal Right As String) As Boolean
       If Right.Length = Left.Length Then
           Dim i As Integer
           For i = 1 To Left.Length
               If Not CByte(Mid(Left, i, 1)) = CByte(Mid(Right, i, 1)) Then Return (CByte(Mid(Left, i, 1)) > CByte(Mid(Right, i, 1)))
           Next
       Else
           Return (Right.Length < Left.Length)
       End If
   End Function
   Public Function Divide(ByVal Left As String, ByVal Right As String) As String
       If Left = Right Then Return "1"
       If Not GT(Left, Right) Then Return ("R" & Left)
       Dim T, D, Out As String
       Dim ND, I As Integer
       T = Left
       Out = "0"
       Do Until GT(Right, T)
           If GT(Mid(T, 1, Right.Length), Right) Then
               Do Until Not GT(Mid(T, 1, Right.Length), Right)
                   T = Subtract(Mid(T, 1, Right.Length), Right) & Mid(T, Right.Length + 1)
                   ND = T.Length - Right.Length
                   D = 1
                   For I = 1 To ND
                       D = D & "0"
                   Next
                   Out = Add(Out, D)
               Loop
           Else
               Do Until GT(Mid(T, 1, Right.Length), Right) Or GT(Right, T)
                   ND = T.Length - Right.Length - 1
                   T = Subtract(Mid(T, 1, Right.Length + 1), Right) & Mid(T, Right.Length + 2)
                   D = 1
                   For I = 1 To ND
                       D = D & "0"
                   Next
                   Out = Add(Out, D)
               Loop
           End If
       Loop
       If T > 0 Then Out = Out & "R" & T
       Return Fix(Out)
   End Function
   Public Function Modulus(ByVal Left As String, ByVal Right As String) As String
       Dim t As String = Divide(Left, Right)
       Dim i As Integer
       For i = 1 To t.Length
           If Mid(t, i, 1) = "R" Then
               Return Mid(t, i + 1)
           End If
       Next
       Return "0"
   End Function
   Public Function Sqrroot(ByVal Number As String) As String
       Dim N1, N2 As String
       Dim i As Int16
       N2 = CInt(Math.Ceiling((CInt(Mid(Number, 1, 1)) / 2)))
       For i = 1 To Math.Ceiling(Number.Length / 2)
           N2 = N2 & "0"
       Next
       Do Until N2 = N1
           N1 = N2
           N2 = RR(Divide(Add(RR(Divide(Number, N1)), N1), "2"))
       Loop
       Return N2
   End Function
   Public Function RR(ByVal number As String) As String
       Dim i As Int16
       i = InStr(number, "R")
       If i = 0 Then Return number
       Return Mid(number, 1, i - 1)
   End Function
   Public Sub FillLength(ByRef Left As String, ByRef Right As String)
       Dim i As Integer
       If Left.Length > Right.Length Then
           For i = Right.Length To Left.Length - 1
               Right = "0" & Right
           Next
       ElseIf Right.Length > Left.Length Then
           For i = Left.Length To Right.Length - 1
               Left = "0" & Left
           Next
       End If
   End Sub

I hope this helps someone or if someone has a faster way of doing any of this thatd be nice.

[rifter1818]

Hmmm

 

The Square root function isnt working so i may need some help there other than that it seems to work fine.. Edit: Devision Failed testing too...

Edited April 27, 2004 by rifter1818

[Nerseus]

You could spend time on your own routines or search for some existing library.

 

This article from MS shows a sample "complex math" library - look for "Figure 3". It's in C#, but I'm sure you could convert it to VB.NET fairly easily.

 

If you want to fix up your library, you may consider adding some error handling. You don't currently check for empty strings, non-digits, etc. If you're sure you'll always have "clean" data going in, this may be an unnecessary step...

 

I'd suggest throwing some unit tests at your code as well, to test out all the functions.

 

-Nerseus