18 thoughts on “Large Number Arithmetic”

1. As soon as I saw this I remebered the excellent “Multi Precision Floating Point Computing and Numerical Methods for EXCEL” at Foxes Team (Italy)

   http://digilander.libero.it/foxes/MultiPrecision.htm

   There are some good mathematical and matrix routines there. Sadly, being free, it looks like further development has ceased, but they do work.

2. Tushar, the approach below to large multiplication is about 30x times faster in calculating the factorial of 1000 (the example on your page), on my PC. It simply breaks the large numbers into chunks of 7 digits, so that VBA can cross multiply all the chunks normally, then it is simply a matter of combining them correctly. I’m sure there are faster methods still!

   Function BigMultiply(ByVal s1 As String, ByVal s2 As String) As String

   Dim X As Long
   X = 7 ‘the number of digits per chunk

   Dim n1 As Long, n2 As Long, n As Long
   n1 = Int(Len(s1) / X + 0.999999)
   n2 = Int(Len(s2) / X + 0.999999)
   n = n1 + n2

   Dim I As Long, j As Long
   ReDim za1(n1) As Double
   I = Len(s1) Mod X
   If I = 0 Then I = X
   za1(1) = Left(s1, I)
   I = I + 1
   For j = 2 To n1
   za1(j) = Mid(s1, I, X)
   I = I + X
   Next j

   ReDim za2(n2) As Double
   I = Len(s2) Mod X
   If I = 0 Then I = X
   za2(1) = Left(s2, I)
   I = I + 1
   For j = 2 To n2
   za2(j) = Mid(s2, I, X)
   I = I + X
   Next j

   ReDim z(0 To n) As Double
   Dim u1 As Long, u2 As Long
   Dim e As String
   e = String(X, “0?)

   For u1 = 1 To n1
   I = u1
   For u2 = 1 To n2
   I = I + 1
   z(I) = z(I) + za1(u1) * za2(u2)
   Next u2
   Next u1

   Dim S As String, y As Double, w As Double, m As Long
   m = n * X
   S = String(m, “0?)
   y = 10 ^ X
   For I = n To 1 Step -1
   w = Int(z(I) / y)
   Mid(S, I * X – X + 1, X) = Format(z(I) – w * y, e)
   z(I – 1) = z(I – 1) + w
   Next I
   ‘truncate leading zeros
   For I = 1 To m
   If Mid$(S, I, 1) GREATER_OR_LESS_THAN “0? Then Exit For
   Next I
   If I > m Then
   BigMultiply = “”
   Else
   BigMultiply = Mid$(S, I)
   End If

   End Function

   Note – I’ve substituted text for the greater or less than symbol in one place above, because the text editor thinks they are HTML tags

3. Mpemba: Thanks for that link. Maybe, I can find something there that I can adapt to new functions rather than reinvent the wheel. The reason for adapting that work rather than using it “as is” is that its stated limit is 250 digits whereas some of the Project Euler solutions require more!

4. Tushar

   No problem – the routines I’ve used most from Foxes Team were for the bigmatrix calculations. But re this problem, their routines are largely for floats not integers.

   M

5. I’ve just extracted the big-multiplication routines (they are not hidden in the xnumbers.xla).
   It seems that the arbitrary “250? is easy to increase.

   In the type definition for xnum you have to set nnn in dgt(nnn) to 0.375*Max-Digits.
   I’ve already tested it for 1600 digit precision. How many do you need?

   I suspect they may have stopped at 250 for all funtions because of the matrix routines (which were limited by excel’s 256 columns)

6. There are also the BigNum algorithms available here:

   http://www.andrijar.com/programs.htm

   They are VB6 but compile in Excel. However, the form does not import. Many seem to require 3 parameters, and I can’t decipher why. The code would seem to be obfuscated VB, to coin a phrase.

   …mrt

7. So far I’ve managed to solve all the questions I’ve tackled using only doubles or non-arithmetic use of strings. Has anyone found a problem that they believe cannot be solved without the use of large number arithmatic?

8. Doug –

   #97?

   The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^(6972593)-1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^(p)-1, have been found which contain more digits.

   However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^(7830457)+1.

   Find the last ten digits of this prime number.

   …mrt

9. Doug –
   #104? Broke AddAsStrings..

   The Fibonacci sequence is defined by the recurrence relation:

   F_(n) = F_(n-1) + F_(n-2), where F_(1) = 1 and F_(2) = 1.

   It turns out that F_(541), which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F_(2749), which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

   Given that F_(k) is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

   …mrt

10. Michael – No 97 was pretty easy (although it took me way longer than it should have). I just successively muliplied by 2, 7,830,456 times, discarding the left hand digits whenever there were more than 10, then multiplied by 20,000, 8,000, and 433, discarding excess digits, added the results then added 1. I used a double rather than long, because a long doesn’t give enough digits.

    I started off doing it in a spreadsheet (in XL 2007), in 7 stages. It works, but it’s very slow.

    104 might be a bit more difficult, because you need the start digits of a long number. I’ll have a think about that one later.

11. Doug: #16, #20, #25 for starters.

12. >So far I’ve managed to solve all the questions
    >I’ve tackled using only doubles or non-arithmetic use of strings

    The main problems for me have been in matrix operations where the precision is an issue.
    Foxes bigmatrix operations solve this limitation.

13. >>
    Doug: #16, #20, #25 for starters.

14. “Doug: #16, #20, #25 for starters.”

    OK, I forgot that I did in fact write specific routines for those questions that in effect used large number arithmatic. I set up big arrays and did it one digit at a time. Not very efficient, but they worked well within the allotted time.

    Here’s the code for the sum of the digits in 100! for instance (which takes less than a second):

    Function SumFact(num)
    Dim DigitA(1 To 1000) As Long, NumDigits As Long, i As Long, j As Long, carry As Long
    Dim k As Long, x As Long, Facts As String

    NumDigits = 1
    DigitA(1) = 1

    For i = 2 To num
    carry = 0
    For j = 1 To NumDigits
    DigitA(j) = DigitA(j) * i + carry
    If DigitA(j) .GT. 9 Then
    carry = Int(DigitA(j) / 10)
    DigitA(j) = DigitA(j) – carry * 10

    If j = NumDigits Then
    DigitA(j + 1) = carry
    NumDigits = NumDigits + 1
    If carry .GT. 9 Then
    x = Int(Log(carry) / Log(10))
    For k = j + 1 To j + x
    DigitA(k) = carry – Int(carry / 10) * 10
    carry = Int(carry / 10)
    NumDigits = NumDigits + 1
    Next k
    DigitA(NumDigits) = carry
    End If
    End If
    Else
    carry = 0
    End If
    Next j
    Next i
    For i = NumDigits To 1 Step -1
    SumFact = SumFact + DigitA(i)
    Next i

    End Function

15. Hi Doug –

    Re: #97. Thank you. Taught me two things. 1. RIGHT() works on doubles. I thought it only worked on strings and variants. I’ve been doing some unnecessary type changes, and 2. RIGHT() and * are commutative. They never taught me that in arithmetic ;-)

    …mrt

16. All the Euler problems lend themselves to solutions in functional programming languages, so Excel itself should be sufficient to solve all of them. For example, #16, the sum of the digits of the base 10 representation of 2^1000. Since INT(LOG10(2^1000)) = 301, this will require 301 decimal places to the left of the decimal point.

    A4 2
    A6 =SUM(A7:IP8)
    A7 =MOD(A4*2,10)
    B7 =MOD(B4*2,10)+INT(A4/5) fill into C7:IP7
    A8 =MOD(A5*2,10)+INT(IP4/5)
    B8 =MOD(B5*2,10)+INT(A5/5) fill into C8:IP8

    Copy A6:IP8, paste into A9. Copy A6:IP11, paste into A12. That is, double the copy/paste range each time, so reach 2^1024 after 10 copy/paste operations.

    The sum of the decimal digits of 2^N (1

17. Grrr! The sum of the decimal digits of 2^N for N from 2 to 1024 is given by INDEX(A:A,3*N).

18. I do have some functions available like sum, difference, greaterorequalthen, multiplication, division, faculty, power, mersenne numbers. Everthing very basic for (still) only defined for integers. All input and output is as string so you may handle numbers of several thousands of digits & everything under VBA. oomenwong @ free.fr (no spaces)

---

Posting code? Use <pre> tags for VBA and <code> tags for inline.