Programming Forums - Spiral Diagonals

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Assembly (http://www.programmingforums.org/forum20.html)

- - Spiral Diagonals (http://www.programmingforums.org/showthread.php?t=1560)

In a numerical spiral such as below the question was given to determine the sum of both diagonals in a 1001 by 1001 spiral.

73 74 75 76 77 78 79 80 81

72 43 44 45 46 47 48 49 50

71 42 21 22 23 24 25 26 51

70 41 20 7 8 9 10 27 52

69 40 19 6 1 2 11 28 53

68 39 18 5 4 3 12 29 54 

67 38 17 16 15 14 13 30 55

66 37 36 35 34 33 32 31 56

65 64 63 62 61 60 59 58 57

I'm curious what algorithm others would have chosen. Mine follows.
I noticed a pattern with the diagonal numbers
- every 4th iteration add 2

 2 2 2 2 4 4 4 4 6 6 6 6 8 8 8 8 

1,3,5,7,9,13,17,21,25,31,37,43,49,57,65,73,81

So I set an inner loop counter at 4 and incremented a reg by 2 each time.

 mov ecx, 1   ; first diagonal spiral number

 xor ebx, ebx  ; determines distance to next diagonal

 mov eax, ecx  ; begin accumulating sum

inner:

 add ebx, 2   ; update distance between diagonals

 mov edx, 4   ; will use distancefor 4 iterations

outer:

 add ecx, ebx  ; go to next diagonal

 cmp ecx, 1002001; is it the last one?

 ja getout   ; yes, go away

 add eax, ecx  ; no, add to sum

 dec edx     ; decrement inner loop counter

 jz inner    ; if zero- reset counter

 jmp outer    ; next number

getout:

That is really the only way to tackle this problem that I can think of, and what is even cooler is that you tackled the problem in ASM :P

It looks good though.

Here's a C version just for you. ;)

#include <stdio.h>



int main()

{

 unsigned long i,j=2,k=0,x=0;



 for(i=1;i<=1002001;i+=j){x+=i;if(k==4){k=0;j+=2;}k++;}

 printf("sum is %u\n",x);

 return 0;

}

Since posting I have reviewed some other solutions. Everyone else completed this with a different algorithm. To me, this one was less complicated though. The above assembler can also be dropped inline in a C program.

int main()

{

 unsigned long x;

 x=myasm();

 printf("sum is %u\n",x);

 return 0;

} 



unsigned long myasm()

{

 asm("

 mov ecx, 1

 xor ebx, ebx

 mov eax, ecx

inner:

 add ebx, 2

 mov edx, 4

outer:

 add ecx, ebx 

 cmp ecx, 1002001

 ja getout

 add eax, ecx

 dec edx

 jz inner

 jmp outer

getout:

 ");

}

compiled with:

gcc -o spiral spiral.c -masm=intel

An intriguing problem, and after about 4 hours and about 5 pages of calculation I think I've finally got another solution for you...

You're itterative approach is awesome and it finds the solution quite nicely, but I couldn't help but wonder if it was possible to derive a simple plug-and-chug formula that can derive the solution in a single pass (something more efficient than the loop approach when working with higher numbers). Here's what I came up with:



2(n^3) + 1.5(n^2) + 4(n) - 7.5

------------------------------ + 1

        3

where n is the width of the figure (or height, they should be the same).

Now, this isn't very useful if you're programming in assembly so applying Horner's Algorithm we get:



n(n(n(2) + 1.5) + 4) - 7.5

-------------------------- + 1

       3

(just work from the middle out, multiplying and adding back and forth).

I know this formula looks a little random, but I assure you it works. Try it! :D

If you're still skeptical, my explanation...

Start by looking back at the problem visually. First, remove all the unnecessary values.

Now, think of each new row as a new layer with four new corner values. Something like this..





   -----------------------

   |43         49|

   | ----------------- |

   | |21      25| |

   | | ----------- | |

   | | | 7   9 | | |

   | | | |---| | | |

   | | | | 1 | | | |

   | | | |---| | | |

   | | | 5   3 | | |

   | | ----------- | |

   | |17      13| |

   | ----------------- |

   |37         31|

   -----------------------





etc..

Looking at the values in each new layer a usable pattern forms:

value 4 (top right)  = n^2 

value 3 (top left)   = n^2 - (n - 1)

value 2 (bottom left) = n^2 - 2(n - 1)

value 1 (bottom right) = n^2 - 3(n - 1)



where n = the width of the current layer

Note that the first layer, with only one value, is excluded from here on because it has only one value and so doesn't apply (we'll add it back on later).

Using these rules and a little algebra we can find the total value of any layer with:



4(n^2) - 6(n - 1)

The total sum of the whole figure (minus one) then is the series summation from r = 3 to the width of the widest layer (that is, the whole figure). Don't forget though that only odd numbers apply to this problem, this series should skip over even values of r. To compensate for this I converted the formula to work off layer number rather than layer size and converted it back when I was done. From there things get even more complicated, with some fancy sigma manipulation and sum identities, but trust me, it works. The finished result is the formula you get at the top. If anyone really want to see the whole thing worked out, let me know and I'll post it, but for now this'll do..

B)

P.S. I've been fiddling with this all afternoon and my eyes have glazed over some time ago. So, I wouldn't be supprised if my writing is a little scattered or full of typos. Feel free to point those out to me. ^_^

Wow. A programmer that isn't a lazy bugger. Nice work, mate.

Well done! Very impressive analytical skills. It works and is very fast. My math background is weak but I'll be looking forward to future math lessons. :)

Heh. It was pretty impressive. If anyone has to work out the value of steps (don't ask), I have a maths paper I wrote at the beginning of the year you can have.

Hello,

I am trying to compile a program with inline assembler like yours, but failing.

When I try to compile your code I get the messages:

perkinel-e586cd:~/cfiles/HIS> gcc -o spiral spiral.c -masm=intel
spiral.c:15:6: missing terminating " character
spiral.c: In function `myasm':
spiral.c:16: error: parse error before "mov"
spiral.c:31:2: missing terminating " character
perkinel-e586cd:~/cfiles

Where line
15 is asm("
16 is mov ecx, 1
32 is ");

I take it you are using linux? what version of gcc have you got.

Linda

Linda,
I compiled the code on Win98 using MingW version 3.2 and sadly the only machine I have any flavor of unix on is in pieces atm. I'm not certain if there is a way to write code using intel syntax on Linux. I'm sure Big_K or some of the others who use unix exclusively may know. I dislike at&t syntax and usually code either inline in C with MingW or straight assembler using MASM and recently FASM on Win98 or XP. So I suppose your quick solution is to simply convert the code to at&t syntax. http://linuxassembly.org/articles/linasm.html#Syntax

Thanks, you may be right.

Linda