Using BigInteger in Visual Basic 2010

Introduction

I was sitting on a plane from Montreal a few years back next to a math professor from McGill University and casually asked him what was new and hot in mathematics. He said: cryptography and encryption. Of course, secrets. In an information age, secrets and secret data are going to be pretty important. More recently I read that the European Union suspended Blackberry text messaging because Blackberry encrypts text messages and routes them through Canada, so the stories seem to suggest. Encrypted messages that can't be intercepted are a risky prospect in this day and age.

Public encryption depends on huge prime numbers. The basic idea is that data encrypted based on primes could theoretically be cracked by brute force, by testing all prime candidates. However, since the primes used for encryption are so big by the time all possibilities are tested for primality the data is no longer relevant, or so that's the basic theory. There is a lot more to prime numbers and encryption, but that represents the broad strokes as I understand them.

Up until now calculating huge prime numbers in .NET required a lot of work. There weren't even primitive data types that could represent very large numbers. .NET framework 4.0 introduced the BigInteger type. The example in this article explores calculating the square root of BigInteger numbers and calculating large prime numbers.

Introducing the BigInteger

The retired Major League Baseball player Randy Johnson was referred to as the "Big Unit". This 6' 10 left handed pitcher occasionally threw a fast ball at more than 100 miles per hour. A 100 mile per hour pitch is approximately 147 feet per second; in other words from pitcher to batter a Randy Johnson fastball covered the 90 feet in two-thirds of second. When I was much younger and stronger I could hit an 85 miler as long as I knew it was coming and it came straight down the pipe. I doubt I could even see a 100 mile an hour pitch or get the bat around fast enough. Perhaps it is better I don't have that pressure.

BigInteger refers to a new data type in the .NET framework. Defined in System.Numerics BigInteger has methods and overloaded operators that make it easier to use like smaller integral native data types, but using it with the Math class and Math's static methods is not supported. For the most part you can use BigInteger like any other integer type.

BigInteger is stored such that the most significant bit of the last byte is the sign bit. If you initialize a BigInteger with an array of bytes then include an additional byte whose value is zero, for the sign bit.

The biggest difference between BigInteger and smaller integer types in .NET is that BigInteger is the only one that doesn't have MinValue and MaxValue properties. The absence of these properties means that BigInteger can grow arbitrarily large and consequently take up a huge amount of memory. The real limitation to BigInteger is the physical resources on your computer. BigInteger types are immutable, so if you increment a BigInteger number then what really happens is the creation of a new BigInteger object though this process is invisible to the developer. Too many small operations on very big BigInteger values or if a BigInteger grows too large then an OutOfMemoryException will be thrown.

Oddly enough there is no Square Root method for BigInteger types. So, the solution I picked to introduce BigInteger is a solution that calculates huge prime numbers using the Sieve of Eratosthenes and a couple of ways of calculating the square root of BigIntegers.

Calculating Square Roots Up To Double.MaxValue

One method for calculating the square root is calculating . You can use the Math class and calculate the square root of a BigInteger up to Double.MaxValue with the following formula:

  Math.Exp(BigInteger.Log(value) / 2)

If the result is greater than Double.MaxValue then the result is Double.PositiveInfinity, making this a reasonable approach for calculating the square root of smaller numbers. Think of this as a quick square root solution for some small-valued BigIntegers but not huge ones.

Calculating the Square Root of Arbitrarily Large BigIntegers

If you need to whip out a square root calculator for really BigIntegers then you can use Newton's method which is substantially more complex. The example for calculating the square root of a BigInteger in Listing 1 is based on John Wein's post of Newton's method, posted on social.msdn.microsoft.com. I translated it to VB, so any mistake in translation is my fault.

  Private Function Sqrt(ByVal number As BigInteger) As BigInteger
    ' problem with lower numbers to right bit shift
    Dim bitLength As Integer = number.ToByteArray().Length * 8 + 1
    Dim G As BigInteger = number >> bitLength / 2
    Dim LastG As BigInteger = BigInteger.Zero
    Dim one As BigInteger = New BigInteger(1)
    While (True)
      LastG = G
      G = (number / G + G) >> 1
      Dim i As Integer = G.CompareTo(LastG)
      If i = 0 Then Return G
      If i < 0 Then
        If (LastG - G).CompareTo(one) = 0 Then
          If (G * G).CompareTo(number) < 0 And
            (LastG * LastG).CompareTo(number) > 0 Then Return G
          End If
        ElseIf (G - LastG).CompareTo(one) = 0 Then
          If (LastG * LastG).CompareTo(number) < 0 And
            ((G * G).CompareTo(number) > 0) Then Return LastG
      End If
    End While
    Return G
  End Function

Listing 1: Calculating the square root of really large BigInteger values in VB2010.

Wein's solution didn't seem to work for very low prime candidates. The reason for this seems to be in the fragment number >> bitLength / 2. This fragment shifts the value of the variable number right by the bit length of number. Very small numbers are going to be shifted to be equal to zero and assigned to G. G is used as a divisor in G = (number / G + G) >> 1, which causes a division by zero error. You can follow this link http://social.msdn.microsoft.com/Forums/en-SG/csharplanguage/thread/c13d3fec-21d9-4f74-92de-a6132d5e9915 for John Wein's original post. For more information on Newton's method you can start with the Wikipedia post http://en.wikipedia.org/wiki/Newton-Raphson. (I think of Wikipedia as a pretty good starting point, but scholarship and accuracy is encouraged based altruism not guaranteed.)

Now we can combine all of these elements and employ the Sieve of Eratosthenes to calculate huge prime numbers based on the BigInteger type.



Using BigInteger in Visual Basic 2010

Calculating Huge Prime Numbers with BigInteger

My implementation of the Sieve of Eratosthenes for calculating prime numbers is to start with a seed number, get the next number in the sequence, and check to see if earlier primes are divisors. Since all numbers are the product of primes then if any previous prime is a divisor then the number is not prime. A refinement to this approach is to test just the earlier primes that are less than the square root of the candidate number-see Listing 2.

  #Const SIMPLE = True
  Imports System.Collections.Generic
  Imports System.Linq
  Imports System.Text
  Imports System.Numerics
  Imports System.Timers
  
  
  Module Module1
  
      Private timer As Timer = New Timer()
  
      Sub Main()
  
        ' Calculate huge primes
         primes.Add(2)
         keepGoing = True
         timer.Interval = 1000000
         AddHandler timer.Elapsed, AddressOf timer_Elapsed
         timer.Start()
         Console.WriteLine("Calculating Primes")
         BuildPrimes()
  
         Console.ReadLine()
      End Sub
  
      Private keepGoing As Boolean = True
      Sub timer_Elapsed(ByVal sender As Object, ByVal e As ElapsedEventArgs)
        keepGoing = False
        timer.Stop()
      End Sub
  
      Private primes As List(Of BigInteger) = New List(Of BigInteger)()
      Private Sub BuildPrimes()
        Dim number As BigInteger = 3
        While (keepGoing)
          If IsPrime(number) Then
            Console.WriteLine("is prime: {0}", number)
            Primes.Add(number)
          End If
          number += 1
        End While
      End Sub
  
  
      Private Function IsPrime(ByVal number As BigInteger) As Boolean
        Dim index As BigInteger = 0
  
        For Each test As BigInteger In primes
          Dim remainder As BigInteger = 0
          BigInteger.DivRem(number, test, remainder)
          If remainder = 0 Then Return False
  
  #If Not SIMPLE Then
          If test * test > number Then Return True
  #Else
          ' Use shorter method for numbers up to Double.MaxValue
          Dim result As Double = Math.Exp(BigInteger.Log(number) / 2)
          If result <> Double.PositiveInfinity Then
            If test >= New BigInteger(result) Then Return True
          ElseIf test >= Sqrt(number) Then
            Return True
          End If
  #End If
        Next
  
        Return True
      End Function
  
      
      ' test known primes with this web site.
      ' adapted from John Wein's implementation of Newton's method 
      ' posted on   social.msdn.microsoft.com
      ' http://primes.utm.edu/curios/includes/primetest.php
      Private Function Sqrt(ByVal number As BigInteger) As BigInteger
        ' problem with lower numbers to right bit shift
        Dim bitLength As Integer = number.ToByteArray().Length * 8 + 1
        Dim G As BigInteger = number >> bitLength / 2
        Dim LastG As BigInteger = BigInteger.Zero
        Dim one As BigInteger = New BigInteger(1)
        While (True)
          LastG = G
          G = (number / G + G) >> 1
          Dim i As Integer = G.CompareTo(LastG)
          If i = 0 Then Return G
          If i < 0 Then
            If (LastG - G).CompareTo(one) = 0 Then
              If (G * G).CompareTo(number) < 0 And
                (LastG * LastG).CompareTo(number) > 0 Then Return G
            End If
          ElseIf (G - LastG).CompareTo(one) = 0 Then
              If (LastG * LastG).CompareTo(number) < 0 And
                ((G * G).CompareTo(number) > 0) Then Return LastG
          End If
        End While
        Return G
      End Function
  End Module

Listing 2: Generating very, very large prime numbers.

The example includes a couple of approaches to testing for prime numbers. The reason I included a couple of methods is because it introduces you to a lot of the behaviors supported by BigInteger, including methods and overloaded operators. Let's walk through the code so you can see what BigInteger is doing.

The first statement defines a conditional compiler directive to permit switching between chunks of code used. The Imports statement, including System.Numerics which contains BigInteger, follows the compiler constant.

The Main function uses a timer and a collection of BigInteger values seeded with the first prime number, 2, to start things off. The timer is just an easy way to stop processing. (It might be interesting to see how far this thing might run by itself.) The timer.Elapsed handler turns off the timer. BuildPrimes really does all of the coordination work.

BuildPrimes is pretty straight forward. As long as the flag keepGoing is true the loop will run and generate primes until you run out of memory. If you moved the primes to a database then you could run the program until you ran out of disk space, but the solution would probably be a lot slower. IsPrime and Sqrt are the workhorses of the solution. If IsPrime returns true then the prime number is added to the collection.

IsPrime calls DivRem to obtain the remainder of the argument number divided by the test number. If number is evenly divisible by test--a known prime--then the number is not prime and IsPrime returns false. In the #If part of the conditional code if test squared is greater than the candidate number then all of the possible known primes that need to be tested have been; that is, if test squared is greater than number then all of the remaining prime numbers are too big to be divisors so number is prime. In the #Else part of the solution the [sample2.jpg] algorithm is used for numbers less than Double.Max and the local Sqrt method is used when [sample3.jpg] returns Double.PositiveInfinity. (Note that IsPrime demonstrates how to use BigInteger.DivRem and construct a BigInteger from a Double.)

Sqrt uses several BigInteger methods and overloaded operators. The first statement in Sqrt converts a BigInteger to a byte array and a bit array by multiplying by 8. The next statement shows the shift right operator for BigInteger which shifts all of the bits right by the number on the right hand side of the operator. The next two statements--BigInteger.Zero and New BigInteger(1)--demonstrate how to obtain a zero-valued BigInteger and explicitly call the BigInteger constructor. If you look at the rest of the code you will see a call to CompareTo, subtraction, multiplication, and comparison operators for BigInteger.

When you are ready to test the results of the solution you can try http://primes.utm.edu/curios/includes/primetest.php. Of course, if you have to depend on this solution for some really secret squirrel stuff then carefully debug the Sqrt function and check the results against a very reliable source of prime numbers. I wouldn't want to be responsible for a national security crisis.

Summary

.NET framework 4.0 defines a new type, the BigInteger. The BigInteger can be used for the most part like any other integer number. The biggest difference is that BigInteger has no MinValue or MaxValue properties and theoretically can consume as much memory as is available on your computer. Really big numbers eventually are going to consume a lot of memory, which may cause performance problems. If you need BigInteger then use it, but if you can work with smaller integer types then use those instead.

Think of BigInteger memory usage in the way that you think of string memory. BigIntegers, like strings, are immutable and can contain a lot of data per instance. If you have huge BigIntegers or big strings you may run into memory problems. That of course doesn't stop you from using strings.





About the Author

Paul Kimmel

Paul Kimmel is the VB Today columnist for CodeGuru and has written several books on object-oriented programming and .NET. Check out his upcoming book Professional DevExpress ASP.NET Controls (from Wiley) now available on Amazon.com and fine bookstores everywhere. Look for his upcoming book Teach Yourself the ADO.NET Entity Framework in 24 Hours (from Sams). You may contact him for technology questions at pkimmel@softconcepts .com. Paul Kimmel is a Technical Evangelist for Developer Express, Inc, and you can ask him about Developer Express at paulk@devexpress.com and read his DX blog at http:// community.devexpress.com/blogs/paulk.

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • You may already know about some of the benefits of Bluemix, IBM's open platform for developing and deploying mobile and web applications. Check out this webcast that focuses on building an Android application using the MobileData service, with a walk-through of the real process and workflow used to build and link the MobileData service within your application. Join IBM's subject matter experts as they show you the way to build a base application that will jumpstart you into building your own more complex app …

  • As mobile devices have pushed their way into the enterprise, they have brought cloud apps along with them. This app explosion means account passwords are multiplying, which exposes corporate data and leads to help desk calls from frustrated users. This paper will discover how IT can improve user productivity, gain visibility and control over SaaS and mobile apps, and stop password sprawl. Download this white paper to learn: How you can leverage your existing AD to manage app access. Key capabilities to …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds