1 min read

APL Hacking: Project Euler Daily (#13)

So, this is actually my post for Friday, but since I was traveling, I was not able to post anything for that day.

This one was pretty fun. The problem is that the input to the incoming function was a series of 100 50-digit numbers. Now, this won't fit within 32-bit integers on my system (bah, 32-bit APL on a 64-bit machine, oh well). This required that I split the integers up, do the additions on them in small chunks, and finally apply a carry algorithm to them.

I initially wanted to do this with a scan and a CARRY operator, but I realized that this won't work because of the nature of the scan algorithm. Instead, I had to collect the results of the carry as I went and do a reduce. That seems to work okay, though. Here's the basic use:

⍝ First ten digits of the sum of the numbers in X.

⌽⊃(100000 CARRY)/⍬,+⌿100 10⍴⎕FI(6000⍴(5⍴1),0)(~⎕R=X)/X



I used the following carry algorithm:

R←E(B CARRY)S

⍝ Performs a carry operation.
R←(¯1↓S),(B|¯1↑S),E+⌊(¯1↑S)÷B