Long Numbers
Hi,
I would like to write applications, such as calculating pi, generating Mandelbrot Sets, factoring large numbers or prime hunts, which use extremely long numbers. I'm not talking about the measly 32 decimal places of the Decimal variable. I'm talking about two or three thousand decimal places.
I've written a couple long number calculators which are, quite frankly, crude, cumbersome and slow. My approach has been to create arrays of byte characters, assign one digit to each byte, and then try to program the whole thing to handle addition, subtraction, multiplication and division; all the while trying to keep track of decimal places and polarities.
It seems to me that there has to be a better way. Anyone know if it is possible to define extremely large numbers in Visual Basic such that the machine level natural math functions can handle the grunt work of crunching these numbers and in so doing reduce the run time of my project to something within my lifetime?
Thanks,
-Science_1
Hi there,
It doesn't look like this will do it for you and I believe you will have to use "string aritmetic" package of know as the Bignum datatype.
I found a reference on the net at source forge but I couldnt ascertain if that was for dot net or not.
On this is true, it gives a clear idea of the types of routine that are required.
I just looked at the Decimal datatype and it has precision out to about 28 places.
Decimal | Decimal | 16 bytes | 0 through +/-79,228,162,514,264,337,593,543,950,335 (+/-7.9...E+28) ? with no decimal point; 0 through +/-7.9228162514264337593543950335 with 28 places to the right of the decimal; smallest nonzero number is +/-0.0000000000000000000000000001 (+/-1E-28) ?
|
It doesn't look like this will do it for you and I believe you will have to use "string aritmetic" package of know as the Bignum datatype.
I found a reference on the net at source forge but I couldnt ascertain if that was for dot net or not.
On this is true, it gives a clear idea of the types of routine that are required.
Bignum was first developed on the VAX something I'm proud of because I'm a former Vax Engineer.
but check out the next for dot net, string arithmetic and Bignum. Also this sounds like a fascinating problem. With stringbuilder and the proper
routines, you could calculate forever. :)
Actually, according to Wiki, bignum (formerly called arbitrary precision arithmetic) came before VAX/VMS on MacLisp (not related to Apple Computer.) This was the late 60's. The VAX didn't come around until the mid 70's.
Birian
Sorry, forgot to add:
Here's an earlier thread that I've addressed on this: http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=389037&SiteId=1
I cannot find a .NET port of GMP... yet anyway. But GMP.DLL does exist (build it yourself?). Once you get that far, you can consider using one of the two .NET interop techniques of calling C DLL's: through DllImport (P/Invoke), or by creating a C++/CLI class layer.
Ok, thanks guys.
I was considering tackling C++ eventually, and now it seems I have a reason to do so.
Till then I may try my hand at a VB long number calculator again, this time using a combination of bit-shift and addition to cut the calculation times.
If you haven't tried your hand at a large number calculator, I recommend it. It's a fun project even if you don't get past addition and subtraction. = )
-Science_1
The forums are acting a bit crickity today--had to keep replying to old messages rather than update with edits. Anyway, I'll stop my googling with this: http://www.codeproject.com/csharp/BigInteger.asp?df=100&forumid=4524&exp=0&fr=26
There could be others, but this probably will serve your needs. It's written in C#, but that should not be a problem if this project is a class library. GMP, however, will probably perform better since it's been around longer and has a following. So you have two avenues to think about.
Brian
Yeah, doing it by hand is fun (but tedious and error prone.) I remember doing a string-based 256-digit calculator when I was a kid, in BASIC on an Apple II. I think 256 was the largest string I could declare...
If you haven't tried your hand at a large number calculator, I recommend it. It's a fun project even if you don't get past addition and subtraction. = )
I've got some bugs I'm working on or this would sound fun. Maybe later tonight?
Whew ! I mentioned that this was always something that interested me. So tonight I did "Add". I'm amazed at what it takes for a machine to read two numbers!
But I'm fairly proud of this. All string arithmetic, by it's very nature runs at the speed of smell. But the interesting thing about string arithmetic is that it will run and character/number crunch for as much memory and machine as you have.
One of the things that fascinated me is that Unix machines used to have a replaceable null (in case they ever did something) and they used to write a null job that would calculate pi forever. That would probably burn a pentium up.
This is optimized for LARGE numbers not small ones. It takes in strings and converts the string to byte arrays. After doing that the order of the bytes are backwards and you have to take uneven length arrays into account.
The larger array is by definition justified and to be able to do aritmetic. Although in retrospect, I see that I didn't need to redimensioned that smaller array :o and then left justified it :o. Looking back I realize there is no reason to do that at all.
There are practical reason why you should not do that. It wastes memory and cycles.
But anyway here is ADD V1.0. I think I'm going to do those optimizations. One thing about this is that string arithmetic JUST does not care about how long numbers are. It really has no concept of that at all. It was a really strange feeling when I could just say "999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"
and it makes no difference.
Public
Class Form1
Protected M As New StringMath
Private Sub Form1_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load
Dim n As String = M.Add("1", "99999999999999999999999999999999999999999999999999999999999999999999")
End Sub
End Class
Imports System.Text
Public Class StringMath
' 3 negative 2 zero 1 overflow 0 carry ...
Public Structure Result
Public Index As Integer
Public Destination As Byte()
Public In1 As String
Public In2 As String
End Structure
Public Structure OP
Public Neg As Boolean
Public Carry As Boolean
Public Zero As Boolean
Public Result As Char
End Structure
Protected R As Result
Protected convert As System.Text.Encoding = System.Text.Encoding.ASCII
Public Sub New()
End Sub
Public Function Add(ByRef In1 As String, ByRef in2 As String) As String
Dim Samelength As Boolean = True ' strings are the same length
Dim OneIsLarger As Boolean ' In1 is longer
Dim i As Integer
Dim In1b() As Byte = convert.GetBytes(In1) ' Convert string to bytes
Dim In2b() As Byte = convert.GetBytes(in2)
Dim Mathlength As Integer
Dim MAXLen As Integer '
'Bytes are now reversed in memory in ascii
'If an input string looked like "1234" - the one is in buffer(0)
' Probably the arrays are of different length
'Strip the ascii converting into arrays of byte integers
For i = 0 To In1b.Length - 1 : In1b(i) -= &H30 : Next
For i = 0 To In2b.Length - 1 : In2b(i) -= &H30 : Next
'check for differences in length and collect data setting up
If In1b.Length > In2b.Length Then
Mathlength = In2b.Length - 1
ReDim Preserve In2b(In1b.Length - 1)
Samelength = False
OneIsLarger = True
MAXLen = In1b.Length - 1
End If
If In2b.Length > In1b.Length Then
Mathlength = In1b.Length - 1
ReDim Preserve In1b(In2b.Length - 1)
Samelength = False
OneIsLarger = False
MAXLen = In2b.Length - 1
End If
' now the two arrays are the same length
' move the smallest value to the highest byte, etc. this is like a "shift" of the smaller array
If Not Samelength Then
Dim ptr As Integer = MAXLen
If OneIsLarger Then
For i = Mathlength To 0 Step -1
In2b(ptr) = In2b(i)
In2b(i) = 0
ptr -= 1
Next
'zero leading (lowest bytes) after shifting
For i = 0 To MAXLen - (Mathlength + 1) : In2b(i) = 0 : Next
Else
MAXLen = In2b.Length - 1
For i = Mathlength To 0 Step -1
In1b(ptr) = In1b(i)
In1b(i) = 0
ptr -= 1
Next
For i = 0 To MAXLen - (Mathlength + 1) : In1b(i) = 0 : Next
End If
Else
MAXLen = In2b.Length - 1
End If
'Now the arrays are the same length and have the same starting pointing
'They are "left - justified" We are ready to do actual arithmetic
Dim Out(MAXLen + 1) As Byte
Dim carryval As Boolean = False
Dim ii As Integer
For i = MAXLen To (Mathlength + 1) Step -1
ii = i + 1
If carryval Then In2b(i) += 1
Out(ii) = In1b(i) + In2b(i)
If Out(ii) > 9 Then
Out(ii) -= 10
carryval = True
Else
carryval = False
End If
Next
'So much for the actual arithmetic - if arrays are unequal only do Arith up where they are the same length
'After that deallocate the smaller array and transfer that larger array directly into the output array
' being mindful of any arithmetic carries
If Samelength Then
If carryval Then Out(0) = 1
Else
If OneIsLarger Then
In2b = Nothing
For i = Mathlength To 0 Step -1
ii = i + 1
If carryval Then In1b(i) += 1
Out(ii) = In1b(i)
If Out(ii) > 9 Then
Out(ii) -= 10
carryval = True
Else
carryval = False
End If
Next
Else ' two is larger
In1b = Nothing
For i = Mathlength To 0 Step -1
ii = i + 1
If carryval Then In2b(i) += 1
Out(ii) = In2b(i)
If Out(ii) > 9 Then
Out(ii) -= 10
carryval = True
Else
carryval = False
End If
Next
End If
End If
If carryval Then Out(0) = 1 'if there is a final carry do it
For i = 0 To Out.Length - 1 : Out(i) += &H30 : Next ' Restore the Ascii
For i = 0 To Out.Length - 1 : If Out(i) <> &H30 Then : Exit For : End If : Next ' i -> first nonzero
Return convert.GetString(Out, i, Out.Length - 1)
End Function
Private Function IsByteCarry(ByVal b1 As Byte, ByVal b2 As Byte) As Boolean
If b1 + b2 > 10 Then Return True
End Function
End Class
This could be improved in lots of ways.
The J# java.math.BigInteger and java.math.BigDecimal routines may be what you need.
If you add a reference to vjslib.dll you'll be able to access these routines.
Great. Now you have four options: 1. Port GMP to .NET. 2. Use the codeproject solution. 3. Use java.math. 4. Use Renee's solution.
That's a good start Reneec. You've been bitten by the bug too, haven't you?
I told you it was fun. = )
Nathan,
That seems like a perfect solution to my problem. Can you give me a snippet of sample code, as compact as possible, which will call that library and, say, divide two long numbers? I'm fairly new to Visual Basic. Most of my programing experience was in basic and assembly on the old Amega 3000, with a smiggin of Cobal before I gave it up as hopelessly archaic.
A Thank You to everyone for your ideas!
-Science_1
You are in a waste, no String, BitArray, the + and - operator ar logic functions, and * is done based in the china multiplication, the same is for divide, yes in VB, I have an long Integral prototype, and I use Fractions for Racionals, I've worked for solving a Eq System of 15 x 15 Gauss-Jordan with this numbers in less than three(3) seconds...
For two number A and B for each Bit, C is CarryOut, D is CarryIn (the previus CarryOut) and R is Result:
+:
R = A Xor B Xor D
C = (A Xor D) Xor (B Xor D)
?More?
"4. Use Renee's solution."
Mine is hardly a project or a solution, it's a leaning experience.
And yes, I've been bitten by the bug. I indexed J# today and the bigint dataype was there althought all of the description boxes had no content and docuentation of those datatypes were less than sparse.
I'm waiting for a replacement motherboard so I'm only on a 2 ghz pentium and I noticed about a once second and maybe more to do that addition. However every digit had a carry operation and they slow you way down.
This is a set of skills in itself. I mentioned that there were better ways to do this and that was in the setup which occurs once.
There were interesting challenges, for example since the bytes are in reverse order, I started to reverse them as we think of them. But then when I thought it over, I realized that I could actually used that to my advantage because if nothing else, it meant that registration was correct. So I did the aritmetic backwards.
Subrtraction will be harder and Divison? That would be a challenge. But all in all it was fun. I think I'm going to do some cleanup tonight in the way it sets up. But that's not going to be noticeable compared to the actual computation.
Brian,
Are you still looking for a vb.net solution for arbitrary precision math?
I have been working on a module for the same thing for the last few months.
I have +, -, *, /, !, ^, pi, e, sin, cos, tan, etc. and several other functions working.
It can add to 10,000,000 digit floating point numbers in about 3 seconds, 10000! in about 1.2 seconds, calculate e to 10,000 places in .7 seconds, etc. on a P4 3.4
Let me know if you are interested and I will post the code here.
