**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!

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

alsokept track of the accuracy as it worked, so that it was possible to see just how useful (or not!) the result was.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

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

Thanks!

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

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/

This code fails if you multiply 4294967296 * 4294967296

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?

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.

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?

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.

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

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

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

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

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.

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

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.

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

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.

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