Programming Forums > Application Development > Assembly

lostcauz · Dec 16th, 2004, 4:38 AM

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

(Toggle Plain Text)

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

(Toggle Plain Text)

 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.

(Toggle Plain Text)

 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:

kurifu · Dec 16th, 2004, 12:32 PM

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

It looks good though.

lostcauz · Dec 16th, 2004, 1:02 PM

Here's a C version just for you.

(Toggle Plain Text)

#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.

(Toggle Plain Text)

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:

(Toggle Plain Text)

gcc -o spiral spiral.c -masm=intel

EdSalamander · Dec 16th, 2004, 7:08 PM

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:

(Toggle Plain Text)

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:

(Toggle Plain Text)

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!

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

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

(Toggle Plain Text)

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

(Toggle Plain Text)


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

(Toggle Plain Text)

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:

(Toggle Plain Text)

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. ^_^

Ooble · Dec 17th, 2004, 2:24 AM

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

lostcauz · Dec 17th, 2004, 2:41 AM

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.

Ooble · Dec 17th, 2004, 9:47 AM

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.

LindaW567 · Feb 17th, 2005, 9:24 AM

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

lostcauz · Feb 17th, 2005, 11:42 AM

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

LindaW567 · Feb 18th, 2005, 8:09 AM

Thanks, you may be right.

Linda

Dec 16th, 2004, 4:38 AM	#1
lostcauz Hobbyist Programmer Join Date: Nov 2004 Location: 1691 miles East of L.A. Posts: 159 Rep Power: 4	In a numerical spiral such as below the question was given to determine the sum of both diagonals in a 1001 by 1001 spiral. (Toggle Plain Text) 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 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 (Toggle Plain Text) 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 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. (Toggle Plain Text) 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: 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: __________________ -- lostcauz Stepped in what?... Behind whose barn?... I didn't even know they had a cow!

Dec 16th, 2004, 12:32 PM	#2
kurifu Expert Programmer Join Date: Jul 2004 Location: Halifax, Nova Scotia (Canada) Posts: 784 Rep Power: 5	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 It looks good though. __________________ Clifford Matthew Roche <geek@cliffordroche.com> Web Hosting: http://www.crd-hosting.com Consulting: http://www.crdev-consulting.com

Dec 16th, 2004, 1:02 PM	#3
lostcauz Hobbyist Programmer Join Date: Nov 2004 Location: 1691 miles East of L.A. Posts: 159 Rep Power: 4	Here's a C version just for you. (Toggle Plain Text) #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; } #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. (Toggle Plain Text) 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: "); } 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: (Toggle Plain Text) gcc -o spiral spiral.c -masm=intel gcc -o spiral spiral.c -masm=intel __________________ -- lostcauz Stepped in what?... Behind whose barn?... I didn't even know they had a cow!

Dec 16th, 2004, 7:08 PM	#4
EdSalamander Programmer Join Date: Dec 2004 Location: Tucson, AZ, USA Posts: 80 Rep Power: 4	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: (Toggle Plain Text) 2(n^3) + 1.5(n^2) + 4(n) - 7.5 ------------------------------ + 1 3 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: (Toggle Plain Text) n(n(n(2) + 1.5) + 4) - 7.5 -------------------------- + 1 3 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! If you're still skeptical, my explanation... Start by looking back at the problem visually. First, remove all the unnecessary values. (Toggle Plain Text) 73 81 43 49 21 25 7 9 1 5 3 17 13 37 31 65 57 etc.. 73 81 43 49 21 25 7 9 1 5 3 17 13 37 31 65 57 etc.. Now, think of each new row as a new layer with four new corner values. Something like this.. (Toggle Plain Text) ----------------------- \|43 49\| \| ----------------- \| \| \|21 25\| \| \| \| ----------- \| \| \| \| \| 7 9 \| \| \| \| \| \| \|---\| \| \| \| \| \| \| \| 1 \| \| \| \| \| \| \| \|---\| \| \| \| \| \| \| 5 3 \| \| \| \| \| ----------- \| \| \| \|17 13\| \| \| ----------------- \| \|37 31\| ----------------------- etc.. ----------------------- \|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: (Toggle Plain Text) 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 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: (Toggle Plain Text) 4(n^2) - 6(n - 1) 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. ^_^ __________________ I can pick my friends. And I can pick my nose. So, why can't I pick my friend's nose?

Dec 17th, 2004, 2:24 AM	#5
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Wow. A programmer that isn't a lazy bugger. Nice work, mate. __________________ Me :: You :: Them

Dec 17th, 2004, 2:41 AM	#6
lostcauz Hobbyist Programmer Join Date: Nov 2004 Location: 1691 miles East of L.A. Posts: 159 Rep Power: 4	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. __________________ -- lostcauz Stepped in what?... Behind whose barn?... I didn't even know they had a cow!

Dec 17th, 2004, 9:47 AM	#7
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	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. __________________ Me :: You :: Them

Feb 17th, 2005, 9:24 AM	#8
LindaW567 Newbie Join Date: Feb 2005 Location: Near London, England Posts: 5 Rep Power: 0	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

Feb 17th, 2005, 11:42 AM	#9
lostcauz Hobbyist Programmer Join Date: Nov 2004 Location: 1691 miles East of L.A. Posts: 159 Rep Power: 4	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 __________________ -- lostcauz Stepped in what?... Behind whose barn?... I didn't even know they had a cow!

Feb 18th, 2005, 8:09 AM	#10
LindaW567 Newbie Join Date: Feb 2005 Location: Near London, England Posts: 5 Rep Power: 0	Thanks, you may be right. Linda

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > Assembly

Spiral Diagonals