# Large Number Arithmetic

One of the incentives to tackle the Project Euler problems has been the opportunity to build a library of functions usable outside of the PE questions themselves.  The first few functions tackle basic arithmetic for numbers that neither Excel nor VBA support natively.  In Excel the limit is 15 digits and in VBA the Decimal data type supports 29 digits.  But, to go beyond that one must roll their own functions.  And the Large Number Arithmetic module is my preliminary stab at it.

Posted in Uncategorized

## 18 thoughts on “Large Number Arithmetic”

1. Mpemba says:

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. dbb says:

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
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. Tushar Mehta says:

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. Mpemba says:

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. Mpemba says:

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. Michael says:

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. Doug Jenkins says:

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. Michael says:

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. Michael says:

Doug –

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. Doug Jenkins says:

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. Tushar Mehta says:

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

12. Mpemba says:

>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 Jenkins says:

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

14. Doug Jenkins says:

“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. Michael says:

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. fzz says:

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. fzz says:

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. wpjo says:

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.