1. Computing

Large Number Calculations

By December 15, 2007

Follow me on:

It's not as easy as you might think!

The Visual Basic 2005 Cookbook ... which is a consistent source of interesting stuff ... has a program that will calculate Pi to an arbitrary precision. The downloadable source calculates it to 500 digits. I verified the answer on the web. In checking out the code, I discovered that the multiplication subroutine, at least, fell quite a bit short of the task of multiplying two arbitrarily large numbers.

The problem is that no datatype in VB can contain an arbitrarily large number. The reigning champion is the new .NET Decimal data type that can hold an integer as large as 79,228,162,514,264,337,593,543,950,335. The Cookbook uses an approach that places one number to be multiplied in an array of integers and the other in an integer variable. The array can be (almost) arbitrarily large, but the other is still limited by Visual Basic datatypes. (In the Cookbook program, the calculation of Pi never requires the second number to get bigger than four digits.)

Not that this is a very frequent problem. Wikipedia points out that calculating Pi to extreme precision only has value as an abstract mathematical problem. "A value (of Pi) truncated to 39 decimal places is sufficient to compute the circumference of any circle that fits in the visible universe to a precision comparable to the size of a hydrogen atom."

I'd say that's good enough for government work.

I set out to write a subroutine that would ... and fell a bit short of the task myself. I shouldn't feel so bad. Even the Greek mathematician Archimedes worked on multiplying large numbers and didn't solve the problem completely.

By reversing the array (counting up instead of counting down) and calculating the maximum number of digits to use as the loop limits, I was able to calculate a number about five digits larger than the maximum that Decimal would allow. Here's the code based on the method of the Cookbook:

Dim NumberDigits As Short
Dim Multiplier As Decimal
Dim Multiplicand(500) As Short
Dim Carry As Decimal
Dim Position As Short
Dim HoldDigit As Decimal
Dim I As Short = 0
Multiplier = CDec(TextMultiplier.Text)
NumberDigits = TextMultiplicand.Text.Length - 1
For I = NumberDigits To 0 Step -1
    Multiplicand(I) = _
	CInt(TextMultiplicand.Text.Substring(NumberDigits - I, 1))
Next
Carry = 0
For Position = 0 To (2 * NumberDigits - 1)
    HoldDigit = (Multiplicand(Position) * Multiplier) + Carry
    Carry = HoldDigit \ 10
    Multiplicand(Position) = HoldDigit Mod 10
Next
Dim TextProductString As New System.Text.StringBuilder
I = 0
For I = (2 * NumberDigits - 1) To 0 Step -1
    TextProductString.Append(Multiplicand(I).ToString)
Next
TextProduct.Text = TextProductString.ToString.TrimStart("0"c)

Pseudocode for a general method can be found at Wikipedia as well. (Converting this into a general program will be left as an exercise for the student.)

'Arrays representing the binary representations
'multiply(a[0..n-1], b[0..n-1]) 
'x ? 0
'for i from 0 to 2n-1
'for j from 0 to i
'k ? i - j
'x ? x + (a[j]  b[k])
'result[i] ? x mod 2
'x ? floor(x/2)

If you run into a requirement like this in real life, one solution is to use the BigInteger function from the Microsoft Visual J# library. Just add a reference to vjslib in your project. The ability of any .NET language to use compiled DLL's from any other comes to the rescue!

Comments
January 2, 2008 at 2:04 pm
(1) PZI says:

Oh, I agree, I agree … but FWIW, in the heyday of UNIVAC I (say 50 years ago) there was a nice little software package that not only did arithmetic to about 100 decimal digits precision, but also kept track of the accuracy as it worked, so that it was possible to see just how useful (or not!) the result was.

March 21, 2009 at 12:55 pm
(2) Paddy says:

This code will do what you want. Arbitrary precision unsigned integer multiply. No practical limit to argument sizes (2b digits). Will multiple two 32,000 digit number in under one second on 2.66 GHz Intel.

Public Function UIntMultiply(ByVal x As String, ByVal y As String) As String

Dim Base As Int32 = 9
Dim Limit As Int64 = 10 ^ 9

x = x.PadLeft(x.Length + (Base – (x.Length Mod Base)), “0″)
y = y.PadLeft(y.Length + (Base – (y.Length Mod Base)), “0″)

Dim a() As Int64 = toArray(x, Base)
Dim b() As Int64 = toArray(y, Base)
Dim Carry As Int64

Dim z(a.Length + b.Length) As Int64

For yCount As Int32 = 0 To b.Length – 1
For xCount As Int32 = 0 To a.Length – 1
Carry = z(xCount + yCount)
z(xCount + yCount) = (a(xCount) * b(yCount)) + Carry
Next
For Count As Int32 = 0 To z.Length – 1
If z(Count) >= Limit Then
Carry = Int(z(Count) \ Limit)
z(Count) -= Limit * Carry
z(Count + 1) += Carry
End If
Next
Next

Dim Result As String = BuildOutPut(z, Base).TrimStart(“0″)
Console.Write(Result)
Return Result

End Function
Private Function toArray(ByVal x As String, ByVal BaseSize As Int32) As Array

Dim j = -1, a((x.Length \ BaseSize) – 1) As Int64
For i As Int32 = x.Length – BaseSize To 0 Step -BaseSize
j += 1
a(j) = CLng(x.Substring(i, BaseSize))
Next

Return a

End Function
Private Function BuildOutPut(ByVal x As Array, ByVal BaseSize As Int32) As String

Dim Result As New System.Text.StringBuilder
Dim temp As String
Dim count As Int32 = 0
For i As Int32 = x.Length – 2 To 0 Step -1
temp = x(i).ToString.PadLeft(BaseSize, “0″)
Result.Append(temp)
Next

Return Result.ToString

End Function

June 27, 2010 at 1:22 pm
(3) Stephan says:

You may also want to try out MegaMath library. Found this on sourceforge today: http://sourceforge.net/projects/megamath/

June 27, 2010 at 8:46 pm
(4) Dan Mabbutt says:

Thanks!

I wrote this a while ago and progress happens. I appreciate the update.

July 7, 2010 at 11:40 pm
(5) mike says:

I have created a string based math program for .Net called MegaMath. I used it to multiply two 30,000 digit numbers (took a few minutes). Output is string…

Can do multiply, add, subtract, divide.

Check it out at: http://sourceforge.net/projects/megamath/files/

August 16, 2010 at 3:36 pm
(6) DavidL says:

This code fails if you multiply 4294967296 * 4294967296

September 8, 2011 at 5:30 am
(7) lara says:

thanks for your code paddy,
i have been trying to adapt it for addition, but over 9 digits my code fails… (a carry problem i think)
could someone help me please?

September 8, 2011 at 12:38 pm
(8) visualbasic says:

Well, Lara, since Paddy responded over two years ago, I doubt that he is going to be monitoring this particular article a lot right now.

But I am!!

I checked Paddy’s code one more time just to make sure it works for multiplication. (It does.)

Post your code and we can work on it.

September 8, 2011 at 7:51 pm
(9) lara says:

thanks,

I have changed few sings and it seems to work, but is very low to execute…

Could you help me to make it run faster?

here is the function that addition two numbers as string, my goal is to loop increment by one a large number. I didn’t figure how to “x.length” on integers and turned them in string then back to integers, but… check it out:

Public Function Uintadd(ByVal x As String, ByVal y As String) As String
Dim Base As Integer = 9
Dim z As UInteger = IIf(x.Length > y.Length, _
x.Length, y.Length)
z = z + (Base – (z Mod Base))
x = x.PadLeft(z + (x.Length – (x.Length Mod z)), “0″)
y = y.PadLeft(z + (y.Length – (y.Length Mod z)), “0″)
Dim Compte As UInteger = (z / Base)
Dim nb_X As UInteger, nb_Y As UInteger, nb_Sum _
As String
Dim Rslt As Integer, Carry As Integer = 0
Dim Rslt_string As String = “”
For i As Integer = (Compte – 1) To 0 Step -1
nb_X = CUInt(Mid(x, (i * Base) + 1, Base))
nb_Y = CUInt(Mid(y, (i * Base) + 1, Base))
nb_Sum = CStr(nb_X + nb_Y)
If nb_Sum.Length > Base Then
Rslt = CInt(Right(nb_Sum, Base)) + Carry
Carry = CInt(Left(nb_Sum, Len(nb_Sum) – Base))
Else
Rslt = CInt(nb_Sum) + Carry
Carry = 0
End If
Rslt_string = CStr(Rslt).PadLeft(Base – Len(Rslt)) _
& Rslt_string
Next
Rslt_string = (CStr(Carry) & Rslt_string).TrimStart(“0″)
Return Rslt_string
End Function

I am working on blocks of 9 digits, would it be faster to work on biger bloks, or mabe on bit to bit?

September 8, 2011 at 10:05 pm
(10) visualbasic says:

Congratulations for working out the code!

Slow?

I slapped a stopwatch into the code and with numbers in the hundreds of digits, it would barely register 1 or 2 milliseconds on my machine. I had to get up to adding numbers with 10,000 digits to start getting times over 10 milliseconds.

In any case, I did a few experiments. Your use of the UInteger data type is probably a good idea. But changing the blocksize to 18 and using the Long data type where appropriate did seem to improve performance a bit.

September 9, 2011 at 4:11 am
(11) lara says:

i have to iterate the loop a 10^600 times… any suggestions?

September 9, 2011 at 4:36 am
(12) lara says:

Hi VisualBasic,

Is the stopwatch part of visual studio or a part of code you had somewhere, could you share it with me?

I would really need it, for the next steps of my program…

thanks a lot

September 9, 2011 at 10:17 am
(13) visualbasic says:

Yes, StopWatch is included in .NET. Here’s the calling code:

Private Sub btnAdd_Click(
ByVal sender As System.Object,
ByVal e As System.EventArgs
) Handles btnAdd.Click
Dim theSW As New Stopwatch
theSW.Start()
lblAnswer.Text =
UIntAdd(txtNum1.Text, txtNum2.Text)
theSW.Stop()
Console.WriteLine(theSW.ElapsedMilliseconds)
End Sub

September 9, 2011 at 10:17 am
(14) visualbasic says:

Although it’s inconsistent (because other processes on my machine were running) I think I got my best performance using larger blocks and Long data types:

Public Function UIntAdd(
ByVal x As String, ByVal y As String
) As String
Dim Base As UInteger = 18
Console.WriteLine(x.Length)
Console.WriteLine(y.Length)
Dim z As UInteger = IIf(x.Length > y.Length,
x.Length, y.Length)
Dim one As UInteger = 1
z = z + (Base – (z Mod Base))
x = x.PadLeft(z + (x.Length – (x.Length Mod z)), “0″)
y = y.PadLeft(z + (y.Length – (y.Length Mod z)), “0″)
Dim Compte As Long = (z / Base)
Dim nb_X As Long, nb_Y As Long, nb_Sum As String
Dim Rslt As Long, Carry As Long = 0
Dim Rslt_string As String = “”
For i As Integer = (Compte – 1) To 0 Step -1
nb_X = CLng(Mid(x, (i * Base) + one, Base))
nb_Y = CLng(Mid(y, (i * Base) + one, Base))
nb_Sum = CStr(nb_X + nb_Y)
If nb_Sum.Length > Base Then
Rslt =
CLng(
Microsoft.VisualBasic.Right(
nb_Sum, Base)) + Carry
Carry =
CLng(
Microsoft.VisualBasic.Left(
nb_Sum, Len(nb_Sum) – Base))
Else
Rslt = CLng(nb_Sum) + Carry
Carry = 0
End If
Rslt_string = CStr(
Rslt).PadLeft(
Base – Len(Rslt)) & Rslt_string
Next
Rslt_string = (
CStr(Carry) & Rslt_string).TrimStart(“0″)
Return Rslt_string
End Function

September 9, 2011 at 12:45 pm
(15) lara says:

thanks a lot,

(i have just finished the division function, and moving on another square function…)

i will use your stop clock to improve them.

September 13, 2011 at 9:45 am
(16) lara says:

does someone could help me for aditions of numbers with flowting points please, thanks

September 13, 2011 at 8:22 pm
(17) Dan Mabbutt says:

Well … As before, post the code you have now and we’ll work on it.

You probably already know that the key to floating point addition is normalizing the mantissas of both numbers. In other words (picking numbers that I can fit in the space here), this floating point number:

1.23E5 is equal to 123,000

This floating point number:

4.56E8 is equal to 456,000,000

So the sum is equal to:

456,123,000

You have to pick the smallest exponent that will encompass the mantissas of both numbers by subtracting the smallest exponent from the largest one.

8 – 5 = 3

Then add that number of zeros to the largest to normalize it with the smallest.

4.56E8 = 456,000.0E5

Now that the two numbers have the same exponent, the mantissas can be added directly. And you already know how to do this.

The problem is that by their very nature, floating point numbers can vary so much in size that it’s simply impractical to add them. In numbers ….

1.23E50 + 4.56E-50

… still yields a number with 100 digits if you want to preserve all of the digits of the original numbers. You have to decide where a cutoff will be. 50 digits? 100 digits? 10 digits? It’s an arbitrary decision but I think the code can’t be written without it.

September 22, 2011 at 7:59 am
(18) vbprogramming says:

Hey :) Thx for nice code, but I have a problem, your code isnt working for number.length>=20. I dont understand why, but it seems becouse of cerry or holddigit. How can I improve it and make multiplication for 200 digit numbers.
And by the way, I find out an interesting algorthm of Karatsuba for multiplying large numbers :) it’s interesting.
Please help me if you can

September 22, 2011 at 10:19 am
(19) visualbasic says:

Sorry it isn’t working for you. But you have to give us more to work with than that.

Posting your own code might help.

Telling us how you decided that it wasn’t working might help.

September 23, 2011 at 1:16 am
(20) vbprogramming says:

I tried to multiply numbers, wich length is >=20 and programm said that this numbers are bigger then int64. I still havnt my own code for post here, but I’ll as soon as I’ll wirte it :)
Thx

Leave a Comment

Line and paragraph breaks are automatic. Some HTML allowed: <a href="" title="">, <b>, <i>, <strike>

©2014 About.com. All rights reserved.