Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Thu Mar 06, 2014 10:38 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: I discovered a new type of puzzle, you should try itPosted: Tue Sep 27, 2011 4:56 am

Joined: Tue Jan 06, 2009 7:23 pm
x86 assembly. Its like a giant 15 puzzle, but with 8 slots instead of 15 and all sorts of tricks and rules you can use to change the board. You should try it some time

my assignment: take this c++ loop for calculating the Mandelbrot set and optomize it using assembly

COLORREF render_point(double x, double y, int N)
{
double a = 0.0, b = 0.0, norm2 = 0.0;
int n;
for (n = 0; norm2 < 4.0 && n < N; ++n)
{
//you only need to convert this inside loop, but you can do the whole thing
double c = a*a - b*b + x;
b = 2.0*a*b + y;
a = c;
norm2 = a*a + b*b;
}
int value = int(255*(1 - double(n)/N));
return RGB(value,value,value);
}
i was able to do it in 31 assembly lines (more like 60, i had to restart once) and it was so much fun
i cant give out full implementation, my school makes us copyright and hold on to all of our code, but i was able to make my program a few seconds faster with it, and it felt like i was playing a game of rush hour mixed with a 15 puzzle. You coders should give a try, just for fun, assembly is way more fun than i thought

-Nick

_________________

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Tue Sep 27, 2011 10:49 pm

Joined: Thu Dec 21, 2006 5:32 pm
Location: Bay Area, CA
x86 meaning 8086 (16 bit, ax, bx etc.) or 386+ which allows 32 bit registers (eax, ebx, etc.)? Would an x87 co-processor be available?

Doing this in true 8086 without the co-processor would be a bit complicated because the numbers are doubles (and not in 31 instructions, I would guess!).

Many years back I wrote an x86 16 bit register based IEEE754 compliant 32 bit floating point library (args passed in ax:bx, cx:dx). It was really fast because it didn't use any stack variables (remember kids: In assembly memory is the slow stuff), but certainly involved a lot of careful register swapping...

Dave

_________________

LitwinPuzzles.com has info on my puzzles.

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Wed Sep 28, 2011 4:08 am

Joined: Thu Sep 17, 2009 6:07 am
Location: Germany, Bavaria
DLitwin wrote:
...Many years back I wrote an x86 16 bit register based IEEE754 compliant 32 bit floating point library....Dave
Many years back, I have ported UNIX (ok XENIX from Microsoft) to a 8086 system and later to a 80186 system. Quite an adventure! Memory 256 KB - 1024 MB. 10 MB hard disk.
Can you even imagine this, kids?
Now, that had been "real programming".

_________________

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Wed Sep 28, 2011 10:05 am

Joined: Tue Jan 06, 2009 7:23 pm
DLitwin wrote:
x86 meaning 8086 (16 bit, ax, bx etc.) or 386+ which allows 32 bit registers (eax, ebx, etc.)? Would an x87 co-processor be available?

Doing this in true 8086 without the co-processor would be a bit complicated because the numbers are doubles (and not in 31 instructions, I would guess!).

Many years back I wrote an x86 16 bit register based IEEE754 compliant 32 bit floating point library (args passed in ax:bx, cx:dx). It was really fast because it didn't use any stack variables (remember kids: In assembly memory is the slow stuff), but certainly involved a lot of careful register swapping...

Dave

Indeed i did forget to mention a few details. The assignment was to be done entirely on the fpu (unless you wanted to write the loop in assembly as well) . And you werent supposed to write any of the variables back except norm2 at the end of each loop, all the other calculated variables needed to stay in the registers and be updated and popped so that when the loop continued the variables were in the same location as where they began. And im still new to assembly so, i didnt understand everything you were saying

_________________

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Wed Sep 28, 2011 5:39 pm

Joined: Sun Nov 23, 2008 2:18 am
I took a semester of x86 assembly back in Spring 2007, but I would have to do some serious refreshing to do anything useful.

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Wed Sep 28, 2011 7:37 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
It's good to know there are other geeks here that like to get their hands dirty.

I have spent far more time reverse engineering compiled code than I have writing x86. Compilers often generate the worst most offensive x86 you could imagine.

My California license plate is "PUSH ECX"

_________________
Prior to using my real name I posted under the account named bmenrigh.

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Fri Sep 30, 2011 11:25 pm

Joined: Thu Dec 21, 2006 5:32 pm
Location: Bay Area, CA
bmenrigh wrote:
Compilers often generate the worst most offensive x86 you could imagine.
One of the points made early in Michael Abrash's Zen of Assembly Language is that the architecture of the x86 has complicated tradeoffs which makes it hard for a compiler to do a good job. This, then, means you have much more room to improve your code by hand written assembly than on other architectures.

Over time this has diminished as the architecture has changed, but for the early 8086 it most definitely held true.

That was a phenomenal book that I read cover to cover as a new employee at my first career job. It is a bit dated and of course very architecture specific, but if you wish to pursue the topic of this thread ("new type of puzzle" i.e. assembly) I can think of few better books that delve deep into the process of optimizing: Gaining a deep understanding of the tools you have (i.e. instruction set), optimizing to do less work (not more work faster), and how real timing of running code always beats out abstract cycle counting or theoretical gains.

Dave

_________________

LitwinPuzzles.com has info on my puzzles.

Top

 Post subject: Re: I discovered a new type of puzzle, you should try itPosted: Sun Oct 02, 2011 11:45 pm

Joined: Sun Mar 11, 2007 3:11 am
Location: Oregon, USA
Here's a semi-historical puzzle about the x86 series: why does the opcode map have an unexplained gap at byte D6?

This empty gap at D6 first appeared in the manuals for the 8086/88 over thirty years ago, and it's been left empty in every subsequent generation until the entire map was redefined for the 64-bit operation. And this, despite continual pressure to free up first-bytes for use as new instructions, multi-byte escapes, prefixes, optimization hints, etc.

Why weren't there any instructions or prefixes staring with D6 for over three decades?

(Note: it was inadvertently documented in Intel's first P6 architecture manual, but dropped from subsequent editions)

_________________
See my blog about 3D printing puzzles at MySD300

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 8 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 5 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic