Hello All –
While Dick and company do the heavy lifting around here writing about VBA Frameworks, I asked if I could contribute about lighter fare, specifically the Project Euler Challenges. I am a systems engineer by trade, and use Excel as a tool to manage requirements. I confessed to Dick I have probably never used an accounting-specific Excel function, though I’ve been using Excel since v1.5 (yep…that old).
Project Euler indicates that all the challenges can be computed in less than one minute of computer time. Once you find a right answer, it’s like a password to review the thoughts, code, and comments of others who solved the problem before you. It’s disconcerting to read from a 14-year-old coder who solved the problem in just a few lines of Haskell (what’s that?). Nobody seems to be doing the problems in VBA, so I asked Dick if I could start conversations about how one might. One thing I won’t post is the answersthat’s a password you’ll at least have to have Excel to get. And there are more than a few that I’ve attempted that I’m stuck on, and then there are the ones that I don’t know how to start coding, and still others that I don’t understand the mathematics. Never-the-less…
Did you know that Excel can compute 2^1000 in four tenths of a second?
I didn’t either until I attempted Project Euler Problem 16 which states:
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
There are two general tasks:
- Time the calculation
- Reproduce the example
and two specific tasks:
- Compute 2 to the 1000
- Calculate the sum of the digits
Here is my code:
Option Base 1
Sub Problem_016()
Dim exp As Long
Dim i As Long
Dim j As Long
Dim Answer As Long
Dim M1 As String
Dim M2 As String
Dim T As Single
Dim IsTest As Boolean
T = Timer ‘starts timing
IsTest = False
If IsTest Then ‘to reproduce the test case
exp = 15
Else
exp = 1000
End If
M1 = “2”
For i = 2 To exp ‘calculates 2^exp
M2 = AddAsStrings(M1, M1)
M1 = M2
Next i
For i = 1 To Len(M2) ‘loops the length of 2^exp to sum digits
Answer = Answer + CLng(Mid(M2, i, 1))
Next i
Debug.Print Answer; ” Time:”; Timer – T; M2
End Sub
And by the way, 2^1000 is precisely:
10715086071862673209484250490600018105614048117055336074437503883703510
51124936122493198378815695858127594672917553146825187145285692314043598
45775746985748039345677748242309854210746050623711418779541821530464749
83581941267398767559165543946077062914571196477686542167660429831652624
386837205668069376
The key part is the AddAsStrings() function. It does addition the way you learned itstarting from the right and carrying to columns on the left.
Dim Sum As Long
Dim Carry As Long
Dim C As Long
Dim Answer As String
If Len(Adder1) > Len(Adder2) Then
For C = 1 To Len(Adder1) – Len(Adder2)
Adder2 = “0” & Adder2
Next C
ElseIf Len(Adder2) > Len(Adder1) Then
For C = 1 To Len(Adder2) – Len(Adder1)
Adder1 = “0” & Adder1
Next C
End If
For C = Len(Adder1) To 1 Step -1
Sum = Carry + CLng(Mid(Adder1, C, 1))
Sum = Sum + CLng(Mid(Adder2, C, 1))
Carry = Int(Sum / 10)
If C <> 1 Then
Answer = CStr(Sum Mod 10) & Answer
Else
Answer = CStr(Sum) & Answer
End If
Next C
AddAsStrings = Answer
End Function
AddAsStrings() does well on Fibonacci numbers, simple multiplication (including squaring), and factorials. It doesn’t do as well on cubes and higher powers. It becomes loops inside loops. It works on powers of 2 because all we do is double and redouble…
You’ve seen me around here as both Michael and …mrt. For whatever it helps, I’m pleased to contribute.
Well, I see that I don’t have the HTML escape codes mastered. Spacing them out, & # 6 2 ; is the “greater than” symbol, & # 6 0 ; is the “less than” symbol, and & amp is the ampersand.
And I don’t know why the code font changes. I didn’t see a setting for that.
I’ll do better. Season’s joy to all.
…Michael
Michael: Within the VB tags, you don’t have to escape anything. That’s not so in comments because of a bug in the hiliter program, but in posts, no escapes are necessary.
Also, for some reason, it doesn’t like blank lines. It changes the font when it encounters a blank line. I un-escaped your characters and added a single space on the blank lines.
Interesting approach, but you seem to run into trouble if the task would have been 2^100000000 or something similar instead. This problem is easily solved by pen and paper for any x in 2^x.
But that’s the charm of the Project Euler problems: quite a few of them are “brute-forceable”.
I am very much looking forward to further posts. I have solved 100+ problems, most in Excel, but I have also used other tools in a few cases.
Dick – thank you. Two quick blog lessons within a half hour already ;-)
Micke – absolutely. I already have. It breaks on Problem 104, which looks for a very very long Fibonacci number. It does the two test cases, but stalls on the challenge. I let it run all weekend on the office computer, and then was “frozen out” when I came in on Monday. So there’s another way for sure… I’ve only done 35 so far, with 3 or 4 that are like Problem 104…I know I have an approach, but it’s just not done in “Euler time.” If I don’t find the other way, I’ll post it as a bad example…
There are many I prototype on a spreadsheet, and then I code up the method I used. Glad there are more solving the problem using Excel.
…Michael (Seasons’ Greetings to all)
VBA can do this much quicker still. I am also using it to do the Euler problems, and wrote a “BigMultiply” function to multiply huge numbers together, which is needed for some later problems.
It is faster than your AddAsStrings because instead of working character by character, it breaks the numbers into chunks of 7 chars which can be multiplied normally, then the chunks are combined.
But the real key to speed is to start by calculating 2^40 normally, then incrementing it as shown below, to reduce the number of arithmetic operations.
k = 2 ^ 40
S = CStr(k)
s1 = BigMultiply(S, S) ’80
s1 = BigMultiply(s1, S) ‘120
s1 = BigMultiply(s1, 32) ‘125
s1 = BigMultiply(s1, s1) ‘250
s1 = BigMultiply(s1, s1) ‘500
s1 = BigMultiply(s1, s1) ‘1000
I have quite a number of the problems solved, and am stuck on others, and I am happy to share, especially helper functions like prime number tests that are needed quite often.
I’ve done up to 32 using Excel and VBA. Mostly VBA, but a few work well with a pure spreadsheet solution. For the 2^1000 problem I set up an array of integers for each digit of the number, rather than working on a string. Probably not very efficient, but it works.
For some reason I found number 31 difficult and haven’t solved it yet (and no time at the moment).
I noticed the anti-VBA bias as well. I also noticed some compiled solutions that took hours that were solvable in less than a second. The algorithm is much more important than the programming language with these things.
Anyone wanting a VBA prime number generator might like to have a look here:
http://newtonexcelbach.wordpress.com/2008/11/18/finding-prime-numbers-with-excel-and-using-array-
I agree about the algorithms, a good insight/trick makes all the difference. This is my solution for problem 31, brute force but it works.
Sub P31()
Dim P1 As Long, P2 As Long, P5 As Long, P10 As Long, P20 As Long, P50 As Long, P100 As Long, P200 As Long
Dim n1 As Long, n2 As Long, n5 As Long, n10 As Long, n20 As Long, n50 As Long, n100 As Long, n200 As Long
Dim n As Long
For P1 = 0 To 200 Step 1
n1 = P1
For P2 = 0 To 200 – n1 Step 2
n2 = n1 + P2
For P5 = 0 To 200 – n2 Step 5
n5 = n2 + P5
For P10 = 0 To 200 – n5 Step 10
n10 = n5 + P10
For P20 = 0 To 200 – n10 Step 20
n20 = n10 + P20
For P50 = 0 To 200 – n20 Step 50
n50 = n20 + P50
For P100 = 0 To 200 – n50 Step 100
n100 = n50 + P100
For P200 = 0 To 200 – n100 Step 200
If n100 + P200 = 200 Then
n = n + 1
End If
Next P200
Next P100
Next P50
Next P20
Next P10
Next P5
Next P2
Next P1
Debug.Print n
End Sub
dbb – I promised myself that I was going to work it out for myself, but then I saw your code and coudn’t resist trying it.
I wouldn’t really call it brute force. There was a real brute force one in the discussion which just tries every feasible combination of the coins, and counts the ones that add up to 200. I converted that from Java to VBA and started it about five minutes ago, and it’s still running.
I might try it in Fortran and see if it completes within the time limit.
I thought the Haskell and Mathematica examples that do this in 2 or 3 lines were just annoying :)
Might have a go at trying to work out how they do it over Christmas.
dbb- Thank you. Problem 31 was one of those where I understood the question, but didn’t have a clue about the coding. Now that I have a clue (and have shamelessly jacked up my Euler total), if I copy your code and start a new Problem 31 thread, will you come back and leave us a paragraph or two about how you visualized the problem and the overlay of your approach over in that thread? I frankly don’t have may arms around that part.
…Michael (Blessings of the season to all)
Hi Michael,
Thanks for getting me hooked on yet other way to spend (waste, some might call it) my time. {grin}
I wrote a set of functions LargeAdd, LargeMult (requires LargeAdd), LargePower, and LargeFactorial (the last two require LargeMult) that work with numbers with more than 15 significant digits. But, before I share my take on Problem 16, I’d like to start with my solutions to other problems. Of course, what I share is not as much the solution as a road map to the solution.
The list of what I have solved (in the sense that the Project Euler website accepts my answer) and written up the solution is at
Project Euler Problems
http://www.tushar-mehta.com/misc_tutorials/project_euler/
Hi Tushar – (Do I have that right?)
I look forward to your “large” functions. My attempt at multiplication has two virtues: (1) it’s accurate and (2) it’s slow. It’ll never meet any standards for Euler time.
I can see nothing but good stuff on your webpages. Thank you for making a Euler page.
…best, Michael (well known for wasting people’s time ;-) )
I think using VB code in Excel violets the very fun aspect of Project Euler. I am trying to solve all of the problem using normal Excel functions (I have been coding for 30 years and find it fun to twist Excel to do this stuff. The basic problem is that an excel cell only has 15 digits of precision (by using a VB long you escape this problem).
My solution, which only took about 3 minutes to write, is to “build” the answer over multiple columns, one column for each digit of the answer.
Imagine that row 1 holds 2 ** 1, row 2 is 2 ** 2, etc. I calculated 2 ** n in the normal way in column a – at row 48 (2 ** 49), the answer is 562,949,953,421,312, which has 15 digits and is the biggest number you can get before losing precision.
So, in column C, I calculate the last digit of the answer. This is done by seeding a ‘2’ in column C1 and calculating the 999 rows below as ‘=mod(cell above me*2, 10). This will work fine for all 1,000 rows, but it is only the last digit – I need a way to calculate the other digits.
So, I copied the following formula ‘=MOD((2*cell above me)+IF(cell above me and one to the left*2>=10,1,0),10)’ to the range d4…ku1000. I used this range because a) you have to skip the top three rows where there is only one digit (2, 4, 8) and the answer to =power(2, 1000) is 1.07E+301, so I went out 305 positions just to be safe (D … KU is 305 columns).
This formula basically looks to see if we need to carry the one.
Using the approach, it built my answer in 301 columns of row 1000. The only hard part is that you have to read the number left to right (backwards), but it is easy to calculate =sum(d1000 .. ku 1000) for the answer.
Has anyone else tried to solve all of these using basic Excel?
Hi Jay –
My approach is just the opposite, and that’s the appeal of Euleryou and I are after different things. I’ve done 41, and about half were prototyped in a spreadsheet and then moved on to VBA. The spreadsheet graphic allows me to visualize the arrays (key examples would be the triangles of Problems 18 and 67) and gives me insight to the code. I started this to expand my coding. I never coded the opening of a file in VBA before I started Euler.
301 columns? That’s cheating… ;-)
…mrt
I have been Working on the same problems using VBScript only. You know, VBS files running under windows scripting host. The syntax is similar to VBA i.e. translates with only slight tweaks. My solution for problem 16 runs .4 of a sec longer than yours, not sure if that is because of the scripting engine or some other difference in the code. Anyway I have solved over 25 of these problems with VBScript now if any of you are interested. It is interesting looking at how someone else solved the same problem especially if their version is drastically faster.
Problem 18 and 67 are a good example. My brute force code on 18 takes longer than my elegant code on 67 which is essentially the same problem only larger.